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

Численные методы оптимизации

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

(1)

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

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

для всех

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

Если допустимое множество в задаче минимизации совпадает со всем пространством , то говорят о задаче безусловной оптимизации

(2)

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

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

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

или (3)

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

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

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

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

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

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

, т.е. .

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

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

.

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

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

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

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

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

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

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

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

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

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

,

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

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

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