ГК и ВО России НГТУ Кафедра АСУ Реферат на тему Метод Зойтендейка Факультет АВТ Группа АС-513 Студент Ефименко Д.В. Преподаватель Ренин С.В. Новосибирск 1997 Содержание Введение 2 Случай линейных ограничений 2 Геометрическая интерпретация возможного направления спуска 2 Построение возможных направлений спуска 3 Задачи с нелинейными ограничениями-неравенствами 9 Алгоритм метода Зойтендейка случай нелинейных ограничений-неравенств 11 Учет нелинейных ограничений-равенств 14 Использование почти активных ограничений 15 Список литературы 18 Введение Я хочу описать Вам метод возможных направлений Зойтендейка. На каждой итерации метода строится возможное направление спуска и затем проводится оптимизация вдоль этого направления.
Следующее определение вводит понятие возможного направления спуска. ОПРЕДЕЛЕНИЕ. Рассмотрим задачу минимизации fх при условии, что хНS, где f ЕnаЕ1, а S непустое множество из Еn. Ненулевой вектор d называется возможным направлением в точке хНS, если существует такое d 0, что хlxНS для всех lН0,d. Вектор d называется возможным направлением спуска в точке xНS, если существует такое d 0, что fхld fx и хldНS для всех lН0, 6. Случай линейных ограничений Вначале рассмотрим случай, когда допустимая область S определена системой линейных ограничений, так что рассматриваемая задача имеет вид минимизировать fх при условиях Ахb, Ехе. Здесь А матрица порядка m n, Е матрица порядка l n, b есть m-мерный вектор, а е есть l-мерный вектор.
В следующей лемме приводятся соответствующие характеристики допустимой области и формулируются достаточные условия для существования возможного направления спуска.
В частности, вектор d является возможным направлением спуска, если A1d0, Еd0 и СfхTd 0. ЛЕММА. Рассмотрим задачу минимизации fх при условиях Ахb и Ехе. Пусть х допустимая точка, и предположим, что А1xb1 и А2x b2, где АTА1T, А2T, а bTb1T, b2T. Тогда ненулевой вектор и является возможным направлением в точке х в том и только в том случае, если A1d0 и Еd0. Если, кроме того, СfхTd 0, то d является возможным направлением спуска.
Геометрическая интерпретация возможного направления спуска. в том и только в том случае, если -d12d20, 3d12d20. Заметим, что если сдвинуться на небольшое расстояние от точки х вдоль ... Таким образом, совокупность направлений спуска определяется открытым п... Пересечение конуса возможных направлений с этим полупространством зада...
Тогда задачу одномерной минимизации можно упростить следующим образом. Шаг 1. Линейный поиск. Более того, точка является точкой Куна Таккера. Поиск решения методом Зойтендейка случай линейных ограничений.
Доказательство. Пусть вектор и удовлетворяет неравенствам и при. В силу дифференцируемости функций gi при имеем где при. Следовательно, вектор и является возможным направлением спуска. Точка х является точкой Ф. Джона для исходной задачи тогда и только тогда, когда оптимальное знач...
Джона. Взять в качестве оптимальное решение следующей задачи одномерной миним... Значение l получается из решения следующей задачи одномерной минимизац... Оптимальным решением этой задачи является l3 0.09245, так что 0.6479, ... Итерация 4 Поиск, направления. Для точки х4 0.6479, 0.8397T имеем 3.08...
Для иллюстрации обратимся к рис. 8, который отвечает единственному ограничению-равенству. Для заданной ... Рис. Рис. Если заданная точка близка к границе, определяемой одним из ограничени...
Список литературы 1. М. Базара, К. Шеттл Нелинейное программирование. Теория и алгоритмы М. Мир 1982 2. Д. Химмельблау Прикладное нелинейное программирование М. Мир 1975.