Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

190 Глава 12. Многомерная оптимизация с ограничениями

Последовательное

Принципиальным преимуществом интер-

квадратичное

претации ньютоновского процесса как по-

программирование

следовательной квадратичной минимизации является возможность его распростра-

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

Подзадача квадратичного программирования. В случае, когда ограничения присутствуют в форме неравенств, линеаризованные ограничения также будут неравенствами, подзадача (12.24)–(12.25) определения ньютоновского шага приобретет вид (постоянное слагаемое L, не влияющее на решение, опущено)

Это — задача квадратичного программирования (см. с. 65)3, таким образом, последовательная условная квадратичная минимизация превращается в последовательное квадратичное программирование (sequential quadratic programming — SQP). Из-за присутствия неравенств ее нельзя решить аналитически, однако для квадратичного программирования существует целый ряд весьма эффективных методов, например метод Вулфа, который мы рассматривали в гл. 9, или приведенный в предыдущем параграфе метод проектирования градиента (метод активного набора).

Линейный поиск при ограничениях. Решив подзадачу

квадратичного программирования (QP subproblem) на k-й итера-

−→

ции, мы получим ньютоновский шаг d k; далее возникает вопрос, как к нему относиться. Поскольку целевая функция в реальных условиях может быть весьма сложной, шаг на полную (единичную) длину может оказаться не самым удачным. Когда подобная

3В стандартной постановке квадратичного программирования требуется неотрицательность переменных, но это обстоятельство не является принципиально важным.

12.4.. Последовательное квадратичное программирование 191

проблема возникла в оптимизации без ограничений (см. с. 118),

предлагалось дополнить классический ньютоновский метод ли-

−→

нейным поиском, т. е. использовать d k только как направление,

а величину перемещения определить поиском минимума функции одномерного сечения в данном направлении. Аналогичный подход обычно используется и в последовательном квадратичном программировании, однако, как мы отмечали ранее (см. с. 166), при этом возникает дополнительная проблема ограничения дли-

протыкает область нелинейных ограничений, довольно сложно, для определения длины шага применяется описанная на с. 167 методика минимизации функции выигрыша (merit function).

Вычисление гессиана функции Лагранжа. Как следует из (12.27), для постановки подзадачи квадратичного программи-

рования необходимо знать гессиан функции Лагранжа в текущей

−→ −→

точке 2L(X k, Y k). Если целевая функция и ограничения представляют собой простые выражения, то гессиан вычисляется непосредственно, в этом случае излагаемый метод должен быть отнесен к методам второго порядка.

Если же вычисление гессиана затруднительно, то на помощь приходит идея, заложенная в квазиньютоновских алгоритмах безусловной оптимизации (см. с. 121). Гессиан оптимизируемой функции (в данном случае функции Лагранжа) не задается заранее, а восстанавливается по результатам предыдущих итераций. Это значит, что на подготовительном этапе гессиан аппроксимируется единичной матрицей, а на последующих итерациях происходит его обновление — update по формулам Дэвидона — Флетчера — Пауэлла (ДФП — DFP) либо Бройдена — Флетчера— Гольдфарба — Шанно (БФГШ — BFGS), причем, как показали многочисленные эксперименты, второй вариант предпочтительнее.

Обновление множителей Лагранжа. Каждая итерация метода (она называется главной итерацией, потому что подзада-

192 Глава 12. Многомерная оптимизация с ограничениями

ча квадратичного программирования, в свою очередь, решается

последовательностью собственных итераций) предполагает пере-

→−

вычисление не только координат текущей точки→−X k, но и соответствующих этой точке множителей Лагранжа Y k. Эти обновленные значения могут быть получены в процессе решения под-

задачи квадратичного программирования. Как метод Вулфа, так

→−

и метод активного набора наряду с оптимальным решением X

→−

дают соответствующие значения Y .

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

Замечание 2. Мы рассмотрели только общую идею подхода, в практической реализации метода необходимо учитывать многие детали и тонкости, влияющие на устойчивость и скорость сходимости. В итоге полные алгоритмы последовательного квадратичного программирования получаются довольно сложными, однако эта сложность окупается проверенной на практике эффективностью. Как утверждают разработчики промышленных пакетов оптимизации4, последовательное квадратичное программирование представляет собой state of the art (достигнутый к настоящему времени уровень знаний в науке или технике) в оптимизации с ограничениями.

П р и м е р. Пусть в предыдущем примере (см. с. 187) ограничение задано неравенством

f (x1, x2) = −x21 + (x2 − 2)2 → min, g(x1, x2) = 4x21 + x22 − 1 0.

4См., например, документацию по пакету Optimization Toolbox в системе MATLAB версии 2010 г. на сайте MathWorks Inc.

Разумеется, точка оптимума будет той же самой, однако теперь для ее нахождения потребуется применить в полном объеме метод последовательного квадратичного программирования.

Ниже в таблице приведены промежуточные результаты глав-

→−

ных итераций. Исходная точка X 0 = (1.5, 1.5)T , y0 = 0.5. В линейном поиске задействована функция выигрыша, включающая штрафное слагаемое

в которой штрафной параметр R = 1. Обновление гессиана функ-

ции Лагранжа проводилось по методике BFGS.

→−

Условный экстремум X = (0, 1)T найден за 5 итераций.

Сравнивая восстановленный гессиан функции Лагранжа с истинным значением

−

видим вполне удовлетворительное совпадение.

12.5. Метод линейной аппроксимации

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

194 Глава 12. Многомерная оптимизация с ограничениями

Общая идея

Пусть имеется задача выпуклого программирования в стандартном виде

→−

f (X ) = min,

→−

gi(X ) 0, i = 1, . . . , m,

→−

X 0.

Так как f и gi выпуклые, то область планов является выпуклой областью, каждая точка этой области может быть представлена в

s

yk = 1

k=1

yk 0, k = 1, . . . , s.

Таким образом, исходную нелинейную задачу аппрксимировали задачей линейного программирования относительно переменных y1, . . . , ys. Решая ее, получаем оптимальные значения yk и по

k=1

n

−→ f (X ) =

j=1

n

(12.30)

j=1

xj 0,

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

Принципиальное упрощение по сравнению с общим случаем состоит в том, что в задаче сепарабельного программирования

196 Глава 12. Многомерная оптимизация с ограничениями

каждую переменную xj линеаризованной задачи (12.29) можно аппроксимировать в отдельности по Sj точкам в области ее определения:

sj

xj = yjkxjk, k=1

где xjk — числа (координаты выбранных точек), а yjk — переменные. Используется двойная индексация: первый индекс — номер аппроксимируемой переменной, второй — номер точки.

C учетом этого линеаризованная задача будет иметь S1 + S2 + · · · + Sn переменных, m + n ограничений и запишется в виде

П р и м е р. Решим методом линеаризации задачу выпуклого программирования, которую мы исследовали аналитически (с. 56). Число переменных n = 2, число ограничений m = 3, условия на неотрицательность переменных записаны в явном виде:

→−

f (X ) = (x1 − 2)2 + (x2 − 2)2 → min,

−→

g1(X ) = x21 + (x22 − 4) 0,

−→

g2(X ) = −x1 + x2 0,

→−

g3(X ) = x2 − 1 0, x1, x2 0.

198 Глава 12. Многомерная оптимизация с ограничениями

Восстанавливая по ним оптимальные значения переменных исходной задачи, имеем

x1 = x11y11 + x12y12 + x13y13 = 1 · 0.333 + 2 · 0.6667 = 1, 6667,

x2 = x21y21 + x22y22 = 1 · 1 = 1,

f = 1.0718. Как видим, приближение получилось не слишком плохим, несмотря на то, что мы сделали очень грубую аппроксимацию нелинейных функций отрезками прямых с шагом x1 = = x2 = 1. Если величину шага уменьшить, результат получится более точным:

0.05 1.7319 1 1.0719

0.021.7320 1 1.0718

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

Замечание 2. Описанный метод с небольшой модификацией применим для решения н е в ы п у к л ы х задач сепарабельного программирования, правда, в этом случае он гарантирует нахождение только локального минимума. Если для некоторого индекса j хотя бы одна из функций fj, gij невыпукла, то для правильной ее аппроксимации кусочно-линейной зависимостью весовые коэффициенты yjk для

данного j должны не только удовлетворять обычным соотношениям

)

yjk 0, k yjk = 1, но, кроме того, их ненулевые значения допускаются только д л я с о с е д н и x индексов k. Для этого в ходе работы

симплексного алгоритма необходимо следить за тем, чтобы на очередной итерации в базис включался только вектор, соседствующий по индексу k с одним из векторов текущего базиса. Детали реализации см. в [23, с. 317].

12.6. Метод секущих плоскостей

Этот аппроксимационный метод — cutting plane method — был предложен Дж. Келли в 1960 г. и носит его имя [23, с. 331].

Линеаризация

Прежде чем излагать сам метод, заметим,

целевой функции

что любая задача минимизации нелинейной

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

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

f (x1, . . . , xn) → min,

gi(x1, . . . , xn) 0, i = 1, . . . , m, (12.31) xj 0, j = 1, . . . , n.

Приведение к виду с линейной целевой функцией достигается ценой небольшого увеличения размерности. Введем дополнительную n + 1-ю переменную, дополнительное m + 1-е ограничение и составим задачу:

f (x1, . . . , xn) − xn+1, i = m + 1.