Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

1.4.8.Другие методы минимизации функций

сограничениями

Квадратичное программирование. Задачей квадратичного программирования называется задача, в которой квадратичная функция минимизируется на многогранном множестве: найти

( Q – положительно определенная матрица) при ограничениях:

Ax ≤ G .

Такие задачи возникают в некоторых приложениях и, кроме того, часто возникают как вспомогательные при описании различных методов минимизации, в том числе метода линеаризации.

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

Метод Ньютона. Этот метод можно применять для задач с ограничениями; при этом направление поиска находится не явно, а получается в результате решения вспомогательной задачи. При этом формула итерационного процесса имеет стандартный вид:

xk +1 = xk + λk Sk ,

где вектор Sk = yk − xk и определяется из решения задачи минимизации на множестве X квадратичной функции

Ψk (x) =< f (xk ), x − xk > + 12 (x − xk )т Q(xk )(x − xk ) .

В последней формуле Q(xk ) – матрица Гессе.

Шаг λk может быть выбран различными способами, в

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

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

Метод покоординатного спуска. Описанный ранее метод покоординатного спуска не трудно модифицировать применительно

96

1.4.9.Способы определения начальной точки

Врассмотренных ранее методах минимизации требовалось в качестве начальной точки x0 выбрать некоторую допустимую

точку x0 X . Для X , таких, как, например, параллелепипед, шар, гиперплоскость, указать такую точку нетрудно. Однако нередко задача определения x0 является весьма непростой.

Например, если

придется решать систему неравенств, что представляет собой весьма серьезную задачу. Если ограничения qi (x) ≤ 0 линейны, то

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

Задачу нахождения точки x0 , принадлежащей множествам

(1.19) или (1.20), можно переформулировать в виде задачи минимизации.

В случае множества (1.19) введем функцию

m

F(x) = ∑qi2 (x), x E n ,

i=1

ав случае множества (3.19) – функцию

97

F(x) = ∑m (max{qi2 (x), 0}) p , x E n , p ≥1,

i=1

и рассмотрим задачу минимизации: найти min F(x), x E n .

Эта задача решается любым из методов безусловной минимизации.

Если множество X не пусто, то условие x X равносильно условию F(x0 ) = min F(x) = 0 = F * .

Если F * > 0 , то X – пустое множество.

Контрольные вопросы и задачи [60]

g1 (x) = −x1 +1 ≤ 0, g2 (x) = x1 + x2 − 2 ≤ 0 методом штрафных функций.

ограничении g1 (x) = x1 + x2 −1 = 0 методом проекции градиента.

98