Численные методы не линейной оптимизации
Рассматривается задача вида
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)=x12+x22->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)=x2+y2-z2-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 глобальный экстремум