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

Общая характеристика методов решения задач

Когда целевая функция и ограничения нелинейны, и для поиска точки экстремума нельзя или очень сложно использовать аналитические методы решения, тогда для решения задач оптимизации применяются методы нелинейного программирования. Как правило, при решении задач методом нелинейного программирования используются численные методы с применением ЭВМ. В основном методы нелинейного программирования могут быть охарактеризованы как многошаговые методы или методы последующего улучшения исходного решения. В этих задачах обычно заранее нельзя сказать, какое число шагов гарантирует нахождение оптимального значения с заданной степенью точности. Кроме того, в задачах нелинейного программирования выбор величины шага представляет серьезную проблему, от успешного решения которой во многом зависит эффективность применения того или иного метода. Разнообразие методов решения задач нелинейного программирования как раз и объясняется стремлением найти оптимальное решение за наименьшее число шагов.

Большинство методов нелинейного программирования используют идею движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния U^kосуществляется переход в следующее состояние U^k+1 изменением вектора U^k на величину DU^k, называемую шагом, т.е.

U^k+1= U^k + DU^k(7.15)

В ряде методов шаг, т.е. его величина и направление определяется как некоторая функция состояния U^k

DU^k=f(U^k)(7.16)

Следовательно, согласно (7.15) новое состояние U^k,получаемое в результате выполнения шага (7.16) может рассматриваться как функция исходного состояния U^k

U^k+1= U^k+f(U^k)(7.17)

В некоторых методах DU^k обусловлен не только состоянием U^k, но и рядом предшествующих состояний

DU^k=f(U^k), U^k-1…, U^k-2(7.18)

U^k+1= U^k+f(U^k), U^k-1..., U^k-2 (7.19)

Естественно, что алгоритмы поиска типа (7.19) являются более общими и принципиально могут обеспечить более высокую сходимость к оптимуму, т.к. используют больший объем информации о характере поведения оптимальной функции.

В настоящее время для решения подобных задач разработано значительное число методов, однако нельзя отдать предпочтение какому-либо одному. Выбор метода определяется сложностью объекта и решаемой задачей оптимизации.

Методы нелинейного программирования в соответствии со способом определения шага поиска R(U) можно отнести к одному из 3-х типов:

1. Безградиентные методы
2. Градиентные методы
3. Методы случайного поиска.

Все эти методы можно назвать прямыми итеративными методами.