Методы решения задач нелинейного программирования

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

Рассмотрим задачу оптимизации

max (min) z = ƒ(x); (6.3)

φ_i(x) = b_i (i = 1,...,m), x = (x₁, x₂,..., x_n). (6.4)

Эта задача выделяется из задачи (6.1), (6.2) тем, что среди ограничений (6.2) нет неравенств, нет условий не отрицательности переменных, их дискретности, m<n и функции ƒ(x) и φ_i(x) непрерывны и имеют частные производные, по крайней мере второго порядка.

Последовательность решения данной задачи методом неопределенных множителей Лагранжа:

1) составить функцию Лагранжа

L(x₁,…, x_n, λ₁,…, λ_m) = ƒ(x₁,..., x_n) + ; (6.5)

λ₁,…, λ_m – множители Лагранжа;

2) найти частные производные функции Лагранжа по всем переменным х₁, х₂,..., х_п, λ₁,…, λ_m

(6.6)

Получили систему уравнений(6.6), состоящую из n + m уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;

3) из стационарных точек, взятых без координат λ₁,…, λ_m , выбрать точки, в которых функция ƒ(x) имеет условные локальные экстремумы при наличии ограничений (6.4).

Признаком существования минимума функции ƒ(x) в стационарнойточке х^* является выполнение в ней достаточных условий минимума – выпуклости функции в окрестности этой точки, что может быть представлено следующим образом [*]:

⃒x= > 0;

> 0,

т.е. все определители должны быть положительны.

Этот метод можно обобщить и на случай, когда переменные не отрицательны и некоторые ограничения заданы в форме неравенств.

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

Допустим, что рассматривается задача безусловной минимизации целевой функции F(x). Сущность всех методов решения этой задачи, о которых далее пойдет речь, состоит в построении последовательности точек х⁽⁰⁾, х⁽¹⁾, ..., х^(р),..., монотонно уменьшающих значение целевой функции, т.е.

F(x⁽⁰⁾) ≥ F(x⁽¹⁾) ≥ F(x⁽²⁾) ≥ … ≥ F(x^(p)) ≥ … .

Такие методы (алгоритмы) называют методами спуска (или подъема при максимизации целевой функции). Их важнейшей характеристикой является сходимость, которая состоит в том, что при беспредельном увеличении последовательность х⁽⁰⁾, х⁽¹⁾, ..., х^(р),... сходится в точке глобального (локального) минимума.

Использование всех методов спуска сводится к следующей схеме. Пусть на р – й итерации (р – м шаге) имеется точка х^(р). Тогда выбирают направление спуска – единичный вектор l^(p), определяющий это направление, а также длину шага α_р > 0 вдоль этого направления. Очередную точку вычисляют по следующей формуле:

х^(р+1) = х^(р) + α_р l^(p), р = 0,1,... .

Различные методы спуска отличаются друг от друга подходом к выбору длины шага α_р (при α_р = αспуск осуществляется с постоянным шагом) и вектора l^(p). Все методы спуска можно разделить на три группы в зависимости от того, какие характеристики целевой функции F(x) используются для определения α_р и l^(p). К первой группе относят методы, требующие только вычисления значений целевой функции. Эти методы называются методами нулевого порядка. Методы первого порядка требуют вычисления значений функции и ее первых производных. Наконец, методы второго порядка предполагают исследование и вторых производных.

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

Широкое распространение в энергетических расчетах нашел метод нулевого порядка – метод покоординатного спуска. В соответствии с этим методом направление спуска выбирают параллельно координатным осям. Сначала проводят спуск вдоль оси Ох₁, затем – вдоль оси Ох₂ и т.д. вплоть до оси Ох_п.

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

Задачи без ограничений. Рассмотрим задачу максимизации нелинейной дифференцируемой функции f(Х). Суть градиентного поиска точки максимума Х^* очень проста: надо взять произвольную точку Х₀ и с помощью градиента , вычисленного в этой точке, определить направление, в котором возрастает с наибольшей скоростью, а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку Х₁. Потом снова определить наилучшее направление для перехода в очередную точку Х₂ и т.д. Таким образом, надо построить последовательность точек Х₀, Х₁, Х₂, …, Х_к, …так, чтобы она сходилась к точке Х^*, т.е. для точек последовательности выполнялись условия

f(Х₀) < f(Х₁) < f(Х₂) < … < f(Х_к) < ….

Градиентные методы позволяют получать точное решение за бесконечное число шагов и только в некоторых случаях – за конечное. В связи с этим градиентные методы относят к приближенным методам решения.

Движение из точки Х_к в новую точку Х_к+1 осуществляется по прямой, проходящей через точку Х_к и имеющей уравнение

Х_к+1 = Х_к + , (6.7)

где числовой параметр, от которого зависит длина шага.

Градиентные методы отличаются друг от друга способом выбора величины шага – значения параметра α_к. Можно, например, двигаться из точки в точку с постоянным шагом α_к = α, т.е. при любом к

Х_к+1 = Х_к + .

Если при этом окажется, что f(Х_к+1) < f(Х_к), то следует возвратиться в точку Х_к и уменьшить значение параметра α, например до α/2.

Если ищется приближенное решение, то поиск можно прекратить, основываясь на следующих соображениях. После каждой серии из определенного числа шагов сравнивают достигнутые значения целевой функции f(Х). Если после очередной серии изменение f(Х) не превышает некоторого наперед заданного малого числа ε, поиск прекращают и достигнутое значение f(Х) рассматривают как искомый приближенный максимум, а соответствующее ему Х принимают за Х^*.

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

Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема (наискорейшего спуска – если решается задача минимизации). Суть его в следующем. После определения f(Х_к) в точке Х_к движение вдоль прямой Х = Х_к + производится до точки Х_к+1, в которой достигается максимальное значение функции f(Х) в направлении градиента f(Х_к). затем в этой точке вновь определяется градиент, и движение совершается по прямой Х = Х_к+1 + в направлении нового градиента f(Х_к+1) до точки Х_к+2, в которой достигается максимальное в этом направлении значение f(Х). Движение продолжается до тех пор, пока не будет достигнута точка Х^*, соответствующая наибольшему значению целевой функции f(Х). На рис.х.х приведена схема движения к оптимальной точке Х^* методом наискорейшего подъема. В данном случае направление градиента f(Х_к) в точке Х_к является касательным к линии уровня поверхности f(Х) в точке Х_к+1, следовательно, градиент в точке Х_к+1 ортогонален градие f(Х_к).

Рис.6.2

Перемещение из точки Х_к в точку Х_к+1 = Х_к + сопровождается возрастанием функции f(Х) на величину

Δ f(Х) = f(Х_к+1) - f(Х_к) = f(Х_к+1,1;…; Х_к+1,п) - f(Х_к,1;…; Х_к,п) =

= . (6.8)

Из выражения (6.8) видно, что Δf является функцией переменной α_к, т.е. Δf = Δf(α_к). При прохождении максимума функции f(x) в направлении градиента f(Х_к) необходимо выбирать шаг перемещения (множитель , обеспечивающий наибольшее возрастание приращению функции, именно функции Δƒ( . Величина при которой достигается наибольшее значение Δƒ( , может быть определена из необходимого условия экстремума функции Δƒ( :

d(Δƒ( )/dα_k = 0. (6.9)

Найдем выражение для производной, дифференцируя равенство (6.9) по α_к как сложную функцию:

f(Х_к+1) f(Х_к).

Подставляя этот результат в равенство (х.х1), получаем

d(Δƒ( )/dα_k f(Х_к+1) f(Х_к).

Это равенство имеет простое геометрическое истолкование: градиент в очередной точке Х_к+1 ортогонален градиенту в предыдущей точке Х_к.

Задачи с линейными ограничениями. Рассмотрим задачу выпуклого программирования с линейными ограничениями:

max Z = ƒ(x); (6.10)

ax ≤ a_i0 (i = 1, 2,...m) (6.11)

x ≥ 0, (6.12)

где х = (х₁; х₂;...; х_п); а_i = (a_i1; a_i2;...; a_in).

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

Начнем с геометрической иллюстрации процесса решения задачи (рис.х.хх). Пусть начальная точка Х₀ расположена внутри допустимой области. Из точки Х₀ можно двигаться в направлении градиента f(Х₀), пока ƒ(Х) не достигнет максимума. В нашем случае ƒ(Х) все время возрастает, поэтому остановиться надо в точке Х₁ на граничной прямой.

Рис. 6.3

Как видно из рисунка, дальше двигаться в направлении градиента f(Х₁) нельзя, т.к. выйдем из области допустимых решений. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выходит из допустимой области, а с другой – обеспечивает наибольшее возрастание ƒ(Х). Такое направление определяет вектор r₁, составляющий с вектором f(Х₁) наименьший острый угол по сравнению с любым другим вектором, выходящим из точки Х₁и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения f(Х₁) r₁ > 0. В данном случае вектор r₁, указывающий наивыгоднейшее направление, совпадает с граничной прямой.

Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает ƒ(Х); в нашем случае – до точки Х₂. Из рисунка видно, что далее следует перемещаться в направлении вектора r₂, который находится из условия максимизации скалярного произведения f(Х₂) r₂ > 0, т.е. по граничной прямой. Движение заканчивается в точке Х₃, поскольку в этой точке завершается оптимизационный поиск, т.к. в ней функция ƒ(Х) имеет локальный максимум. Ввиду вогнутости оптимизационной функции, в этой точке ƒ(Х) достигает глобального максимума в допустимой области. Градиент в точке максимума Х₃ = Х^* составляет тупой угол с любым вектором r_к из допустимой области, проходящей через Х₃, поэтому скалярное произведение f(Х₃) r_к будет отрицательным для любого допустимого r_к, кроме r₃, направленного по граничной прямой. Для него скалярное произведение f(Х₃) r₃ = 0, т.к. f(Х₃) и r₃ взаимно перпендикулярны (граничная прямая касается линии уровня поверхности ƒ(Х), проходящей через точку максимума Х^*). Это равенство и служит аналитическим признаком того, что в точке Х₃ функция ƒ(Х) достигла максимума.

Аналитическое решение задачи (х.хх1) – (х.хх3) требует, чтобы при выборе α_к определение очередной точки Х_к+1 = Х_к + α_к f(Х_к) осталось в допустимой области. Существуют различные методы оптимизации длины шага (α_к) и проверки принадлежности очередной точки Х_к допустимой области.

Задачи с нелинейными ограничениями. Если в задачах с линейными ограничениями движение по граничным прямым оказываетя возможным и даже целесообразным, то при нелинейных ограничениях, определяющих выпуклую область, любое сколь угодно малое перемещение из граничной точки может сразу вывести за пределы области допустимых решений, и возникает необходимость в возвращении в допустимую область (рис. 6.4). Подобная ситуация характерна для задач, в которых экстремум функции ƒ(Х) достигает на границе области. В связи с этим

Рис 6.4

применяются различные способы перемещения, обеспечивающие построение последовательности точек, расположенных вблизи границы и внутри допустимой области, или зигзагообразное движение вдоль границы с пересечением последней. Как видно из рисунка, возврат из точки Х₁ в допустимую область следует осуществлять вдоль градиента той граничной функции φ_к(Х), которая оказалась нарушенной. Это обеспечит отклонение очередной точки Х₂ в сторону тоски экстремума Х^*. Признаком экстремума в подобном случае будет коллинеарность векторов ƒ и φ_к.