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

Нередко методы нелинейного программирования могут быть охарактеризованы как многошаговые методы или методы улучшения исходного решения. Разнообразие методов решения задач нелинейного

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

В большинстве методов нелинейного программирования используется идея движения в n -мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния u i осуществляется переход в следующее состояние u i +1 изменением вектора u i на величину Δ u i, называемую шагом.

При поиске минимума целевой функции для удачно выбранного шага должно выполняться условие , в противном случае переход в состояние u i +1 нецелесообразен.

В значительной части методов шаг определяется как некоторая функция состояния и,следовательно, новое состояниеможно рассматривать как функцию исходного состояния

В этом смысле шаговые методы поиска оптимума называются итеративными.

Методы нелинейного программирования в зависимости от способа задания шага подразделяются на три основных класса: 1) градиентные методы; 2) безградиентные методы; 3) методы случайного поиска. Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации (u -скаляр) и многомерной оптимизации (u -вектор).

Задача нелинейного программирования в общем случае рассматривается в n -мерном пространстве, где наглядное графическое изображение отсутствует, в связи с этим используется следующий прием графического представления.

Если целевая функция непрерывна в области U, то вокруг точки u опт всегда можно провести в данной плоскости замкнутую линию, вдоль которой значение Q(u) постоянно (рис. 2.1, а). Эти замкнутые линии называются линиями равного уровня функции и отвечают различным значениям = q ι. Вокруг точки u опт можно провести сколько угодно линий уровня, причем каждая из них будет целиком охватывает любую линию, для которой значение целевой функции меньше (или больше).

Рисунок 2.1 – Геометрическое представление целевой функции:

а – линии равного уровня; б – линии равного уровня и связи типа равенств;

в – линии равного уровня и ограничения типа неравенств

При наличии связи , что в n -мерном пространстве определяет (n –1) -мерную поверхность, пересечение которой с рассматриваемой поверхностью определяет область (рис. 2.1, б), в которой и ищется оптимальное решение.

Ограничения типа неравенств независимо от их числа наглядно представлены на рис. 2.1, в. Здесь заходить в заштрихованную область нельзя.

Особенностями целевой функции являются седловые точки, так называемые "овраги" и многоэкстремность. В седловых точках функция по одному или нескольким направлениям имеет минимум, в то время как по остальным – максимум. При наличии оврагов вдоль определенных направлений величина функции изменяется очень слабо. Целевая функция может иметь не один, а несколько оптимумов. Оптимум называется глобальным, если для него справедливо условие

которое выполняется для любых допустимых значений u. Если существуют другие оптимумы, то они называются локальными, и соотношения типа выполняется только в окрестностях точек . Для отыскания глобального оптимума необходимо найти и проверить, вообще говоря, все без исключения локальные оптимумы, имеющейся целевой функции. Среди методов, применяемых для решения задач нелинейного программирования значительное место занимают методы поиска решения, основанные на анализе производных оптимизируемой функции. Эта функция должна быть непрерывно дифференцируемой. Для этого вводится понятие производной по направлению l

,

где u, u * – точки, расположенные на прямой l. Эта производная характеризует скорость изменения функции Q (u) в точке и в направлении l, она может быть выражена через производные по координатам, число которых конечно и равно размерности n. Согласно правилу дифференцирования сложных функций, можно записать

.

Рассмотрим расчет ∂ u ι /∂ l в пространстве двух переменных (рис. 2.2).

Рисунок 2.2 – К определению направляющих косинусов

Из прямоугольного треугольника АВС можно записать

l= .

Таким образом, величины / dl есть не что иное, как направляющие косинусы выбранного направления l по отношению к осям координат. Следовательно, можно переписать следующим образом

.

Если теперь рассмотреть поверхность равного уровня, которая имеет (n –1) независимых переменных, то в каждой точке этой поверхности, называемой гиперповерхностью, можно провести (n –1) взаимно перпендикулярных касательных в соответствии с числом измерений этой поверхности. Кроме того, в этой же точке можно провести ось, перпендикулярную всем касательным и, следовательно, направленную по нормали к поверхности. Подобное построение для случая (n = 3) изображено на рис. 2.3

Рисунок 2.3 – Система координат, связанная с произвольной точкой

поверхности постоянного уровня

Касательные и нормаль могут рассматриваться как система координат с началом в выбранной точке поверхности. Данная система координат обладает тем важным свойством, что частные производные от

функции Q (u) по направлениям осей равны нулю, так как вдоль этих направлений функция Q (u) сохраняет постоянное значение. В соответствии со сказанным производная по произвольному направлению l запишется как

,

что следует из, где производные по всем осям, за исключением нормали, оказываются равными нулю.

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

Формулу можно записать как – проекция градиента функции по направлению l. Отсюда следует, что проекции вектора градиента на оси координат равны производным функции Q (u) по соответствующим переменным, т.е. .

Основным свойствам градиента целевой функции является то, что вектор градиента по направлению совпадает с направлением наискорейшего возрастания этой функции. Именно это свойство обусловило применение градиентных методов при решении задач нелинейного программирования.

Дата добавления: 2015-10-21