Нелинейные оптимизационные модели, страница 5

1. Выберем внутри допустимой области произвольную точку х₀. Из этой точки сделаем шаг в направлении градиента , обозначенного на рисунке g(x₀), до максимального на этом направлении значения  или до границы допустимой области. Если максимальное значение находится внутри допустимой области, следующий шаг надо сделать в направлении нового градиента, как это рассмотрено в разделе 9.3. Если максимальное значение в направлении градиента g(x₀) находится за пределами допустимой области, то шаг делаем только до границы в точку х₁, как показано на рисунке.
2. Из точки х₁ двигаться в направлении градиента g(x₁) нельзя, не позволяет граница допустимой области. Можно двигаться по границе в сторону возрастания , указанную вектором r₁. Признаком возрастания служит положительный знак скалярного произведения Ñf(x₁)×r₁>0.

Длина шага вдоль границы ограничена следующими возможными вариантами: а) достижением максимального значения функции f(x);

б) выходом на другую граничную линию в точке х₂, как это имеет место на рисунке.

3. Из точки х₂ опять выполним шаг по границе в направлении r₂, таком что Ñf(x₂)×r₂>0. Длина шага определится достижением максимального на данном направлении значения функции f(x) в точке х₃.
4. В точке х₃ - конец поиска. В этой точке:

а) Функция f(x) имеет локальный максимум. Ввиду вогнутости f(x) – это и глобальный максимум для допустимой области.

б) Для любых векторов в допустимой области .

в) Для векторов, направленных по границе . Последнее равенство является признаком максимума функции .

Сформулируем аналитическое решение задачи.

1.  Имеем точку   внутри допустимой области (в самом начале это произвольно назначенная точка ). Следующую точку располагаем по направлению градиента

                                             (9.9)

Чтобы точка  не вышла за границы допустимой области, ее координаты должны удовлетворять ограничения (9.2) и (9.3), то есть

                                            (9.10)

                                                   (9.11)

Решая систему неравенств (9.10) и (9.11), найдем отрезок  допустимых значений параметра , при которых очередная точка  не выйдет из допустимой области.

Определим еще , соответствующее локальному максимуму  в направлении градиента , для чего решим уравнение:

                                 (9.12)

Если  попадает в интервал , то принимаем  и по форм. (9.9) вычислим координаты точки , которая как и  окажется внутри, допустимой области. Затем делаем новый шаг, как это описано в пункте 1.

Если  выходит за пределы интервала , то принимаем  и по формуле (9.9) вычислим координаты точки , которая попадет на граничную гиперплоскость, то есть на границу допустимой области. При этом точка  попадает конкретно на ту границу, которая соответствует неравенству, по которому в (9.10) было вычислено .

2.  Точка  находится на границе допустимой области.

Напишем уравнение соответствующей ограничивающей гиперплоскости:

.                                                         (9.13)

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

Координаты (k+ 1)-ой точки

Чтобы точка х_к+1 оказалась на границе должно выполняться равенство:

.

Учитывая (9.13) получаем

.                                                   (9.14)

Уравнение (9.14) означает, что вектор  лежит в ограничивающей гиперплоскости. Направление его, как уже отмечено, должно быть выбрано таким, чтобы оно составляло наименьший угол с направлением градиента  Иными словами, должен быть обеспечен максимум скалярного произведения . Следовательно, для определения вектора  должна быть решена следующая задача выпуклого программирования

max                                            (9.15)

при ограничениях