Численные методы не линейной оптимизации

Рассматривается задача вида

F(x)->min (1)

При выполнение ограничений.

G(x)<=0, i=1,k (2)

G(x)=0, i=k+1,m (3) x э Р (4)

Рассматривается задача условной оптимизации, в которой ищется вектор х*=(x1,x2,x3,…xn), который доставляет экстремум к целевой функции один при выполнение ограничений (2,4).

Возможны два варианта:

1)когда соотношения (1,3) имеют аналитическую форму

2)когда хотя бы одно из них нельзя выразить явным образом

3)в первом случае, когда число n –переменных не велико используются аналитические методы, во втором случае используются численные методы.

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

Часто в задачах оптимизации независимые переменные имеют различную физическую природу (скорость, температуру, концентрацию, расход и т.д.), поэтому их часто нормализуют. Пусть имеется

Y=(y1,y2,…,yn)

Yj э [yjmin, yjmax], j=1,n

Yj<->xj; xj= yj-jmin /ymax-ymin

J=1,n; xj э [0,1]

Тогда исходная задача (1,3) может быть сформулирована для новых нормализованных переменных.

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

Геометрическая интерпретация целевой функции и ограничений

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

f(x1,x2)=x1²+x2²->mm

пример: рассечем параболоид вращения плоскостями параллельными плоскости х1ох2 и расположенные на разном расстояние от этой плоскости, полученные в сечение окружности спроецируем на плоскость. В результате получим множество концентрических окружностей разного радиуса для каждой из которых значение целевой функции одинаково, эти линии называются линиями равного уровня (постоянного уровня).

В общем случае для непрерывной функции f(x) вокруг оптимальной точки всегда можно провести в плоскости замкнутую линию вдоль которой f(x)=const.

Таких линий бесконечно много, при чем каждая из них охватывает все другие линии с меньшим значением f(x). Форма этих линий для различных значений const может быть различной.

Ограничения типа равенств должно быть одно рассмотренный способ изображения f(x) не является единственным, в функции f(x) и gi(x) могут иметь различную форму в зависимости от ориентации плоскости в пространстве.

Особые точки и линии

По необходимому условия существования экстремума, условие не является достаточным. Примером тепловая точка.

В седловых точках для n-мерного случая являются такие точки, в которых по одной или нескольким переменным имеет место максимум, а по другим минимум.

Другими особенностями являются овраги, при наличии которых величина f(x) меняется очень слабо.

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

Наличие оврагов f(x) существенно затрудняет поиск экстремума и нужны специальные «овражные» методы.

Градиент целевой функции f(x) это есть вектор, компонентами которого является частные производные f(x) по всем переменным

F(x)=>град f(x)

Вектор градиента в каждой точке области определения Х направлен по нормали к поверхности равного уровня, проведенный через эту точку по направлению он совпадает с наискорейшем возрастанием целевой функции f(x) в этой точке.

Именно это свойство используется в процессе поиска экстремума f(x).

 

Поиск экстремума, функция многих переменных

Пример:

Найти экстремум min и max, целевой функции (критерии)

f(xyz)=x²+y²-z²-xy+x-2z

по сколько f(xyz) имеет явный аналитический вид и является непрерывной то применим методы классического анализа.

В нашем случае имеет место задача безусловной оптимизации.

По необходимому условию NQ существования экстремума непрерывной функции имеет частное производное.

df(xyz)/2x=2x+0-0-1y+1-0=2x-y+1=0

df(xyz)/2y=0+2y-0-x+0-0=2y-x=0

df(xyz)/2z=0+0-2z-0+0-z=-2z-z

таким образом получим систему уравнений с 3 не известными. Систему 3 линейных алгебраических уравнений.

2x-y+1=0

2y-x=0

-2z-z=0

Для этого составим матрицу Гессе из 2 производных вычисленных в подозрительной точке.

а11 а12 а13

а21 а22 а23

а31 а32 а33

 

f(x), x э [a, b]

f(x)->min

E>0

N=|b-a/E|+1 глобальный экстремум