Принципы методов численного поиска минимума функции многих переменных

Многие задачи оптимизации, какими бы способами они ни решались в конце концов сводятся к задаче минимизации функции многих переменных

     (1)

В качестве  могут быть проектные параметры приборов и технологических процессов, элементы матриц оптимизируемых функционалов, начальные условия для множителей Лагранжа и др. Здесь  – допустимое значение множества изменения параметров . Точка называется точкой глобального минимума , если для всех  выполняется неравенство  для всех

Точка  называется точкой локального минимума функции , если существует  - окрестность точки : ( , такая, что  для всех . Если допустимое множество  в задаче минимизации совпадает со всем пространством , то говорят о задаче безусловной оптимизации (2)

Методы безусловной оптимизации базируются на результатах, известных из математического анализа, в частности на необходимых и достаточных условиях минимума функции. 1. Если в точке  функция дифференцируема и достигает локального минимума, то  или (3) Точки, в которых выполняются условия (3), называются точками стационарности функции . 2. Если в стационарной точке  функции  дважды дифференцируема и матрица  положительно определена, то  - точка локального минимума (достаточное условие). Эти условия лежат в основе классического метода минимизации функций, дифференцируемых во всем пространстве :

1) решается система уравнений (3) и находятся стационарные точки;

2) используются достаточные условия, находятся точки локального минимума и глобального.

Общие принципы – мерной оптимизации

1) Для численного решения задач безусловной оптимизации, используются итерационные процедуры   (4)

т.е. выбор параметра на  шаге зависит от информации о предыдущих шагах.

Простейшие процедуры типа (4) можно представить в виде:

                           (5)

где  – направление движения из точки  в точку  , число  – величина шага.

2) Величина шага выбирается так, чтобы выполнилось условие

Практически все методы оптимизации можно разделять условно на две группы.

1) Прямые методы оптимизации, в которых на каждом шаге вычисляется только значение целевой функции.

2) Методы, использующие производные целевой функции.

Прямые методы.

1. Метод перебора. Ограничимся случаем одномерной оптимизации унимодальных функций. Функция называется унимодальной на отрезке , если она непрерывна на  и существуют числа  такие, что:

1) на отрезке  функция монотонно убывает;

2) на отрезке  функция монотонно возрастает.

В этом случае отрезок разбивается на равных частей точками . Вычисляются во всех точках, сравниваются и находится точка  минимального значения, т.е. , т.е. . Понятно, что погрешность определения  не превосходит величины .

Для обеспечения необходимой точности нужно выбрать число деления участков  из условия .

2. Метод поразрядного поиска. Используются некоторые возможности улучшения метода перебора. Во-первых, если оказывается, что , то не нужно вычислять и т.д. Во-вторых, разумно сначала определить  грубо, а потом искать более точное с меньшим шагом дискретизации. Есть и другие методы одномерной оптимизации (например, метод золотого сечения, метод аппроксимации параболой).

Прямые методы –мерной оптимизации. Остановимся сначала на вычислительных процедурах вида (5),в которых выбор нового приближения к точке минимума определяется сравнением значений функций в нескольких точках пространства .

1. Минимизации по правильному симплексу (ПС). ПС в  называется множество из  равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий 2 вершины – ребро. В  ПС – равносторонний треугольник в  – правильный тетраэдр.

2. Метод покоординатного спуска.

3. Метод случайного поиска ,где  – величина шага,  - некоторая реализация  – мерного случайного вектора. Есть разные реализации этого метода, например, - алгоритм с возвратом при неудачном шаге,- алгоритм наилучшей пробы.

Методы, использующие производные целевой функции. Пусть  – дифференцируемая функция в . Рассмотрим итерационные процедуры минимизации вида где направление убывания  определяется тем или иным способом с учетом информации с частных производных функции , а величина  выбирается так, что .

Метод градиентного спуска Здесь , а может быть постоянной.

Метод наискорейшего спуска.Здесь тоже находится в результате одномерной минимизации , где

Многомерная минимизация при наличии ограничений.Задача математического программирования.

Соотношение (1) – (3) – задача математического программирования.

1. Задача линейного программирования, когда все функции линейны и .

2. Задачи нелинейного программирования, когда хотя бы одна функция – нелинейная.

2.1. Задача на условный экстремум, когда отсутствуют условия (2).

2.2. Задача выпуклого программирования, когда все функции выпуклых и отсутствует условия (3).

Напомним, что функция, заданная на отрезке называется выпуклой на отрезке, если для всех  и , принадлежащих отрезку и произвольного числа  выполняется неравенство .  Другое определение: Для выпуклости на отрезке  необходимо и достаточно, чтобы во всех точках выполнялось неравенство .