ГК и ВО России
НГТУ
Кафедра АСУ
Реферат на тему:
Факультет: АВТ
Группа: АС-513
Студент: Ефименко Д.В.
Преподаватель: Ренин С.В.
1997
Содержание:
Геометрическая интерпретация возможного
направления спуска 2
Я хочу описать Вам метод возможных направлений Зойтендейка. На каждой итерации метода строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.
Следующее определение вводит понятие возможного направления спуска.
ОПРЕДЕЛЕНИЕ.
Рассмотрим задачу минимизации f(х)
при условии, что хНS,
где f:
ЕnаЕ1, а S—непустое множество из
Вначале рассмотрим случай, когда допустимая область S определена системой линейных ограничений, так что рассматриваемая задача имеет вид
мин
Ех
Здесь А—матрица
порядка m ´ n,
Е—матрица порядка l ´ n, b есть m-мерный вектор, а е есть
ЛЕММА. Рассмотрим
задачу минимизации f(х)
при условиях Ах£b и Ех=е. Пусть
Геометрическая интерпретация возможного направления спуска
Проиллюстрируем теперь геометрически на примере множество возможных направлений спуска.
ПРИМЕР
Минимизировать при условиях
(x1-6)2+(x2-2)2
-x1+2x2£4
3x1+2x2£12
-x1£0
-x2£0
Возьмем
3d1+2d2£0.
На рис. 1, где начало координат перенесено в точку х, изображена совокупность этих направлений, образующая конус возможных направлений. Заметим, что если сдвинуться на небольшое расстояние от точки х вдоль любого вектора d, удовлетворяющего двум приведенным выше неравенствам, то останемся в допустимой области.
Если вектор d
удовлетворяет неравенству 0>Сf(х)Td=-8d1+2d2, то он является
направлением спуска. Таким образом, совокупность направлений спуска
определяется открытым
полупространством {(d1,d2}:
-8d1+2d2<0
Рис. 1. Возможные
направления спуска, 1—конус возможных направлений: 2 — конус возможных направ
Пусть задана
допустимая точка х. Как показано в лемме , ненулевой
вектор и является возможным направлением спуска.
Естественный подход к построению такого направления заключается в минимизации Сf(х)Td.
Заметим, однако, что если существует вектор d, такой, что
возможного
направления спуска, В каждой из этих задач используются различные формы
нормировки.
Задачи Р1 и
ЛЕММА. Рассмотр
Доказательство.
Вектор х является точкой Куна—Таккера тогда и только тогда, когда существуют
векторы u³0 и v, такие, что . По следствию 2 из теоремы эта
система разрешима в том и только в том случае, если
система не имеет решений,
т. е. тогда и только тогда, когда оптимальное
значение в задачаx Р1, Р2 или РЗ равн
Только что было
показано, как строить возможное направление спуска или убедиться, что текущая
точка удовлетворяет условиям Куна—Таккера. Пусть
теперь хk —текущая точка, а
Минимизировать
при условиях
Предположим теперь, что АT=(А1T, А2T), а bT=(b1T, b2T), так что и . Тогда задачу одномерной минимизации можно упростить следующим образом. Во-первых, заметим, что Ехk=е и Еdk=0, так что ограничение излишне. Так как и для всех l³0. Таким образом, рассматриваемая задача приводится к следующей задаче линейного поиска;
(1)
Алгоритм метода
Ниже приведен
алгоритм метода Зойтендейка для минимизации дифференцируемой функц
Начальный этап. Найти начальную допустимую точку х1, для которой . Положить k = 1 и перейти к основному этапу.
Основной этап. Шаг 1. Пусть задан хk. Предположим, что АT=(А1T, А2T), а bT=(b1T, b2T), так что . Взять в качестве dk оптимальное решение следующей задачи (заметим, что вместо этой задачи можно использовать Р2 или РЗ):
Если , то остановиться; хk—точка Куна—Таккера, В противном случае перейти к шагу 2.
Заметим, что
Итерация 1
Эту задачу можно решить симплекс методом для решения задач линейного программирования. На рисунке 2 показана допустимая область этой задачи.
Линейный поиск.
Теперь, двигаясь из точки (0, 0) вдоль направления (1, 1), нужно найти точку, в
которой значение целевой функции минимально.
Любая точка может быть записана в виде ,
а целевая функция в этой точке принимает вид
Следовательно, если —новая точка, то значение получается из решения следующей задачи одномерной минимизации:
минимизировать —10+2
при условии 0£ £ .
Очевидно, что решением является , так что
Итерация 2
Поиск, направления. В точке имеем .
Рис 3.
Кроме того,
множество активных ограничений
в точке х2 равно l={2}, так
минимизировать
при условии
Читатель может
проверить на рис. 3, что оптимальным решением этой задачи линейного
программирования является точка , а
соответствующее значение целевой функции равно
Линейный поиск.
При начальной точке х2 любая точка в направлени
Макс
Таким образом, в
качестве ^ берется оптимальное решение следующ
минимизировать
при условии
Оптимальным
решением этой задачи является , так
Рис 4.
Итерация 3
Поиск напра
Можно легко
проверить по рис. 4. что действительно является решением этой задачи
линейного программирования. Соответствующее значение целевой функции равно
нулю, и процедура заканчивается. Более того, точка является точкой Куна—Такк
В этой конкретной задаче функция f выпукла, и по теореме 4.3.7 точка х является оптимальным решением.
Таблица 1
Рис. 5. По
В табл. 1 приведены результаты вычислений для рассмотренной задачи. На рис. 10.5 изображен процесс поиска решения в соответствии с описанным алгоритмом.
Теперь рассмотрим задачу, в которой допустимая область задается системой ограничений-неравенств не обязательно линейных:
минимизировать f(х)
при условиях gi (х)£0, i=1, ...,m.
В теореме формулируются достаточные условия, при которых вектор d является возможным направлением спуска.
Рис. 6. Совокупность возможных направлений спуска в задаче с нелинейными ограничениями. 1— 1-е ограничение; 2—3-е ограничение; 3—4-е ограничение; 4— 2-е ограничение; 5— возможные направления спуска; 6— линии уровня целевой функции.
Доказательство. Пусть вектор и удовлетворяет
неравенствам и при . Для выполняются неравенства , и так
как gi непрерывны в точке
где при . Так как , то при достаточно малых . Следовательно, при i = 1, .
. .,m, т.е. точка допустимая для достаточно малых положительных
значений . Аналогично из следует, что для достаточно малых
> 0
имеем . Следовательно, вектор
На рис. 6
показана совокупность возможных направлений спуска в точке х. Вектор
Пусть (z, d)—оптимальное
решение этой задачи линейного программирования. Если
Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное значение целевой функции задачи поиска направления равно нулю.
Точка
Это и есть условие Ф. Джона.
Алгоритм метода
Начальный этап.
Выбрать начальную точку х1, для которой gi(xi)£0
при i= 1,
Основной этап. Шаг 1. Положить и решить следующую задачу:
Пусть
где
Решим э
Итерация 1
Можно легко проверить, используя симплекс-метод, что оптимальным решением этой задачи является вектор
Л
минимизировать 6l2—2.5l—3.375
пр
Оптимальное значение равно l1= 0.2083. Следовательно, х2 = (x1 +l1d1) -(0.2083,0.5417)T.
Итерация 2
Поиск
направления. В точке x2=
(0.2083, 0.5417)T имеем
минимизировать z
при условиях —4.25d1—4.25d2—z£0,
Оптимальным решением является вектор d2=(1, 1)T, а z2 = -8.50.
Линейный поиск.
Можно легко проверить, что максимальное l, при котором точка x2+ld2 допустима, равно lmax ==
0.3472. При этом активным становится ограничение . Значение l2
получается минимизацией при условии и, очевидно, равно l2 = 0.3472, так что хз
= х2 +l2d2
Итерация 3
Оптимальным решением является вектор .
Ли
Итерация 4
Поиск
Оптимальным
решением этой задачи является вектор d4 = (-0.5171, 1.0000
Линейный поиск.
Максимальное значение К, для которого точка х4 +ld4 допустима, равно lmах
В табл. 2
приведены результаты вычислений на первых четырех итерациях метода
Таблица 2
Метод
возможных направлений может быть модифицирован на случай, когда имеются
нелинейные ограничения-равенства. Для иллюстрации обратимся к р
Рис.
8. Нелинейные
ограничения-равенства. 1—касательное
Чтобы быть более точным, рассмотрим следующую задачу:
минимизировать f(х)
при условиях gi(х)£0, i= 1
Рис. 9. Использование почти активных ограничений. 1 — оптимальное решение; 2— линии уровня целевой функции; 3—1-е ограничение; 4— 2-е ограничение.
Использование почти активных ограничений
Напомним задачу
определения направления как для случая л
определения
направления даст вектор и, который обеспечивает
большие возможности для движения в рамках допустимой области. Таким образом,
это наводит на мысль
о том, что в качестве множества I следует брать совокупность индексов почти
активных ограничений. Точнее, вместо множества {i:
gi(х)
следует из того, что соответствующее алгоритмическое отображение незамкнуто. При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического отображения и, следовательно, сходимость общего алгоритма.
Список литературы:
1. М. Базара, К. Шеттл «Нелинейное программирование. Теория и алгоритмы» М.: Мир 1982
2. Д. Химмельблау «Прикладное нелинейное программирование» М.: Мир 1975
|
|