Седловая точка функции Лагранжа
Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция
Точка 
называется седловой точкой функции Лагранжа, если для всех 
и 
Теорема Куна-Таккера
Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция
Точка называется седловой точкой функции Лагранжа, если для всех и
Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.
Для задачи выпуклого программирования (множество допустимых решений которой обладает свойством регулярности, X0 тогда и только тогда является оптимальным решением, когда существует такой вектор 
, что — седловая точка функции Лагранжа.
Основная идея градиентных методов решения ЗНЛП
Две группы: 1. барьерные 2. штрафные
В общем случае под градиентными методами понимают методы, в которых направления движения к точке оптимума функции совпадают с направлением градиента этой функции. Используя градиентные методы, можно найти решение любой ЗНЛП. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X(k) осуществляется последовательный переход к некоторым точкам до тех пор, пока не выявляется приемлемое решение исходной задачи.
|
|
|
Метод Франка –Вульфа
Итак, процесс нахождения решения задачи методом Франка-Вулфа включает следующие этапы:
1. Определяют исходные допустимые решения задачи.
2. Находят градиент функции в точке допустимого решения.
3. Строят функцию и находят ее максимальное значение при условиях
4. Определяют шаг вычислений.
5. По формулам находят компоненты нового допустимого решения.
6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.
Метод штрафных функций
процесс нахождения решения задачи выпуклого программирования методом штрафных функций включает следующие этапы:
1. Определяют исходное допустимое решение.
2. Выбирают шаг вычислений.
3. Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР задачи.
4. По формуле 
находят координаты точки, определяющей возможное новое решение задачи.
|
|
|
5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.
6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.
Метод наискорейшего спуска
1. выбирают любую точку X0, удовлетворяющую области решений (в дальнейшем эта точка Xk)
2. Находят частные производные, а затем градиент функции в точке.
3. определяют шаг лямбда
4.по формулам 1. Xk+1= Xk+”лямбда”*1 и 2. Xk+1= Xk+”лямбда”*”обратная дельта’Z(Xk) находят точку Xk+1
5. проверяют, находиться ли точка Xk+1 внутри области решений.
6. проверяют, точку Xk+1 на оптимальность. Если точка не является оптимальным решением повторяют пункты 2-6
Дата добавления: 2018-05-12; просмотров: 1613; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!