jadan (1)

понятия как вершина,ребро и т.д.Пусть множество индексов J = [1 : m] разбито на два непересекающиеся подмножества J1 и J2.Пусть,кроме того, A1 подматрица матрицы A, составленная из строк с номерами из J1, a A2 подматрица матрицы A,составленная из строк с номерами из J2.В соответствии с разбиением матрицы A разобьем также вектор правых частей b на два подвектора b1 и b2.Тогда систему равенств и неравенств

A1x = b1, A2x ≤ b2

(51)

принято называть k-граничной,если множество J1 состоит из k индексов и все строки в матрице A1 (их число также равно k)линейно независимы.Если множество решений

X(J1) системы(51)не пусто,то оно называется	k-гранью полиэдрального и,что одно и то
же,многогранного множества решений X системы(50).Важный результат состоит в том,
что если система(50)совместна и имеет ранг	r > 0,то для любого 0 < k ≤ r существует
k-грань.Убедимся в этом.

Определение29. Неравенство cT x ≤ d, где c Rn, d R, называется следствием си - стемы неравенств Ax ≤ b (или системы уравнений Ax = b),если любое решение системы удовлетворяет также и нему.

Лемма9. Пусть ai Rn, 0 ≤ i ≤ m и A m × n матрица,строками которой являются последние m векторов ai, 1 ≤ i ≤ m.Пусть,кроме того,для некоторых b0 R и b = [b1, . . . , bm] система

Ax = b, a0T x ≤ b0

(52)

совместна.Тогда для того,чтобы неравенство aT0 x ≤ b0 являлось следствием системы

Ax = b,	(53)
необходимо и достаточно,чтобы
a0 = AT y	(54)

для некоторого y Rm.

Доказательство. Достаточность.Покажем,что если выполнено(54),то любое решение системы(53)удовлетворяет неравенству aT0 x ≤ b0.Возьмем некоторое решение x1 системы(52),оно одновременно является и решением системы уравнений(53).Поэтому произвольное решение xø системы(53)может быть представлено как xø = x1 + x2, где x2произвольное решение однородной системы Ax = 0m.Подставляя это решение системы (53)в неравенство aT0 x ≤ b0 и учитывая(54),получаем

a0, xø = AT y, x1 + x2 = y, Ax1 = AT y, x1 = a0, x1 .

Но x1 есть решение общей системы(52),поэтому aT0 xø = aT0 x1 ≤ b0.Отсюда приходим к выводу,что произвольное решение xø системы(53)удовлетворяет одновременно и неравенству aT0 x ≤ b0.

41

Необходимость.Предполагаем,не умаляя общности,что векторы	a1, . . . , am линейно
независимы.Если допустить,что равенство(54)не выполняется,т.е.вектор		a0 не является
линейной комбинацией векторов a1, . . . , am,то система линейных уравнений
Ax = b, a0, x = d
имеет решение xø для любых b и d.Поэтому,беря d > b0,получаем,что это решение xø удо-
влетворяет системе(53),но не удовлетворяет неравенству a0T x ≤ b0.Таким образом,данное

неравенство не является следствием системы(53),что противоречит условиям леммы.

Теорема22. Пусть система(50)совместна и ее ранг равен r > 0. Тогда для любого 0 < k ≤ r существует k-грань.

Доказательство. проведем индукцией по k.Возьмем сначала k = 1.Предположим,

что точка x1 удовлетворяет системе(50),а			x2 не удовлетворяет.Пусть
÷			J : aj, x2 > bj}
J(x2) = {j
и пусть
λj(x1, x2) = min {λ [0, 1] : aj, xλ ≤ bj,				xλ = λx1 + (1 − λ)x2} ,				÷
								j J(x2).
Обозначим	(x , x	) = min			(x , x	),
λ				λ
	1 2		÷	j	1 2
			j J(x2)
J÷ (x2) = j J÷(x2) : λj(x1, x2) = λ (x1, x2) .
÷							÷
Множество J (x2) не пусто.Выберем произвольный индекс							j1 J (x2) и положим :J1 =
{j1}, J2 = J \ J1.Тогда,если рассмотреть систему
	aj, x = bj,			j J1,				(55)
	aj, x ≤ bj, j J2,

то точка x = λ x1 + (1 − λ )x2, где λ = λ (x1, x2),удовлетворяет этой системе,т.е.эта система является 1-граничной для системы(50),а множество ее решений есть 1-грань.

Предположим теперь,что утверждение теоремы доказано для k < r и покажем,что

найдется (k+1)-грань.С этой целью возьмем произвольную k-грань,существование которой
следует из предположения индукции.Она совпадает с множеством решений некоторой	k-
граничной системы вида(55),в которой множество индексов J1 содержит k индексов из J,
причем векторы aj, j J1,линейно независимы.Пусть x1 принадлежит этой k-грани,а	x2
решение системы уравнений

aj, x = bj, j J1,	(56)
не являющейся решением всей системы(55).Такая точка	x2 обязательно найдется,так как

иначе каждое из неравенств aj, x ≤ bj, где j J2,было бы следствием системы(56).Но

42

тогда по лемме9каждый вектор aj, j J2,был бы представим в виде линейной комбинации векторов aj, j J1 и следовательно ранг системы Ax ≤ b равнялся бы k,что противоречит предположению k < r.

Далее поступаем аналогично первому случаю,когда k = 1,но только множество индек-

сов ÷( ) формируем теперь не из ,а из подмножества индексов .Беря теперь индекс

J x2 J J2

÷ ( ) и добавляя его в множество ,получаем,что новая система векторов , , j1 J x2 J1 aj j J1

остается линейно независимой и соответствующая точка x удовлетворяет системе(55),в которой множество J1 содержит уже k + 1 индекс.Таким образом,эта система определяет (k + 1)-грань.

Если система(50)имеет ранг r > 0,то ее r-грани называются минимальными.В случае ранга r ≥ n − 1,если (n − 1)-грань не является точкой,то она называется ребром.Геометрически ребро может быть отрезком,лучом или прямой.Для системы полного ранга, когда r = n, вводится понятие вершины.Вершина это n-грань.Любая вершина является крайней точкой многогранника решений системы(53),т.е.не существует принадлежащего этому многограннику отрезка положительной длины такого,что данная точка является серединой этого отрезка.

Альтернативные системы.Наряду с системами линейных неравенств большой инте-

рес представляют общие системы линейных равенств и неравенств:

A1x = b1, A2x ≤ b2,

(57)

в которых A1 Rm1×n, A2 Rm2×n, b1 Rm1 , b2 Rm2 .Системы(50)или(57)называются неоднородными,если правые части в них ненулевые.В противном случае они называются однородными.Встает вопрос,когда системы вида(50)или(57),а также всевозможные их частные случаи имеют решение и каковы должны быть условия,которые гарантировали бы существование решения таких совместных систем.Сначала будем предполагать,что рассматриваемые нами системы неоднородны.

Один из возможных подходов состоит в использование так называемых теорем об альтернативах.Поясним его основную идею на примере простейшей линейной неоднородной системы уравнений Ax = b, где A m × n матрица, b = 0m.Понятно,что данная система имеет решение тогда и только тогда,когда вектор b принадлежит пространству столбцов матрицы A.Обозначим это пространство через L.Если b L,то проекция вектора b на ортогональное дополнение L пространства L должна быть равна нулю.Но ортогональное дополнение L имеет вид L = y Rm : AT y = 0n .

Поэтому система уравнений будет иметь решение тогда и только тогда,когда для любого y Rm такого,что AT y = 0n,выполняется bT y = 0.

Приведенный результат можно представить в несколько иной форме,а именно,в виде теоремы об альтернативах.

43

Теорема23. (Фредгольма).Пусть A матрица размера m × n и b Rm. Тогда если неоднородная система

Ax = b	(58)
совместна,то система
AT y = 0n, bT y > 0	(59)

несовместна и наоборот,если система(59)совместна,то система(58)несовместна.

Доказательство. Действительно,если система(58)имеет решение,то как уже говорилось выше,вектор b L,и следовательно bT y = 0 для всех y L .Поэтому неравенство bT y > 0 не выполняется ни для одного y из L .С другой стороны,если система(59)не имеет решения,то это возможно только в том случае,когда b L.Но тогда система(58) обязательно имеет решение.

Обратное утверждение,что система(59)имеет решение тогда и только тогда,когда система(58)не имеет решения,доказывается аналогично.

Разумеется,требование bT y > 0 в(59)может быть заменено на bT y < 0.Знак здесь не играет роли,важно только,чтобы bT y = 0.Обратим также внимание на то,что пространство столбцов L матрицы A,как всякое линейное подпространство,есть выпуклый конус, а его ортогональное дополнение L согласно утверждению9 сопряженный к L конус.

Аналогичные результаты могут быть получены для систем линейных неравенств,а также для совместных систем равенств и неравенств.Приведем их для некоторых частных случаев.

а). Рассмотрим задачу нахождения решения той же системы линейных уравнений(58) при дополнительном предположении,что x ≥ 0n.По прежнему предполагаем,что система (58)неоднородна.Нетрудно видеть,что беря x ≥ 0n,мы будем получать в левой части(58) точки Ax,принадлежащие конусуpos A.Поэтому данная система Ax = b, x ≥ 0n может иметь решение тогда и только тогда,когда вектор b posA.Возьмем конус,сопряженный к конусуpos A.Согласно(37)он имеет вид

(posA) = y Rm : AT y ≥ 0n .T	y ≥ 0,для всех	(60)
Но если b posA,то,по определению сопряженного конуса b		y (posA) .

Если же вектор b не принадлежитpos A,то обязательно найдется такой вектор y из (posA) , для которого bT y < 0.Отсюда делаем вывод,что система(58)имеет неотрицательное ре-

шение тогда и только тогда,когда для любого	y	R	n такого,что	AT y	≥	0 выполнялось
бы bT y ≥ 0.						n
Придадим этому результату иную формулировку в виде теоремы об альтернативах.
Теорема24. (Фаркаша-Минковского).Пусть		A матрица размера m × n и b Rm,
b = 0m.Тогда если неоднородная система
Ax = b,	x ≥ 0n

44

совместна,то система

AT y ≥ 0n, bT y < 0

несовместна и наоборот.

Теорему Фаркаша-Минковского24довольно часто ее называют леммой или теоремой Фаркаша.Она играет очень важную роль при доказательстве условий оптимальности различных оптимизационных задач и допускает другие формулировки.

б). Рассмотрим далее неоднородную систему Ax ≤ b, x ≥ 0n.Из ее вида следует,что она имеет решение тогда и только тогда,когда вектор b принадлежит конусу K = posA + Rm+ . Обратимся к сопряженному конусу K .На основании утверждения10 K = (posA) ∩(Rm+ ) . Но (Rm+ ) = Rm+ , а конус (posA) ,как мы уже знаем,имеет вид(60).Поэтому

K = y Rm+ : AT y ≥ 0m .

Включение b K будет выполняться тогда и только тогда,когда b, y ≥ 0 для всех y K . Отсюда приходим к условию разрешимости системы Ax ≤ b, x ≥ 0n,а именно,она разрешима в том и только том случае,когда b, y ≥ 0 для любого y ≥ 0m,удовлетворяющего неравенству AT y ≥ 0m.Сформулируем теперь данный результат в виде теоремы об альтернативах

Теорема25. Пусть A матрица размера m × n и b Rm, b = 0m. Тогда если неоднородная система

Ax ≤ b, x ≥ 0n

совместна,то система

AT y ≥ 0m, y ≥ 0m bT y < 0

несовместна и наоборот.

в). Опустим теперь теперь в предыдущей системе Ax ≤ b, x ≥ 0n требование x ≥ 0n,т.е. рассмотрим систему неравенств Ax ≤ b.Пусть L линейное подпространство,порожденное столбцами матрицы A.Несложно понять,что данная система неравенств будет иметь решение тогда и только тогда,когда вектор b принадлежит конусу K = L+Rm+ .А он(вектор b) в

свою очередь будет принадлежать K тогда и только тогда,когда

b, y

≥

0 для всех y

K .

K = L

(

m

) .

Сопряженный к K конус опять же на основании утверждения10равен

∩

R+

m

Но L согласно утверждению9совпадает с L , а конус R+ ,как уже отмечалось,является

самосопряженным,т.е. (R+m) = R+m.Имеем L =

y Rm : AT y = 0n .Отсюда следует,

что система неравенств

Ax b

разрешима в том

и только том

случае,когда

b, y

0

≤

≥

T

для любого y ≥ 0m,удовлетворяющего условию A

y = 0n.Снова переформулируем этот

результат в виде соответствующей теорем об альтернативах.

Теорема26. (Гейла).Пусть

A матрица размером m × n и b Rm, b = 0m. Тогда

если неоднородная система

Ax ≤ b

45

соместна,то система

AT y = 0m, y ≥ 0m bT y < 0

несовместна и наоборот.

г). Если обратиться теперь к однородным системам вида(50)или(57),то все они заведомо имеют тривиальное решение x = 0n.Поэтому интерес вызывают те случаи,когда существуют нетривиальные решения однородных систем.

Теорема27. (Гордана).Пусть

A матрица размера m × n.Тогда если однородная

система

Ax = 0m,

x ≥ 0n,

x = 0n

(61)

совместна,то система

AT y < 0n

(62)

несоместна и наоборот.

Доказательство. Предположим сначала,что система(61)имеет решение

xø.Тогда,если

допустить,что и

система(62)имеет решение

yø,то обязательно вектор yø = 0

. Умножая обе

T

yø <

0n на xø

T

и учитывая,что xø = 0n,получаем:

T m

=

Ax,ø yø < 0.

части неравенства A

x,ø A yø

Но Axø = 0m,поэтому x,ø

A

T

yø = 0.Мы пришли к противоречию.Поэтому система(62)не

имеет решения.

С другой стороны,предположим,что система(62)имеет решение.Тогда очевидно имеет

решение система

AT y ≤ −e,

(63)

где e n-мерный вектор,состоящий из единиц.Но тогда по теореме26у системы

n

x ≥ 0,

i

Ax = 0m,

e, x =

xi > 0.

(64)

=1

не существует решения.Система(64)полностью эквивалентна системе(61).

Теорема28. (Вилля).Пусть

A матрица размером m × n.Тогда если однородная

система

Ax ≤ 0m,

x ≥ 0n,

x = 0n

(65)

совместна,то система

AT y > 0n,

y ≥ 0m

(66)

несоместна и наоборот.

Доказательство. Рассмотрим сначала случай,когда система(65)имеет решение.Пусть xø ее решение.Покажем,что система(66)в этом случае решения не имеет.От противного, пусть существует yø,удовлетворяющий(66).Тогда после умножения левой и правой части неравенства AT y > 0n на xøT получаем с учетом того, xø ≥ 0n, xø = 0n,неравенство

46

x,ø AT yø > 0. Но Axø ≤ 0m, yø ≥ 0m,поэтому Ax,ø yø = x,ø AT yø ≤ 0. Мы получили два противоречивых неравенства.Поэтому система(66)неразрешима.

Сдругой стороны,пусть у системы(66)существует решение.Тогда существует решение

усистемы AT y ≥ e, y ≥ 0m, где e n-мерный вектор,состоящий из единиц.Переписывая эту систему систему в виде

−AT e ≤ −e, y ≥ 0m

и применяя теорему24,получаем,что система

n
i
Ax ≤ 0m, x ≥ 0m, e, x =	xi > 0	(67)
=1
не имеет решения.Система(67)эквивалентна системе(65).

д). Рассмотрим теперь случай,кода однородная система не только имеет нетривиальное

решение,но это решение таково,что	x > 0n.
Теорема29. (Штимке).Пусть	A матрица размером m × n.Тогда если однородная
система	Ax = 0m,	x > 0n	(68)
совместна,то система		AT y = 0n
AT y ≥ 0n,			(69)
несовместна и наоборот.
Доказательство. В случае,когда система(68)имеет решение			xø,предполагая,что

и система(69)также имеет решение yø,получаем после умножения левой и правой ча-

сти	неравенства AT yø			≥	0	на xøT , что	x,ø AT yø > 0.Но с другой стороны,согласно(68),
		T			n
x,ø A			yø = Ax,ø yø = 0.Данное равенство противоречит предыдущему неравенству.Таким

образом,система(69)неразрешима.

Обратно,пусть система(69)имеет решение.Тогда можно указать ненулевой вектор b Rm+ такой,что система AT y ≥ b также имеет решение.Поэтому по теореме26система

Ax = 0m, x ≥ 0n, bT x > 0,

не имеет решения.Но тогда заведомо не имеет решение и система(68),поскольку из неравенства x > 0n следует выполнение пары неравенств x ≥ 0n, bT x > 0.

Отметим,что размерности переменных в альтернативных системах могут отличаться друг от друга.Поэтому,если размерность вектора x в исходной системе очень большая,а размерность вектора y в альтернативной системе,напротив,гораздо меньше размерности y,то в ряде случаев целесообразно обратиться к решению альтернативной системы.Хотя может оказаться,что она заведомо не имеет решение,но в ней найдено решение,минимизирующее"невязку,то по специальным формулам можно определить решение исходной системы.Если же окажется,что в альтернативной системе"невязка"равна нулю,то это означает,что исходная система не имеет решения.

47

1.1.7.Линейные матричные неравенства

Наряду с различными линейными системами неравенств большую роль,особенно в теории управления,играют линейные матричные неравенства.Под линейным матричным неравенством относительно неизвестных переменных x = [x1, x2, . . . , xm] понимается неравенство вида

	m
	i
F (x) = B +	xiAi 0,	(70)
	=1

где B и Ai, 1 ≤ i ≤ m, -симметричные матрицы порядка n.Запись F (x) 0 означает,что суммарная матрица F (x) должна быть положительно определенной.Сама матрица F (x)

зависит от x аффинным образом.

Наряду со строгим неравенством(70)рассматривают также и нестрогое неравенство

F (x) 0,

(71)

в котором от матрицы F (x) уже требуется,чтобы она была положительно полуопределенной.Множество точек x,удовлетворяющих как строгому неравенству(70),так и нестрогому неравенству(72),как нетрудно проверить,является выпуклым.

Если матрица B и все матрицы Ai, 1 ≤ i ≤ m,диагональные,неравенства(70)и(72) переходят в обычные линейные неравенства.

Если у нас есть несколько линейных матричных неравенств,например,

F1(x) 0, F2(x) 0, . . . , Fk(x) 0,

то они могут записаны также в виде одного ограничения(70),если положить

F (x) = Diag (F1(x), F2(x), . . . , Fk(x)) 0,

где через Diag(F1, . . . , Fk) обозначена блочная диагональная матрица с блоками F1, . . ., Fk на диагонали,так что форма(70)для представления линейных матричных неравенств в виде одного неравенства не является ограничительной.

Важность линейных матричных неравенств состоит также в том,что к ним формально могут быть сведены и некоторые нелинейные матричные неравенства.Рассмотрим линейное матричное неравенство с матрицей F (x) блочного вида

F (x) =	ST (x)	R(x)	0,	(72)
	Q(x)	S(x)

где Q(x) и R(x) симметричные матрицы и все матрицы,входящие в блочную матрицу F (x), как Q(x) и R(x), так и S(x),зависят от x Rm аффинным образом.

Если Q(x) 0, то F (x) 0 тогда и только тогда,когда

R(x) − ST (x)Q−1(x)S(x) 0

(73)

48

x 2

(справедливость этого условия доказывается в следующем параграфе).Матрица,стоящая в левой части этого неравенства,называется дополнением по Шуру матрицы Q(x) в матрице

F (x).

Таким образом,если у нас есть нелинейная система матричных неравенств

Q(x) 0, R(x) − ST (x)Q−1(x)S(x) 0,

(74)

(нелинейным здесь является второе неравенство),то формально она может быть записана как линейное матричное неравенство(72).Система(74)эквивалентна неравенству(72). Отсюда,в частности,следует,что множество решений системы(74)выпукло.

Пример.Пусть Z(x) матрица размера m × n,аффинным образом зависящая от вектора x,и пусть требуется,чтобы норма этой матрицы была бы меньше единицы,т.е. чтобы выполнялось

Z(x) ≤ 1,

(75)

где Z норма матрицы Z,подчиненная евклидовым нормам в соответственно пространствах Rn и Rm,т.ею

Z = sup Zx 2 .

x Rn

Если обратиться к линейному матричному неравенству
Im	Z(x)	0,
ZT (x)	In
то,в силу вышесказанного,оно будет выполняться,когда
In − ZT (x)Z(x) 0.
Нетрудно видеть,что данное неравенство эквивалентно(75).
Часто встречаются неравенства,где переменными являются матрицы,например,			нера-
венство А.М.Ляпунова
G(X) = QT X + XQ 0,			(76)

где Q и X квадратные матрицы порядка n, матрица X симметричная.Запись G(X) 0 означает,что матрица G(X) должна быть отрицательно определенной.

Неравенство(76)появляется,например,при исследовании устойчивости тривиального положения равновесия y (t) ≡ 0n следующего линейного дифференциального уравнения

	dy	= Qy,	(77)
	dt

где Q матрица с постоянными элементами.

Пусть мы хотим узнать является ли данное положение равновесия асимптотически устойчивым или нет.Выяснить этот вопрос можно,если воспользоваться положительно

49

определенной функцией Ляпунова,т.е.такой функцией v(y), которая равна нулю в начале координат(точке 0n)и строго положительна в некоторой окрестности 0n.Предположим, что функция v(y) является непрерывно дифференцируемой.Тогда тривиальное положение равновесия y (t) ≡ 0n будет асимптотически устойчивым,если выяснится,что полная производная по времени функции v(y),вычисленная вдоль траекторий системы(77),в окрестности 0n удовлетворяет неравенству

	dV (y(t))					dy
vú(y) =				= vy(y),			< 0, y = 0n.		(78)
	dt					dt
Попытаемся строить v(y) в виде квадратичной функции
		v(y) = y, Xy ,							(79)
где от матрицы X потребуем,чтобы она была симметричной положительно определенной.
Подставляя функцию(79)в(78),приходим к следующему неравенству
	vú(y) = y,ú Xy + y, Xyú < 0
или с учетом(77)	y, QT X + XQ y < 0.								(80)
Неравенство(80)заведомо будет выполняться					,если			симметричная матрица	QT X + XQ

является отрицательно определенной,т.е.для нее выполняется матричное неравенство вида

(70).

Чтобы придать(80)форму линейного матричного неравенства(70),возьмем некоторый

базис в пространстве Sn симметричных матриц порядка n:
X1, X2, . . . Xm.	(81)

Пространство Sn является конечномерномерным и его размерность равна так называемому "треугольному числу"k (n) = n(n + 1)/2,стало быть для числа m в(81)имеем m = k (n). Тогда полагая

B = 0nn, , Ai = −QT Xi − XiQ, 1 ≤ i ≤ m,

и вводя вектор x Rm,приходим к линейному матричному неравенству(70).

1.2.Выпуклые функции

1.2.1.Основные определения и свойства выпуклых функций

Выпуклые функции,наряду с выпуклыми множествами,играют исключительно важную роль в теории оптимизации.Для задач математического программирования,задаваемых выпуклыми функциями,удается получить наиболее содержательные условия оптимальности,а также разработать эффективные численные методы их решения.

50