Общая схема решения задач выпуклого программирования методами спуска состоит в построении последовательности
Х0, Х1, …, Хk, … (8.15)
решений системы ограничений данной задачи по следующему принципу: в качестве Х0 выбирается, вообще говоря, любая точка области решений и затем каждая последующая точка получается из предыдущей по формуле:
Хk+1 = Хk +λ∙ l, (8.16)
где l = (l1, l2, …, ln) – некоторое направление (т.е. вектор), а λ – число, выражающее длину шага. При этом направление l и «длина шага» λ выбираются так, чтобы обеспечить сходимость последовательности (8.15) к оптимальному решению Х*. В общем случае процесс получения последовательных приближений Хk бесконечен (и тогда некоторое Хk0 берется за приближенное значение оптимального решения Х*), однако иногда процесс может завершиться и за конечное число шагов, приводя к локальному, а в задачах ВП и глобальному оптимуму.
Находя производную по направлению дZ/дl, мы можем определять, является ли направление l «невыгодным» или «выгодным» в смысле приближения к оптимуму.
Так как направление градиента Z целевой функции является направлением ее наискорейшего роста, то при отыскании максимума вогнутой функции (минимума выпуклой функции) в качестве l часто берется 
Z (- Z) и тогда формула (8.16) принимает вид
Хk+1 = Хk +λ∙ Z(Xk), λ>0 (если ищется Zmax) (8.17)
или Хk+1 = Хk -λ∙ Z(Xk), λ>0 (если ищется Zmin) (8.17′)
Методы спуска, в которых итерационная последовательность (8.15) находится по формуле (8.17) (или (8.17′)), называются градиентными.
Друг от друга они отличаются способами выбора длины шага λ и алгоритмами нахождения точки Хk+1, если Хk находится на границе области решений и формула (8.17) выводит Хk+1 за пределы этой области.
Выбор длины шага λ очень важен. Как видно из рис. 8.3, перемещаясь из точки Хо в направлении Z, мы в некоторый момент можем «проскочить» мимо точки Х1, в которой достигается максимум.
Если величина λ выбирается так, чтобы приращение функции ∆Z при перемещении из точки Хk в точку Хk+1 было наибольшим (при отыскании Zmax) или наименьшим (при отыскании Zmin), то градиентный метод называется методом скорейшего спуска.
Таким образом, по методу скорейшего спуска длины шага λ в формуле (8.17) (или (8.17′)) выбирается так, чтобы при этом λ достигался экстремум функции ∆Z = Z(Хk+1)- Z(Хk). (Обратите внимание на то, что при нахождении точки Хk+1 предыдущая точка Хk считается уже известной, т.е. Z(Хk) и ∆Z(Хk) являются постоянными величинами, а ∆Z – функцией одной переменной λ).
Продифференцировав функцию ∆Z с учетом выражения Хk+1 по формуле (8.17) и выражения градиента в точке Хk, Z(Хk)= 
, получим, что необходимое условие экстремума 
примет вид:
(8.18)
Ему можно придать более компактную форму, если использовать скалярное произведение векторов:
(8.18′)
(Напомним, что скалярное произведение векторов в прямоугольной системе координат равно сумме произведений их соответствующих координат. Например, если l1=(2, -1) и l2=(3, 5), то l1·l2 = 2·3 +(-1) ·5 = 1. Скалярное произведение векторов равно нулю тогда и только тогда, когда они ортогональны).
Если оптимум достигается внутри области решений системы ограничений данной задачи ВП, то нет опасности, что точка Хk+1, найденная по формуле (8.17) или (8.17′), выйдет за пределы этой области, и длину шага λ определяем по формуле (8.18) без каких-либо дополнительных ограничений.
|
Для случая двух переменных метод скорейшего спуска имеет простую геометрическую интерпретацию: для любого k луч, идущий от точки Хk к точке Xk+1, перпендикулярен к линии уровня функции Z, проходящей через точку Xk (так как направлен по градиенту), и касается линии уровня, проходящей через точку Xk+1 (так как ввиду условия (8.17′) он перпендикулярен к следующему лучу, который в свою очередь перпендикулярен к этой линии уровня).Таким образом, на плоскости скорейший спуск происходит по двум взаимно перпендикулярным направлениям так, как показано на рис.8.4.
Замечание. Для упрощения счета можно в формулах (8.17) и (8.17′) брать вместо Z(Хk)= с тем же направлениям, то есть координаты можно умножать или делить на положительное число.
Рассмотрим теперь задачу ВП, когда оптимум целевой функции достигается на границе области решений системы ограничений. В этом случае, взяв, как и ранее, в качестве исходной точки Х0 любую точку из области решений и находя последующие точки по формулам (8.17) и (8.17′), мы на некотором шаге получим, что Xk уже не лежит в области решений (рис. 8.5-а). Тогда вместо Xk берем точку X ′ k, которая лежит на пересечении направления спуска с границей области решений, а все последующие точки находятся путем проектирования на эту границу точек, получаемых обычным методом скорейшего спуска.
 |  | ||
Поскольку общий оператор проектирования не изучается в нашем курсе, ограничимся случаем, когда система ограничений линейная, т.е. область решений задачи для случая двух переменных ограничена отрезками прямых (рис. 8.8-б).
В этом случае система ограничений данной задачи примет вид:
(8.19)
Пусть по методу скорейшего пуска мы построили точки X0, …, Xk, Xk+1
и убедились (подставляя в (8.19) координаты этих точек), что X0, …, Xk лежат в области решений, а точка Xk+1 уже не лежит в ней. Значит, координаты точки Xk+1 не удовлетворяют хотя бы одному неравенству системы (8.19).
