Решение Задач Нелинейного Программирования

Нелинейное программирование занимается оптимизацией моделей задач, в которых либо ограничения qi(x) либо целевая функция Z(X) либо то и другое нелинейны.
Найти max(min)=Z=z(X)
в области
где R – отношение порядка (=, ≥, ≤), Ω– область допустимых решений; bi– константа, ;
X=(x1, …, xn)={xj}, j=1..n – план или вектор управления.
Для выяснения трудностей решения задач данного класса, порождаемых нелинейностью, сопоставим задачи линейного и нелинейного программирования. Можно указать три характерные особенности для каждого класса.

Задачи линейного программирования
1. Область Ω допустимых планов – выпуклое множество с конечным числом угловых (крайних) точек.	1. Множество Ω допустимых планов может быть невыпуклым, несвязным, иметь бесконечное число крайних точек.
2. Экстремальное значение линейная целевая функция z(X) достигает в одной из крайних точек (на границе области Ω допустимых решений).	2. Экстремум может достигаться не только на границе, но и внутри области Ω допустимых решений.
3. Экстремальное значение z(X) целевой функции является и глобальным значением.	3. Целевая функция z(X) в области Ω может иметь несколько локальных экстремумов.

На рисунке приводится классификация задач и методов нелинейного программирования. Рисунок - Классификация задач и методов нелинейного программирования

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

1. Прямые методы - методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек – решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
   Недостаток: трудно получить свойство глобальной сходимости.
   Задачи с ограничениями в виде равенств.
   Метод замены переменных (МЗП)
2. Двойственные методы - методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
   Недостаток: не дают решения исходной задачи в ходе решения – оно реализуемо лишь в конце итерационного процесса.
   • Метод множителей Лагранжа (ММЛ)
   • Методы штрафов
   • Метод множителей
   • Методы линеаризации для задач условной оптимизации
     Алгоритм Франка–Вульфа
     Метод допустимых направлений Зойтендейка
   • Метод условного градиента
   • Метод проекции градиента
   • Сепарабельное программирование.
   • Квадратичное программирование

Функция двух переменных

1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).

Методы прямого поиска

1. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x1 – x13 + 3x22 + 4x2. x0=(0.78;1)

• Двойственная Задача Линейного Программирования
• Задачи Линейного Программирования
• Постановка Задачи Линейного Программирования
• Решение Задачи Линейного Программирования