Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
б) Нижняя граница 3 вогнута. Метод не будет работать, так как даже при точном значении X* поиск минимума JSf (х, X’) приведет к далекой от решения точке х(Х).
в) Нижняя граница 3) строго выпукла вниз только в окрестности оси ординат. Метод имеет шансы на успех при хорошем начальном приближении. (Напомним, что, решая задачу (4), находят именно локальный минимум.)
Свойства выпуклости области & обычно неизвестны. Поэтому метод множителей Лагранжа в той форме, в какой он описан выше, применяется в вычислениях редко. Перейдем к описанию второго алгоритма.
Метод условного градиента. Более употребительна другая форма использования идей Лагранжа, к которой можно прийти разными путями. (В зависимости от этого одинаковые по существу методы получают разные названия: метод линеаризации, метод приведенного градиента и т.п.) Мы предпочтем вывести основную конструкцию на основе линеаризации. Итак, пусть точка х допустима в смысле выполнения всех условий /' = 0 (г = 1, 2, ..., /). Ищем малую поправку дх, линеаризуя задачу и добавляя ограничение на дх.
Смещение дх определяется задачей (3) при условиях
/'(*) + Z1x(X) дх = 0, і = 1,2, ...,/. (5)
Составляя для этой задачи функцию Лагранжа:
Я(дх, X, ц) = /° дх + 2 XiUi 4- Px дх) - § (дх, дх),
находим минимум из уравнений дЛС/ддх = 0. В результате имеем систему уравнений для дх, X, ц:
v;)-
Подставляя это выражение в (5), получаем для X систему уравнений с параметром (х:
S^P + (ІЇ> /І) + І *,(/?, = °« г = 1> 2, ..., /.
J=і ¦
ПОИСК МИНИМУМА
421
Решая систему уравнений дважды (один раз с правыми частями (/», f‘x), второй раз с /'), находим общее решение вида X/ + цХ/', после чего можно определить (А из условия (Ьх, Ьх) = Б2. Здесь не случайно в задачу включены значения /'^ 0 . Ниже нам понадобится именно такая более общая конструкция. Заметим только, что при вычислении (л следует выбрать решение, дающее минимум, а не максимум функции Лагранжа SC.
Итак, пусть в точке х выполнены условия f‘(x) = О и определено возмущение Ьх. Теперь есть два способа использовать этот результат.
Первый способ: формируется «линия спуска» х + s Ьх. Тогда (если в точке х выполнены условия /' = 0) можно утверждать, что
f‘(x + s Ьх) I s=0 = Zix(X) Ьх,
т.е. смещение по s сопровождается линейным (по s) убыванием /° и соблюдением (в первом порядке) условий /' = 0.
Однако мы должны выбрать какое-то конечное значение s. Работающие по вышеприведенной схеме алгоритмы различаются выбором того критерия, по которому при увеличении s падение /° считается еще выгодным, хотя оно и сопровождается нарушением условий. На следующей итерации приходится варьировать х с учетом уже имеющихся малых нарушений в условиях /' = О, и проблема выбора s осложняется.
Второй способ: Ьх считается уже готовой вариацией, т.е. нужно переходить к точке х + Ьх. Здесь возникают те же, в сущности, проблемы, но они должны решаться в терминах достаточно ответственного назначения величины е (в первом способе, очевидно, величина є никакой роли не играет).
Выпуклое программирование. Перейдем к описанию некоторой общей идеи, приведшей в конечном счете к одной (из двух, в сущности) фундаментальных конструкций эффективных алгоритмов математического программирования. Предположим, что область достижимости 3 есть строго выпуклое множество.
Определение 1. Множество 3 называют строго выпуклым, если для любых двух его граничных точек z' и z" все точки соединяющего их интервала z(s) = sz' + (I — s)z" (s Є (0, 1)) лежат строго внутри Qf.
Можно характеризовать свойство строгой выпуклости и по-другому. Для любого вектора X = {1, X1, ..., X1 } задача min (z, X) име-
ет единственное решение z(X) Є дЗ. Заметим, что граница строго
422
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
выпуклого множества может содержать угловые точки. При этом разные X могут дать одну и ту же точку z(X). Все такие X называют опорными к 5? в точке z(X). Если граница в точке Z0 Є дЗ является гладкой, то значение X0, для которого z(X0) = z0, является внутренней нормалью к д& в точке z0. Докажем важную теорему.
Теорема 1. Если область достижимости 3 является строго выпуклой, то задача на условный экстремум (1), (2) эквивалентна суперпозиции задач на безусловный экстремум
max { Hiin-^(X1X)J,
где 5?(х, X) = (f(x), X).
Эту задачу можно сформулировать в несколько иной редакции:
max F(X), где F(X) = min (f(x),X).
*¦ - X-SxSX+
Таким образом, речь идет просто о нахождении максимума функции F(X) при достаточно сложном ее определении: эта функция задана алгоритмом поиска минимума.
Доказательство. Пусть х* — точка, решающая исходную задачу на условный экстремум (1), (2). Существование такой точки следует из общих теорем, в которых используется непрерывность функций /, а также, например, ограниченность и замкнутость 3.
Пусть X* — опорный вектор к дЗ в точке z* =/(х*). Покажем, что для всех X имеет место F(X) ^ F(Xt).
В самом деле, пусть X^ X*. Вычислим z(X) и F(X) = (z(X), X). Тогда вся область 3) и, следовательно, точка z* лежат выше гиперплоскости, проходящей через z(X) ортогонально X:
