56. Седловая точка функции Лагранжа

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

57. Теорема Куна-Таккера

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.

Для задачи выпуклого программирования (множество допустимых решений которой обладает свойством регулярности, X₀ тогда и только тогда является оптимальным решением, когда существует такой вектор , что — седловая точка функции Лагранжа.

58.Основная идея градиентных методов решения знлп

Две группы: 1. барьерные 2. штрафные

В общем случае под градиентными методами понимают методы, в которых направления движения к точке оптимума функции совпадают с направлением градиента этой функции. Используя градиентные методы, можно найти решение любой ЗНЛП. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X^(k) осуществляется последовательный переход к некоторым точкам до тех пор, пока не выявляется приемлемое решение исходной задачи.

59.Метод Франка –Вульфа

Итак, процесс нахождения решения задачи методом Франка-Вулфа включает следующие этапы:

1. Определяют исходные допустимые решения задачи.

2. Находят градиент функции в точке допустимого решения.

3. Строят функцию и находят ее максимальное значение при условиях

4. Определяют шаг вычислений.

5. По формулам находят компоненты нового допустимого решения.

6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

60. Метод штрафных функций

процесс нахождения решения задачи выпуклого программирования методом штрафных функций включает следующие этапы:

1. Определяют исходное допустимое решение.

2. Выбирают шаг вычислений.

3. Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР задачи.

4. По формуле находят координаты точки, определяющей возможное новое решение задачи.

5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.

61. Метод наискорейшего спуска

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