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

Среди методов нулевого порядка в САПР применяют методы:

1. Покоординатного спуска.

2. Метод Розенброка.

3. Метод конфигураций.

4. Метод деформируемого многогранника.

С использованием производных:

1. наискорейшего спуска

2. сопряжения градиентов

3. переменной метрике.

а

Целевая функция представлена линиями равного уровня, около каждой записано значение F(x). Точка Э – точка минимума, точки Х_К – точки траектории поиска, Х_i – управляемые параметры (Х₁ и Х₂).

Критерий окончания поиска:

│Х_k – Х_k-n│< ε

Вероятно застревание поиска на дне оврага, вдали от точки экстремума.

При попадании в т. А шаги возможны в направлении аа, вв, что приводит к ухудшению целевой функции.

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

Но существует благоприятное расположение оврага.

Чтобы это получить используется метод Розенброка

При благоприятном ориентировании оврага поиск происходит быстро.

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

Поворот осуществляется на основе данных полученных после серии из n шагов покоординатного спуска.

Метод покоординатного спуска (метод Хука- Джирса).

После трех измерений проводится Х₄ по оси между Х₁ и Х₃

Метод деформируемого многогранника (Нельдера - Мида).

РИСУНОК 1

Построение многогранника с n+1 вершинами на каждом шаге поиска, n- размерность пространства управляемых параметров. (n+2).

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

Выбраны вершины Х₁, Х₂, Х₃. Новая вершина Х₄ находится на луче, проведенном из худшей вершины Х₁ (с наибольшим значением целевой функции) через центр тяжести многогранника на расстоянии d от центра тяжести d = │ц.т. – Х₁│

Х₄ заменяет худшую вершину Х₁. Если Х₄ имеет лучшее значение целевой функции среди вершин многогранника, то расстояние d можно увеличить (т. Х₅).

Новый многогранник: Х₁ Х₃ Х₅; худшая Х₄. Аналогично получим точку Х₆, затем Х₇.

Если новая вершина окажется худшей, то в многограннике нужно сохранить лучшую вершину, а длины всех ребер уменьшить (вдвое) – стягивание многогранника к лучшей вершине.

Поиск прекращается при выполнении условий уменьшения размеров многогранника до некоторого предела.