§ 7. Метод наискорейшего спуска (наискорейшего подъема)

Рассмотрим теперь решение задачи выпуклого программирования, заключающееся в минимизации выпуклой (максимизации вогнутой) функции

на выпуклой области, определяемой неравенствами

Метод наискорейшего подъема фактически уже использовался выше в § 6 при решении задач на максимум. Аналогичным по структуре является метод наискорейшего спуска, используемый при решении задач на минимум [3, 8, 9]. Общую схему решения этими методами задач выпуклого программирования можно представить следующим образом.

1. Выбирается некоторая начальная точка, являющаяся допустимым решением задачи. В этой точке вычисляется градиент функции цели.
2. Из начальной точки производится движение в направлении градиента до тех пор, пока функция цели возрастает (в задаче на максимум) или убывает (в задаче на минимум).
3. По достижении точки, в которой функция цели получает наибольшее приращение, движение прекращается. В этой точке снова нужно найти значение градиента функции цели. Далее движение происходит в новом направлении градиента.
4. Этот процесс продолжается до тех пор, пока не достигается граница области допустимых решений, и движение вдоль градиента становится невозможным.
5. В достигнутой граничной точке определяется возможное направление, при движении вдоль которого функция цели возрастает. Оказывается, что наивыгоднейшим из возможных направлений является такое, для которого максимален косинус угла между этим направлением и градиентом функции цели. При решении задачи с линейными ограничениями наивыгоднейшее направление движения совпадало с соответствующим ограничением задачи.
6. Процесс движения от точки к точке с возрастанием функции цели продолжается до тех пор, пока не достигается точка, в которой не существует ни одного возможного направления. Эта точка и является искомым оптимальным решением задачи.

Методы решения задач с линейными и нелинейными ограничениями отличаются в основном способами движения вдоль ограничений. Если при линейных ограничениях движение вдоль ограничений не приводит к выходу за границу области допустимых решений, то в случае нелинейных ограничений движение вдоль ограничений, определяющих выпуклую область, как правило, невозможно, поскольку мы быстро оказываемся вне области допустимых решений. Поэтому применяются различные способы движения, обеспечивающие выбор последовательности точек, расположенных вблизи границы и внутри области допустимых решений, или зигзагообразное движение вдоль границы с пересечением последней.

Перейдем к описанию решения общей задачи выпуклого программирования методом наискорейшего спуска. Прежде всего преобразуем саму задачу. Добавим к имеющимся n переменным дополнительную переменную x_n+1 и дополнительное ограничение вида

Тогда общая задача (2.35)-(2.36) может быть сформулирована следующим образом:

минимизировать линейную функцию

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

Линейную функцию z можно представить в виде

где p₁, ..., p_n - заданные числа, выбранные таким образом, чтобы p₁x₁ + p₂x₂ + ... + p_nx_n = x_n+1. Ограничения запишем в виде

где обозначено m = m'+1. Представленная в таком виде задача минимизации линейной функции (2.37) при нелинейных ограничениях вида (2.38), заданных гладкими выпуклыми функциями ψ_i (x₁, ..., x_n), называется канонической Формой общей задачи выпуклого программирования.

Во многих практических задачах сравнительно легко можно найти начальную точку X₀, принадлежащую области допустимых решений. Однако, если возможное исходное решение неизвестно, оно может быть найдено, например, следующим образом.

Грубо оценим область определения переменных x_j и возьмем из этой области любую точку X^*. Подставим это решение в ограничения задачи. Если оказалось, что все

то выбранная точка может быть принята за начальную точку X₀. Если ψ_i (x₁^*, ..., x_n^*)> 0, то введем дополнительную переменную ξ, такую, чтобы выполнялось неравенство

и будем искать минимум функции

способом, описанным выше, т. е. находя в точке X^* градиент функции u, определяя длину допустимого продвижения и т. д. Для того чтобы найти начальную точку, в действительности необходимо лишь получить решение X₀, для которого ξ≤0.

Пусть найдена начальная точка X₀. В соответствии со сказанным выше и без ограничения общности изложения можно считать, что X₀ лежит на границе области допустимых решений, поскольку в противном случае достаточно проделать один или несколько шагов из X₀ в направлении градиента, чтобы достигнуть границы области.

Впрочем, продвижение непосредственно до границы области не является обязательным. Более того, на каждом шаге вычислений следует устанавливать значение некоторого достаточно малого параметра δ_k > 0 (k - номер шага), считая, что точка X_k-1 принадлежит границе области ψ_i (X) = 0, если выполняется неравенство

Оно означает, что удаление точки X_k-1 от границы области допустимых решений неположительно и не больше чем - δ_k. Соответственно для начальной точки X₀ можно написать

Перейдем к определению направления ξ⁽¹⁾ = (ξ⁽¹⁾₁, ..., ξ⁽¹⁾_n) наикратчайшего спуска из точки X₀. При движении в этом направлении функция цели z должна убывать, т. е. производная от z по направлению ξ должна быть

(2.40)

Напомним, что производной функции z по направлению ξ называется скорость изменения функции в этом направлении:

где Δz = z₂ - z₁ и Δl - приращение функции и приращение длины вдоль ξ соответственно.

Воспользовавшись известной формулой для производной сложной функции, можно написать:

Правая часть этого выражения является скалярным произведением двух векторов: вектора градиента и вектора направления

где

Градиент линейной функции z есть ∇z = (p₁, ..., p_n); поэтому можно в точке X₀ записать условие (2.40) в виде

(2.41)

Кроме выполнения условия необходимо еще, чтобы направление ξ вело внутрь области допустимых решений, т. е. чтобы вдоль этого направления убывали все Функции ψ_i (x), или чтобы удовлетворялись неравенства

где ∇ψ_i (X₀) - градиент функции ψ_i в точке X₀.

Величины (2.41) и (2.42) определяют соответственно скорость убывания функций z и ψ_i в направлении ξ. Для осуществления наискорейшего спуска при движении внутри области допустимых решений необходимо, чтобы величина (2.41), т. е. абсолютная скорость убывания функции z, была как можно большей при условии, что выполняется неравенство (2.42). Поэтому наряду с δ₁>0 выберем произвольное достаточно малое λ₁> 0, и направление ξ⁽¹⁾ определяем, решая следующую задачу линейного программирования:

минимизировать функцию

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

Для сходимости итерационного процесса необходимо, чтобы вектор направления ξ был ограниченным. Поэтому положим |ξ₁| ≤c, ..., |ξ_n|≤c, где c - заданное число Многие известные методы решения задач выпуклого программирования отличаются способами нормализации, т. е. выбором величины c [9]. В частности, можно считать c = 1. таким образом, условие |ξ_i| ≤ c учитывается при решении задачи (2.43)-(2.44).

Пусть решением задачи (2.43)-(2.44) является величина η₁, причем

Тогда, меняя величину α в выражении

двигаемся в направлении ξ⁽¹⁾ до тех пор, пока не встретим границу области допустимых решений. Величина α₁ определяется как наименьший из положительных корней уравнений

и называется шагом приближения. Далее находим точку X₁ = X₀ + α₁ξ⁽¹⁾, в которой необходимо прекратить движение и искать новое направление движения, считая теперь точку X₁ исходной. Полагаем δ₂ = δ₁, λ₂ = λ₁ и повторяем все вычисления, относившиеся к точке X₀, пока на k-м шаге не придем к тому, что

В случае 0>η_k≥-δ_k определяем α_k, X_k и продолжаем процесс из точки X_k, считая теперь δ_k+1 = ^δ_k/₂ и λ_k+1 = ^λ_k/₂.

После некоторого числа шагов параметры δ и λ уменьшится настолько, что с достаточной степенью точности можно будет считать, что точка X_i принадлежит границе части допустимых решений, и min u = η_l+1 = 0. Это означает, что X_i является решением задачи, и итерационный процесс закончен.

Вообще говоря, из того факта, что на некотором шаге кажется η_l+1 = 0, т. е. из факта отсутствия направления спуска из точки X_l, еще нельзя сделать вывод, что точка X_l является решением задачи. Дело в том, что отсутствие направления спуска может быть следствием того, что недостаточно мало, и равенство нулю η_l+1 объясняется наличием поверхностей, на которых X_l в действительности не лежит, но уклонение от них меньше, чем δ_l+1. Известны способы проверки того, является ли X_l решением. Наиболее простой из них - в несколько раз уменьшить значение параметра δ и снова проделать вычисления η_l+1. Если окажется, что величина η_l+1 отличается от 0, то итерационный процесс следует продолжать до тех пор, пока не достигнем новой точки X_l, для которой η_l+1 = 0. После некоторого числа шагов решение задачи может быть найдено с заданной точностью.

Совершенно аналогично проводится решение задачи максимизации вогнутой функции методом наискорейшего подъема.

Обратимся к примеру. Опять возьмем уже рассмотренную выше (см. § 5 данной главы) задачу:

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

Ранее мы решали эту задачу о сепарабельными функциями приближенным методом, теперь же используем метод наискорейшего подъема.

Прежде всего представим задачу в канонической форме. Для этого в случае максимизации f надо ввести дополни, тельную переменную x₃≤f и записать выражение (2.37) и новое ограничение в следующем виде:

или

Выбор величин p₁ и p₂ до некоторой степени произволен, лишь бы всегда выполнялось ограничение, в которое они входят. Очевидно, p₁ и p₂ можно выбрать исходя из условий

или

Ранее в § 5 мы уже оценивали, что (x₁)_max≤5, (x₂)_max≤5, следовательно, имеем p₁≤1,5, p₂≤2,5. Вместе с тем возрастание функции z происходит тем быстрее, чем больше p₁ и p₂; поэтому выбираем p₁ = 1,5 и p₂ = 2,5 и приходим к задаче:

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

Выбираем начальную точку с координатами x₀₁ = 1 и x₀₂ = 1, которая заведомо принадлежит области допустимых решений, и из этой точки движемся в сторону возрастания z. Для этого находим ∇z:

Так как ∇z не зависит от x₁ и x₂, то можно в принципе двигаться сразу до границы области допустимых решений, и при этом функция z (и вместе с ней и f, так как z ≤ f) рее время будет возрастать. Однако, если продвинуться до самой границы, дальнейшее движение вдоль ограничений будет практически невозможным, так как по крайней мере какое-нибудь одно ограничение будет нарушаться уже при самом малом шаге. Кроме того, также будут сильно сказываться ошибки вычислений, обычно накапливающиеся из-за округления результатов. Именно для этого вводится параметр δ₁>0, ограничивающий приближение к границе. Выберем, например, δ₁ = 1,01 и перепишем ограничения в виде

Подставим в эти уравнения значения x₁₁ = 1 + 1,5α₁, x₁₂ = 1 + 2,5α₁ и найдем (α₁)_max, при котором точка (x₁₁, x₁₂) еще находится в области, задаваемой ограничениями (аналогично тому, как это делалось в примере, рассмотренном в § 6). Получаем (α₁)_max = 0,838 и точку с координатами x₁₁ = 2,257, x₁₂ = 3,095, которую считаем находящейся на границе области допустимых решений. При этом z₁ = 11,123.

Далее переходим к движению вдоль границы. Для этого ищем компоненты вектора ξ⁽¹⁾ (ξ₁, ξ₂), являющиеся решением следующей линейной задачи:

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

(*)

Здесь выражения в скобках есть компоненты вектора ∇ψ_i (например, и т. д.), в которые следует подставить значения x₁ = x₁₁ = 2,257 и x₂ = x₁₂ = 3,095. Величину λ₁>0 выберем несколько позже. В результате получаем систему ограничений в виде

Эту задачу линейного программирования, конечно, можно решить симплексным методом, однако мы поступим проще. Для того чтобы функция z увеличилась, необходимо, чтобы было u>0, что, очевидно, будет иметь место, когда по крайней мере или ξ₁>0, или ξ₂>0. Значения ξ₁ и ξ₂, соответствующие крайним точкам многоугольника ограничений, можно легко найти, решая попарно уравнения, полученные из этой системы ограничений. Нетрудно убедиться, что только совместное решение последнего уравнения с остальными тремя дает ξ₁> 0. При этом max u = 0,89λ₁ достигается при значениях ξ₁ = 8,65λ₁, ξ₂ = - 4,84λ₁, получающихся при совместном решении уравнений

Согласно условиям |ξ_i|≤1 примем λ₁ = 0,1; тогда ξ₁ = 0,865, ξ₂ = - 0,484 и max u = η₁ ≈ 0,089.

Так как η₁<δ₁ (случай максимизации),то надо брать величину ^δ₁/₂ = δ₂ и вычислять α₂, используя ограничения в виде

и переменные x₁ = x₂₁ = 2,257 + 0,865α₂ и x₂ = x₂₂ = 3,095 - 0,484α₂. Опять прежде всего будет нарушено первое ограничение, и оно определяет (α₂)_max = 0,668. Поэтому получаем после второго шага x₂₁ = 2,835, x₂₂ = 2,772. Для контроля правильности вычислений полезно бывает еще раз убедиться в том, что полученное решение удовлетворяет первым трем ограничениям. Что касается четвертого ограничения, то по условно оно удовлетворяется, если x₁<5 и x₂<5. Значение функции z также увеличилось в точке (x₂₁, x₂₂) и стало равным 11,183. После этого можно переходить к следующему шагу, определяя прежде всего ξ⁽²⁾ (ξ₁, ξ₂) путем решения той же задачи линейного программирования (*), но при значениях x₁ = 2,835 и x₂ = 2,772. Как указано выше, процесс решения повторяется до тех пор, пока мы не получим max u = η_l+1 = 0. Количество шагов будет во многом определяться необходимой точностью решения задачи с учетом оговорок о проверке сходимости, сделанных выше. Естественно, что использование метода наискорейшего Куска (подъема) при расчетах вручную является весьма трудоемким, однако при наличии ЭВМ его применение не вызывает затруднений.