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

x > 0,

где х = (хь х2,..., ХП) — вектор переменных задачи.

Пусть F(x) — дифференцируемая функция.

Необходимые условия того, что в точке х° достигается максимум функции F(x):

f ,0, v f = 0, ,-!._„.

Это означает, что:

Э F

< 0 для х = х° в случае х,° = 0

и

dF

= 0 для х = х° в случае х(° > 0.

Если F(x) вогнутая функция (для задачи минимизации — выпуклая), то эти условия являются также достаточными.

Функция F(x) с числовыми значениями, определенная на выпуклом множестве точек К, называется вогнутой, если для любой пары точек х1, х2 и для всех чисел X, 0 < X < 1, выполняется неравенство F(Xxl + (1 - Х)х2) >Л№)>.

Если + 0 — ^)х2) - ^F(x\') + (1 — X)F(x2),T0 функция /*\'(х) называется выпуклой. Если имеют место

строгие неравенства, то говорят, что функция строго вогнута или строго выпукла.

Данное определение вогнутости (выпуклости) годится для любого типа функции. Практически, однако, применять его трудно.

Для дважды дифференцируемой функции F(x) имеет место следующий критерий. Дифференцируемая

0 = (х,? х2?

* "

если выполняются

функция /*(х) строго вогнута в некоторой окрестности точки х следующие условия: ^и(х°) < О,

F\'2г(хО) < О, F;з(х<>) < О,

F< 2(х°)

(4)

>0,

F^i*0)

Fn\'(x°) Fu(x°) F,3(x«)

<0,

^,\'(х0) /?(х°) F^x")

F^) F32(X°) F3^(x°)

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

Здесь (х ) — частная производная второго порядка, вычисленная в точке х°.

Матрица размера п х п, составленная из элементов называется матрицей Хессе (Hesse). По

значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функция F(x) строго выпукла в малой окрестности точки х0, если все главные миноры ее матрицы Хессе строго положительны. Если имеют место нестрогие неравенства (>), то функция в окрестности точки х0 выпукла. Если при этом главные миноры матрицы Хессе от х не зависят, то функция всюду (строго) выпукла.

Весьма распространены относящиеся к данному типу модели квадратичного программирования, в которых целевая функция F(x) является квадратичной функцией переменных х1, х2, ..., х„. Существует большое число алгоритмов решения такого типа задач, в которых функция F(x) вогнутая (для задач минимизации — выпуклая).