Страница: 2/7
Рис. 1. Возможные направления спуска, 1—конус возможных направлений: 2 — конус возможных направлений спуска; 3 — линии уровня целевой функции; 4 — полупространство направлений спуска.
Построение возможных направлений спуска
Пусть задана допустимая точка х. Как показано в лемме , ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñ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 или РЗ равно нулю.
Линейный поиск
Только что было показано, как строить возможное направление спуска или убедиться, что текущая точка удовлетворяет условиям Куна—Таккера. Пусть теперь хk —текущая точка, а dk-возможное направление спуска. В качестве следующей точки xk+1 берется , где длина шага К& определяется из решения следующей задачи одномерной минимизации:
Минимизировать
при условиях
Предположим теперь, что АT=(А1T, А2T), а bT=(b1T, b2T), так что и . Тогда задачу одномерной минимизации можно упростить следующим образом. Во-первых, заметим, что Ехk=е и Еdk=0, так что ограничение излишне. Так как и для всех l³0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;
(1)
Алгоритм метода Зойтендейка (случай линейных ограничений)
Ниже приведен алгоритм метода Зойтендейка для минимизации дифференцируемой функции f при условии, что .
Начальный этап. Найти начальную допустимую точку х1, для которой . Положить k = 1 и перейти к основному этапу.
Реферат опубликован: 8/06/2009