Основные типы вычислительных процедур оптимизации

<== Возврат к содержанию раздела

2.2 Основные типы вычислительных процедур оптимизации

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

Примеры необходимых условий оптимальности (условие А необходимо для выполнения В, если при выполнении В всегда выполняется А):

- если дифференцируемая функция f (x) имеет в точке x=x* экстремум, то f ¢(x*)º0;

- для дифференцируемой функции многих переменных f(x1,x2,...,xn) необходимое условие экстремума ;

- eсли в окрестности некоторой точки x* (xÎ [x*–d, x*+d], d >0)

f (x) > f (x*), то в точке x=x* функция f (x) имеет локальный минимум (в окрестности другой точки x значения f (x) могут быть еще меньше).

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

Примеры достаточных условий оптимальности (условие А достаточно для выполнения В если при выполнении А всегда выполняется В):

- eсли в точке x=x* функция f (x) имеет минимум, то в некоторой окрестности этой точки xÎ [x*-d, x*+d], d >0 выполняется условие f (x) > f (x*);

- если f’(x*)=0 и f ¢¢(x*)¹0, то в т. x* f (x) имеет экстремум (при

f ¢¢(x*) >0 - минимум, при f ¢¢(x*) < 0 - максимум);

- для того, чтобы дифференцируемая функция f(x1,x2,...,xn) имела в точ-ке (x1*, x2*,..., xn*) минимум достаточно, чтобы и все миноры матрицы Гессе

были положительны (если миноры нечетного порядка отрицательны, а четного - положительны, то в т.(x1*,x2*,...,xn*) f (x1,x2,...,xn) имеет максимум).

Обобщенное достаточное условие оптимальности (рисунок 2.3): для того, чтобы был лучшим элементом множества D допустимых решений рассматриваемой задачи, достаточно чтобы был лучшим элементом мно-

жества VÉD (если Î D - глобальный экстремум функции f (x1,x2) на множестве V, тоявляется глобальным экстремумом f (x1,x2) и на множестве D).

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

1. Сравнение значений целевой функции на сетке значений аргументов. Сетка образуется в результате разбиения областей допустимых значений аргументов на равные интервалы (рисунок 2.4). Оптимальному решению соответствует минимальное или максимальное значение целевой функции в “узлах” сетки. Процедура обычно применяется многократно: вначале шаг сетки “крупный”, а затем вокруг лучшей точки строится более “мелкая” сетка.

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

2. Использование необходимых условий экстремума целевой функции, т. е. формирование и решение систем уравнений вида

.

3. Использование достаточных условий оптимальности: образуется вспомогательная задача, множество решений которой шире допустимого, а критерий оптимальности на допустимом множестве совпадает с критерием исходной задачи (например задача условной оптимизации заменяется задачей безусловной оптимизации, в критерий которой вводится “штраф” за выход из допустимой области, т. е. за невыполнение условий (2.1), (2.2)).

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

5. Построение оптимизирующей последовательности допустимых решений задачи: выбирается одно из допустимых решений , называемое начальным приближением, и на его базе строится последовательность допустимых решений , где , k=0,1,…,n, причем выбирается так, чтобы при поиске min выполнялось условие , а при поиске max – условие . Приращение чаще всего является функцией одного или нескольких предыдущих членов последовательности: = или =. Построение последовательности заканчивается в момент выполнения необходимых условий ext.

Процедура типа 1 применяется в вычислительной практике всегда, когда это не связано со слишком большим объемом вычислений. Применению процедуры 2 препятствует необходимость получения аналитических выражений производных целевой функции. Процедуру типа 3 использует один из методов условной оптимизации - метод штрафных функций, процедуру типа

4 - два метода одномерной оптимизации (методы Больцано и "золотого сечения"). Большинство методов оптимизации основаны на процедуре типа 5.

<== Возврат к содержанию раздела