Построение возможных направлений спуска - Метод Зойтендейка - Физика - Каталог статей - AlexLat
Главная » Статьи » Физика » Метод Зойтендейка

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

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





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

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

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

Доказательство. Вектор х является точкой КунаТаккера тогда и только тогда, когда существуют векторы u³0 и v, такие, что                        . По следствию 2 из теоремы эта система разрешима в том и только в том случае, если система                                            не имеет решений, т. е. тогда и только тогда, когда оптимальное значение в задачаx Р1, Р2 или РЗ равно нулю.
Категория: Метод Зойтендейка | Добавил: alexlat (26.04.2012)
Просмотров: 230 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]