Безусловная оптимизация

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

найти .

Необходимые условия минимума в одномерной задаче без ограничений

A1. (16.6)

A2. . (16.7)

Любую точку , в которой выполнено равенство , называют стационарной точкой функции f. Стационарность - это одно из свойств точек минимума гладких функций; при этом, однако, стационарными будут и точки из локальных максимумов.

Кроме того, производная может обращаться в нуль в точках, где нет ни минимума, ни максимума; их называют точками перегиба.

Требование равенства нулю производной f(x^*) называют необходимым условием оптимальности первого порядка. В названии отражено, что это условие касается только первой производной.

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

Многомерный случай

В данном разделе рассматривается минимизация функции n переменных:

найти .

Необходимые условия минимума:

C1. , т.е. x* является стационарной точкой.

C2. Матрица положительно полуопределена.

Условия, достаточные для того, чтобы точка x^* была точкой сильного локального минимума в задаче. Они состоят в следующем:

D1. .

D2. Матрица положительно определена.

Оптимизация при линейных ограничениях

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

В том числе нередко используются ограничения в виде требований, чтобы некоторые линейные функции переменных были равны нулю, неотрицательны или неположительны. При этом линейной мы называем функцию вида , где ^ - некоторая вектор-строка, а  - число.

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

(ограниченное-равенство) (16.8)

(ограниченное-неравенство). (16.9)

Простейшими среди линейных являются ограничения, заданные функциями l(x), зависящими только от одной переменной. В этом случае, если соответствующая переменная есть x_i, возможны такие варианты:

(x_i фиксируется на ) (16.10)

( есть верхняя граница для x_i) (16.11)

( есть нижняя граница для x_i). (16.12)

Условия (16.7) и (16.8) принято называть простыми ограничениями на переменную x_i.

Оптимизация при нелинейных ограничениях

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

(ограничение-равенство) (16.13)

(ограничение-неравенство). (16.14)

Достаточные условия оптимальности, представим в двух вариантах. Это связано с проблемой нулевых множителей Лагранжа. Первый набор условий получается если снять эту проблему, потребовав, чтобы все множители Лагранжа были положительны. Тогда достаточными условиями существования в x^* сильного локального минимума в задаче будут следующие соотношения:

, причем , (16.15)

, или, что эквивалентно, (16.16)

(16.17)

Матрица положительно определена. (16.18)

Можно получить и другие, допускающие наличие нулевых множителей Лагранжа достаточные условия. В заключении, рассмотрим достаточные условия минимума с нулевыми множителями Лагранжа:

, причем , (16.19)

, или, что эквивалентно, (16.20)

(16.21)

Матрица положительно определена.