Реферат: Метод Зойтендейка

Если вектор d удовлетворяет неравенству 0> Ñf(х)^T d=-8d₁ +2d₂ , то он является направлением спуска. Таким образом, совокупность направлений спуска определяется откры тым полупространством {( d₁ ,d₂ }: -8d₁ +2d₂ < 0} . Пересече­ние конуса возможных направлени й с эти м полупространством задает множество всех возможных направлений спуска.

Рис. 1. Возможные направления спуска, 1 —конус возможных направле­ний: 2 — конус возможных направл ени й спуска; 3 — линии уровня целевой функции; 4 — полупространство направлений спуска.

Построение возможных направлений спуска

Пусть задана допустимая точка х. Как показано в лемме , ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñf(х)^T d. Заметим, однако, что если существует вектор d, такой, что Ñ f(х)^T d <0, А ₁ d£0, Еd= 0, то оптимальное значение целевой функции в сформу­лированной задаче равно — ¥, так как ограничениям этой за­дачи удовлетворяет любой вектор l d, где l—сколь угодно большое число. Таким образом, в задачу должно быть включено условие, которое ограничивало бы вектор и или оптимальное значение целевой функции. Такое ограничени е обычно называют нормирующим. Ниже приведены три задачи построения

??????????? ??????????? ??????, ? ?????? ?? ???? ????? ???????????? ????????? ????? ??????????.

Задачи Р1 и РЗ являют ся задачами линейного программиро­вания и, следовательно, могут быть решены симплекс-методом. Задача Р2 содержит квадратичное ограничение, но может быть рассмотрена в несколько упрощенном виде. Так как d = 0 является допустимой точкой в каждой из приведен­ных выше задач и так как значение целевой функции в этой точке равно нулю, то ее оптимальное значение в задачах Р1, Р2 и РЗ не может быть положительным. Если минимальное значе­ние целевой функции в задачах Р1, Р2 или РЗ отрицательно, то по лемме построено возможное направление спуска. С другой стороны, если минимальное значение целевой функции равно нулю, то, как показано ниже, х является точкой Куна — Таккера.

ЛЕММА. Рассмотри м задачу минимизации f (х) при условиях Ах £b и Ех = е. Пусть х — допустимая точка, для которой А₁ x=b и А₂ x<b₂ , где А ^T =(А₁ ^T , А₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ). Тогда х является точкой Куна—Таккера в том и только в том случае, если оптимальное значение целевой функции в задачах Р1, Р2 или РЗ равно нулю.

Доказательство. Вектор х является точкой Куна—Таккера тогда и только тогда, когда существуют векторы u³0 и v, такие, что. По следствию 2 из теоремы эта система разреши ма в том и только в том случае, если система не имеет решени й, т. е. тогда и только тогда, когда оптимальное значение в задачаx Р1, Р2 или РЗ равно нулю.

Ли нейный пои ск

Только что было показано, как строить возможное направление спуска или убедиться, что текущая точка удовлетворяет условиям Куна—Таккера. Пусть теперь х _k —текущая точка, а d_k -возможное направление спуска. В качестве следующей точки x_k+1 берется, где длина шага К& определяется из реше­ния следующей задачи одноме рной мини мизации:

Минимизировать

при условиях

Предположим теперь, что А ^T =(А₁ ^T , А₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ), такчто и .Тогда задачу одномерной мини­ мизации можно упростить следующим образом. Во-первых, за­метим, что Ех_k =е и Еd_k =0, так что ограничение излишне. Так как и для всех l³0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;

(1)

Алгоритм метода Зойтендейка (случай линейных ограничений)

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

Начальный этап. Найти начальную допустимую точку х ₁ , для которой . Положить k= 1 и перейти к основ­ному этапу.

Основной этап. Шаг 1. Пусть задан х _k . Предположим, что А^T =(А₁ ^T , А₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ),так что . Взять в качестве d_k оптимальное решение следующей задачи(заметим, что вместо этой задачи можно использовать Р2 или РЗ):

Если , то остановиться; х _k —точка Куна—Таккера, В противном случае перейти к шагу 2.

??? 2. ???????? ?????? ???????????? ??????? е ??-., ?????? ?????? ????????? ??????:
??? ???????????? ? ???????????? ? (1). ????????, ?????????? ????? ????????? ???????? ???????????? ? ? ?????????????? ?₁ ? А ₂ . ???????? k ?? k+ 1 ? ??????? ? ???? 1.

Заметим, что . Решим задачу методом Зойтендейка, взяв в качестве начальной точки . Каждая итерация алгоритма содержит решение подзадачи, определенной в описании шага 1, для нахождения направления, а затем линейный поиск вдоль этого направления.

Итерация 1

????? ?????в ?????. ? ????? ????? . ????? ????, ? ????? x₁ ????????? ???????? ??????? ??????????? ????????????????? ??????????, ??? ??? l = {3,4}. ?????? ??? ?????????? ??????????? ????? ???

Рис. 2

Эту задачу можно решить симплекс методом для решения задач линейного программирования. На рисунке 2 показана допустимая область этой задачи.

Линейный поиск. Теперь, двигаясь из точки (0, 0) вдоль направления (1, 1), нужно найти точку, в которой значение це­ левой функции ми ни мально. Любая точка может быть записана в виде , а целевая функция в этой точке при нимает вид . Максимальное значение коэффициента l, для ко­торого точка допустима, в ычисляется по формулам и равно

Следовательно, если —новая точка, то значе ние по­лучается из решения следующей задачи одномерной миними­зации:

минимизировать —10+2

при условии 0 ££ .

Очевидно, что решением является , так что

Итерация 2