Метод Зойтендейка (стр. 1 из 4)

ГК и ВО России

НГТУ

Кафедра АСУ

Реферат на тему:

Метод Зойтендейка

Факультет: АВТ

Группа: АС-513

Студент: Ефименко Д.В.

Преподаватель: Ренин С.В.

Новосибирск

1997

Содержание:

Введение2

Случай линейных ограничений 2

Геометрическаяинтерпретация возможного

направления спуска2

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

Задачи с нелинейными ограничениями-неравенствами 9

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

ограничений-неравенств)11

Учет нелинейных ограничений-равенств 14

Использование почти активных ограничений 15

Список литературы18

Введение

Я хочу описать Вам метод возможных направлений Зойтендейка. На каждой итерации метода строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.

Следующее определение вводит понятие возможного направления спуска.

ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации f(х) при условии, что хÍS, где f: Е_n-Е₁, а S—непустое множество из Е_n. Ненулевой вектор d называется возможным направлением в точке хÍS, если существует такое d>0, что х+lxÍS для всех lÍ(0,d). Вектор d называется возможным направлением спуска в точке xÍS, если существует такое d>0, что f(х+ld)<f(x) и х+ldÍS для всех lÍ(0, 6).

Случай линейных ограничений

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

минимизировать f(х)

при условиях Ах£b,

Ех=е.

Здесь А—матрица порядка m´ n,Е—матрица порядка l ´ n, b есть m-мерный вектор, а е есть l-мерный вектор. В следующей лемме приводятся соответствующие характеристики допустимойобласти и формулируются достаточные условия для существования возможного направления спуска. В частности, векторdявляется возможным направлением спуска, если A₁d£0, Еd=0 и Ñf(х)^Td<0.

ЛЕММА. Рассмотрим задачу минимизации f(х) при условиях Ах£b и Ех=е. Пусть х—допустимая точка, и предположим, что А₁x=b₁ и А₂x<b₂, где А^T=(А₁^T, А₂^T), а b^T=(b₁^T, b₂^T). Тогда ненулевой вектор и является возможным направлением в точке х в том и только в том случае, если A₁d£0и Еd=0. Если, кроме того, Ñf(х)^Td<0, то d является возможным направлением спуска.

Геометрическаяинтерпретация возможного направления спуска

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

ПРИМЕР

Минимизировать при условиях

(x₁-6)²+(x₂-2)²

-x₁+2x₂£4

3x₁+2x₂£12

-x₁£0

-x₂£0

Возьмем х=(2, 3)^T и заметим, что первые два ограничении являются активными в этой точке. В частности, матрица А₁ из леммы равна А₁=[^-1₃ ²₂]. Следовательно, вектор dявляется возможным направлением тогда и только тогда, когда А₁d£0, т.е. в том и только в том случае, если

-d₁+2d₂£0,

3d₁+2d₂£0.

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

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

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

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

Пусть задана допустимая точка х. Как показано в лемме , ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñf(х)^Td. Заметим, однако, что если существует вектор d, такой, что Ñf(х)^Td <0, А₁d£0, Еd= 0, то оптимальное значение целевой функции в сформулированной задаче равно —¥, так как ограничениям этой задачи удовлетворяет любой вектор ld, где 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 или РЗ):