Поиск подходящих направлений

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

j_i(x) ® min, iÎ M, (3.44)

j _i(x) £ 0, iÎ I, (3.45)

где x =(x(1), x(2),..., x(n))^T - вектор n - мерного евклидова пространства E_n,

j _i (x) - выпуклые дифференцируемые функции, iÎ M È I.

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

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

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

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

Пусть множество Х имеет вид: X = { xÎ E_n, j _i(x) £ 0, i Î I }. Пусть xÎ X, через I(x) обозначим множество { iÎ I \ j _i(x) = 0 }.

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

Пусть у является некоторой точкой пространства E_n, то есть уÎ E_n

Определение3.20. Будем говорить, что направление s Î E_n - подходящее по Слейтеру в точке yÎ X, если для достаточно малого l> 0 справедливы неравенства:

j _i (y+l´ S) £ 0, iÎ I, (3.46)

j _i (y+l´ S) < j_i(y), iÎ M. (3.47)

 

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

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

Целью данной лабораторной работы является определение признаков, позволяющих выявить одну из следующих ситуаций:

1. уÎ Х ¹ Æ и является оптимум Слейтера (Парето);

2. уÎ Х ¹ Æ и существует возможное направление S такое, что при малых l> 0 y +lS ß Y ( или у +lS < ß Y- по Парето) где ß - предпочтение по Слейтеру, < ß - предпочтение по Парето;

3. уÏ Х и К (у) =Æ, т.е. Х =Æ;

4. уÏ Х и К (у)¹ Æ и существует S, S Î К (у) такое, что при малых l> 0 у +lS ß Y ( или у +lS < ß Y- по Парето);

5. уÎ Х и К (у)¹ Æ, однако не существует SÎ К (у) такое, что при малых l > 0 у +lS ß Y ( или у +lS < ß Y- по Парето).

Следует заметить, что ситуация 1 и 2 частично рассмотрена в пункте 3.7

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

Задача ZS(y).

max s,

< j’_i (y), s> + s £ 0, iÎ I(y)È M,

|| s || £ 1, (3.48)

s ³ 0.

 

Задача ZS(y) не является задачей линейного программирования из-за нелинейности ограничения (2. 5). Обычно это ограничение заменяют ограничением вида:

-1 £ s(j) £ 1, j Î [1..n]. (3.49)

Для решения поставленной задачи воспользуемся теоремой.

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

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