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

ГК и ВО России

НГТУ

Кафедра АСУ

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

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

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

Группа: АС-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(х)^T d< 0.

ЛЕММА. Рассмотрим задачу минимизации f (х) при условиях Ах £b и Ех= е. Пусть х— допустимая точка, и предположим, что А₁ x=b₁ и А₂ x<b₂ , где А^T =(А₁ ^T , А ₂ ^T ), а b^T =(b₁ ^T , b₂ ^T ). Тогда ненулевой вектор и является возможным направлением в точке х в том и только в том случае, если A₁ d£0и Еd =0. Если, кроме того, Ñ f(х)^T d<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(х)^T d=-8d₁ +2d₂ , то он является направлением спуска. Таким образом, совокупность направлений спуска определяется откры тым полупространством {( d₁ ,d₂ }: -8d₁ +2d₂ < 0} . Пересече­ние конуса возможных направлени й с эти м полупространством задает множество всех возможных направлений спуска.

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

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

Пусть задана допустимая точка х. Как показано в лемме , ненулевой вектор и является возможным направлением спуска. Естественный подход к построению такого направления заключается в минимизации Ñf(х)^T d. Заметим, однако, что если существует вектор d, такой, что Ñ f(х)^T d <0, А ₁

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать