Анализ некоторых вычислительных алгоритмов решения задачи нелинейного программирования

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

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

Пусть для задачи НП построено расширение.

причем при всех /, X функция R монотонна по /₀. Пусть, кроме того, вектор-функция Дх) определена в каждой точке множества V_x, т. е. принимает в ней фиксированное значение с. Тогда решению расширенной задачи х*(Х) соответствует значение функции/, равное с (А,), а.

Действительно, при фиксированном / = с максимум R достигается только за счет максимизации/₀. Таким образом, х*(А) доставляет/₀(х) максимум при/= с (Х), т. е. решение расширенной задачи реализует одну из ординат функции достижимости исходной задачи. При изменении X вектор х*(Х) перемещается на множестве V_x, меняются величина с (Х) и значение R (x*(X), X) расширенной задачи. Нас интересуют, как правило следующие вопросы:

• 1. Какие ординаты функции достижимости могут быть подсчитаны таким образом?
• 2. Пересечет ли траектория х*(Х) поверхность, выделяемую условиями Дх) = 0 (множество допустимых решений исходной задачи)? Если пересечет, расширение эквивалентно.

Для эквивалентного расширения найдется такое X = X*, что х*(А.) удовлетворяет условиям Дх) = 0, а ординаты функции достижимости, которые могут быть получены при максимизации функции (2.86), включают ординату для с = 0. При X = X* функция R (c, /₀* (с)), полученная из (2.86) подстановкой вместо Дх) вектора с, а вместо/₀(х) — функции достижимости, достигает абсолютного максимума в точке с = 0.

Для расширения Лагранжа, когда в (2.86).

справедлива теорема Эверета: ординаты функции достижимости /о © задачи (2.81), которые могут быть подсчитаны при решении расширенной задачи для различных значений X, соответствуют тем значениям с, на которых /₀* © совпадает со своей выпуклой оболочкой на множестве V_c. Доказательство этой теоремы непосредственно следует из построений, приведенных в подпараграфе 2.4.2.

В предположении эквивалентности расширения вычисление решения исходной задачи сводится к решению двойственной задачи

Алгоритмы отличаются друг от друга видом функции R и способом нахождения минимума и максимума в (2.87).

А. Поиск седловой точки функции Лагранжа.

В этом случае функция R имеет форму (2.84). Алгоритм примет вид.

В этих формулах параметр у, определяющий величину шага, может быть различным по величине, но в обеих формулах он положителен. Алгоритм не всегда сходится к решению двойственной задачи (2.87), он может остановиться в точке, удовлетворяющей необходимым условиям оптимальности этой задачи, в которой максимум по х и минимум по А, — локальные. Кроме того, в условиях (2.88) фигурируют градиенты функций /о и /_f, а значит, алгоритм применим только для дифференцируемых функций/о и/,-.

Априори мы, как правило, не знаем функции /₀* ©. Рассмотрим, как ведет себя алгоритм поиска седловой точки в случае, когда выпуклая оболочка функции достижимости проходит в точке с = 0 строго выше самой этой функции (рис. 2.29, а). При изменении, А из условий (2.88),.

(2.89) для некоторого А* функция К*(с, A*) = /q © = ?А*с, — будет иметь.

i

несколько одинаковых максимумов, каждый из которых выше /₀* (0).

Рис. 2.29. Характер функции достижимости [а) и изменение по итерациям значений, А и максимума f₀ (б).

Точка, А при изменении, А всегда лежит на графике R*(c, А), но ни при каких, А не является точкой ее максимума. Величина R дает верхнюю оценку значения задачи НП; любое, даже малое, изменение X в силу условий (2.89) приводит к таким изменениям х^к+1(Х^к), при которых знак функций/_г(х) меняется. В соответствии с условиями (2.88) значения множителей Лагранжа колеблются от итерации к итерации, средние же их значения, подсчитанные по двум соседним итерациям, меняются незначительно и равны составляющим градиента Co_Vc /J¹ © в точке с = 0 (рис. 2.29, б). Эти соображения могут быть использованы для введения в функцию R таких добавочных слагаемых, чтобы расширение оказалось эквивалентно.

Б. Комбинация функции Лагранжа с квадратичной функцией штрафа.

Имеем.

Как уже упоминалось, расширение с использованием исчезающего слагаемого (2.90) эквивалентно при конечных значениях X и, а для непрерывной функции /₀* © независимо от того, выпукла она или нет. На первый взгляд кажется, что нужно взять достаточно большое значение а = а⁰, зафиксировать его и использовать для выбора X формулу (2.89), а х находить согласно выражению.

Однако чем больше а⁰, тем более ярко выражен овражный характер функции R и тем труднее решить задачу безусловной максимизации (2.91). Поэтому стремятся тем или иным способом оценить то минимальное значение а, при котором расширение задачи НП эквивалентно.

Изложим одну из возможных схем выбора параметров X и а.

1 шаг. Полагают Х° = 0, а множитель, а = а⁰ — некоторому ограниченному значению и решают задачу.

Обозначим ее решение через х°; значения /_?(х°) = ср.

2 шаг. Аппроксимируют функцию достижимости /₀* © в окрестности с = 0 плоскостью.

Выбирают X_t так, чтобы функция достижимости расширенной задачи.

в которой вместо /₀*© фигурирует ее линейное приближение (2.93), достигала в точке с = 0 абсолютного максимума. Подставив в Rjj © правую часть равенства (2.93), получим.

Величину же к? найдем через а⁰ и с° из того условия, что абсолютный максимум функции достижимости расширенной задачи достигается в точке с°:

Подставляя в это равенство выражение (2.93), получим откуда.

Если функция достижимости действительно линейна, то найденные значения А. — точные и подстановка их в (2.91) позволяет получить решение исходной задачи в первом же цикле алгоритма.

В общем случае, если найденное согласно (2.91) решение не оказалось допустимым, увеличивают, а и повторяют процедуру решения. Этот алгоритм реализует общую схему последовательной линеаризации Ньютона (алгоритм касательных для решения нелинейных уравнений) и сходится за конечное число шагов (рис. 2.30).

Рис. 2.30. Функция достижимости расширенной задачи при начальных (а) и окончательных (б) значениях неопределенных параметров.