ГК и ВО России
НГТУ
Кафедра АСУ
Реферат на тему:
Метод Зойтендейка
Факультет: АВТ
Группа: АС-513
Студент: Ефименко Д.В.
Преподаватель: Ренин С.В.
Новосибирск
1997
Содержание:
Введение 2
Случай линейных ограничений 2
Геометрическая интерпретация возможного
направления спуска 2
Построение возможных направлений спуска 3
Задачи с нелинейными ограничениями-неравенствами 9
Алгоритм метода Зойтендейка (случай нелинейных
ограничений-неравенств) 11
Учет нелинейных ограничений-равенств 14
Использование почти активных ограничений 15
Список литературы 18
Введение
Я хочу описать Вам метод возможных направлений Зойтендейка. На каждой
итерации метода строится возможное направление спуска и затем проводится
оптимизация вдоль этого направления.
Следующее определение вводит понятие возможного направления спуска.
ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации f(х) при условии, что х(S,
где f: Еn(Е1, а S—непустое множество из Еn. Ненулевой вектор d
называется возможным направлением в точке х(S, если существует такое
(>0, что х+(x(S для всех (((0,(). Вектор d называется возможным
направлением спуска в точке x(S, если существует такое (>0, что
f(х+(d)
является направлением спуска. Таким образом, совокупность направлений
спуска определяется открытым полупространством {(d1,d2}: -8d1+2d2 0 имеем . Следовательно, вектор и
является возможным направлением спуска.
На рис. 6 показана совокупность возможных направлений спуска в точке х.
Вектор d, удовлетворяющий равенству , является касательным к
множеству в точке х. Поскольку функции gi нелинейны, движение вдоль
такого вектора d может привести в недопустимую точку, что вынуждает нас
требовать выполнения строгого неравенства .
Чтобы найти вектор d, удовлетворяющий неравенствам для ,
естественно минимизировать максимум из и для . Обозначим этот
максимум через z. Вводя нормирующие ограничения Для каждого j,
получим следующую задачу для нахождения направления.
Пусть (z, d)—оптимальное решение этой задачи линейного программирования.
Если z0—достаточно малое число. Метод возможных направлений
не обязательно сходится к точке Ф. Джона. Это
следует из того, что соответствующее алгоритмическое отображение
незамкнуто. При более формальном использовании введённого здесь понятия
почти активного ограничения можно установить замкнутость
алгоритмического отображения и, следовательно, сходимость общего
алгоритма.
Список литературы:
М. Базара, К. Шеттл «Нелинейное программирование. Теория и алгоритмы»
М.: Мир 1982
Д. Химмельблау «Прикладное нелинейное программирование» М.: Мир 1975
Метод Зойтендейка
PAGE
PAGE 5
Нашли опечатку? Выделите и нажмите CTRL+Enter
