3.4. Задача выпуклого векторного программирования с ограничениями типа неравенства. Поиск подходящих направлений.

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

i(x)  min, i M,	(2.1)
xX={x| i(x)  0 , iI }Rn,	(2.2 )

 _i (x) –выпуклые дифференцируемые функции, iMI.

Задача означает, что требуется:

• либо определить множество оптимальных точек при заданном предпочтении (в данной лабораторной работе по Слейтеру);

• либо определить, что множество оптимальных точек при заданном предпочтении пусто;

• либо убедиться, что множество допустимых решений определяемых ограничениями (2. 2) пусто;

Обозначим X={xRⁿ,  _i(x)0, iI}. Пустьx X,черезI(x)обозначим множествоI(x)={iI\ _i(x)=0}.

Определение 2.17.Будем говорить, что множествоXудовлетворяет условиям регулярностиR2 по Слейтеру, если существует точкаz X такая, что _i(z)<0для всехiI.

Пусть у является некоторой точкой пространстваRⁿ , т.е.у Rⁿ

Определение 2.18.Будем говорить, что направлениеs  Rⁿ–подходящеепо Слейтеру в точкеyX,если для достаточно малого>0 справедливы неравенства:

 i (y+s)0, iI,	(2. 3)
 i (y+s)<i(y), iM	(2. 4)

Согласно определению 2.14, множество всех подходящих направлений в точке yXобразует конус, который будем обозначать черезK(y). Тогда справедлива следующая теорема.

Теорема. 2.16.Пусть множествоXудовлетворяет условию регулярностиR2. Для того, чтобы точкаyXбыла точкой оптимума по Слейтеру, необходимо и достаточно, чтобы конусK(y)=.

Для поиска подходящих направлений по Слейтеру рассмотрим следующую задачу (назовем её ZS(y)).

Задача ZS(y).

	(2.5)

где s =(s₁, s₂ ,..., s_n )^T. ЗадачаZS(y)не является задачей линейного программирования из–за нелинейности ограничения (2.5). Обычно это ограничение заменяют ограничением вида:

(2.6)

В терминах задачи ZS(y) критерий оптимальности можно записать.

Теорема 2.17.Пусть множествоX удовлетворяет условию регулярностиR2. Для того, чтобы точкаyXбыла точкой оптимума по Слейтеру, необходимо и достаточно, чтобы максимальное значение  в задачеZS(y)было равно нулю.

Заметим, что если в этой задаче  >0, то получившееся соответствующее значениеs дает подходящее направление в точкеy.

Алгоритм безусловной векторной оптимизаци.

Предлагаемый ниже алгоритм является развитием градиентных методов и метода возможных направлений Зойтендейка. Так задача ZS(y) для однокритериальной задачи безусловной оптимизации в качестве направленияs вырабатывает в однокритериальной задаче возможное подходящее направление.

Алгоритм.

0–ой шаг.В качествех₀ задаем произвольную точку из Rⁿ.

k– ый шаг( k= 0, 1, 2, …).

Полагаем

xk+1=xk+sk k ,

(2. 7)

где значения _k , s_k получены из решения задачиZS(x_k).

_k выбирается следующим образом:

1. Выбираем некоторое l (одно на всех итерациях) и полагаемl_k = l.

2. Вычисляем  _i (x) = _i (x_k +  s_k _k), i M.

3. Если для всех

 i ( x) –  i ( xk ) –  k k 2 ,  (0, 1),

(2. 8)

то _k является искомым, в противном случае полагаем _k = _k , где(0,1) и переходим к шагу 2.

Последовательности {x_k}, {_k}, {s_k} обрываем, если для некоторогоk в точкеx_k оказалось_k=0 , в этом случае при выполнении достаточных условий точкаx_k являются оптимумом по Слейтеру.

Пример.

Для задачи

₁(x)= x₁² + x₂²  min,

₂(x)= x₁² + (x₂ –4)²  min,

₃(x)= (x₁ –4)² + x₂²  min,

₄(x)= (x₁ –4)² + (x₂ –4)²  min.

проверить на оптимальность точку y = (2,2)^T.

Решение.

В этой задаче множество I=, поэтому задачаZS(y) примет вид:

Задача ZS(y).

	(2.9)

Подставляя в (2.9) значения градиентов  _i'(y) в точкеу= (2, 2),получим

max  ,

4s₁ + 4s₂ +   0,

4s₁ – 4s₂ +   0,

–4s₁ + 4s₂ +   0,

–4s₁ – 4s₂ +   0,

–1  s₁  1,

–1  s₂  1.

Проведя замену переменных s_j = s'_j –1, j=1,2, получим

max  ,

4s'₁ + 4s'₂+   8,

4s'₁ – 4s'₂+   0,

–4s'₁+ 4s'₂+   0,

–4s'₁– 4s'₂+   –8,

s'₁  2, s'(2)  2,

s'₁ 0, s'₂ 0,   0.

Решая эту задачу симплекс – методом, получаем, что максимальное значение  = 0.Это означает, что точкаy = (2,2) оптимальна по Слейтеру