Методы решения нелинейных задач МП. Содержательное истолкование градиентных методов
Методы нелинейного программирования могут быть охарактеризованы как многошаговые методы или методы последующего улучшения исходного решения. Нельзя сказать, какое число шагов гарантирует нахождение оптимального значения с заданной степенью точности. Выбор величины шага представляет серьезную проблему, от успешного решения которой во многом зависит эффективность применения того или иного метода. Разнообразие методов решения задач нелинейного программирования объясняется стремлением найти оптимальное решение за наименьшее число шагов.
Большинство методов нелинейного программирования используют идею движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния Uk осуществляется переход в следующее состояние Uk+1 изменением вектора Ukна величину DUk, называемую шагом , т.е. Uk+1=Uk+DUk
Шаг ,т.е. его величина и направление определяется как некоторая функция состояния Uk: DUk=f(Uk)
Функция исходного состояния Uk: Uk+1=Uk+f(Uk)
DUK=f(Uk) ,Uk-1...,Uk-2 Uk+1=Uk+f(Uk),Uk-1...,Uk-2
Выбор метода определяется сложностью объекта и решаемой задачей оптимизации.
Градиентные методы, в основе которых лежит свойство градиента функции в точке (вектора частных производных, вычисленного в точке) как указателя направления наибольшего роста функции в окрестности точки. В основу градиентных методов поиска оптимума положены вычисления и анализ производных целевой функции R(U). Если аналитический вид R(U) известен, то вычисление производных dR/dUj чаще всего не составляет особого труда. В противном случае единственным способом определения производных являютсячисленные методы.
где DUj -величина приращения независимой переменной Uj. Точность приближения зависит от величины приращения DUj.
Процесс поискаоптимума в методе градиента также осуществляется в два этапа. На первом находятся значения частных производных по всем независимым переменным, которое и определяет направление градиента в рассматриваемой точке. На втором этапе осуществляется шаг в направлении, обратном направлению градиента, т.е. в направлении наискорейшего убывания целевой функции. Алгоритм градиентного поиска:
Применяется нормализованный вектор градиента, указывающий лишь направление наискорейшего изменения целевой функции, но он не указывает скорости изменения по этому направлению. При этом шаг поиска определяется величиной hk, стратегию изменения кот м\о строить независимо от абс. вел-ны градиента.
Недостатком градиентного методаявляется то, что при его использовании можно обнаружить только локальный минимум. Для того, чтобы найти у функции другие локальные минимумы, необходимо проводить поиск из других начальных точек. Таким образом, с помощью метода градиента каждый локальный минимум целевой функции можно охарактеризовать некоторой областью "притяжения", обладающей тем свойством, что при задании начального состояния U0 в границах этой области метод градиента всегда приводит в один и тот же локальный минимум.
Содержание общей проблемы оценки надежности решений задач МП. Понятие областей устойчивости.