Реферат: Метод Зойтендейка

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

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

Группа: АС-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.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--