Нелинейно програмиране

Нелинейното програмиране (НЛП) е раздел на математическото програмиране и изследването на операциите, който се занимава със задачи за оптимизация, при които целевата функция и/или поне едно от ограниченията са нелинейни функции от променливите на решението.

НЛП е обобщение на линейното програмиране и позволява моделирането на по-широк клас реални системи и процеси, при които зависимостите между променливите не са строго пропорционални (т.е. описват се с криви, а не с прави линии).

Предмет и предназначение

Нелинейното програмиране се използва за намиране на оптимални решения в ситуации, когато:

• Зависимостта на целевия показател (печалба, разходи, ефективност и др.) от управляваните параметри е нелинейна (например намаляваща възвращаемост от мащаба, квадратични разходи).
• Ограниченията върху ресурсите или технологичните процеси се описват с нелинейни зависимости (например химични реакции, физични закони, икономически зависимости).

Задачите на НЛП възникват в много области:

• Инженерно проектиране (оптимизация на конструкции и процеси).
• Икономика и финанси (оптимизация на портфейл с отчитане на риска, моделиране на пазара).
• Химична технология (оптимизация на режимите на реактори).
• Machine Learning (обучение на Neural Network, метод на опорните вектори).
• Управление на производствени процеси. Логистика (с отчитане на нелинейни разходи).

Математическа постановка на задачата за НЛП

Общата задача на нелинейното програмиране се формулира по следния начин:

Необходимо е да се намери набор от стойности на променливите на решението, който максимизира или минимизира нелинейната целева функция. При това стойностите на променливите трябва да удовлетворяват система от ограничения, които могат да бъдат изразени както под формата на неравенства (например „величина А трябва да бъде по-малка или равна на В"), така и под формата на равенства (например „величина С трябва точно да се равнява на D"). Важно е, че поне една от функциите, описващи целта или ограниченията, е нелинейна. Често се добавят условия за неотрицателност на променливите, т.е. изискване стойностите им да бъдат по-големи или равни на нула.

Множеството от всички набори стойности на променливите, удовлетворяващи ограниченията, образува областта на допустимите решения (ОДР).

Разлики от линейното програмиране

Нелинейното програмиране се различава съществено от линейното програмиране (ЛП):

• Нелинейност: Целевата функция или ограниченията (или и двете) съдържат нелинейни зависимости.
• Свойства на ОДР: Областта на допустимите решения при НЛП може да бъде невипъкла (за разлика от ЛП, при което ОДР винаги е изпъкнал многоъгълник).
• Свойства на оптимума: Оптималното решение при НЛП не се намира задължително във върха на ОДР — то може да лежи на границата или вътре в областта. При НЛП могат да съществуват локални оптимуми, които не са глобални.
• Сложност на решението: Задачите на НЛП, като правило, са значително по-трудни за решаване от задачите на ЛП. Не съществува единен универсален алгоритъм, аналогичен на симплекс метода, за всички задачи на НЛП.

Основни трудности и предизвикателства на НЛП

Решаването на задачи за нелинейно програмиране е свързано с редица трудности:

• Наличие на локални екстремуми: Повечето методи на НЛП гарантират намирането само на локален оптимум (решение, което е най-добро в определена околност). Намирането на глобален оптимум (най-доброто решение в цялата ОДР) е сложна задача, особено за невипъкли проблеми.
• Невипъклост: Ако задачата не е изпъкла (целевата функция или ОДР не са изпъкнали), може да съществуват множество локални оптимуми и стандартните градиентни методи могат да „заседнат" в един от тях.
• Изчислителна сложност: Алгоритмите за решаване на НЛП често изискват значително по-големи изчислителни ресурси в сравнение с ЛП.

Важни класове задачи на НЛП

Въпреки общата сложност, съществуват важни подкласове задачи на НЛП, за които са разработени ефективни методи за решаване:

• Изпъкнало програмиране: Задача за минимизиране на изпъкнала функция върху изпъкнало множество от допустими решения (или максимизиране на вдлъбната функция). Ключово свойство: всеки локален минимум е едновременно и глобален минимум. Това значително улеснява намирането на оптималното решение.
• Квадратично програмиране: Целевата функция е квадратична, а всички ограничения са линейни.
• Сепарабелно програмиране: Целевата функция и ограниченията могат да бъдат представени като суми от функции, всяка от които зависи само от една променлива.

Методи за решаване на задачи на НЛП

Методи за решаване на задачи на нелинейното програмиране (НЛП)

I. Методи за безусловна оптимизация (оптимизация без ограничения):

• Градиентни методи (метод на най-стръмното спускане, метод на спрегнатите градиенти);
• Метод на Нютон и квазиньютонови методи (например BFGS);
• Методи с използване на апроксимация на Хесиана.

II. Методи за условна оптимизация (оптимизация с ограничения):

• Методи на преобразуване:
  • Метод на наказателните функции (penalty methods);
  • Метод на бариерните функции (barrier methods).
• Методи за пряко търсене на посоки:
  • Метод на допустимите посоки.
• Методи, базирани на условия за оптималност:
  • Методи на Каруш-Кун-Тъкър (KKT-условия);
  • Метод на множителите на Лагранж.
• Итерационни методи:
  • Последователно квадратично програмиране (SQP);
  • Методи на вътрешните точки.

III. Методи за глобална оптимизация:

• Евристични и метаевристични методи:
  • Генетични алгоритми;
  • Симулирано охлаждане;
  • Търсене с табу (tabu search).
• Детерминирани методи:
  • Разклоняване и граници (branch and bound);
  • Алгоритми за глобална оптимизация за задачи със специална структура.

Литература

• Базара М., Шети К. Нелинейно програмиране. Теория и алгоритми. — М.: Мир, 1982.
• Фиако А., Мак-Кормик Г. Нелинейно програмиране. Методи на последователната безусловна минимизация. — М.: Мир, 1972.
• Химелблау Д. Приложно нелинейно програмиране. — М.: Мир, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Вижте също

• Изследване на операциите
• Оптимизация
• Линейно програмиране
• Изпъкнало програмиране
• Целева функция
• Ограничения
• Област на допустимите решения