close

Вход

Забыли?

вход по аккаунту

?

Некоторые вопросы кусочно-линейного программирования.

код для вставкиСкачать
1997
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 12 (427)
УДК 519.853
И.И. ЕРЕМИН
НЕКОТОРЫЕ ВОПРОСЫ
КУСОЧНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задачи кусочно-линейной оптимизации составляют важный класс задач математического
программирования. С одной стороны, они ближайшим образом обобщают задачи линейного
программирования, сохраняя многие свойства последних, а с другой | служат самостоятельным хорошо работающим аппаратом в различных областях прикладной математики. Кусочнолинейными задачами можно аппроксимировать нелинейные задачи оптимизации, бывает полезным редуцировать к ним те или иные типы многоэкстремальных задач. Есть еще одно важное
обстоятельство, характеризующее кусочно-линейные функции: они обладают уникальными разделительными свойствами, что позволяет их использовать в дискриминантном анализе.
Алгебра кусочно-линейных функций (k-функций) и задач кусочно-линейного программирования может изучаться в рамках более общих конструкций, а именно, | в рамках -расширений
функциональных пространств. Речь идет об алгебраическом расширении фиксированного функционального пространства F0 , замкнутого относительно операции дискретного максимума.
Если F | указанное расширение, а F0 | пространство линейных функций, то F | пространство
кусочно-линейных функций; если F0 | класс квадратичных функций, то F | класс кусочноквадратичных функций и т.д.
Хотя кусочно-линейные функции и соответствующий аппарат для них имеют важное значение, тем не менее число работ, посвященных этим вопросам, незначительно. Отметим работы
[1]{[6], первая из которых содержит главу III под названием \Кусочно-линейные функции и
полиэдральные множества". В этой главе проводится довольно основательное исследование по
алгебре и геометрии класса кусочно-линейных функций.
1.
-расширения функциональных пространств
Пусть F0 | некоторое функциональное пространство с вещественным пространством X значений аргумента функций из F0 . Если ffj (x)gj2J F0 , то функция дискретного максимума
f (x) := max
f (x) может как принадлежать F0 , так и не принадлежать. Способ образования
j 2J j
функции f (x) назовем -операцией.
Речь пойдет о минимальном расширении пространства F0 до пространства F, обеспечивающего свойство -замкнутости
ffj (x)gj2J F =) max
f (x) 2 F:
(1.1)
j 2J j
В этой ситуации выполняется, очевидно, свойство линейной замкнутости
ffji j i 2 I; j 2 Ji g F =)
где i 2 R, i 2 I .
X
i2I
i max
f i 2 F;
j 2J j
i
(1.2)
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(проект 96{01{00116).
49
Минимальное -замкнутое расширение назовем -расширением. Из смысла такого расширения видно, что
+[
1
F =
Fk ;
k=0
nP
o
где Fk+1 =
i max
f i j f i 2 Fk ; i 2 R; i 2 I; j 2 Ji ; jI j < +1; jJi j < +1 .
j 2J j j
i2I
На самом деле все функции из F могут быть преобразованы к некоторому стандартному
виду. В основе такого преобразования лежит ряд тождеств, справедливых для произвольного
набора функций:
max
f + max
g = max (f + gi );
(1.3)
j 2J j
i2I i (j; i)2J I j
i
X
i2I
i max
f i = max
j 2J j s 2J
i
где I+ = fi j i > 0g, I; = fi j i < 0g;
max f
j =1;:::;m j
=
max f ; fm
j =1;:::;m;1 j
i
i
+
min f = ; i=1min
f ; fn
i=1;:::;n i
;:::;n;1 i
+
X
i2I+
i fsi ; max
s 2J
i
i
i
X
i2I;
ji jfsi ;
+ fm = fm ; j=1max
f + + j=1max
f;
;:::;m;1 j
;:::;m;1 j
+ i=1min
f = ; fn ; i=1min
f + + fn ;
;:::;n;1 i
;:::;n;1 i
max
f ; max
g + = (j;max
ff ; g g ; max
g;
j 2J j
i2I i
i2I i
i)2J I j i
max
f ; max
g = min
max (f ; gi ) = max
min (f ; gi ):
j 2J j
i 2I i
i2I j 2J j
j 2J i2I j
(1.4)
i
(1.5)
(1.6)
(1.7)
(1.8)
Выписанные тождества носят общелогический характер и проверяются непосредственно.
Наравне с F введем пространство
+[
1
H =
Hi ;
i=0
nP
o
где H0 = F0 , Hk+1 =
i fi+ j i 2 R; fi 2 Hk ; jI j < +1 .
i2I
Операция взятия положительной срезки \+" является частным случаем -операции, однако
она потенциально (т.е. многократно примененная) дает тот же класс функций F. Имеет место
Теорема 1.1. 1) Все функции из F могут быть приведены к любому из стандартных видов:
max
f ; max
g;
(1.9)
j 2J j
i2I i
min
max f i ;
(1.10)
i2I j 2J j
max
min f j ;
(1.11)
j 2J i2I i
i
j
где ffj ; gi ; fji g F0 ; (1.9) означает Fk = F1 при k > 1, следовательно, F = F1 .
2) Классы F и H совпадают.
3) Представления (1.9){(1.10) эквивалентны.
Доказательство. 1) Соотношение (1.9) означает совпадение Fk с F1 при k > 1. На самом
деле достаточно доказать F2 = F1 . В силу (1.4) можно ограничиться преобразованием функции
f (x) = max
f при ffigI F1 к виду (1.9). Пусть I = f1; : : : ; ng. Доказательство можно вести
i2I i
индукцией по n. Если n = 1, то f (x) = f1 (x) удовлетворяет требуемому свойству представления
(1.9). Пусть n > 1. Так как fi 2 F1 , то эти функции можно представить в виде
fi = max
f i ; max gi
j 2J j k2I k
i
i
50
при ffji ; gki g F0 . Имеем
f (x) (1=:5) i=1max
f ; fn + + fn:
;:::;n;1 i
По индукции i=1max
f =: f 2 F1 . Так как f = [f ; fn]+ + fn, причем ff; fn g F1 , то по (1.4)
;:::;n;1 i
f ; fn 2 F1 , а по (1.7) [f ; fn]+ 2 F1, что (с учетом fn 2 F1 ) и дает f 2 F1 . Итак, F2 = F1 , а
вместе с тем и F = F1 .
Представимость функций из F в виде (1.10) или (1.11) следует из тождества (1.8).
2) Докажем вначале включение H F1 , т.е. Hk F1 8 k. Если f 2 H1 , то в силу (1.4) f 2 F1 .
Следовательно, H1 F1 . Пусть Hk F1 , докажем Hk+1 F1 . Произвольная функция из Hk+1
имеет вид
X
f = i fi+; ffi g Hk F1 :
i2I
Из этого следует, что f представляется линейной комбинацией функций дискретного максимума
при образующих из F0 , что с учетом (1.4) и дает для f требуемое представление (1.9).
Обратно, если f 2 F, т.е. f имеет вид (1.9), то показав, что функция дискретного максимума
при образующих из F0 принадлежит H, т.е. некоторому Hk , тем самым покажем и f 2 H. Итак,
пусть
f = max
f ; ffj g F0 ; j = 1; : : : ; m:
j 2J j
Если m = 1, то f = f1 H0 . Пусть m > 1. Если по индуктивному предположению f =
max f 2 Hk , то в силу (1.5) f = [f ; fm]+ + fm 2 Hk+1 , что и требовалось.
j =1;:::;m;1 j
3) Мы уже отметили, что представление функции в форме (1.9) может быть переписано
в форме (1.10) при fji = fj ; gi (см. (1.8)). Нужно убедиться в обратном. Итак, пусть f =
min
max f i . Если I = f1; : : : ; ng и n = 1, то f = max
f 1 2 F1 . При n > 1 доказательство, как это
i2I j 2J j
j 2J1 j
и делалось выше, можно провести индукцией по n. По (1.6)
f = i=1min
max f i ; max f n + + max
f n:
;:::;n;1 j 2J j j 2J j
j 2J j
i
i
По индуктивному предположению
n
n
f = i=1min
max f i 2 F1 ;
;:::;n;1 j 2J j
i
т.е. f может быть представлено в форме (1.9), но тогда с использованием преобразований (1.3),
(1.4) и (1.7) функция f приводится к виду (1.9), что и требовалось.
Эквивалентность представлений (1.11) и (1.9) доказывается аналогично.
Функции f из F будем называть -функциями или -кусочными функциями. Если F0 |
пространство линейных (аффинных) функций, то F | пространство кусочно-линейных функций.
2. Кусочно-линейные функции
Кусочно-линейные функции | это -функции в ситуации, когда F0 | пространство линейных (аффинных) функций. К определению кусочно-линейных (в дальнейшем | k-функций)
можно подойти двояко: либо так, как это только что сделано, либо исходя из некоторой аксиоматики, идентифицирующей такие функции. Остановимся на втором подходе.
Пусть имеются конечные совокупности многогранников fMj gJ и собственных линейных
функций flj (x)gJ . Будем говорить, что система fMj ; lj (x)g задает однозначную кусочно-линейную
функцию l(x) на X, если:
S
1)
Mj = X; Mi0 T Mj0 = ; при i 6= j ;
j 2J
51
2) l(x) lj (x) 8 x 2 Mj ; 8 j 2 J .
Здесь Mj0 | алгебраическая внутренность многогранника Mj , т.е. y 2 Mj0 () y + ts 2 Mj при
любом s 2 X и достаточно малом t > 0. Термином многогранник, как и ранее, обозначается
множество, задаваемое конечной системой собственных линейных неравенств
(fj ; x) ; j 0; j 2 J:
В данном определении некоторые из многогранников Mj или Mj0 могут быть и пустыми.
Будем использовать обозначения: L0 | пространство аффинных функций, L | пространство k-функций, определенных внешним образом в силу свойств 1) и 2). Действительно, класс
функций L совпадает с классом F из предыдущего параграфа, который строится из F0 = L0 , т.е.
L | это минимальное алгебраическое расширение пространства аффинных функций, замкнутое относительно операций дискретного максимума [1]. Следовательно, представление (1.9) (а
также каждое из (1.10) и (1.11)) является универсальным представлением кусочно-линейных
функций (k-функций).
Для унификации и упрощения записи k-функций, систем неравенств из k-функций, задач
кусочно-линейного программирования и т.д. будем в дальнейшем полагать X = Rn , тогда
n
L0 = fl (x) = (a; x) ; j a 2 R ; 2 Rg;
L = max lj (x) ; max hi (x) j flj ; hi g L0 ; jJ j < +1; jI j < +1 :
j 2J
i2I
Введем обозначения:
jzjmax = max
z ; jz jmin = min
z;
(i) i
(i) i
где z | вектор конечномерного пространства. Если Ax ; b = [l1 (x); : : : ; lm (x)]T | вектор аффинных функций, то в соответствии с введенным обозначением будем иметь
jAx ; b jmax = max
l (x):
(i) i
Представления кусочно-линейных функций в виде (1.9){(1.11) принимают унифицированную
форму
jAx ; bjmax ; jBx ; djmax;
(2.1)
min
jAi x ; bijmax;
(2.2)
i
max
jAj x ; bj jmin:
(2.3)
(j )
Отметим также свойства функций дискретного максимума
jzjmax = ;jzjmin;
при > 0 : j z jmax = jz jmax ;
при < 0 : j z jmax = jz jmin :
3. Системы кусочно-линейных неравенств и их геометрическая
интерпретация
Конечная система k-функций может быть записана в виде
min
jAtj x ; bjt jmax 0; t = 1; : : : ; T;
(j )
или с помощью одного неравенства
T
X
t=1
min
jAtj x ; bjt jmax 0;
(j )
52
(3.1)
или (на основе теоремы 1.1) в виде
min jAj x ; bj jmax 0:
(3.2)
j =1;:::;m
Это задание будем считать одним из стандартных. Другим стандартным видом является
jAx ; bjmax ; jBx ; djmax 0
(3.3)
(см. (2.1)). Итак, произвольная конечная система кусочно-линейных неравенств может быть
приведена к любому из стандартных видов (3.1){(3.3).
Рассмотрим представление системы в виде (3.2). Положим Mj = fx j Aj x bj g. Тогда
m
S
множеством решений неравенства (3.2) будет M = Mj . С другой стороны, если M | проj =1
m
S
извольное полиэдральное множество, пусть из
т.е. M = Mj и Mj | многогранники,
j =1
которые задаются конечными системами линейных неравенств (Mj = fx j Aj x bj g), то M
является множеством решений неравенства (3.2).
С этой же точки зрения посмотрим на неравенство (3.3). Пусть
Ax ; b = [l1 (x); : : : ; lm (x) ]T ; Bx ; d = [s1 (x); : : : ; sk (x) ]T ;
k
flj (x); si (x)gm;
1; 1 L0
( L0 | пространство аффинных функций). Положим
Mi = fx j lj (x) si(x); j = 1; : : : ; mg:
n
R ,
s
S
Тогда, как легко видеть, Mi совпадает с множеством решений неравенства (3.3). Тем самым
i=1
для неравенства (3.3) указаны те многогранники Mi , объединение которых и дает множество
решений неравенства (3.3). С другой стороны, если полиэдральное множество M задано тем
или иным образом, например, как в предыдущем случае, | совокупностью систем линейных
неравенств, каждая из которых задает выпуклую многогранную компоненту множества M ,
то требуется цепочка тех или иных преобразований типа (1.3){(1.8), приводящая к заданию
множества M одним неравенством вида (3.3).
Наконец, рассмотрим систему кусочно-линейных неравенств в форме (3.1), формально более
сложную, чем (3.2) или (3.3). Положим
[
\
Mjt := fx j Atj x bjt g; Mt := Mjt ; M := Mt:
(j )
(t)
Множество Mt | это множество решений t-го неравенства в системе (3.1), так что M | множество решений всей системы.
Материал, изложенный в x 1{x 3, устанавливает способы конструктивного соответствия между полиэдральными множествами и их аналитическим заданием. Хотя сопутствующая этому
алгебра преобразований может быть достаточно громоздкой, тем не менее логика этих преобразований проста и может быть в реальных прикладных ситуациях поручена компьютеру.
4. Задача кусочно-линейного программирования
4.1. Предварительные замечания. Произвольной задаче кусочно-линейного программирования, т.е. задаче поиска экстремума k-функции при ограничениях в форме конечной системы
неравенств с k-функциями в левых частях, можно придать универсальный и простой вид
P : maxf(c; x) j=1min
jA x ; bj jmax 0; x 0g:
(4.1)
;:::;m j
Действительно, о способе сведения системы k-неравенств к одному k-неравенству уже говорилось. Если же f (x) | произвольная оптимизируемая, пусть максимизируемая, k-функция при
53
одном k-неравенстве, пусть g(x) 0 (возможно с x 0), то переписав задачу max ff (x)jg(x) 0g
в виде
max ft j g(x) 0; f (x) tg
и преобразовав систему из двух k-неравенств к одному k-неравенству, получим задачу поиска
максимума линейной функции при одном ограничении в форме k-неравенства. В (4.1) ограничение x 0 выделено для целей обеспечения симметрии в ряде аналитических конструкций,
рассматриваемых ниже.
Итак, объектом рассмотрения примем задачу (4.1). Введем частичную задачу
Lj : max f(c; x) j Aj x bj ; x 0g:
(4.2)
Связь между задачей (4.1) и Lj проста:
opt(4:1) = (jmax
opt Lj ;
(4.3)
:M 6=;)
j
где Mj = fx 0 j Aj x bj g. В (4.2) для некоторых j множества Mj = fx 0 j Aj x bj g
могут быть пустыми при свойстве разрешимости исходной задачи (4.1), т.е. произвольная
k-задача, будучи преобразована к виду (4.1), распадается на конечное число задач линейного
программирования, решив которые, тем самым находим решение и исходной задачи. Поскольку конструктивизм соответствующих преобразований обеспечен, то формально решение произвольной задачи кусочно-линейного программирования сводится к использованию отмеченного
конструктивизма и некоторого метода (напр., симплекс-метода) решения задачи ЛП.
4.2. Условия разрешимости k-задачи. Для k-задач выполняется ряд свойств и теорем, формулируемых в рамках теории линейного программирования. Некоторые из них являются следствиями теорем из ЛП, некоторые же требуют своих доказательств, по крайней мере, уточнений.
Не требует самостоятельного доказательства
Теорема 4.1 (о достижимости). Если
sup f(c; x) min
jAj x ; bj jmax 0; x 0g < +1;
(j )
то операция sup в этой задаче достижима.
Выпишем задачу, двойственную к Lj :
Lj : min f(bj ; uj ) j ATj uj c; uj 0g:
Пусть Mj = fuj 0 j ATj uj cg.
Теорема 4.2.
(4.4)
Задача (4.1) разрешима тогда и только тогда, когда
M=
m
[
j =1
Mj 6= ;
Mj 6= ; =) Mj 6= ;:
и
Поскольку условия Mj 6= ; и Mj 6= ; являются необходимыми и достаточными для разрешимости задачи Lj , то jmax
opt Lj конечен и является значением opt P . Обрат:M 6=;
но, если задача P разрешима, то все задачи Lj c Mj 6= ; разрешимы (т.е. ситуации opt Lj = +1
исключаются), а тогда в соответствии с теоремой двойственности в ЛП Mj 6= ;, что и требовалось.
Замечание 4.1. Другой вариант формулировки теоремы 4.2 состоит в эквивалентности
(P разрешима ) () (M 6= ; & Mj 6= ; =) Lj разрешима):
Доказательство.
j
54
4.3. Двойственность. Исходную k-задачу возьмем в форме (4.1), дополнив ее предположением (впрочем, несущественным): размерность векторов Aj x ; bj одинакова, т.е. число неравенств
в каждой из систем Aj x bj одно и то же. Введенное условие позволяет двойственную переменную для Lj , т.е. переменную uj в задаче (4.4) обозначать одним символом u. В соответствии
со сказанным задачу (4.4) перепишем в виде
min f(bj ; u) j ATj u c; u 0g; j = 1; : : : ; m:
(4.5)
Задачу
P : j:max
min f(bj ; u) j ATj u c; u 0g
(4.6)
M 6=;
j
будем рассматривать как двойственную к P . По отношению к форме задания P задача P не
симметрична, но если P переписать в эквивалентном виде
max min f(c; x) j Aj x bj ; x 0g;
(4.7)
j 21;m
то (4.6) и (4.7) принимают симметричный вид.
В отношении задачи (4.6) справедлива
Теорема 4.3. Задача (4.6) разрешима тогда и только тогда, когда
9 j 2 1; m : Mj 6= ; & Mj 6= ;:
(4.8)
Доказательство. Действительно, если J := fj j Mj 6= ;; Mj 6= ;g, то для j 2
= J : inf f(bj ; u) j
x 2 Mj g = ;1, поэтому в (4.6) максимум можно брать только по j 2 J . Этим и обеспечивается
разрешимость задачи P . Необходимость условий (4.8) очевидна: если P разрешима, то хотя
бы для одного j 0 задача Lj разрешима, что эквивалентно (4.8).
Из теорем 4.2 и 4.3, а также теоремы двойственности в ЛП вытекает
Теорема 4.4. Если задача (4.1) разрешима, то (4.6) также разрешима, при этом их оптимальные значения совпадают.
В ситуации задач P и P свойство одновременной их разрешимости или неразрешимости
в отличие от ЛП теряется. Принимая во внимание возможность несобственных оптимальных
значений, запишем эти задачи в виде
P : sup xinf
(c; x);
P : sup uinf
(bj ; u):
2M
2M (j )
(j )
j
и P
j
Условия одновременной разрешимости P
определяются теоремами 4.2 и 4.3, но возможна
и ситуация: P не разрешима, P разрешима. Это соответствует тому, что при разрешимости P 9 j0 : Mj0 6= ; & Mj0 = ;, т.е. задача Lj0 | несобственная 2-го рода. Так как в рассматриваемой
ситуации sup (c; x) = +1, то opt P = +1, т.е. P не разрешима. Одновременная неразрешиx2M 0
мость задач P и P реализуется на паре задач линейного программирования L и L , являющихся
несобственными 3-го рода.
j
5. Задача о седловой точке дизъюнктивной функции Лагранжа
Пусть fMj gm1 Rn и f (x) | произвольная функция, заданная на Rn . Запишем задачи
P\ : max f (x) j x 2
\
[
P[ : max f (x) j x 2
55
(j )
(j )
Mj ;
Mj :
(5.1)
Первую из них назовем задачей в конъюнктивной постановке, вторую | в дизъюнктивной.
Первая из постановок обычна для традиционных постановок задач математического программирования. Вторая из них отражает ситуацию кусочно-линейной задачи (4.1), которую можно
переписать в виде
[
max (c; x) j x 2 Mj
(j )
при Mj = fx j Aj (x) bj ; x 0g, j = 1; : : : ; m.
Рассмотрим задачу (5.1) при условиях
Mj = fx j Fj (x) 0; x 0g; Fj : Rn ! Rm ; j = 1; : : : ; m:
Зафиксируем схему соответствия задачам P\ и P[ их функций Лагранжа
j
P\ ! f (x) ;
m
X
j =1
(uj ; Fj (x)) = \ (x; u);
P[ ! f (x) ; min
(uj ; Fj (x)) = [(x; u)
(j )
(5.2)
| дизъюнктивная функция Лагранжа для P [ .
Задачу (5.1) назовем вполне регулярной, если каждая из задач
max ff (x) j Fj (x) 0; x 0g
(5:1j )
разрешима. Эквивалентом такой регулярности является разрешимость задачи и Mj 6= ;, j =
1; : : : ; m.
Используем в дальнейшем следующее обозначение: если экстремальной задаче приписан
номер t, то ее решение или множество решений будет обозначаться через arg(t), Arg(t) соответственно, а оптимальное значение | через opt(t).
Пусть j (x; uj ) = f (x) ; (uj ; Fj (x)) | функция Лагранжа для (5.1)j , x 2 Rn , uj 2 Rm .
Справедлива хорошо известная (напр., [7])
Лемма 5.1. Если точка [
x; u] 0 является седловой для функции Лагранжа (x; u) =
f (x) ; (u; F (x)), поставленной в соответствие задаче
j
max ff (x) j F (x) 0; x 0g;
(5.3)
то (u; F (x)) = 0 и x 2 Arg(5:3).
Лемма 5.2. Пусть каждая из функций j (x; uj ) обладает седлом [
xj ; uj ] 0, j = 1; : : : ; m.
Если x | такое значение xj , на котором достигается max
f (xj ), то
(j )
(x; u) f (x) 8x 0;
(5.4)
где (x; u) = f (x) ; min
(u ; F (x)).
(j ) j j
Согласно лемме 5.1 (uj ; Fj (xj )) = 0, j = 1; : : : ; m, и f (x) ; (uj ; Fj (x)) f (xj ) ( f (x)) 8 x 0. Отсюда
max
[f (x) ; (uj ; Fj (x))] f (x) ; min
(uj ; Fj (x)) = (x; u) f (x) 8 x 0: (j )
(j )
Доказательство.
Лемма 5.3.
Arg(5:1).
Если [x; u] 0 | седловая точка для (x; u), то min
(uj ; Fj (x)) = 0 и x 2
(j )
56
Доказательство.
В соответствии с определением седловой точки
(x; u) (x; u) (x; u);
8x0
или
8u0
f (x) ; min
(uj ; Fj (x)) f (x) ; min
(u ; F (x));
(j )
(j ) j j
8x0
f (x) ; min
(u ; F (x)) f (x) ; min
(u ; F (x)):
(j ) j j
(j ) j j
8u0
Соотношение (5.6) перепишем в виде
min
(u ; F (x)) min
(uj ; Fj (x)):
(j ) j j
(j )
8u0
(5.5)
(5.6)
(5.7)
Докажем, во-первых, x 2 M = Mj , т.е. j0 : Fj0 (x) 0. Если бы Fj (x) 6 0 8 j , то за счет
(j )
выбора u 0 можно было бы значение правой части в (5.7) сделать как угодно большим, что
будет противоречить соотношению (5.7). Доказанное дает := min
(u ; F (x)) 0. На самом
(j ) j j
деле, = 0. Если бы < 0, то соотношение (5.7) при u = 0 порождало бы противоречивое
неравенство 0 > ;jj 0. Итак, соотношение min
(u ; F (x)) доказано.
(j ) j j
Необходимо доказать оптимальность вектора x для (5.1), т.е. f (x) f (x) 8 x 2 M . Обратимся
к соотношению (5.5), которое можно теперь переписать в виде
f (x) ; f (x) ; min
(u ; F (x)):
(5.8)
(j ) j j
S
Если x 2 M , т.е. x 2 Mj0 при некотором j0 , то min
(u ; F (x)) 0, что в силу (5.8) дает f (x) ;
(j ) j j
S
f (x) 0 8 x 2 Mj .
(j )
Лемма 5.4.
Пусть задача (5.1), т.е.
L[ : max (c; x) j x 2
m
[
j =1
Mj ;
при Mj = fx j Aj x bj ; x 0g разрешима и Mj 6= ; 8 j (т.е. вполне регулярна). Тогда функция
L[ (x; u) = (c; x) ; min
(u ; Aj x ; bj ) обладает седлом [x; u], причем в качестве x и u = [u1 ; : : : ; um ]
(j ) j
выступают
x = arg max
(c; xj ); xj 2 Arg xmax
(c; x); uj 2 Arg umin
(bj ; u); j = 1; : : : ; m:
2M
2M (j )
j
Если показать, что := min
(uj ; Aj x ; bj ) = 0, то в силу леммы 5.2 левое
(j )
неравенство в определении седла для L[ (x; u) будет выполнено. Так как вектор x 0 удовлетворяет одной из систем Aj x bj , то 0. Покажем 0. Имеем
min
(u ; A x ; bj ) = min
[;(bj ; uj ) + (c; x) + (ATj uj ; c; x)] min
[(c; x) ; (c; xj )] 0:
j
(j ) j j
(j )
Доказательство.
Выше мы воспользовались соотношениями: ATj uj ; c 0; (bj ; uj ) = (c; xj ) | по теореме двойственности в ЛП; (c; x) (c; xj ) 8 j .
Остается показать выполнимость правого неравенства в определении седловой точки для
L[ (x; u), т.е.
L[ (x; u) 8u0 L[ (x; u):
С учетом = 0 выписанное неравенство принимает вид
0 ; min
(u ; A x ; bj ):
(5.9)
(j ) j j
8uj 0
57
Так как 8 j0 Aj0 x ; bj 0, то при любом u 0 min
(u ; A x ; bj ) 0, следовательно, (5.9)
(j ) j j
верно.
Из лемм 5.3 и 5.4 вытекает
j
Теорема 5.1. Если системы Aj x b , x 0, j = 1; : : : ; m, совместны, то задача (5.1)
разрешима тогда и только тогда, когда ее дизъюнктивная функция Лагранжа
L[ (x; u) = (c; x) ; min
(u ; A x ; bj )
(j ) j j
обладает седлом [x; u] 0, при этом
1) если L[ разрешима и xj 2 Arg Lj , uj 2 Arg Lj , x = arg max
(c; xj ), то [x; u] | седло;
(j )
2) если [x; u] | седло для L[ (x; u), то fx; uj g удовлетворяют всем соотношениям из 1).
Существование седловой точки [x; u] 0 функции (x; u), пусть в форме (5.5){(5.6), эквивалентно выполнимости соотношения
max
min (x; u) = min
max (x; u) = (x; u):
x0 u0
u0 x0
(5.10)
В игровой интерпретации двойственности в математическом программировании утверждения
типа теоремы 5.1 естественно давать через соотношение (5.1), а именно, справедлива
Теорема 5.2. Пусть задача (5.1) разрешима и Mj 6= ; 8 j . Тогда для x
2 Arg(5:1) существуют uj 0, j = 1; : : : ; m, такие, что вектор [x; u] будет удовлетворять соотношению (5.10)
при
(x; u) = L[(x; u) = (c; u) ; min
(u ; A x ; bj ):
(j ) j j
6. Метод точных штрафных функций для задачи
кусочно-линейного программирования
Общую задачу кусочно-линейного программирования в канонической постановке (4.1), т.е.
P[ : max f(c; x) j=1min
jA x ; bj j max 0; x 0g;
;:::;m j
(6.1)
можно привести к эквивалентной задаче этого же типа, но со снятием основного ограничения в
(6.1). Поставим задаче L[ в соответствие k-задачу
sup (c; x) ; min
(Rj ; (Aj x ; bj )+ ) ;
(j )
x0
(6.2)
где Rj | неотрицательный векторный параметр размерности mj , т.е mj | число неравенств в
системе Aj x ; bj 0.
Как и в предыдущем параграфе, будем использовать следующие обозначения: Lj | это
задача max f(c; x) j Aj x bj ; x 0g, Lj | двойственная к ней, uj = arg Lj , u = [u1 ; : : : ; um ],
Mj = fx 0 j Aj x bj g.
Теорема 6.1. Пусть задача (6.1) разрешима, Mj 6= ; 8 j ; u
j 2 Arg Lj . Если Rj R0 uj ,
R0 > 1, то оптимальные значения и оптимальные множества задач (6.1) и (6.2) совпадают,
т.е.
opt(6:1) = opt(6:2);
Arg(6:1) = Arg(6:2):
58
(6.3)
(6.4)
Доказательство. Обозначим целевую функцию в (6.2) через R (x), а вычитаемую из (c; x)
часть | через 0 (x). Докажем вначале равенство (6.3). Для x 2 Arg(6:1) получаем R (x) =
(c; x) = opt(6:1), следовательно, opt(6:2) = sup R (x) opt(6:1).
x0
Докажем обратное неравенство. По леммам 5.4 и 5.3
(c; x) ; min
(uj ; Aj x ; bj ) (c; x) 8 x 0:
(j )
С учетом этого неравенства оценим R (x) для x 0
R(x) (c; x) + min
(u ; Aj x ; bj ) ; 0 (x) (j ) j
opt(6:1) + min
(u ; (Aj x ; bj )+ ) ; 0 (x) opt(6:1) + R1 (Rj ; (Aj x ; bj )+ ) ; 0 (x) =
(j ) j
0
R
0;1
= opt(6:1) ; R min
(Rj ; (Aj x ; bj )+ ) opt(6:1): (6.5)
(j )
0
Отсюда sup R (x) opt(6:1). Таким образом, равенство (6.3) доказано. Из него, в частности,
x0
следует включение Arg(6:1) Arg(6:2), что позволяет, на самом деле, в задаче (6.2) вместо sup
писать max. Докажем обратное включение. Пусть x 2 Arg(6:2). Согласно (6.5) имеем
opt(6:1) = (x) opt(6:1) ; R0 ; 1 min (R ; (A x ; bj )+ ):
R
R0
(j )
j
j
Отсюда вытекает min(j) (Rj ; (Aj x ; bj )+ ) = 0; а потому 9 j0 : (Rj0 ; (Aj0 x ; bj0 )+ ) = 0, что ввиду
m
Rj0 > 0 дает Aj0 x bj0 . Следовательно, x 2 Mj0 M = S Mj . Допустимость вектора x для
j =1
задачи (6.1) вместе с (c; x) = opt(6:1) означает x 2 Arg(6:1), а потому и Arg(6:2) Arg(6:1).
Доказательство равенства (6.4) также завершено.
Конструкция доказательства может быть повторена для более общей ситуации, а именно
для задачи (5.2) и эквивалентной редукции ее к задаче
+ (x)):
sup f (x) ; min
(
R
;
F
(6.6)
j
j
(j )
Справедлива
x0
Теорема 6.2. Пусть каждая из задач max ff (x) j Fj (x) 0; x 0g обладает седлом [
xj ; uj ].
Тогда при Rj > R0 uj , R0 > 1, задачи (5.2) и (6.6) эквивалентны в смысле совпадения их оптимальных значений и оптимальных множеств.
Действительно, в соответствии с леммой 5.3 можно выписать неравенство
f (x) f (x) + min
(u ; F (x)) 8 x 0;
(j ) j j
а далее все повторить в соответствии с выкладками (6.5).
7. Вопросы полиэдральной разделимости
Задача разделимости непересекающихся множеств M и N из некоторого пространства X с
помощью функции f (x) из фиксированного класса F0 называется дискриминацией множеств.
Функция f (x) в этом случае называется дискриминантной. Разделимость состоит в выполнимости неравенств
f (x) > 0 8 x 2 M ; f (y) < 0 8 y 2 N:
(7.1)
Можно говорить и о нестрогой разделимости, когда в (7.1) допускаются нестрогие неравенства.
59
Если M и N | выпуклые многогранники, а F0 | класс аффинных функций, то говорят о
задаче линейной дискриминации. Задача линейной дискриминации является одной из важнейших задач в распознавании образов (РО). В качестве одной из базовых формальных моделей
РО является система строгих линейных однородных неравенств. Убедимся в этом.
Пусть G и L | некоторые образы, A = faj g Rn и B = fbi g Rn | формализованные
выборки представителей этих образов. Если ffs (x)gk1 | некоторый базовый набор функций (воk
P
обще говоря, произвольный), то разделяющую функцию можно искать в виде f (x) = zs fs (x),
s=1
где fzs g | числовые коэффициенты. Свойство разделимости состоит в выполнимости системы
неравенств
k
X
или в матричном виде
s=1
k
X
zs fs(aj ) > 0 8 j ;
s=1
zs fs (bi ) < 0 8 i;
Az > 0; Bz < 0;
(7.2)
где A := [ajs ], ajs := fj (as ); B := [bis ], bis := fs (bi ).
k
P
Если z = [z1 ; : : : ; zk ] | некоторое решение системы (7.2), то функция f (x) = zs fs (x) будет
s=1
строго разделяющей множества A и B . Дискриминантная функция f (x) реализует соотнесение
(по свойству принадлежности одному из образов G и L) предъявляемого для распознавания
вектора y по правилу
y 2 G ; если f (y) > 0; y 2 L; если f (y) < 0:
Функция f (x) реализует решающее правило. Система (7.2) может быть как совместной, так
и несовместной. На случай несовместности имеется обобщение понятия решения как конечной
совокупности векторов fcl g Rn (именуемой комитетным решением) такой, что любое из
неравенств системы (7.2) удовлетворяется более чем половиной векторов этой совокупности.
Комитетная технология и ее использования в задачах распознавания составляют важное и хорошо разработанное направление в распознавании
образов [8].
T
Если M и N | многогранники, причем M N = ;, то эти множества строго разделяются аффинной функцией. Ниже речь пойдет о разделимости произвольных непересекающихся
полиэдральных множеств
кусочно-линейной
функцией (k-функцией).
S
S
Итак, пусть M = Mj , N = Ni , fMj g и fNi g | конечные совокупности выпуклых
(j ) T
(i)
многогранников, причем M N = ;. Имеет место
Теорема 7.1. Полиэдральные множества M и N с пустым пересечением строго разделяются k-функцией, т.е. функцией вида (2.2)
f (x) = min jAj x ; bj jmax :
(7.3)
j 21;m
Полиэдральное множество может быть задано одним k-неравенством:
если
и Ni = fx j Bi x di g, то
M = fx j f (x) 0g;
где f (x) | функция (7.3);
N = fx j g(x) 0g;
i
где g(x) = max
jBi x ; d jmin. Учитывая соотношения: XnM N , XnN M , при любых > 0 и
(i)
> 0 будем иметь
f (x) + g(x) < 0 8 x 2 M ; f (y) + g(y) > 0 8 y 2 N:
Доказательство.
Mj = fx j Aj x bj g
60
Таким образом, построена функция f; (x) := f (x)+ g(x), зависящая от числовых параметров
> 0 и > 0, строго разделяющая полиэдральные множества M и N .
n
n
n
Следствие 7.1. Пусть R faj gj 2J и R fbi gi2I | конечные совокупности точек из R ,
T
при этом faj g fbi g = ;. Тогда существует k-функция f (x), строго разделяющая эти множества,
т.е.
f (aj ) < 0 8 j 2 J ; f (bi) > 0 8 i 2 I:
Действительно, поскольку точка из Rn может быть задана конечной системой линейных
неравенств (если x = [x1 ; : : : ; xn ], то x = fx j x x xg), то сформулированное следствие превращается в частный случай теоремы 7.1. На самом деле, в данном следствии пространство, из
которого берутся точки, может быть произвольным. Сведение к конечномерному арифметическому пространству тривиально: достаточно
взять подпространство Ek исходного пространства,
S
натянутое на совокупность faj gj2J fbi gi2I , выделить его базис, в котором векторы aj и bi будут представлены точками конечномерного арифметического пространства. Если взять прямое
разложение X = Ek + H, то k-функция f (x), разделяющая указанные совокупности точек в Ek ,
может быть продолжена до k-функции f(x), определенной на всем пространстве X, по правилу:
если x 2 X и x = x + h, x 2 Ek , h 2 H, то f(x) = f (x).
Литература
1. Плотников С.В. Методы проектирования в задачах нелинейного программирования. Дисс. : : :
канд. физ.-матем. наук. { Свердловск: УрГУ, 1983. { С. 83{118.
2. Волокитин Е.П. О представлении непрерывных кусочно-линейных функций // Управляемые
системы. { Новосибирск: Наука, 1979. { Є 19. { C. 14{21.
3. Meltzer D. On the expressibility of piecewise linear continuous functions as the dierence of two
piecewise linear convex functions // Math. Program., Study 29. { 1986. { P. 118{134.
4. Kripfganz A., Schulze R. Piecewise ane functions as a dierence of two convex functions //
Optimization. { 1987. { V. 18. { Є 1. { P. 23{29.
5. Benchekroun B. A nonconvex piecewise linear optimization problem // Computers Math. Applic.
{ 1991. { V. 21. { Є 6 / 7. { P. 77{85.
6. Gorokhovik V.V., Zorko O.I. Piecewise ane functions and polyhedral sets // Optimization. { 1994.
{ V. 33. { P. 209{221.
7. Исследования по линейному и нелинейному программированию / Под ред. K.Дж. Эрроу,
Д. Гурвица, Х. Удзавы. { M.: Иност. Лит., 1962. { 298 c.
8. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. { M.: Наука,
1990. { 246 c.
Институт математики и механики
Уральского отделения
Российской Академии Наук
Поступила
22.08.1997
61
Документ
Категория
Без категории
Просмотров
7
Размер файла
233 Кб
Теги
кусочно, вопрос, некоторые, линейного, программирование
1/--страниц
Пожаловаться на содержимое документа