Методы безусловной оптимизации

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

Если в точке функция дифференцируема и достигает локального минимума, то

или (3)

Точки, в которых выполняются условия (3), называются точками стационарности функции .

Если в стационарной точке функции дважды дифференцируема и матрица положительно определена, то - точка локального минимума (достаточное условие).

Эти условия лежат в основе классического метода минимизации функций, дифференцируемых во всем пространстве :

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

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

 

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

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

(4)

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

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

(5)

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

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

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

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

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

 

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

1. Метод перебора.

Ограничимся случаем одномерной оптимизации унимодальных функций.

Функция называется унимодальной на отрезке , если она непрерывна на и существуют числа такие, что:

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

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

В этом случае отрезок разбивается на равных частей точками .

Вычисляются во всех точках, сравниваются и находится точка минимального значения, т.е.

, т.е. .

Понятно, что погрешность определения не превосходит величины .

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

.

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

Используются некоторые возможности улучшения метода перебора. Во-первых, если оказывается, что , то не нужно вычислять и т.д.

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

Есть и другие методы одномерной оптимизации (например, метод золотого сечения, метод аппроксимации параболой).

Прямые методы –мерной оптимизации.

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

1. Минимизации по правильному симплексу (ПС).

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

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

3. Метод случайного поиска

,

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

- алгоритм с возвратом при неудачном шаге,

- алгоритм наилучшей пробы.