§ 7. Общая задача нелинейного программирования

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

7.1. Постановка задачи.

Общей задачей нелинейной условной оптимизации мы будем называть условную задачу минимизации

f0(x) ® min,   x О W,

(1)

где W выделяется как ограничениями типа равенств

fi(x) = 0,   i = 1, ..., k,

(2)

так и ограничениями типа неравенств

gj(x) Ј 0,   j = 1, ..., l

(3)

(см. рис. 22).

Рис. 22.

Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из R^m в R^k и R^l, соответственно, определяемые координатами f_i и g_j. Поэтому задачу (1)–(3) можно записывать в виде

f0(x) ® min,   f(x) = Q,   g(x) Ј Q.

(4)

(напомним, что неравенство g(x) Ј Q означает покоординатные неравенства).

Нам также потребуется следующее обозначение: a₊ = (a + |a|)/2; таким образом, a₊ = a, если a і 0 и a₊ = 0, если a Ј 0. Для векторов a О R^m операция "+" определяется покоординатно: a₊ = ((a₁)₊, ..., (a_m)₊). Кроме того, через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j О {1, ..., l}: g_j(x) = 0} — это номера ограничений, которые в данной точке существенны. Например, на рис. 22 J(x¹) = {2}, а J(x²) = Ж.

7.2. Теорема (обобщенное правило множителей Лагранжа).

Пусть f₀, f, g О C¹, а x* — локальное решение задачи (4). Тогда найдутся такие l*₀ О R, l* О R^k, m* О R^l, не равные одновременно нулю, такие, что m*_j і 0 при j О J(x*) и

l*0 f ў0(x*)+  k е i = 1 l*i f ўi(x*)+    е jОJ(x*) m*j gўj(x*) = Q.

(5)

Д о к а з а т е л ь с т в о.  Возьмем r > 0 таким, чтобы x* = argmin_xОWr f(x), где W_r = W З B(x*, r). Для любого n О N определим функцию f ⁿ: R^m ® R равенством

f n(x) = f0(x) + n(||f(x)||2 + ||g+(x)||2) + ||x - x*||2.

З а д а ч а   7.1. Докажите, что f ⁿ О C¹, в частности, покажите, что (||g₊(x)||²)ў = 2g₊(x)gў(x).

Поскольку f ⁿ непрерывно дифференцируемы и поэтому непрерывны, функции f ⁿ на шаре B(x*, r) достигают минимума; обозначим его через xⁿ. В частности,

f n(xn) Ј f n(x*),

(6)

т. е.

f0(xn) + n(||f(xn)||2 + ||g+(xn)||2) + ||xn - x*||2 Ј f n(x*).

Отсюда, поскольку, как легко видеть, f ⁿ(x*) = f₀(x*),

||f(xn)||2 + ||g+(xn)||2 Ј  1 n [f0(x*) - ||xn - x*||2 - f0(xn)],

Выражение в квадратных скобках ограничено, так как xⁿ О B(x*, r). Поэтому ||f(xⁿ)||² + ||g₊(xⁿ)||² ® 0 при n ® Ґ и, следовательно, f(xⁿ) ® Q и g₊(xⁿ) ® Q при n ® Ґ.

Пусть теперь {xni} — произвольная сходящаяся, скажем к y, подпоследовательность. Тогда, как легко видеть, во-первых, y О W и, во-вторых, f ni(xni) ® f0(y) + ||y - x*||2 при n ® Ґ. Поэтому, подставляя в (6) ni вместо n и переходя к пределу в получившемся неравенстве при i ® Ґ, получим

f0(y) + ||y - x*||2 Ј f0(x*).

С другой стороны, так как x* = argmin f(x), f₀(x*) Ј f₀(y). Отсюда ||y - x*||² Ј 0, т. е. y = x*. Таким образом, любая сходящаяся подпоследовательность последовательности {xⁿ} сходится к x*. Последнее, учитывая компактность последовательности, гарантирует ее сходимость к тому же пределу.

Далее, в силу доказанного можно считать, что при всех n точка xⁿ лежит внутри шара B(x*, r). Поэтому в силу теоремы Ферма (f ⁿ)ў(xⁿ) = Q, т. е.

f ў0(xn)+ 2 k е i = 1 fi(xn)f ўi(xn)+ 2 l е j = 1 [gj(xn)]+gўj(xn)+ 2(xn - x*) = Q.

(7)

Положим теперь

sn =  ж и 1 + 4n2 k е i = 1 [fi(xn)]2 + 4n2 l е j = 1 [gj(xn)]2 ц ш -1/2 ,

ln0 = sn, lni= 2nfi(xn)sn, mnj= 2n[gj(xn)]+sn. Поскольку ln0,lnj,mnjО [-1, 1] (n О N; i = 1, ..., k; j = 1, ..., l), можно считать, не ограничивая общности, что найдутся такие l*0,l*iи m*j,что

ln0® l*0,  lni® l*i,  mnj® m*j  при  n ® Ґ.

Умножив (7) на sⁿ и переходя в получившемся равенстве к пределу при n ® Ґ, получаем

l*0f ў0(x*)+  k е i = 1 l*if ўi(x*)+  l е j = 1 m*jgўj(x*)= Q.

(8)

Остается заметить, что, во-первых, так как |ln0|2+ еki=1|lni |2+еlj=1|mnj|2=1, не все из l*0,l*i,m*jравны нулю, во-вторых, поскольку mnj= 2n[gj(xn)]+sn і 0, неотрицательны и m*jи, наконец, в-третьих, если j П J(x*) (т. е. gj(x*) < 0), то gj(xn) < 0 при больших n; поэтому [gj(x*)]+ = 0, что влечет равенство m*j= 0 и, следовательно, равенство

l е j = 1 m*jgўj(x*)=    е jОJ(x*) m*jgўj(x*).

Таким образом (8) — это (5).

7.3. Регулярный случай.

Так же, как и в случае ограничений-равенств в случае общей задачи нелинейной оптимизации, необходимый признак, задаваемый теоремой 7.2, информативен только в случае, если l*0№ 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (5) на l*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: Rm×Rk×Rk ® R (в регулярном случае) равенством

L(x, l, m) = f0(x) + (l, f(x)) + (m, g(x)).

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ў₁(x),..., f ў_k(x)линейно независимы и для некоторого ненулевого вектора h О R^m

(f ўi(x),h) = 0 при i = 1, ..., k

и

(gўj(x),h) < 0 при j О J(x).

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ўi(x)),и, во-вторых, он образует с градиентами gўj(x)активных ограничений (указывающими, очевидно, вовне множества W) тупой угол (см. рис. 23).

Рис. 23.

7.4. Теорема (обобщенное правило множителей Лагранжа в регулярном случае).

Пусть f₀, f, g О C¹, а x* — регулярное локальное решение задачи (4). Тогда найдутся l* О R^k, m* О R^l не равные одновременно нулю, такие, что m*_j і 0 при j О J(x*) и

Lўx(x*,l*, m*) = 0,

(9)

(m*, g(x*)) = 0.

(10)

Д о к а з а т е л ь с т в о.  Пусть l0**, l** и m** — величины, существование которых утверждается в теореме 7.2. Покажем, что l0** № 0. В предположении противного умножим (5) скалярно на вектор h, фигурирующий в определении регулярности x*:

k е i = 1 li**(f ўi(x*),h)+    е jОJ(x*) mj**(gўj(x*),h) = Q.

(11)

В силу регулярности (f ўi(x*),h) = 0 и (gўj(x),h) < 0, а по теореме 7.2 mj**і 0 при j О J(x*). Поэтому (11) влечет равенство m** = Q. Но тогда (5) означает, что

k е i = 1 li**f ўi(x*)= Q,

что вместе с линейной независимостью f ўi(x*)дает равенство l** = Q. Противоречие.

Таким образом l₀**№ 0. Положим теперь l*_i= l_i**/l₀**(i = 1, ..., k),

m*j=  м н о mj**/l0**при  j О J(x*), 0  при  j П J(x*).

Очевидно теперь, (10) выполняется автоматически, а (9) тривиально получается из (5).

7.5. Достаточные условия, существование, единственость.

Ситуация с задачей (1)–(3) несколько отличается от изучавшихся ранее, поскольку минимумы здесь могут быть двух типов. В случае, когда в точке минимума x* нет активных ограничений, т. е. J(x*) = Ж, ситуация полностью аналогична описанной в предыдущем параграфе, поскольку ограничения-неравенства в окрестности точки x* можно опустить (см. рис. 24а). В случае же, когда J(x*) № Ж минимум может достигаться на границе множества W и точка x* может не быть стационарной точкой (см. рис. 24б).

Рис. 24.

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

Теорема (достаточные условия минимума). Пусть f₀, f, g О C², а x* — допустимая точка такая, что для некоторых l* О R^k и m* О R^l, одновременно не равных нулю, выполнены условия (9)–(10) и при любых h О R^m, h № Q таких, что

(f ўi(x*),h) = 0  при  i = 1, ..., k; (gўj(x*),h) = 0  при  j О J(x*), m*j> 0; (gўj(x*),h) і 0  при  j О J(x*), m*j= 0

выполнено неравенство (Lўўxx(x*,l*, m*)h, h) > 0. Тогда x* — локальное решение задачи (1)–(3).

З а д а ч а  7.2. Докажите.

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

З а д а ч а  7.3. Сформулируйте и докажите аналоги утверждений задач 6.7 и 6.8 для задачи (1)–(3).

7.6. Об ограничениях-равенствах.

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

f(x) = Q

эквивалентно ограничениям

f(x) Ј Q,   -f(x) Ј Q.

С другой стороны, задачи с ограничениями-равенствами мы уже достаточно подробно рассматривали выше.

Здесь, правда, следует помнить об одном важном обстоятельстве. При решении задач с ограничениями-неравенствами часто бывает важна (существенно используется) выпуклость функций, фигурирующих в задаче, вернее, выпуклость минимизируемой функции f₀ и выпуклость множества W допустимых точек. Последнее гарантируется выпуклостью функций g_j в ограничениях-неравенствах (см. задачу 7.4 ниже). Множества же, выделяемые ограничениями-равенствами, не бывают выпуклыми, за исключением случая аффинных функций f_i. Поэтому методы решения задач условной оптимизации, существенно использующие "выпуклость задачи" могут применяться к задачам с ограничениями-равенствами с большой осторожностью.

Напомним, что множество W М R^m называется выпуклым, если "(x, y О W, l О [0, 1])[lx + (1 - l)y О W].

З а д а ч а  7.4. Докажите, что если функции g_i: R^m ® R (i = 1, ..., l) выпуклы, то множество W = {x О R^m: g_i(x) Ј 0, i = 1, ..., l} выпукло.

З а д а ч а  7.5. Докажите, что если функция g: R^m® R выпукла, вместе с функцией -g, то она аффинна: g(x) = (b, x) + c.

7.7. Еще один достаточный признак условного минимума.

Напомним, что точка (x*, l*) называется седловой точкой функции L: W₁×W₂ ® R (W₁ М R^m, W₂ М R^l), если при всех (x, l) М W₁×W₂ выполнены неравенства

L(x*, l) Ј L(x*, l*) Ј L(x, l*)

Теорема. Пусть (x*, l*) — седловая точка функции Лагранжа L: Rm×Rl+® R задачи (1), (3) (здесь Rl+= {l О Rl: l і Q}), l* і Q, x* — допустимая точка. Тогда x* — глобальное решение этой задачи.

Д о к а з а т е л ь с т в о.  Пусть x — произвольная допустимая точка, т. е. g_i(x) Ј 0 (i = 1, ..., l). Тогда

f0(x*) + (l*, g(x*)) = L(x*, l*) Ј L(x, l*) = f0(x) +(l*, g(x)).

(12)

Покажем, что

(l*, g(x*)) = 0.

(13)

Тогда из (12), поскольку l* і Q, а g(x) Ј Q, будет следовать нужное неравенство f₀(x*) Ј f₀(x). Для доказательства (13) заметим, что по условию теоремы L(x*, Q) Ј L(x*, l*), т. е.

(l*, g(x*)) і 0.

(14)

Равенство (13) вытекает теперь из (14), т.к. l* і Q, а g(x*) Ј Q.

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

З а д а ч а  7.6. Покажите, что одномерная задача минимизации функции f(x) = -x при ограничениях x Ј 1, -x Ј 0 разрешима, но ее функция Лагранжа не имеет седловых точек.

З а д а ч а  7.7. Если в предыдущей теореме (x*, l*) — локальная седловая точка, то можно ли утверждать, что x* — локальное решение задачи (1), (3)? (Ответ: нельзя).

Однако, если функции f₀ и g_i (i = 1, ..., l) выпуклы, а множество W содержит хотя бы одну внутреннюю точку, то условия доказанной теоремы являются необходимыми и достаточными (это утверждение называется теоремой Куна — Таккера; оно является центральным фактом теории выпуклого программирования).

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

7.8. Методы возможных направлений.

Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным для задачи (1), (3), если малое перемещение в этом неправлении уменьшает значение функции f₀ и не выводит из множества допустимых точек, т. е. если при достаточно малых s точка x^s = x + sz допустима и f(x^s) < f(x). Если теперь на каждом шаге сдвигаться в возможном направлении на достаточно малое расстояние, то мы очевидно получим релаксационную последовательность, которая во многих случаях будет сходиться к решению задачи. Методы этого типа называются методами возможных направлений.

З а д а ч а  7.8*. Докажите, что если (f₀(x), z) < 0, то малое перемещение из точки x в направлении z уменьшает значение функции f₀ (ср. с доказательством теоремы Ферма).

З а д а ч а  7.9*. Докажите, что если точка x допустима и (g_i(x), z) < 0 при i О J(x), то малое перемещение из точки x в направлении z не выводит из множества допустимых точек.

В силу этих задач возможное направление zⁿ в очередной точке xⁿ, в котором функция f₀ будет убывать быстрее всего, можно искать, решая задачу линейного программирования (о методах решения линейных задач см. список литературы)

(f ў0(xn),z) ® min,

(15)

(gўi(xn),z) Ј 0,   i О J(xn),

(16)

zi - 1 Ј 0,   -zi - 1 Ј 0,   i = 1, ..., m.

(17)

Здесь "нормализующие" ограничения (16) введены для того, чтобы искать вектор возможных направлений на ограниченном множестве, т. е. для того, чтобы линейная задача (15)–(16) была разрешима. К сожалению, решение задачи (15)–(16) не всегда дает возможное направление (см. рис. 25). Причиной этого являются нестрогие неравенства в (16) (задачи же со строгими неравенствами часто оказываются неразрешимыми, поскольку точная нижняя грань значений функции f₀ часто достигается на границе множества допустимых точек, которая в случае строгих ограничений-неравенств не принадлежит этому множеству). Эту трудность можно обойти разными способами. Например, на каждом шаге можно "возвращать" точку во множество W с помощью какой-либо процедуры "проектирования" см., например, следующий пункт). Можно также поступать следующим образом. Для любой допустимой точки x и произвольного e > 0 определим множество J_e(x) индексов так называемых e-активных ограничений:

Je(x) = {i О {1, ..., m}: gi(x) і -e}.

Рис. 25.

Таким образом, если e малó и i О J_e(x), то i-ое ограничение в точке x почти обращается в равенство. В одном из вариантов метода возможных направлений выбирают последовательность e_n ® 0 и из очередной точки xⁿ следующий шаг совершют в направлении zⁿ:

xn+1 = xn + anzn,

(18)

где zⁿ есть решение следующей линейной задачи

x® min

с ограничениями

(f ў0(xn),z) - x Ј 0,

(gўi(xn),z) - x Ј 0,   i О Jen(xn)

и нормализующими ограничениями (16). Подчеркнем, что в этой задаче неизвестными являются z и x. Длина шага в (18) выбирается таким образом, чтобы точка xⁿ⁺¹ не выходила из множества допустимых точек.

7.9. Методы проекции градиента.

Проекцией P_Wx точки x О R^m на множество W М R^m называется любая ближайшая к x точка множества W:

||x - PWx|| Ј ||x - y|| при всех y О W.

З а д а ч а  7.10. Докажите, что если W замкнуто и выпукло, то для любой точки проекция сужествует и единственна.

З а д а ч а  7.11. Приведите пример, когда проекция: а) не существует; б) не единственна.

В тех случаях, когда проекцию точки на множество допустимых точек задачи (1), (3) найти достаточно легко (например, когда W — линейное подпространство, полупространство, шар, Rm+и  т. д.) используют метод проекции градиента:

xn+1 = PW(xn - anf ў0(xn))

(см. рис. 26), являющийся прямым обобщением градиентного метода.

Рис. 26.

Можно доказать, например, что если функция f₀ О C¹ сильно выпукла и f ў удовлетворяет условию Липшица, а множество W замкнуто и ограничено, то метод проекции градиента сходится со скоростью геометрической прогрессии.

7.10. Методы линеаризации.

Суть этих методов, как следует из названия, состоит в линеаризации минимизируемой функции и ограничений в очередной точке xⁿ строящейся релаксационной последовательности и объявлении следующим значением xⁿ⁺¹ решения получающейся линейной задачи, т. е. задачи

(f ў0(xn),x - xn) ® min,

(19)

gi(xn) + (gўi(xn),x - xn) Ј 0,   i = 1, ..., l.

(20)

Чтобы эта (линейная) задача была разрешима либо добавляют штраф в минимизируемую функцию, заменяя (19), например, задачей

(f ў0(xn), x- xn) + d||x - xn||2 ® min,

либо добавляя к (20) простые ограничения, которые делают множество допустимых точек этой задачи ограниченным, например, (линейные) ограничения

xi - xni- an Ј 0,   -xi + xni- an Ј 0   (i = 1, ..., m).

Часто для уменьшения объема вычислительной работы среди ограничений (20) оставляют только e-активные.

7.11. Методы штрафов.

Основная идея здесь заключается в переходе от задачи (1), (3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества W допустимых точек (внешний штраф), либо приближение изнутри множества W к его границе (внутренний штраф). Например, это можно сделать так. Для любого s > 0 определим функцию Fsout:Rm ® R равенством (индекс "out" станет понятен чуть ниже)

Fsout(x)= f0(x) + s l е i = 1 (gi)2+(x).

(21)

З а д а ч а  7.12 (ср. с задачей 6.11). Пусть f₀, g О C¹, а x* — единственное решение задачи (1), (3). Пусть, кроме того, множество {x О R^m: ||g_i(x)|| Ј e, i = 1, ..., l} при некотором e і 0 непусто и ограничено. Докажите, что (безусловная) задача

F sout(x)® min

(22)

при всех s разрешима и ее решение x^s сходится к x* при s® Ґ.

Геометрическая трактовка замены задачи (1), (3) задачей (22) изображена на рис. 27.

Рис. 27.

Задачу (22) решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности задачи (22) с ростом s.

Описанный класс методов называют методами внешних штрафов, поскольку минимизируемая функция изменяется вне множества W. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества W возводятся барьеры, не позволяющие приближаться к его границе. Например, вместо задачи (1), (3) можно рассмотреть задачу

Fsin(x)® min,

(23)

где функция Fsin: Wg ®R определяется равенством (ср. с ((21))

Fsin(x)= f0(x) + s l е i = 1 1 gi(x) .

Сравнение геометрических интерпретаций задач (1), (3) и (23) изображено на рис. 28.

Рис. 28.

З а д а ч а  7.13. Сформулируйте и докажите аналог задачи 7.5 для метода барьеров.

Задача (23) решается методами, развитыми для безусловных задач; при этом "крутизна барьера" характеризуемая числом s, возрастает на каждом шаге.

З а д а ч а  7.14. Попытайтесь выписать аналоги штрафных функций Fsoutи Fsinдля общей задачи нелинейного программирования (1)–(3), содержащей как ограничения-неравенства, так и ограничения-равенства.

7.12. Двойственные методы.

Суть методов из этого весьма обширного класса в применении к задачам с ограничениями-неравенствами, так же как и в задачах с ограничениями-равенствами, заключается в замене условной задачи (1), (3) задачей поиска стационарной (часто седловой) точки функции Лагранжа. В выпуклом случае задача (1), (3) и задача о поиске седловой точки функции Лагранжа в силе теоремы Куна – Таккера эквивалентны. Например, применение простейшего (градиентного) метода к последней задаче приводит к следующему методу Эрроу – Гурвица – Удзавы:

xn+1 = xn - anLўx(xn,mn), mn+1 = [mn + anLўm(xn,mn)]+.

Для поиска седловой точки в двойственных методах применяют почти весь спектр описанных выше методов минимизации — методы Ньютона, квазиньютоновские методы, методы сопряженных направлений и  т. д.

File based on translation from T_EX by T_TH, version 3.05.
Created 10 Jun 2001, 20:58.