![]() | § 7. Общая задача нелинейного программирования | ![]() |
Ибо самое странное, заставляющее быть настороже в этой среде, или мире, в котором мы вынуждены существовать, состоит в том, что
Х. Ортега-и-Гассет. Человек и люди
Здесь в соответствии со схемой предыдущего параграфа рассматривается общая задача нелинейного программирования с гладкими функциями.
Общей задачей нелинейной условной оптимизации мы будем называть условную задачу минимизации
f0(x) ® min, x О W, | (1) |
где W выделяется как ограничениями типа равенств
fi(x) = 0, i = 1, ..., k, | (2) |
так и ограничениями типа неравенств
gj(x) Ј 0, j = 1, ..., l | (3) |
(см. рис. 22).
Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (1)(3) можно записывать в виде
f0(x) ® min, f(x) = Q, g(x) Ј Q. | (4) |
(напомним, что неравенство
Нам также потребуется следующее обозначение:
7.2. Теорема (обобщенное правило множителей Лагранжа).
Пусть f0, f, g О C1, а x* локальное решение задачи
(4). Тогда найдутся такие
| (5) |
Д о к а з а т е л ь с т в о. Возьмем r > 0
таким, чтобы
f n(x) = f0(x) + n(||f(x)||2 + ||g+(x)||2) + ||x - x*||2. |
З а д а ч а 7.1. Докажите, что
Поскольку
f n(xn) Ј f n(x*), | (6) |
|
Отсюда, поскольку, как легко видеть,
|
Выражение в квадратных скобках ограничено, так как
Пусть теперь {xni} произвольная сходящаяся, скажем к y, подпоследовательность. Тогда, как легко видеть, во-первых, |
f0(y) + ||y - x*||2 Ј f0(x*). |
С другой стороны, так как
Далее, в силу доказанного можно считать, что при всех n точка xn лежит внутри шара
| (7) |
Положим теперь
|
ln0 = sn, lni= 2nfi(xn)sn, mnj= 2n[gj(xn)]+sn. Поскольку |
ln0® l*0, lni® l*i, mnj® m*j при n ® Ґ. |
Умножив (7) на sn и переходя в получившемся равенстве к пределу при
| (8) |
Остается заметить, что, во-первых, так как |
|
Так же, как и в случае ограничений-равенств в случае общей задачи нелинейной оптимизации, необходимый признак, задаваемый теоремой 7.2, информативен только в случае,
если |
L(x, l, m) = f0(x) + (l, f(x)) + (m, g(x)). |
Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы
(f ўi(x),h) = 0 при i = 1, ..., k |
и
(gўj(x),h) < 0 при j О J(x). |
Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами
( |
7.4. Теорема (обобщенное правило множителей Лагранжа в регулярном случае).
Пусть f0, f, g О C1, а x* регулярное локальное решение задачи (4). Тогда найдутся
Lўx(x*,l*, m*) = 0, | (9) |
(m*, g(x*)) = 0. | (10) |
Д о к а з а т е л ь с т в о. Пусть l0**, l** и |
| (11) |
В силу регулярности |
|
что вместе с линейной независимостью |
Таким образом l0**№ 0. Положим теперь
|
Очевидно теперь, (10) выполняется автоматически, а (9) тривиально получается из (5).
7.5. Достаточные условия, существование, единственость.
Ситуация с задачей (1)(3) несколько отличается от изучавшихся ранее, поскольку минимумы здесь могут быть двух типов. В случае, когда в точке минимума x* нет активных ограничений,
Мы ограничимся лишь формулировками результатов, поскольку в идейном плане они не доставляют ничего нового. Аналогом теоремы 6.9 может служить следующая
Теорема (достаточные условия минимума). Пусть
(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. Тогда |
З а д а ч а 7.2. Докажите.
Что касается утверждений о существовании и единственности, то ситуация с результатами, которые могут быть доказаны изученными выше приемами, полностью аналогична.
З а д а ч а 7.3. Сформулируйте и докажите аналоги утверждений задач 6.7 и 6.8 для задачи (1)(3).
7.6. Об ограничениях-равенствах.
С целью упрощения изложения, начиная с этого момента, мы будем рассматривать задачу условной оптимизации, содержащую только ограничения-неравенства. Это, с одной стороны, не снижает общности изложения, поскольку ограничения-равенства сводятся к ограничениям-неравенствам: ограничение
f(x) = Q |
эквивалентно ограничениям
f(x) Ј Q, -f(x) Ј Q. |
С другой стороны, задачи с ограничениями-равенствами мы уже достаточно подробно рассматривали выше.
Здесь, правда, следует помнить об одном важном обстоятельстве. При решении задач с ограничениями-неравенствами часто бывает важна (существенно используется) выпуклость функций, фигурирующих в задаче, вернее, выпуклость минимизируемой функции f0 и выпуклость множества W допустимых точек. Последнее гарантируется выпуклостью функций gj в ограничениях-неравенствах (см.
Напомним, что множество W М Rm называется выпуклым, если
З а д а ч а 7.4. Докажите, что если функции
З а д а ч а 7.5. Докажите, что если функция
7.7. Еще один достаточный признак условного минимума.
Напомним, что точка
L(x*, l) Ј L(x*, l*) Ј L(x, l*) |
Теорема. Пусть |
Д о к а з а т е л ь с т в о. Пусть x произвольная допустимая точка,
f0(x*) + (l*, g(x*)) = L(x*, l*) Ј L(x, l*) = f0(x) +(l*, g(x)). | (12) |
Покажем, что
(l*, g(x*)) = 0. | (13) |
Тогда из (12), поскольку
(l*, g(x*)) і 0. | (14) |
Равенство (13) вытекает теперь из (14), т.к.
Тот факт, что доказанная теорема дает лишь достаточный признак условного минимума демонстрируетсмя в следующей задаче.
З а д а ч а 7.6. Покажите, что одномерная задача
минимизации функции
З а д а ч а 7.7. Если в предыдущей теореме
Однако, если функции f0 и gi
Перейдем к описанию методов решения задач с ограничениями-неравенствами. Многие из описываемых ниже методов либо существенно используют выпуклость объектов, фигурирующих в задаче, либо вообще неработоспособны на невыпуклых задачах.
7.8. Методы возможных направлений.
Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным для задачи
З а д а ч а 7.8*. Докажите, что если (f0(x), z) < 0, то малое перемещение из точки x в направлении z уменьшает значение функции f0 (ср. с доказательством теоремы Ферма).
З а д а ч а 7.9*. Докажите, что если точка x допустима и (gi(x), z) < 0 при i О J(x), то малое перемещение из точки x в направлении z не выводит из множества допустимых точек.
В силу этих задач возможное направление zn в очередной точке xn, в котором функция f0 будет убывать быстрее всего, можно искать, решая задачу линейного программирования (о методах решения линейных задач см. список литературы)
(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) введены
для того, чтобы искать вектор возможных направлений на ограниченном множестве,
Je(x) = {i О {1, ..., m}: gi(x) і -e}. |
Таким образом, если e малó и
xn+1 = xn + anzn, | (18) |
где zn есть решение следующей линейной задачи
x® min |
с ограничениями
(f ў0(xn),z) - x Ј 0, |
(gўi(xn),z) - x Ј 0, i О Jen(xn) |
и нормализующими ограничениями (16). Подчеркнем, что в этой задаче неизвестными являются
7.9. Методы проекции градиента.
Проекцией PWx точки x О Rm на множество W М Rm называется любая ближайшая к x точка множества W:
||x - PWx|| Ј ||x - y|| при всех y О W. |
З а д а ч а 7.10. Докажите, что если W замкнуто и выпукло, то для любой точки проекция сужествует и единственна.
З а д а ч а 7.11. Приведите пример, когда проекция: а) не существует; б) не единственна.
В тех случаях, когда проекцию точки на множество допустимых точек задачи |
xn+1 = PW(xn - anf ў0(xn)) |
(см. рис. 26), являющийся прямым обобщением градиентного метода.
Можно доказать, например, что если функция
Суть этих методов, как следует из названия, состоит в линеаризации минимизируемой функции и ограничений в очередной точке xn строящейся релаксационной последовательности и объявлении следующим значением
(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) оставляют только
Основная идея здесь заключается в переходе от задачи |
| (21) |
З а д а ч а 7.12 (ср. с задачей 6.11). Пусть f0, g О C1, а
F sout(x)® min | (22) |
при всех s разрешима и ее решение xs сходится к x* при
Геометрическая трактовка замены задачи
Задачу (22) решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности задачи (22) с ростом s.
Описанный класс методов называют методами внешних штрафов, поскольку минимизируемая функция изменяется вне множества W. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества W возводятся барьеры, не позволяющие приближаться к его границе. Например, вместо задачи
Fsin(x)® min, | (23) |
где функция Fsin: Wg ®R определяется равенством (ср. с ((21)) |
|
Сравнение геометрических интерпретаций задач
З а д а ч а 7.13. Сформулируйте и докажите аналог задачи 7.5 для метода барьеров.
Задача (23) решается методами, развитыми для безусловных задач; при этом "крутизна барьера" характеризуемая числом s, возрастает на каждом шаге.
З а д а ч а 7.14. Попытайтесь выписать аналоги штрафных
функций |
Суть методов из этого весьма обширного класса в применении к задачам с ограничениями-неравенствами, так же как и в задачах с ограничениями-равенствами, заключается в замене условной задачи
xn+1 = xn - anLўx(xn,mn), mn+1 = [mn + anLўm(xn,mn)]+. |
Для поиска седловой точки в двойственных методах применяют почти весь спектр описанных выше методов
File based on translation from
TEX by TTH,
version 3.05.
Created 10 Jun 2001, 20:58.