![]() | § 6. Задачи с ограничениями типа равенств | ![]() |
Не уклоняйся ни направо, ни
налево; удали ногу твою от зла...
Книга притчей Соломоновых, 4:27
Я должен удержать то, что считаю истинным ..., даже вопреки собственному желанию.
А. Камю. Миф о Сизифе
В этом параграфе рассматривается одна из простейших задач условной оптимизации. Проводится теоретическое исследование. Описываются методы решения
Напомним, что общая задача условной оптимизации выглядит так
f(x) ® min, x О W, |
где W собственное подмножество Rm. Подкласс задач с ограничениями типа равенств выделяется тем, что множество W задается ограничениями вида
где fi: Rm ®R (i = 1, ..., k). Таким образом,
В этом параграфе, как и в предыдущих, мы предполагаем, что все участвующие в рассмотрении функции достаточно гладкие. В общем случае множество W представляет собой гладкое Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде
Если обозначить теперь через f функцию на Rm со значениями в Rk, координатная запись которой имеет вид
Геометрически задача с ограничениями типа ![]() Рис. 19. Точки, удовлетворяющие всем ограничениям (
Если (3) выполняется только для допустимых x, лежащих в некоторой окрестности Vx* точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.
6.3. Правило множителей Лагранжа. Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим
Координаты вектора m, Теорема. Пусть F О C1 и
6.4. Обсуждение правила множителей Лагранжа. Начнем с геометрической интерпретации. Пусть для наглядности m = 2, а k = 1. В соответствии с теоремой 6.3, если
![]() Рис. 20. Правило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки
Поскольку, очевидно, множители Лагранжа можно искать с точностью до постоянного множителя, то в общей ситуации этих уравнений хватает для отыскания x*. 6.5. Доказательство теоремы 6.3. Допустим противное:
Допустим, для определенности, что отличный от нуля минор
Обозначим
Тогда, во-первых,
и, во-вторых, в силу (5),
В частности, это равенство имеет место для
Таким образом, при достаточно малых s, во-первых,
и, во-вторых,
Последнее равенство означает, что точки xs являются допустимыми, а (8) (если взять s достаточно малым и 6.6. Обсуждение доказательства. Основную идею доказательства, приведенного выше можно, немного модифицировав,
интерпретировать так. Разобьем переменные xi на две
группы
можно было выразить y через z:
Теорема Ферма для задачи (9) при этом порождает теорему 6.3. З а д а ч а 6.2. Проведите аккуратные рассуждения.
Очевидно, L(x, l) = M(x, m), где m = (1, l). 6.8. Теорема (правило множителей Лагранжа в регулярном случае). Пусть F О C1, а x* регулярное локальное решение задачи
Д о к а з а т е л ь с т в о. Покажем, что теоремы 6.3 и 6.8 вытекают друг из друга (для доказательства теоремы 6.8 достаточно, разумеется, импликации "
Первые m уравнений системы,
Поэтому эта система переписывается следующим образом:
или, что то же самое,
Таким образом, (x*, l*) стационарная точка функции Лагранжа. В некотором смысле правило множителей Лагранжа сводит задачу о поиске условного минимума к безусловной задаче о поиске стационарной точки
6.9. Одно достаточное условие локального минимума.
Д о к а з а т е л ь с т в о. Добавим к функции Лагранжа "штраф за нарушение ограничений (2)":
З а д а ч а 6.5. Докажите, что В силу задачи 6.5 и условий теоремы
а
Тогда, если З а д а ч а 6.6. Покажите, что s0 можно выбрать не зависящим от y. Таким образом, стационарная точка x* функции
при x близких к x*. Остается заметить, что если
точка x допустима, то 6.10. Замечания о существовании и единственности решений. Поскольку в идейном плане утверждения, приводимые ниже, не доставляют ничего нового по сравнению с утверждениями пп. 2.6 и 2.7, мы формулируем их в виде задач и предоставляем читателю возможность доказать их. З а д а ч а 6.7. Пусть F О C и при некотором a множество
З а д а ч а 6.8. Докажите, что невырожденная точка минимума локально единственна. Перейдем к приближенным методам решения задачи 6.11. Методы решения задач с ограничениями типа равенств. Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа Поэтому естественно искать решение x* как первые m координат стационарной точки функции Лагранжа, например, методом Ньютона, для которого не важен тип стационарной точки (он одинаково хорошо ищет как экстремальные, так и седловые точки (см., напр.,
(см. уравнение (4.5)), или, в "координатной" форме
и мы получаем m + k линейных уравнений для нахождения З а д а ч а 6.9. Пользуясь теоремой 4.2, сформулируйте и докажите утверждение о сходимости метода Ньютона для задачи Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи
или, что то же,
|
Можно доказать, что этот метод (его обычно называют методом |
Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные (l) переменные.
Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного |
xn+1 = argmin [(f ў0(xn),x - xn) + a||x - xn||2], | (11) |
fi(xn) + (f ўi(xn),x - xn) = 0, i = 1, ..., k. | (12) |
Ограничения (12) в этом |
З а д а ч а 6.10. Пусть Pn
оператор ортогонального проектирования на касательную гиперплоскость Wўxn. Докажите, что метод
|
|
(Поэтому метод
Один из распространенных методов решения задач с ограничениями, с которым мы еще
fs(x) = f0(x) + s||f(x)||2 |
без ограничений, в которой s положительный параметр.
З а д а ч а 6.11. Пусть задача
Поэтому задачу
xn = argmin f sn(x), |
где sn некоторая неограниченно возрастающая
последовательность. Недостаток этого метода для задачи с ограничениями типа равенств обусловлен тем, что при
File based on translation from
TEX by TTH,
version 3.05.
Created 9 Jun 2001, 117:22.