Градиент и производная по направлению
Пусть мы имеем выпуклую целевую функцию
Z = Z(X) = Z(x1, x2,...,xn).
В каждой точке области, где определена и дифференцируема функция Z, определяется градиент gradZ= i׶Z/¶x1+j׶Z/¶x2+ ...+k׶Z/¶xn .
Градиент Zможетиметь другие обозначения:
gradZ= {¶Z/¶x1;¶Z/¶x2; ...;¶Z/¶xn } или gradZ=Ñ Z (набла).
Вектор антиградиент -gradZ= antigradZ= -Ñ Z.
Вектор - градиент, вычисленный в точке X0 (gradZ(X0)), показывает направление скорейшего возрастания функции Z в этой точке.
Вектор-антиградиент, вычисленный в точке X0 (antigradZ(X0)), показывает направление скорейшего убывания функции Z в этой точке.
Пусть N - единичныйвектор, задающий произвольное направление, тогда скалярное произведение gradZ×Nназываетсяпроизводнойпо направлению вектора N.
Скалярное произведение gradZ×Yпоказывает какизменяется Zпо направлению вектора Y,гдеY – любой необязательно единичный вектор.
Если скалярное произведение gradZ×Y <0,то функцияZ уменьшается при движении по направлению вектора Y.
Если скалярное произведение gradZ×Y >0,то функцияZ увеличивается при движении по направлению вектора Y.
Если скалярное произведение gradZ×Y =0,то функцияZ не изменяется при движении по направлению вектора Y.
Это локальные свойства скалярного произведения, то есть свойства, справедливые только для окрестности точки X0 . Они используются для организации итеративного процесса движения к минимуму или к максимуму.
Практически задачи выпуклого программирования возникают при учете нелинейной зависимости, например, себестоимости от производства.
Существует очень много способов решения задач выпуклого программирования: метод штрафных функций, метод случайного и неслучайного поиска, метод последовательного изменения координат, градиентные методы и другие. Алгоритмы решения задач выпуклого программирования реализуются только численными методами. Градиентные итерационные методы предполагают использование ПК ввиду громоздкости вычислений. Любой расчет ведется с конечной точностью, поэтому вводится специальный параметр, например, e или d, учитывающий точность расчета.
Если поверхность ji(X)Î[- d, 0] в точке X0, то точка X0Îji(X).
Пусть поверхность j1 (X) < 0, d = 0,0005, X0 =0,000005, тогда X0 = =0,000005Ï[-0,0005; 0 ], поэтому X0 Ï j1 (X). Если X0 = -0,00005, тогда X0 == -0,00005 Î [-0,0005; 0 ], поэтому X0 Î j1 (X).
Геометрически ji(X)Î[- d, 0] это соответствует выделению вместо поверхности ji(X) = 0 полосы толщиной d.
Пусть заданы три поверхности: ji(X) £ 0, i = 1 ¸ 3.
Рис. 7. Изображение поверхностей
Задана точка X0 и величинаd, являющаяся толщиной поверхностей. На рис. 7 точка принадлежит двум поверхностям: X0Î j1 (X) иX0Î j2 (X).
АЛГОРИТМ РЕШЕНИЯ ОБЩЕЙ ЗАДАЧИ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ
Пусть задана исходная форма общей задачи выпуклого программирования:
min Z = f(X) = f(x1, x2,...,xn),
ji (X) £ 0, i = 1 ¸ m,
X ³ 0,
где f(X) – выпуклая функция,
ji(X) – выпуклые функции, i = 1 ¸ m.
В общем случае канонической формой для задачи выпуклого программирования является запись:
min Z = С1x1+С2x2+...+Cn xn - целевая функция,
система ограничений
ji(X) £ 0, i = 1 ¸ m,
X(x1, x2,...,xn) ³ 0,
ji(X) – выпуклые функции, i = 1 ¸ m.
I шаг[8]. Пусть исходное допустимое решение X0 найдено, то есть X0Î ji (X), i = 1 ¸ m или X0 существует (X0Î ji (X) = 0, i = 1 ¸ m или X0 принадлежит полосам: -d £ ji (X) £ 0, i = 1 ¸ m, где d - параметр точности).
II шаг - основной.
1. Функция ji(X) в n – мерном пространстве соответствует поверхности ji (X) = 0. Для задач выпуклого программирования – это выпуклые поверхности. Так как точность представления чисел на ПК ограничена, то точное равенство ji (X) = 0 часто не достигается, поэтому обязательно вводится какой –то параметр точности d. Проверкой всех ограничений выделяются те ограничения, которым принадлежит допустимое решение X0. Следовательно, проверяются неравенства -d £ ji (X) £ 0, i = 1 ¸ m. Если неравенство выполняется, то X0 принадлежит выпуклой поверхности ji (X). Эти неравенства выделяем и перенумеровываем или переименовываем.
Например, X0 Ï j1 (X).
X0 Ï j2 (X).
X0 Î j3 (X)Þ X0 Î jn1 (X) .
X0 Ï j4 (X).
X0 Î j3 (X) Þ X0 Î jn2 (X).
………….
X0 Î jm (X)Þ X0 Î jnk (X)
Тогда из системы ограничений ji(X) £ 0, i = 1 ¸ m выделяется новая система:
jn1 (X) £ 0.
jn2 (X) £ 0.
...............
jnk (X) £ 0.
Или jni (X) £ 0, i = 1 ¸ k, где k £ m.
2. Далее формируется задача линейного программирования, которая является вспомогательной и служит для определения направления спуска, то есть такого направления, при котором целевая функция убывает. Кроме того осуществляется движение, по крайней мере, в окрестности точки X0, которое ведет внутрь области допустимых решений. Символически вспомогательную задачу можно записать в виде:
min U = y n+i - целевая функция вспомогательной задачи.
grad Z = (С1,С2, …,Сn) – коэффициенты целевой функции основной задачи, записанной в канонической форме.
Система ограничений вспомогательной задачи:
Часть А:
grad Z×Y £ y n+i
grad jni (X0) ×Y £ y n+i , i = 1 ¸ k,
Часть Б:
-1£ y 1 £ 1,
-1£ y 2 £ 1,
………….
-1£ y n £ 1.
Ограничения Б вводятся для того, чтобы сделать вектор Y(y 1, y 2, …, yn) ограниченным. При неограниченном векторе Y скалярное произведение типа grad f ×Y (где f – функция) стремится к бесконечности, так как модуль этого произведения может быть слишком большим. Если минимальное значение целевой функции вспомогательной задачи U < 0, то по направлению Y целевая функция будет убывать, то есть движение будет внутрь области допустимых решений. Если минимальное значение целевой функции вспомогательной задачи U < 0, то по направлению Y функции jni также будут убывать, так как jni (X) £ 0, i = 1 ¸ k. Следовательно, направление Y ведет внутрь области допустимых решений.
Перепишем вспомогательную задачу линейного программирования более подробно.
min U = y n+i
grad Z = (С1,С2, …,Сn)
Часть А:
С1 y 1+С2 y 2 + …+Сn y n £ y n+i
[¶jn1(X0)/(¶x1)]×y1+[¶jn1(X0)/(¶x2)]×y2+[¶jn1(X0)/(¶x3)]×y3+[¶jn1(X0)/ /(¶xn)]×yn £ y n+i
................
[¶jnk(X0)/(¶x1)]×y1 + [¶jnk(X0)/(¶x2)]×y2+[¶jnk(X0)/(¶x3)]×y3 + [¶jnk(X0)/ /(¶xn)]×yn £ y n+i
Часть Б:
-1£ y j £ 1, j = 1¸n.
Это исходная форма вспомогательной задачи.
Для ее решения симплексным методом каждую переменную yj, j=1¸n нужно заменить разностью двух неотрицательных переменных yj= yj¢- y j² , причем yj¢ ³ 0, yj² ³ 0 и привести вспомогательную задачу линейного программирования к канонической форме.
Решение этой задачи является по существу и критерием оптимальности, так как если min U = y* n+i ³ 0, то направления спуска нет, а это означает, что точка X0, принадлежащая области допустимых решений, является приближенным оптимальным решением вспомогательной задачи.
3. Определение шага по направлению.
Пусть вектор Y найден из решения вспомогательной задачи линейного программирования и используется для движения к «лучшему»[9] допустимому решению. Для этого в формуле X′ = X0 +t ·Y необходимо определить такое значение t, равное t* , чтобы точка X′ была допустимым решением.
Для каждого неравенства системы ограничений ji(X) £ 0, i = 1 ¸ m можно найти наименьший положительный корень ti из системы уравнений ji(X′)= ji (X0 +t ּY) = 0, i = 1 ¸ m. Каждое уравнение ji(X′) является нелинейным уравнением. Для решения таких уравнений есть численные методы: половинного деления, секущих (хорд), касательных (Ньютона), комбинированный, итераций и др.
Например, пусть ji(X)= х12+х22 - 5 £ 0, задана точка X0(1;1) и вектор Y(2;1). Тогда ji(X)= ji (X0 +t ּY) =(х10+t ּ y1)2+(х20+t ּ y2)2 -5 £ 0.
ji(X) = (1+tּ2)2 + (1+tּ1)2 - 5 = 1+4t+4t2 +1 + 2t + t2 –5 = 5t2 + 6t – 3 £ 0.
5t2 + 6t – 3 = 0; D = 62 - 4ּ5ּ(-3) = 96; t1 = - 0,6 – 0,4ּ√ 6; t2 = - 0,6 + 0,4ּ√ 6;
Взято только одно неравенство, а у нас их m и каждое дает свое значение t. Возьмем t* = min {ti}, i=1 ¸ m. По формуле X′ = X0 +t ·Y находим допустимое решение, которое принимаем за исходное X0 . Далее процесс продолжается с пункта 2 шага II.
Шаг III. Исходное допустимое решение можно определить, применяя рассмотренный алгоритм для следующей задачи.
min Q = x n+1
j1(X)= j1(x1, x2,...,xn) ≤ xn+1
………………………………………
jm(X)= jm(x1, x2,...,xn) ≤ xn+1.
Как только xn+1 станет меньше нуля, так X(x1, x2,...,xn) станет допустимым. Во многих практических задачах сравнительно легко можно найти начальную точку, принадлежащую области допустимых решений ω. Необходимо грубо оценить область определения переменных Хj, взять из этой области любую точку X′. Подставить это решение в ограничения задачи. Если все ji(X′) ≤ 0, то принять точку X′ за начальную точку X0 . Если есть хотя бы одно ограничение ji(X′) > 0, то вводится дополнительная переменная α такая, чтобы выполнялось неравенство ji(X′) ≤ α для определенного ранее i. Определяем Min Q = α. Чтобы найти начальную точку, необходимо получить решение X0, для которого α<0.
Замечание. Применение алгоритма затруднено в виду изменения размеров вспомогательной задачи и необходимости решения нелинейных уравнений.
Укрупненная схема алгоритма
1. Определение исходного (начального) допустимого решения.
2. Формулировка и решение вспомогательной задачи линейного программирования. Нахождение вектора Y. Проверка решения на оптимальность.
3. Определение шага по направлению. Движение по направлению вектора Y: X′ = X0 +t ·Y. Решение последовательности нелинейных уравнений. Переход к пункту 2.