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

Размещено на http://www.allbest.ru/

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

Построение ОДЗП. Выбор начальной точки

Система ограничений решаемой задачи нелинейного программирования имеет следующий вид:

-5x1+2 x2+2 0

x1+2 x2-10 0

x1,2 0

Каждое из ограничивающих неравенств определяет полуплоскость лежащую по одну сторону от прямой. ОДЗП получается в результате пересечения этих полуплоскостей. Условие неотрицательности позволяют ограничиться рассмотрением положительного квадранта.

ОДЗП решаемой задачи:

Рис. 1 - ОДЗП задачи нелинейного программирования и начальная точка

В качестве начального приближения к точке экстремума выберем точку x0=[2,2], принадлежащую ОДЗП.

Экстремальные задачи без ограничений. Метод наискорейшего спуска. Метод Ньютона-Рафсона

Задача поиск безусловного экстремума функции многих переменных формулируется следующим образом: найти значения переменных x1, x2…xn, доставляющие экстремум скалярной целевой функции F(x1, x2…xn), если ограничения на переменные отсутствуют.

Функция цели решаемой задачи: F(x)=6x12+4x22+ x1x2 -3x1-6x2 (max)

Здесь x0=[2,2] Ї начальное приближение к точке экстремума, выбранное в предыдущем пункте.

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

Градиент функции F(x) Ї вектор, составляющие которого равны частным производным функции F(x) по соответствующим переменным.

Градиент функции цели решаемой задачи:

Направление вектора градиента совпадает с направлением наискорейшего возрастания функции. Вектор противоположного знака - F(x), называется антиградиентом, его направление совпадает с направлением наискорейшего убывания функции.

Матрица вторых производных F(x) - это симметричная квадратная матрица порядка n вторых частных производных функции F(x). Эту матрицу называют матрицей Гессе.

Матрица Гессе решаемой задачи:

Для наличия в точке x* локального минимума (максимума) необходимо, чтобы градиент функции F(x*) в этой точке равнялся нулю, а матрица Гессе была положительно (отрицательно):

F(x*) =0, xT H(x)?0

В общем случае процедура поиска осуществляется по формуле:

x k+1= x k -H-1(x k)F(x k),

где xk Ї текущее приближение к решению x* на k-м шаге; Sk - направление движения в точке xk; бk - параметр, характеризующий величину шага.

Величина шага бk определяется из условия обеспечения экстремального значения функции цели F(x) в рассматриваемом направлении Sk.

Процедура поиска прекращается, когда норма вектора градиента:

¦F(x k)¦? е

где е - заранее заданная точность решения задачи (предположим, что е=0,05).

Метод наискорейшего спуска:

В методе наискорейшего спуска направление движения при поиске минимума функции цели F(x) задается вектором антиградиента -?F(x) функции F(x) в рассматриваемой точке. Очередная точка при поиске минимума функции вычисляетя по формуле:

x k+1= x k +б k F(x k)

Найдем составляющие вектора градиента:

Градиент функции в точке x0:

F(x 0)=[23; 12]

1-й шаг.

Движение осуществляется из точки x0 вдоль вектора -?F(x0) в новую точку x1:

Определим величину б0, из условия обеспечения экстремума функции в направлении -F(x0). Подставим координаты точки x1 в функцию F(x) получим:

В результате координаты точки x1 получатся равными:

Определим составляющие вектора градиента ?F(x1):

F(x 0)=[-1.072; 2.054]

Проверим точность решения задачи:

¦F(x k)¦=v (-1.072) 2 +(2.054) 2 =2.317 ?0.05

Следовательно, заданная точность решения задачи не достигнута. Переходим к следующему шагу.

2-й шаг.

Движение осуществляется из точки x1 вдоль вектора -F(x1) в новую точку x2:

Определим величину б1, из условия обеспечения экстремума функции в направлении -F(x1):

В результате координаты точки x2 получатся равными:

Определим составляющие вектора градиента ?F(x2):

F(x 0)=[0.236; 0.195]

Проверим точность решения задачи:

¦F(x k)¦=v (0.236) 2 +(0.195) 2 =0.306 ?0.05

Следовательно, заданная точность решения задачи не достигнута. Переходим к следующему шагу.

3-й шаг.

Движение осуществляется из точки x3 вдоль вектора -F(x2) в новую точку x3:

Определим величину б2, из условия обеспечения экстремума функции в направлении -F(x2):

В результате координаты точки x2 получатся равными:

Определим составляющие вектора градиента ?F(x3):

F(x 3)=[-0.03; 0.037]

Проверим точность решения задачи:

¦F(x k)¦=v (-0.03) 2 +(0.037) 2 =0.048? 0.05

Заданная точность достигнута.

Рис. 2

Графическая интерпретация метода наискорейшего спуска рис. 2

Метод Ньютона-Рафсона:

Решим эту же задачу методом Ньютона-Рафсона. Каждая очередная точка поиска вычисляется в соответствии с выражением:

x k+1= x k -H-1(x k)F(x k)

где H-1(xk) - матрица, обратная по отношению к матрице Гессе (3.6), вычисленной в точке xk.

Важно, что метод Ньютона-Рафсона обеспечивает решение задачи за один шаг, если функция цели квадратичная, как в нашем случае (3).

Определим составляющие вектора градиента F(x0) в начальной точке:



Матрица Гессе решаемой задачи:

Матрица, обратная по отношению к матрице Гессе H(x) решаемой задачи вычисляется по следующей формуле:

где detH - определитель матрицы H; AdjH - присоединенная к матрице Н матрица (транспонированная матрица алгебраических дополнений).

Алгебраические дополнения элементов матрицы H:

11=8 12=-1

21=-1 22=12

Тогда: , определитель матрицы Гессе: det(H)=95

Искомая матрица, обратная матрице Гессе:

В результате координаты точки x1 получатся равными:

Определим составляющие вектора градиента F(x1):



F (x 1)=[12*0.189+0.726-3;4*0.726+0.189-6]=[0;0].

Соответственно, в точке x1=[0.189; 0.726] функция F(x) достигает минимального значения:

F(min)=-2.432

Убедиться в правильности решения задачи можно, используя пакет прикладных программ системы Matlab. В частности подпрограмму fminunc, предназначенную для нелинейной оптимизации без ограничений:

Using Toolbox Path Cache.

Type "help toolbox_path_cache" for more info.

To get started, select "MATLAB Help" from the Help menu.

>> F=inline('6*x(1)^2+4x(2)^2-x(1)*x(2)-3*x(1)+6*x(2)');

>> x0=[2,2];

>> [x,Fmin]=fminunc(F,x0)

Optimization terminated successfully:

x = 0.1891 0.7264

Fmin = -2.4320

Таким образом, задача решена правильно.

Экстремальные нелинейные задачи с ограничениями. Метод допустимых направлений Зойтендейка. Метод линейных комбинаций. Условие теоремы Куна-Таккера

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

Найти значения переменных x1, x2…xn, доставляющие экстремум скалярной целевой функции F(x1, x2…xn) при наличии ограничений вида gj(x) ?0, j=1…n, где по крайней мере одна из функций F(x) или g(x) является нелинейной.

Функция цели решаемой задачи:

нелинейный задача ограничение матрица

F(x)=6x12+4x22+x1x2-3x1 -6 x2 (min)

x0=[2,2] Ї начальное приближение к точке экстремума.

Система ограничений решаемой задачи нелинейного программирования имеет следующий вид:

-5x1+2 x2+2 0

x1+2 x2-10 0

x1,2 0

Метод допустимых направлений Зойтендейка:

В общем случае процедура поиска осуществляется по формуле:

x k+1= x k +бkF(x k).

где xk - текущее приближение к решению x* на k-м шаге; Sk - направление движения в точке xk; бk - параметр, характеризующий величину шага.

Величина шага бk определяется на основании выполнения двух условий:

Очередная точка x 1 должна принадлежать ОДЗП. Чтобы это условие выполнялось, должна выполняться система неравенств:



Находится значение б0, которое максимизирует функцию F- б0*.

Если , то б0= б0*, в этом случае очередная точка x 1 будет лежать внутри ОДЗП и очередной шаг нужно будет делать опять в направлении вектор-градиента. Если же , то выбирается б0= б0”, в этом случае очередная точкам x 1 будет находиться на границе ОДЗП.

1-й шаг.

Движение из начальной точки x0=(2,2) лежащей внутри ОДЗП осуществим вдоль вектора антиградиента -?F(x0). Определим составляющие вектора антиградиента в точке x0:

-F (x 0)=[-23; -12]

Тогда координаты очередной точки x1:

Определим величину б0 из условия принадлежности x1 к ОДЗП и обеспечения экстремума функции F(x) в заданном направлении:

Найдем интервал . Для этого подставим координаты точки x 1 в ограничения:

В результате координаты точки x1 получатся равными:

Так как , то точка x 1 лежит на границе ОДЗП. Тогда из точки x 1 в направлении вектора-градиента двигаться нельзя, так как градиент выходит за пределы области. Нужно найти то направление, по которому нужно двигаться.

Очередное направление Sk должно удовлетворять двум условиям:

Очередная точка должна принадлежать ОДЗП.

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

Координаты очередной точки записываются:

x k+1= x k -бk S k.

Точка x 1 лежит на линии -5x1+2x2=-2. Найдем направление S, используя выражение и условие нормализации ¦S¦=1, где -коэффициенты соответствующего неравенства.

Таким образом получаем:

В результате получаем:



Найдем очередную точку :

Найдем б1:

Найдем интервал допустимых значений :

Проанализируем полученный интервал:

В результате координаты точки будут равны:

Определим градиент в точке :



Так как , то в точке x 2 функция F(x) достигает экстремума.

Таким образом, min функции F(x) будет равен:

Рис. 3

Графическая интерпретация метода Зойтентейка рис. 3

Метод линейных комбинаций:

Метод линейных комбинаций ориентирован на решение задач, в которых функция цели нелинейная, а все ограничения линейны:

Функция цели решаемой задачи:

F(x)=6x12+4x22+x1x2-3x1 -6 x2 (min)

x0=[2,2] Ї начальное приближение к точке экстремума, выбранное в предыдущем пункте.

Система ограничений решаемой задачи нелинейного программирования имеет следующий вид:

-5x1+2 x2+2 0

x1+2 x2-10 0

x1,2 0

В основе метода лежит замена нелинейной функции F(x) общего вида линейной функцией в окрестности точки xk:

Т.к. выражение [F(xk)-?F(xk)Txk], вычисленное в точке xk, есть некоторое число, то для нахождения вектора , доставляющего экстремум линейной функции цели, нужно решить следующую задачу ЛП:

Т.к. точка - оптимальное решение линеаризованной задачи, принадлежит вершине ОДЗП, а истинное решение исходной задачи может лежать внутри ОДЗП - необходимо произвести дополнительную корректировку :

Здесь Ї направление движения в точке xk; бk Ї параметр, характеризующий величину шага.

Величина шага бk должна обеспечивать экстремальное значение функции цели F(x) в рассматриваемом направлении. Для этого решают уравнение:

Определим выражение градиента:

2 итерация:

Определим составляющие вектора градиента в точке x0:

Осуществим линеаризацию функции F(x) относительно точки x0:

Составим задачу линейного программирования и для ее решения применим симплекс-метод:

Процедура решения задачи симплекс-методом:

Таблица 1

Базисные переменные	Свободные члены	Небазисные переменные
		x1	x2
x3	-2	-5	2
x4	10	1	2
W0	0	23	12

Таблица 2

Базисные переменные	Свободные члены	Небазисные переменные
		x3	x2
x1	2/5	-1/5	-2/5
x4	48/5	1/5	12/5
W0	-46/5	23/5	106/5

Таблица 2 соответствует оптимальному решению линеаризованной задачи.

Скорректируем найденное решение, используя формулу:

Таким образом получим:

Подставим эти значения в функцию F(x) и осуществим ее минимизацию по параметру :



Тогда:

Найдем координаты точки и значение функции в этой точке

2 итерация:

Определим составляющие вектора градиента в точке x1:

Осуществим линеаризацию функции F(x) относительно точки x1:

Составим задачу линейного программирования и для ее решения применим симплекс-метод:

Процедура решения задачи симплекс-методом:

Таблица 3

Базисные переменные	Свободные члены	Небазисные переменные
		x1	x2
x3	-2	-5	2
x4	10	1	2
W0	0	4.352	-3.482

Таблица 4

Базисные переменные	Свободные члены	Небазисные переменные
		x3	x2
x1	0.4	-0.2	-0.4
x4	9.6	0.2	2.4
W0	-1.741	0.87	-1.74

Таблица 5

Базисные переменные	Свободные члены	Небазисные переменные
		x3	x4
x1	2	0.167	0.167
x2	4	0.083	0.417
W0	5.22	1.015	0.725

Таблица 5 соответствует оптимальному решению линеаризованной задачи.

Скорректируем найденное решение, используя формулу:

Таким образом получим:

Подставим эти значения в функцию F(x) и осуществим ее минимизацию по параметру :

Тогда:

Найдем координаты точки и значение функции в этой точке

3 итерация:

Определим составляющие вектора градиента в точке x2:

Осуществим линеаризацию функции F(x) относительно точки x2:

Составим задачу линейного программирования на основании и для ее решения применим симплекс-метод, рассмотренный в разд. 2:



Процедура решения задачи симплекс-методом:

Таблица 6

Базисные переменные	Свободные члены	Небазисные переменные
		x1	x2
x3	-2	-5	2
x4	10	1	2
W0	0	5.33	-1.995

Таблица 7

Базисные переменные	Свободные члены	Небазисные переменные
		x3	x2
x1	0.4	-0.2	-0.4
x4	9.6	0.2	2.4
W0	-2.132	1.066	0.137

Таблица 7 соответствует оптимальному решению линеаризованной задачи.

Скорректируем найденное решение, используя формулу:

Таким образом получим:



Подставим эти значения в функцию F(x) и осуществим ее минимизацию по параметру :

Тогда:

Найдем координаты точки и значение функции в этой точке

Графическая интерпретация метода линейных комбинаций:

Рис. 4

Графическая интерпретация метода линейных комбинаций рис. 4

Условие теоремы Куна-Таккера:

Теорема Куна-Таккера предназначена для отыскания условного экстремума функции многих переменных F(x1, x2, … xn) в задачах с ограничениями неравенствами вида gj(x)???j=1…m и ограничениями на знак переменных xi??i=1…n.

Функция цели решаемой задачи:

F(x)=6x12+4x22+x1x2-3x1 -6 x2 (min)

Здесь x0=[2,2] Ї начальное приближение к точке экстремума, выбранное в предыдущем пункте. Система ограничений решаемой задачи нелинейного программирования имеет следующий вид:

-5x1+2 x2+2 0

x1+2 x2-10 0

x1,2 0

Формулировка теоремы Куна-Таккера:

Пусть существует вектор x, такой, что xi???i=1…n и gj(x)???j=1…m. Тогда для того, чтобы вектор x* был оптимальным решением задачи (задача минимизации), необходимо и достаточно, чтобы существовал такой неотрицательный m-мерный вектор л, чтобы выполнялось условие:

для всех x???л?.

Здесь:



Ї функция Лагранжа, где gj(x) Ї левые части ограничений, приведенные к нулевой правой части; лi Ї неопределенные множители Лагранжа.

При этом, если F(x) и gj(x) являются дифференцируемыми функциями, то условие теоремы Куна-Таккера запишется следующим образом:

Экстремальная точка (x*, л*) с такими свойствами называется седловой точкой. Задача нахождения экстремума функции F(x) сводится к нахождению седловой точки для функции Лагранжа.

Процедура решения:

Поскольку решаемая задача на нахождении минимума функции F(x), то точкой экстремума является седловая точка с минимумом по x и максимумом по л. Следовательно, ограничения решаемой задачи необходимо привести к виду gj(x)?

Определим функцию Лагранжа решаемой задачи:

Условие теоремы Куна-Таккера примет следующий вид:

Приведем систему неравенства к системе уравнений, домножив первые два неравенства на -1 и введя дополнительные переменные V и W, получим:

Относительно данной системы уравнений применим симплекс-метод. В качестве базисных переменных выберем введенные дополнительные переменные - V1, V2, W1, W2. При этом строка для функции цели отсутствует.

Процедура решения иллюстрируется симплекс-таблицами 8 - 9:

Таблица 8

Базисные переменные	Свободные члены	Небазисные переменные
		x1	x2	л 1	л 2
V1	-3	-12	-1	5	-1
V2	-6	-8	-1	-2	-2
W1	-2	-5	2	0	0
W2	10	1	2	0	0

Решение, соответствующее табл. 8, не является оптимальным. Перейдем к следующей таблице, выбирая в качестве ведущего элемент, стоящий на пересечении столбца x1 и строки V1:

Таблица 9

Базисные переменные	Свободные члены	Небазисные переменные
		V1	x2	л 1	л 2
x1	0.25	-0.083	0.083	-0.416	0.833
V2	-4	-0.66	-0.333	-5.333	-1.333
W1	-0.75	-0.416	2.416	-2.083	0.416
W2	9.75	0.083	1.916	0.416	-0.083

Решение, соответствующее табл. 9, не является оптимальным. Перейдем к следующей таблице, выбирая в качестве ведущего элемент, стоящий на пересечении столбца л 1 и строки W1

Таблица 10

Базисные переменные	Свободные члены	Небазисные переменные
		V1	x2	W1	л 2
x1	0.4	3.09	-0.4	-0.2	-3.09
V2	-2.08	0.4	-6.52	-2.56	-2.4
л 1	0.36	0.2	-1.16	-0.48	-0.2
W2	9.6	-3.09	2.4	0.2	3.09

Решение, соответствующее табл. 9, не является оптимальным. Перейдем к следующей таблице, выбирая в качестве ведущего элемент, стоящий на пересечении столбца x2 и строки V2

Таблица 11

Базисные переменные	Свободные члены	Небазисные переменные
		V1	V2	W1	л 2
x1	0.527	-0.02	-0.061	-0.04	0.147
x2	0.319	-0.061	-0.153	0.392	0.368
л 1	0.73	0.128	-0.117	-0.02	0.226
W2	8.834	0.147	0.368	-0.74	-0.883

Решение, соответствующее табл. 11, является допустимым:

=0.319

Кроме того выполняется условие:

Следовательно, =0.319 - оптимальное решение задачи и оптимальное значение функции цели:

Убедиться в правильности решения задачи можно, используя пакет прикладных программ системы Matlab. В частности подпрограмму quadprog, предназначенную для нелинейной оптимизации c ограничениями:

>> x0=[2 2];

>> H=[12 1; 1 8];

>> F=[23 12];

>> A=[-5 2; 1 2];

>> B=[-2 10];

>> VLB=zeros(2,1);

>> VUB=[];

>> x=quadprog(H,F,A,B,[],[],VLB,VUB)

Optimization terminated successfully.

x =

0.581

0.456

>> z=F*x+1/2*x'*H*x

z = -1.354

Размещено на Allbest.ru