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

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

Для того чтобы точка х*∈Rn являлась оптимальным решением (локальным минимумом) необходимо и достаточно, чтобы в этой точке градиент минимизируемой функции равнялся нулю, а ее гессиан был положительно определенной матрицей:
∇Q(x*) = grad Q(x*) = 0 или

∂Q/∂xj, j = 1,2,…, n; (1.55)
xTG(x*)x > 0 для любых х ≠ 0. (1.56)

Для задачи (1.28) многопараметрической минимизации унимодальной функции Q (х), определенной в n-мерном параллелепипеде Dx = {x|xj≤xj≤xj, j=1, 2, …, n}, условия оптимальности формулируются следующим образом.

Для того чтобы точка х*∈Dx являлась оптимальным решением (локальным минимумом), необходимо, чтобы выполнялись следующие условия:

∂Q/∂xi|x=x* > 0, если хi* =xi;

∂Q/∂xi|x=x* < 0, если хi* =xi+;

∂Q/∂xi|x=x* = 0, если xi < xi* < xi+;

Доказательство справедливости условий (1.57) проведем для одной переменной xi*, предположив, что остальные (n — 1) переменные остаются неизменными.

Пусть точка х* является точкой локального минимума функции Q (х). Тогда для любой точки (xi* + ξ) ∈d (х*, ξ) справедливо неравенство

Q(xi*+ξ) ≥ Q(xi*),

или, используя формулу Тейлора (1.54), получаем, что

Q(xi*+ξ) — Q(xi*) ≈ ξ dQ/dxi|x=x* ≥ 0. (1.58)

Пусть хi* =xi. При этом возможны только положительные значения приращения ξ > 0 (рис. 1.10, кривая Q1 (x)), т. е. для выполнения неравенства (1.58) необходимо, чтобы первая производная функции Q (х) по переменной xi; была положительна dQ/dxi > 0. Аналогично, при хi* =xi+, возможны только отрицательные значения приращения ξ < 0 (рис. 1.10, кривая Q2 (x)), т. е. для выполнения неравенства (1.58) необходимо, чтобы первая производная функции Q (х) по переменной хi была отрицательной: dQ/dxi < 0. Если xi < xi < xi+, то приращение



Рис. 1.10. Условия оптимальности унимодальной функции, определенной на отрезке [xi, xi+]

ξ может быть любого знака (рис. 1.10, кривая Q3(x)), т. е. выполнение неравенства (1.58) возможно только при равенстве нулю первой производной функции Q (х) по переменной xi:

dQ/dxi = 0

Условия оптимальности (1.57) показывают, что оптимальное решение х* задачи многопараметрической оптимизации (1.28) может находиться как внутри области Dx, так и на границе гиперпараллелепипеда, т. е. одна или несколько его координат могут принять предельные значения (xi или xi+). Наличие такой ситуации требует для отыскания оптимального решения х* применения следующей процедуры. Сначала решается задача безусловной оптимизации для функции Q (х). Затем решается 2n задач безусловной оптимизации для функций Qi от (n — 1)-й переменной, которые получаются из Q (х) подстановкой xi = xi или xi = xi+. После этого рассматривается Зn (n — 1) задач безусловной оптимизации для функций Qij от (n — 2)-х переменных, которые получаются из Q (х) путем подстановки вместо xi и xj всевозможных сочетаний их предельных значений и т. д. Оптимальное решение х* задачи (1.28) будет совпадать с наименьшим из минимумов всех рассмотренных задач безусловной оптимизации. Очевидно, что такой подход к решению задачи оптимизации (1.28) требует больших вычислительных затрат. Поэтому в некоторых специальных случаях целесообразно применять функции преобразования xi = fi (z), рассмотренные ранее, для того чтобы перейти от исходной задачи (1.28) к задаче безусловной оптимизации (1.31).


Оставить комментарий





Статистика

Рейтинг@Mail.ru