OCT Jan MAR 13 2007 2009 2010 16 captures 8 Apr 05 - 17 Mar 09

Close Help

2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Литература:

3. Хачиян Л. Г. Сложность задач линейного программирования. М.: Знание, 1987, N 10.

§ 5. Понятие о сложности задачи

линейного программирования (ЛП)

Определение основной задачи ЛП (озЛП). Принцип граничных решений и геометрическое описание симплекс-метода. Алгебраическая и битовая сложность методов ЛП. Результаты по сложности задач, близких к ЛП. Теорема о границах решений задач ЛП с целыми коэффициентами. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами.

1. Согласно [3] линейное программирование - это раздел прикладной математики, изучающий теорию, приложения и методы решения конечных систем линейных неравенств с конечным числом вещественных неизвестных x₁,ј,x_n:

a11x1 + a12x2 + ј+ a1nxn Ј b1 a21x1 + a22x2 + ј+ a2nxn Ј b2 јјјјјјјјј ј am1x1 + am2x2 + ј+ amnxn Ј bm ь п п э п п ю

(1)

или в сокращенной записи Ax Ј b. Считаем, что матрица A не содержит нулевых строк a_i. Основная задача ЛП (озЛП) состоит в нахождении такого решения (1), которое максимизирует заданную линейную функцию бc,xс = c₁ x₁+c₂ x₂+ ј+ c_n x_n вектора неизвестных x по всем вещественным x, удовлетворяющим системе (1):

max x О Rn: Ax Ј b  бc,xс;

(2)

озЛП (2) с n неизвестными и m ограничениями называется задачей размерности (n,m) и задается числовой таблицей

к к к к к к к к a11 a12 ј a1n b1 a21 a22 ј a2n b2 ј ј ј ј ј am1 am2 ј amn bm c1 c2 ј cn 0 к к к к к к к к

(3)

своих коэффициентов. В частном случае c = [`0] задача (2) эквивалентна (1), так что умение решать озЛП предполагает умение решать системы линейных неравенств (ЛН). В § 7 будет показано обратное сведение. Вообще говоря, в форме (2) может быть представлена любая задача ЛП с ограничениями равенствами и неравенствами, в том числе каноническая задача ЛП

max Ax = b, x і [`0]  бc,xс.

(Здесь и далее черта сверху будет использоваться для выделения вектора в отличие от похожего числа.)

УПРАЖНЕНИЕ 5. Представить каноническую задачу ЛП в форме озЛП.

Несмотря на то, что формально задачи ЛП не являются дискретными (x О Rⁿ), их решение нетрудно свести к перебору конечного числа угловых точек (вершин полиэдра (1), задающего ограничения) на основании принципа граничных решений:

если задача (2) имеет решение, то найдется такая подматрица A_I

матрицы A, что любое решение системы уравнений A_I x = b_I, т.е.

{ai1x1 + ai2x2 + ј+ ainxn = bi| i О I},

реализует максимум в (2).
Отметим, что для невырожденных A_I решение соответствующей системы уравнений A_I x = b_I, удовлетворяющее ограничениям (1), является угловой точкой (1). Из принципа граничных решений следует, что если угловая точка (1) существует, то разрешимая задача (2) имеет решение и в угловой точке (1), т.е. она эквивалентна максимизации бc,xс на конечном множестве вершин полиэдра (1). Процедура решения системы линейных уравнений методом Гаусса требует не более полинома 3-й степени от m,n (точнее, max(m,n)[min(m,n)]²) арифметических операций с элементами A и b. Однако число возможных подматриц матрицы A экспоненциально, и метод полного их перебора не эффективен.

В 1820-х гг. Ж. Фурье и затем в 1947 г. Дж. Данциг предложили метод направленного перебора смежных вершин (1) - в направлении возрастания целевой функции (2) - симплекс-метод. Хотя каждый шаг симплекс-метода (представляющий собой определенную процедуру пересчета элементов симплекс-таблицы (3)) ограничен по порядку числом mn арифметических операций, в настоящее время для всех известных вариантов симплекс-метода приведены примеры, экспоненциальные по числу итераций, когда перебирается более 2^min(n,m/2) вершин, но доказательство невозможности построить полиномиальный симплекс-метод также отсутствует. Подчеркнем, что на практике симплекс-метод не показывает данной оценки (``плохие" примеры довольно редки). Можно построить алгоритм решения задачи ЛП с оценкой f(n)m арифметических операций (над числами, записанными в (3)), где f(·) растет быстрее экспоненты. Алгоритм с полиномиальной оценкой одновременно по n и m не известен и вряд ли будет построен.

Теперь заметим, что функция, оценивающая число арифметических операций в зависимости от n и m, не учитывает длину кода элементов (3), а только их количество и поэтому не является временн'ой сложностью алгоритма. Указанная функция носит название алгебраической сложности в отличие от битовой сложности - функции, оценивающей число арифметических операций с битами (или с конечными порциями - по размеру машинного регистра) цифровой записи параметров индивидуальной задачи ЛП в зависимости от длины входного слова, т.е. от n, m и длин l кодов чисел в симплекс-таблице. Очевидно, битовая сложность алгоритма соответствует его временн'ой сложности (см. § 1). Входные коэффициенты задачи ЛП обычно рациональны, поэтому далее условимся считать их целыми, тогда l - длина записи максимального коэффициента в (3) - конечна. Набор (n, m, l) называется битовой размерностью задачи ЛП. Вопрос о существовании алгоритма ЛП с полиномиальной битовой сложностью был решен Л. Г. Хачияном в 1978 г., и тем самым была доказана полиномиальность задач ЛП. Основные моменты этого доказательства излагаются в следующем пункте и § 6. Здесь же укажем на отличие классов сложности задачи ЛП и других линейных задач.

Метод Гаусса решения системы линейных алгебраических уравнений имеет полиномиальную алгебраическую сложность, т.е. является сильнополиномиальным. Для ЛП вопрос о существовании сильнополиномиального алгоритма открыт. Кроме того, задача решения системы линейных уравнений принадлежит классу NC, а аналогичный результат для ЛП означал бы равенство NC=P, ожидать которое нет оснований.

Из полиномиальности ЛП вытекает полиномиальность задачи ЛН (существует ли решение системы ЛН):  ЛН О P. Аналогичные задачи с дополнительным ограничением целочисленности или булевости решения NP-полны: ЦЛН, БЛН О NPC (см. § 2), т.е. полиномиальные алгоритмы для них вряд ли будут построены.

Существует неполиномиальное обобщение ЛП - задача проверки истинности высказываний вида

Q1x1јQnxn F(бa1,xс Ј b1,ј, бam,xс Ј bm),

где Q_i О {", $}, а F(·,ј,·) - предложение, составленное из линейных неравенств с помощью связок &,Ъ,Ш (и, или, отрицание). Доказано, что любой алгоритм, решающий эту массовую задачу, имеет не менее чем экспоненциальную сложность. Тот же результат будет и при замене равенствами всех неравенств в постановке задачи.

2. Рассмотрим некоторые свойства задач ЛП с целыми коэффициентами. Для любой целочисленной матрицы D введем параметр

D(D)= max {Dў -  квадратная подматрица D}  |det Dў|.

Будем обозначать через [A|b] матрицу, составленную из A и вектора-столбца b О Z^m, дописанного справа. Здесь и далее Z^m - m-мерное пространство целочисленных векторов, Z^m₊ - его неотрицательный ортант.

Теорема 1 (о границах решений). Если озЛП (2) размерности (n,m) с целыми коэффициентами разрешима, то у нее существует рациональное решение x^* в шаре ||x|| Ј n^1/2 D([A|b]) и значением озЛП (2) d^*= бc,x^*с является рациональное число t/s со знаменателем, ограниченным величиной D(A).

Доказательство. На основании принципа граничных решений и по правилу Крамера $A_I Н A:  x_j^* = det A_I^j /detA_I Ј D([A|b]), ибо det A_I і 1, а определитель матрицы A_I^j, полученной из A_I заменой j-го столбца на ±b_I, не превышает по модулю D([A|b]). Отсюда для евклидовой нормы x^* получаем требуемую оценку. С учетом целочисленности вектора c знаменатель d^* может быть выбран равным знаменателю x_j^* "j, и 2-е утверждение теоремы следует из определения D(A) і |det A_I|.

Определение 1. Точка x^e называется e-приближенным решением системы линейных неравенств (1), если

бai,xeс Ј bi + e  "i = [`1,m],  где ai - i-я строка матрицы A,

или в матричной записи, обозначая e - вектор-столбец из единиц,

Axe Ј b+ee.

(1e)

Теорема 2 (о мере несовместности). Если система ЛН (1) имеет e₁-приближенное решение для e₁ = 1/[(n+2)D(A)], то эта система разрешима, т.е. имеет точное решение x⁰.

Доказательство. Обозначим через e^* минимальное e, при котором система (1_e) имеет решение (по условию e^* Ј e₁):

e*= min (x,e): Ax Ј b+ee  e.

Допустим, что утверждение теоремы не верно, тогда e^* > 0. Задача определения e^* является (с учетом равенства min(·) = -max(-·)) озЛП с целевым вектором c = (0,ј,0,-1),  n+1 переменными (x,e) и ограничениями Ax-ee Ј b. Следовательно, по теореме 1 e^* может быть представлена в виде дроби со знаменателем, не превышающим D([A|-e]) Ј (n+1)D(A), т.е. e^* і 1/[(n+1)D(A)] > e₁ - пришли к противоречию с определением e^*.

Аналогичное утверждение справедливо и для озЛП.

Определение 2. Точка x^*_e называется e-приближенным решением озЛП (2), если она является e-приближенным решением системы (1) и реализует максимум в (2) с e-точностью:

бai,x*eс Ј bi + e  "i = [`1,m]  и бc,x*eс і d* - e.

Теорема 2 ^*  (о мере несовместности). Если озЛП (2) имеет e₂-приближенное решение для e₂ = 1/(2n²D³(A)), то эта задача имеет точное решение x^*.

Доказательство см. в [3, с. 21].

§ 6. Метод эллипсоидов

Полиномиальный алгоритм округления e₁-приближенного решения системы линейных неравенств. Метод эллипсоидов e₂-приближенного решения озЛП. Оценка сложности метода эллипсоидов. Полиномиальность ЛП.

1. Имея e-приближенное решение (1) с e Ј e₁, можно (на основании теоремы 2, § 5) быть уверенным в существовании точного решения системы линейных неравенств. Оказыватся, процедура получения x⁰ из x^e₁ является полиномиальной. Соответствующий алгоритм округления e₁-приближенного решения системы (1) до точного был указан Л. Г. Хачияном и состоит в следующем.

Присвоим x¹: = x^e₁ и подставим x¹ в (1). Разобьем множество M= {1,ј,m} индексов неравенств в системе на два подмножества

M(x1)= {i:  |бai,x1с- bi| Ј e1},

M\M(x1)= {i:  бai,x1с- bi Ј -e1}.

Найдем решение xў¹ системы равенств A_M(x¹)x = b_M(x¹) (существует по теореме 2). Пусть xў¹ не является точным решением (1), т.е. в xў¹ не выполнилось i-е неравенство для какого-либо i П M(x¹). Тогда введем множество индексов невыполненных неравенств M⁺= {i| бa_i, xў¹с > b_i} Н M\M(x¹) и рассмотрим на отрезке [x¹,xў¹] ближайшую к x¹ точку, в которой еще выполнены все неравенства для i О M⁺ (в x¹ они выполнены с e₁-запасом). А именно определим

t= min i О M+  bi-бai,x1сбai,xў1с- бai,x1с

и присвоим x²: = (1-t)x¹+txў¹. Имеем M(x²) К M(x¹)ИM⁺, ибо неравенства с индексами из M(x¹)  e₁-приближенно выполнялись как равенства на всем отрезке [x¹,xў¹], а неравенства с индексами из M⁺, не выполненные в точке xў¹, выполняются в x² по построению. Таким образом, M(x²) Ј M(x¹), но |M(x)| Ј m, поэтому, повторяя указанную процедуру с заменой x¹ на x² и т.д., придем не более чем через max(n,m) шагов к тому, что решение xў соответствующей системы равенств окажется x⁰ - решением (1).

С учетом полиномиальности решения систем уравнений предложенный алгоритм округления полиномиален.

Аналогичный алгоритм имеется и для округления e₂-приближенного решения озЛП x^*_e2 до точного x^* (см. [3, с. 21]). Поэтому для построения полиномиального алгоритма решения озЛП осталось указать полиномиальный алгоритм поиска e₂-приближенного решения озЛП в шаре ||x|| Ј n^1/2 D или удостоверения, что такого решения нет (по теоремам 1,2^* из § 5). Требуемый алгоритм, основанный на методе эллипсоидов, который предложили в 1976-77 гг. Д. Б. Юдин и А. С. Немировский и (независимо) Н. З. Шор, приводится в следующих пунктах.

Здесь и далее D= D(D), где матрица D задается таблицей (3).

2. Пусть E - произвольный эллипсоид в Rⁿ с центром x и ненулевого объема volE. Рассмотрим (n-1)-мерную плоскость, заданную вектором g нормали и проходящую через центр x эллипсоида E. Обозначим через E^-(g) один из двух полуэллипсоидов, на которые разбивает E данная плоскость, E^-(g) = EЗ{x| бg,x-xс Ј 0}.

Утверждение 1. Полуэллипсоид E^-(g) эллипсоида E можно целиком заключить в новый эллипсоид Eў, имеющий объем, строго меньший E,

volEўvolE < e-1/(2n+2),

(*)

и Eў можно вычислить по E^-(g) за O(n²) арифметических операций.

Доказательство. Пусть E - единичный шар с центром в точке [`0]:  E = {x О Rⁿ: ||x|| Ј 1}, а E^-(g) = EЗ{x_n і 0}. Поместим центр Eў в точку xў = (0,ј,0,1n+1), тогда

Eў = {x| (x12+ј+xn-12)/b2 + (xn -1n+1)2/a2 Ј 1},

где a= 1-1/(n+1) < e^-1/(n+1),  b²= 1+1/(n²-1) < e^1/(n2-1).
Отношение объемов равно произведению полуосей ab^n-1 < e^-1/(2n+2), отсюда получаем (*), ибо любой эллипсоид можно превратить в шар афинным преобразованием координат, сохраняющим объем. Действительно, будем представлять произвольный эллипсоид E с помощью его центра x и матрицы Q (n×n), задающей указанное преобразование: E = {x| x = x+Qy, ||y|| Ј 1}. Обозначим h= Q^Tg/||Q^Tg||, где верхний индекс ^T - знак транспонирования. Тогда xў и Qў, представляющие эллипсоид Eў минимального объема, описанный вокруг полуэллипсоида E^-(g), пересчитываются по формулам

xў = x-1n+1Qh,  Qў = n   _____ Ј(n2-1)   {Q+( Ц   n-1n+1   -1)QhhT}

за O(n²) арифметических операций.

3. Метод эллипсоидов получения e-приближенного решения озЛП. Положим e: = e₂= 1/(2n²D³). Введем множество e-приближенных решений озЛП в шаре радиуса R= n^1/2 D с центром в [`0]:  X<sup>*</sup><sub>e</sub>= {x| бa<sub>i</sub>,xс Ј b<sub>i</sub> + e  "i = [`1,m],  бc,xс і d^* - e,  ||x|| Ј R}. Выберем указанный выше шар в качестве начальной итерации для эллипсоида E Ј X^*_e. Рассмотрим произвольную итерацию.

Проверяем, является ли центр x эллипсоида E e-приближенным решением. Если да, то алгоритм заканчивает свою работу, в противном случае строим эллипсоид Eў для очередной итерации как минимальный по объему эллипсоид, содержащий полуэллипсоид E^-(g) (см. п.2), где вектор g определяется следующим образом. Так как x П X^*_e, то либо

1⁰) $i:  бa_i,xс > b_i + e, и тогда g: = a_i, либо

2⁰) бc,xс < d^* - e и g: = -c.
Убедимся, что при этом X^*_e М Eў. Действительно, для варианта 1⁰
"x О X^*_e   бa_i,xс Ј b_i + e < бa_i,xс, т.е. X^*_e М EЗ{x| бa_i,x-xс Ј 0} = E^-(a_i) М Eў; и аналогично получим для варианта 2⁰

X*e М EЗ{x| бc,x-xс і 0} = E-(-c) М Eў.

Теперь с E: = Eў возвращаемся к началу итерации (на новый шаг).

Оценим число итераций метода эллипсоидов. Покажем, что X^*_e содержит шар радиуса r/2, где r= e/(hn^1/2) < R,  h і |a_ij|, |c_j|  (h высота задачи). Пусть x^* - точное решение в X^*_e. Из ||x^* - x|| Ј r следует |бa_i,xс- бa_i,x^*с| Ј ||a_i|| ||x^*-x|| Ј hn^1/2r = e   "i О M и |бc,xс- бc,x^*с| Ј ||c|| ||x^*-x|| Ј hn^1/2r, т.е. указанный выбор r гарантирует, что все такие x будут e-приближенными решениями. Поскольку ||x^*|| Ј R, то множество тех из рассматриваемых x, для которых ||x|| Ј R (т.е. пересечение шаров радиуса r и R, включающее центр первого), содержит шар радиуса r/2. Этот шар и принадлежит X^*_e. Таким образом, объем X^*_e больше объема n-мерного шара радиуса r/2. Значит, объем эллипсоида, построенного последним, например E^k для k-й итерации, не должен оказаться меньше объема этого шара. Отсюда и из утверждения 1 получаем для k соотношение

(r2R)n Ј volX*evolE1 Ј volEkvolE1 < e-k/(2n+2),

из которого k (по определению r, R,e,h и D) не превосходит

2n2ln(Rnh/e) < 2n2ln(2n3.5D5) < 10n2ln(nD).

УПРАЖНЕНИЕ 6. Оценить по порядку битовую длину L входа озЛП: доказать, что L > O(ln(nD)).

Следовательно, число итераций метода эллипсоидов k < O(n²)L, и с учетом O(n²+nm) арифметических операций для каждой итерации получим оценку O(n³(n+m)L) для числа арифметических операций, достаточного методу эллипсоидов при поиске e₂-приближенного решения озЛП. Алгоритм округления e₂-приближенного решения до точного этой оценки не портит (см.[3, с. 21]). Можно также показать, что при реализации метода эллипсоидов и алгоритма округления все арифметические операции достаточно проводить с числами двоичной длины, ограниченной O(L). При этом ошибки, возникающие за счет конечности числа разрядов (ошибки округлений), поглощаются путем некоторого дополнительного увеличения (``раздутия") описанного эллипсоида Eў на каждой итерации [3, с. 24], что не влияет на порядок оценки для общего числа итераций. В результате временн'ая сложность такой процедуры решения озЛП оказывается полиномом от длины входа и справедлива

Теорема 3. Задача ЛП с целыми коэффициентами разрешима за полиномиальное от длины входа время.

Следствием данной теоремы является

Утверждение 2. ЛН О P.

Подчеркнем, что несмотря на доказанную полиномиальность, метод эллипсоидов не может конкурировать с симплекс-методом при практическом решении задач ЛП (реально он применяется в выпуклом квадратичном программировании), поскольку полученная оценка числа его итераций достигается на любых индивидуальных задачах, даже если в качестве начального приближения взять решение. Тогда как симплекс-метод для ``хороших" (невырожденных) задач дает оценку O(n³), на порядок меньшую, чем метод эллипсоидов, и за одну итерацию может подтвердить, что начальное приближение является решением. Тем не менее сам факт полиномиальности ЛП инициировал поиск новых методов ЛП, что привело к созданию целого класса эффективных методов математического программирования - методы внутренней точки - и позволило построить конкурентоспособные полиномиальные алгоритмы ЛП. Идея их построения будет изложена в следующем параграфе, где также приводятся необходимые сведения по теории ЛП, начиная с ЛН.

§ 7. Теория двойственности ЛП. Идея метода Кармаркара

Следствия систем ЛН. Афинная лемма Ф'аркаша /без доказательства/. Лемма Фаркаша о неразрешимости. Теорема двойственности ЛП. Сведение озЛП к однородной системе уравнений с ограничением положительности. Идея метода Кармаркара и его отличие от симплекс-метода.

1. Система ЛН (1) называется разрешимой, если $x: Ax Ј b, и неразрешимой - в противном случае. ОзЛП (2) разрешима, когда разрешима система (1) и максимум в (2) достигается.

Определение 3. Линейное неравенство

бc,xс Ј d

(4)

является следствием разрешимой системы линейных неравенств (1), если для любого x, удовлетворяющего (1), выполнено (4).

Способ получения неравенств-следствий довольно прост: выберем произвольные И_i і 0  "i О M, домножим на И_i каждое i-е неравенство системы (1) и сложим; получим для вектора

c = е i О M  Иi ai  и любого числа  d і е i О M  Иi bi,

что (4) будет следствием (1). Оказывается, других следствий у ЛН не бывает. А именно справедлива

Лемма Ф'аркаша (афинная). Линейное неравенство (4) является следствием разрешимой в вещественных переменных системы ЛН (1) тогда и только тогда, когда существует вектор И О R^m:

c = е i О M  Иiai,  d і е i О M  Иi bi,  Иi і 0  "i О M.

(5)

(Схему доказательства см. в [3, с. 18].)

Для неразрешимой системы ЛН (1) можно формально считать следствием (1) заведомо неверное неравенство б[`0],xс Ј -1 и далее пользоваться афинной леммой Фаркаша, как показывает

Лемма Фаркаша о неразрешимости.  Система ЛН (1) неразрешима тогда и только тогда, когда разрешима система

е i О M  Иi ai = _ 0   ,   е i О M  Иi bi Ј -1,  Иi і 0  "i О M.

(6)

Доказательство. Пусть (1) неразрешима, тогда из разрешимости системы бa_i,xс+ x_n+1 Ј b_i  "i О M должно следовать, что x_n+1 Ј -e < 0, т.е. следствием этой системы является неравенство б(0,ј,0,1/e),(x,x_n+1)с Ј -1 и из афинной леммы Фаркаша получаем (6) (а также в дополнение еИ_i = 1/e). Если же (6) разрешима, то указанное выше неравенство б[`0],xс Ј -1 оказывается следствием (1) и должно выполняться для всех x, удовлетворяющих (1), значит, таких не существует.

Теперь мы можем доказать основной теоретический результат ЛП - теорему двойственности, на которой базируются как методы решения задач ЛП, так и способы анализа решения, и которая фактически дает необходимые и достаточные условия оптимальности в ЛП. Наличие двойственности, обусловив хорошую характеризацию задачи ЛН, предопределило полиномиальность ЛП.

Определение 4. Двойственной к задаче ЛП на максимум с ограничениями неравенствами в форме озЛП (2) называется следующая задача ЛП на минимум с ограничениями в канонической форме:

min  { е i О M  Иi bi |  е i О M  Иi ai = c, Иi і 0 "i О M},  или  в краткой записи

min ИA = c, И і [`0]  бИ,bс.

(7)

Для того, чтобы построить двойственную к произвольной задаче ЛП, надо представить ее в форме озЛП, применить формулу (7), а затем вернуться к обозначениям исходной задачи.

УПРАЖНЕНИЕ 7. Показать, что двойственная задача к двойственной задаче ЛП совпадает с прямой задачей ЛП: представить (7) в форме озЛП (аналогично упражнению 5), выписать двойственную к полученной задаче и свести ее к (2).

Теорема 4 (двойственности ЛП).  Задача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней. В случае разрешимости оптимальные значения целевых функций в обеих задачах совпадают, т.е. d^* = d^**, где d^* - значение (2), d^** - значение (7).

Доказательство проведем для случая озЛП, поскольку любая задача ЛП адекватно представляется в такой форме.

Пусть задача (2) разрешима, тогда (4) является следствием (1) "d і d^* и не является "d < d^*, что по афинной лемме Фаркаша эквивалентно разрешимости (5) при d і d^* и неразрешимости (5) при d < d^*, т.е. d^* = min{d| (5)}, а это и есть значение (7).

И наоборот, из разрешимости (7) следует неразрешимость (6), ибо в противном случае min в (7) обращался бы в -Ґ (так как прибавление решения (6) к решению (7) дает допустимую точку и уменьшает значение целевой функции (7)). Отсюда получаем разрешимость (1) по лемме Фаркаша о неразрешимости. Кроме того, разрешимость (7) означает разрешимость (5) для любого d і d^**, так что (4) оказывается следствием (1) для d і d^**, и поэтому d^** ограничивает сверху значение (2), т.е. максимум в (2) достигается. Таким образом получили разрешимость задачи (2) и можем вернуться к началу доказательства для установления равенства d^* = d^**.

Из теоремы 4 непосредственно получаем

Утверждение 3. Задача ЛП оптимизации эквивалентна решению системы линейных неравенств.

Действительно, озЛП (2) эквивалентна задаче ЛП (7) и обе они эквивалентны системе ЛН относительно неизвестных (x,И):

Ax Ј b, бc,xс = бb,Ис, ИA = c, И і _ 0   .

(8)

Утверждение 4. Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных.

Доказательство. От системы ЛН (8) переходим к ограничениям в канонической форме аналогично упражнениям 5,7.

Утверждение 5. Задача ЛП эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений.

Доказательство. На основании утверждения 4 озЛП сводится к некоторой системе ЛН (с целыми коэффициентами) относительно вектора вещественных неизвестных y:

^ P   y = ^ q   ,  y і _ 0   ,

(9)

пусть [^P] - матрица (K×(N-1)). Введем параметр R, мажорирующий координаты какого-то решения (9) (по теореме о границах решений), если система (9) разрешима. Добавим к (9) неравенство

бy,eс = y1+ј+yN-1 Ј NR,

которое превратим в равенство с помощью дополнительной переменной y_N: б[^y],eс = y₁+ј+y_N-1+y_N = NR, а (9) перепишется как [[^P]|[`0]][^y] = [^q],  [^y] і [`0]. Теперь сделаем замену переменных x: = [^y]/R и обозначим P= NR[[^P]|[`0]]-[[^q]|[^q]|ј|[^q]]. Придем к однородной системе Px = [`0] с дополнительными ограничениями x = (x₁,ј, x_N) і [`0], бx,eс = N, что соответствует системе Px = [`0],  x і [`0],  бx,eс > 0  с решениями-лучами tx⁰  "t > 0, любое из которых пересчитывается в решение исходной системы.

2. Метод Кармаркара (N. Karmarkar, 1984 г.). Воспользуемся утверждением 5 и обозначениями, введенными при его доказательстве. Пусть p(x)= (бp₁,xс)²+ј+(бp_K,xс)², где p_i - строки P. Тогда p(x) = 0 эквивалентно Px = [`0]. Введем функцию Кармаркара

k(x)= [p(x)]N/2x1 x2·ј·xN.

Применяя теорему 2 и алгоритм округления к задаче решения (9), можно показать, что для точного ее решения достаточно найти такой [^x] > [`0], для которого k([^x]) Ј 1/[3(D([^P]))^N] [3, с. 25-26].

Полиномиальный алгоритм поиска нужного приближенного [^x] приводится в [3, с. 26-28], и мы не будем его описывать. Отметим только, что аналогичный алгоритм может быть построен на основании применения метода Ньютона (см. в разд.3) к задаче минимизации функции Кармаркара или ей подобных. В результате получаем целый класс полиномиальных алгоритмов ЛП, которые на практике оказываются сравнимыми с симплекс-методом, не имея теоретических недостатков последнего. Предложенные алгоритмы строятся на принципиально новой идее: не дискретной, а непрерывной трактовки задачи ЛП, когда вместо перебора конечного числа угловых точек осуществляют поиск решения в исходном пространстве вещественных переменных, и траектории алгоритмов не проходят через угловые точки. Напомним, что метод эллипсоидов также не ориентируется на угловые точки многогранника ограничений. Характерно, что именно такой уход от дискретного программирования позволил построить полиномиальные алгоритмы ЛП. Поэтому далее будет дан некоторый обзор основных подходов к решению непрерывных задач оптимизации.

Замечание. Если бы речь шла о непосредственном поиске точного решения задачи ЛП указанными методами, то нельзя было бы гарантировать конечношаговость (не то, что полиномиальность) соответствующих алгоритмов. Для их применения существенной является возможность остановки в приближенном решении благодаря наличию полиномиального алгоритма округления. Но поскольку для его работы требуется начальное приближение из определенной окрестности решения, зависящей от длины l или высоты h, или длины входа L конкретной задачи ЛП, то и число итераций алгоритмов, базирующихся на рассматриваемом принципе, зависит от числа цифр в записи элементов матрицы ограничений. Так что не удается использовать данную идею для построения сильнополиномиальных алгоритмов ЛП, кроме как в частных случаях ограниченности элементов матрицы (например, в задачах на графах и сетях, где a_ij = 0,±1).

3. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ (МП)

Литература:

4. Карманов В. Г. Математическое программирование. М.: Наука, 1986.

5. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1985.

6. Мину М. Математическое программирование. М.: Наука, 1990.

§ 8. Oбзор идей МП

Классификация задач МП. Преимущества выпуклого случая. Понятие о градиентных и Ньютоновских методах минимизации. Условная оптимизация, способы освобождения от ограничений (методы барьеров и штрафов).

1. Задача ЛП, как и задача минимизации функции Кармаркара, является частным случаем задачи МР:

min x О X  f(x).

(1)

Здесь требуется найти arg min x О X  f(x) О Arg min x О X  f(x), т.е.

x* О X*= {x* О X| f(x*) Ј f(x)  "x О X},  и f* = f(x*).

(2)

Любой такой x^* называется решением (1); f^* - значение (1), или оптимальное значение целевой функции f в задаче (1), X - множество ограничений или допустимое множество.

В зависимости от природы множества X задачи оптимизации классифицируются как: дискретные (комбинаторные) - X конечно или счетно, целочисленные - x_j О Z, булевы - x_j О B, вещественные (непрерывные) - X Н Rⁿ, бесконечномерные или в функциональном пространстве, например, когда X - подмножество гильбертова пространства L₂, и т.п. В данном разделе будем по преимуществу рассматривать задачи с вещественными переменными, которые собственно и называются (традиционно) задачами математического программирования (ЗМП). Если X М Rⁿ, то говорим о задаче условной оптимизации (при условии x О X), иначе (X = Rⁿ) получаем задачу безусловной оптимизации.

Для ЗМП минимум в (1) достигается в условиях теоремы Вейерштрасса (f непрерывна, X компактно или для некоторого [^x] О X ограничено множество Лебега функции f - {x О X|f(x) Ј f([^x])}).

Кроме разделения на условные и безусловные, ЗМП классифицируются по свойствам целевой функции и множества ограничений соответственно на задачи ЛП, выпуклого программирования, гладкие или негладкие и др. Для каждого из классов ЗМП разрабатываются свои численные методы их решения. С точки зрения численных методов существенно также разделение на локальную и глобальную оптимизацию. В определении (2) речь идет о глобальном минимуме, который, однако, найти не просто, и поэтому задачу стараются свести к дискретной оптимизации на множестве локальных минимумов.

Определение 1. Точка x⁰ О X называется точкой локального минимума в ЗМП (1), если $e > 0:   f(x⁰) Ј f(x)  "x О XЗO_e(x⁰). Здесь и далее O_e(x) обозначает e-окрестность точки x.

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

Утверждение 1.  ЦЛН µ ЗМП.

Доказательство. Поскольку задача ЛН является частным случаем задачи ЛП, то для сведения ЦЛН к ЗМП достаточно представить условие целочисленности переменных в виде ограничений (неравенств) на вещественные переменные, что нетрудно сделать, например, так:  {x_j О Z} эквивалентно {x_j О R|sin² (px_j) Ј 0}.

Поэтому методы глобальной оптимизации будут рассмотрены в разд.4, а в данном параграфе остановимся на поиске локального экстремума. Отметим, что для ряда экстремальных постановок задач физики точки локального экстремума имеют самостоятельное значение. Кроме того, существует целый класс ЗМП, для которого локальный экстремум совпадает с глобальным минимумом, это - задачи выпуклого программирования.

Определение 2. Функция f называется выпуклой на X, если ее надграфик epigraf_Xf={(x,y)| y і f(x), x О X} - выпуклое множество. Функция, выпуклая на всей области определения, называется выпуклой. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит отрезок, их соединяющий.

Утверждение 2. Любая точка локального минимума выпуклой функции является точкой ее глобального минимума.

Доказательство. Пусть f(x⁰) > f(x^*). Тогда f(x⁰) > f(x) для всех точек x полуинтервала (x⁰,x^*]  (по определению 2), а значит, и в некоторой окрестности x⁰ - противоречие с определением 1.

Для решения задач выпуклого программирования примен'им метод эллипсоидов, причем в гладком случае отсечение полуэллипсоида проводится на основе градиента невыполненного ограничения в полной аналогии с алгоритмом из § 6. Поэтому задача поиска e-приближенного решения задачи выпуклого программирования оказывается полиномиально разрешимой. Для острых задач выпуклого программирования - когда функция цели убывает в окрестности минимума не медленнее некоторой линейной функции - можно получить и точное решение.

2. Общими методами локальной оптимизации (для произвольного, не обязательно выпуклого, случая) являются методы локального спуска.

Определение 3. Вектор h О Rⁿ называется направлением убывания функции f в точке x, если f(x+ah) < f(x) для всех достаточно малых a > 0.

Утверждение 3. Пусть f дифференцируема в точке x. Тогда, если бgradf(x),hс < 0, то h - направление убывания функции f в точке x, и наоборот, если h - направление убывания функции f в точке x, то бgradf(x),hс Ј 0.

Доказательство. Из условия дифференцируемости f имеем для достаточно малых a > 0:  f(x+ah)-f(x) = бgradf(x),ahс+o(a) = a{бgradf(x),hс+o(a)/a}. Очевидно, последняя добавка не изменит знака выражения в фигурных скобках, если скалярное произведение строго отрицательно или строго положительно. Отсюда автоматически вытекает требуемое утверждение.

Таким образом, направление локального убывания дифференцируемой функции должно составлять острый угол с ее антиградиентом, который является в смысле линейного приближения наилучшим направлением убывания. Для мнемоники приведем эпиграф к главе, посвященной градиентным методам минимизации, из 1-го издания книги Ф. П. Васильева Численные методы решения экстремальных задач:  ``Вот кто-то с горочки спустился - антиградиент!"

Если gradf(x) = 0, то x будет стационарной точкой. Отметим, что в условной оптимизации равенство нулю градиента уже не является необходимым условием минимума (соответствующие условия будут рассмотрены в § 9). Но в более простом случае X = Rⁿ можно, двигаясь небольшими шагами в направлении антиградиента функции f в текущей точке, прийти в стационарную точку, как правило, локального минимума. Так мы получаем идею градиентного метода безусловной минимизации, задаваемого итеративной процедурой

xt+1 = xt-atgrad f(xt),  t = 1,2,ј,  "x1 О Rn.

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

1) Пассивные способы - {a_t} выбирается заранее.
Постоянный шаг - a_t = a₀ для достаточно малых a₀.
Убывающий шаг (если a₀ не известно или при наличии помех) -
a_tЇ 0,  еa_t = Ґ,  еa²_t < Ґ,  например a_t = 1/t.

2) Адаптивные способы - {a_t} зависит от реализующейся {x^t}.
Метод скорейшего спуска - a_t О Argmin_{a > 0}f(x^t-a gradf(x^t)).
Метод дробления шага (деления пополам) - если f(x^t+1) > f(x^t), то возврат к t-й итерации с a_t: = a_t/2. (Возможно и увеличение шага при стабильном убывании f, т.е. приближенный скорейший спуск.)
Правило Армихо - путем дробления шага добиваемся для a_t выполнения условия  f(x^t-a_tgradf(x^t))-f(x^t) Ј -ea_t||gradf(x^t)||².

В общем случае дифференцируемой, ограниченной снизу f можно получить сходимость градиентного метода к множеству стационарных точек, а при дополнительных предположениях доказывается (за исключением варианта с убывающим шагом) линейная скорость сходимости, которая в выпуклых задачах означает  ||x^t+1 - x^*|| Ј q||x^t - x^*|| для некоторого 0 < q < 1. Указанная линейная оценка объясняется тем, что в процессе минимизации градиентным методом используется линейная аппроксимация целевой функции на каждом шаге. Более высокую скорость сходимости получают для методов, основанных на квадратичной аппроксимации, в предположении дважды дифференцируемости f. Типичным примером здесь является метод Ньютона.

Пусть f О C²(Rⁿ), разложим функцию f в ряд Тейлора в окрестности текущей точки x^t:

f(x)-f(xt) = бgrad f(xt), x-xtс+12бfўў(xt)(x-xt), x-xtс+ o(||x-xt||2).

Выберем x^t+1 из условия минимизации квадратичной аппроксимации f(x) в точке x^t, т.е. квадратичной части приращения f(x)-f(x^t), получим метод Ньютона:

xt+1 = xt-(fўў(xt))-1grad f(xt),  t = 1,2,ј,

где начальное приближение x¹ должно находиться достаточно близко к точке оптимума x^*. В таком случае (и при дополнительных предположениях, более сильных, чем для приведенной ранее оценки скорости сходимости градиентного метода) для метода Ньютона будет справедлива квадратичная скорость сходимости

||xt+1 - x*|| Ј Q||xt- x*||2,  т.е.  ||xt+1 -x*|| Ј 1Q(Q||x1 - x*||)2t,

что предполагает ||x¹ - x^*|| < 1/Q (оценку для Q см., например, в [5, с. 192]). Еще раз подчеркнем, что градиентный метод в отличие от ньютоновского сходится при любом начальном приближении. Из определения метода Ньютона также следует требование невырожденности матрицы вторых производных (гессиана) функции f.

Нетрудно видеть, что полученная формула метода Ньютона решения задач безусловной минимизации совпадает с формулой метода Ньютона решения системы уравнений gradf(x) = 0, соответствующей необходимым условиям экстремума.

3. Для задач условной минимизации, например   min x О [1,2]  x2,

предложенные методы нуждаются в модификации. В частности, для приведенного примера, когда множество X имеет достаточно простую структуру, указанные выше формулы совмещаются с процедурой проектирования на X на каждом шаге метода. Так приходим к методу проекции градиента

xt+1 = PrX{xt-atgrad f(xt)},  t = 1,2,ј,  "x1 О Rn.

Для более сложных множеств X, допустим, задаваемых ограничениями неравенствами

X= {x О Rn| gi(x) Ј 0  "i О M},

(3)

универсальным способом освобождения от ограничений является их штрафование. А именно для достаточно большой константы C > 0 вместо задачи условной минимизации (1),(3) рассматривают задачу безусловной минимизации оштрафованной целевой функции

min x О Rn  {f(x)+C е i О M  [gi+(x)]p},  где   е i О M  [gi+(x)]p -

это функция штрафа (штрафная функция) для ограничений неравенств, g⁺(·)= max[0,g(·)] - срезка g, параметр штрафа p і 1. (Другие виды функций штрафа см. в [4,5].) В условиях непрерывности функций f, g_i, непустоты X и ограниченности множества Лебега функции f можно доказать, что с ростом константы штрафа

lim C­Ґ  min x О Rn  {f(x)+C е i О M  [gi+(x)]p} = f*.

(4)

Если p = 1 (функция-срезка и, следовательно, штрафная функция является острой), то $C^*:  min{f(x)+C^*е_{i О M}g_i⁺(x)} = f^* (существует точный штраф). Однако при p > 1 - гладкий штраф  подобное равенство означало бы несущественность ограничений x О X (точка безусловного минимума и так находится в X).

Утверждение 4. Пусть f,g_i О C¹(Rⁿ), выпуклы, p > 1 и $C^*:  x^C=argmin{f(x)+C^*е[g_i⁺(x)]^p} О X, тогда

xC О Arg min x О Rn  f(x), т.е.   min x О Rn  f(x) = min x О X  f(x).

Доказательство. Так как x^C - точка безусловного экстремума дифференцируемой функции, то градиент оштрафованной функции цели в ней равен нулю:  gradf(x^C)+C^*pе[g_i⁺(x^C)]^p-1gradg_i(x^C) = 0. Но из условия x^C О X все выражения в квадратных скобках, а значит, и второе слагаемое равны нулю. Отсюда следует gradf(x^C) = 0, т.е. необходимое условие экстремальности точки x^C для задачи безусловной оптимизации, которое в выпуклом случае оказывается и достаточным (см. утверждение 2). Поэтому x^C - точка безусловного минимума f. Но x^C О X, так что x^C - и точка условного минимума f на X, ибо безусловный минимум не превышает условного. Утверждение доказано.

Таким образом, для гладкого штрафа не удается свести задачу условной минимизации к безусловной, тем не менее формула (4) позволяет итеративно комбинировать метод штрафов и градиентный метод в следующей процедуре:  "x¹ О Rⁿ

xt+1 = xt-at{gradf(xt)+Ctp е i О M  [gi+(xt)]p-1gradgi(xt)},  t = 1,2,ј,

которая сходится при определенных соотношениях между {a_t} и {C_t}, в частности для убывающего шага при еa_t²C_t² < Ґ (например, a_t = 1/t,  C_t < Јt).

Утверждение 4 показывает, что траектории метода штрафа проходят, вообще говоря, вне множества ограничений X, хотя и сходятся к данному множеству. Из-за этого рассмотренный метод иногда также называют методом внешних штрафов в отличие от методов внутренней точки, или барьеров. Типичным примером применения метода барьеров является описанный в § 7 метод Кармаркара, когда задача (9), эквивалентная задаче условной минимизации

min x і [`0], еxj = N  p(x),

сводится к безусловной минимизации специальной барьерной функции k(x), не позволяющей методу Ньютона выйти за ограничения x > 0, если в этих ограничениях выбрано начальное приближение. Различные виды барьерных функций см. в [4,5] - для них характерно быстрое возрастание при приближении изнутри к границе множества ограничений (тогда как штрафная функция стремится к нулю при приближении к множеству ограничений - извне). Для решения общей задачи МП (1),(3) с ограничениями неравенствами методу Кармаркара соответствует использование вместо рассмотренной выше штрафной функции, основанной на срезке, логарифмической барьерной функции, равной

-1C е i О M  ln[-gi(x)]

при g_i(x) < 0 "i О M и +Ґ в противном случае. Эта функция также прибавляется к целевой, и справедливо соотношение, аналогичное (4).

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

§ 9. Двойственность в МП

Необходимые условия локального минимума обобщенно дифференцируемых функций при ограничениях неравенствах. Теорема Куна-Таккера. Понятие о регулярности ограничений неравенств в задаче МП. Метод множителей Лагранжа.

1. В этом параграфе будем рассматривать задачу условной оптимизации (1) с X М Rⁿ,  X № Ж, по преимуществу, с ограничениями неравенствами (3). Как уже отмечалось, условие равенства нулю градиента для таких задач может не иметь никакого отношения к точкам условного экстремума. Поэтому выведем соответствующие необходимые условия для рассматриваемого случая. Вначале они будут даны в достаточно общей форме, допускающей применение для широкого класса задач МП (кусочно-гладких и при произвольным образом заданных ограничениях, а также не обязательно конечномерных). Затем проведем конкретизацию для ограничений (3). Для обычных задач МП (конечномерных, с дифференцируемыми функциями) справедливы все дальнейшие построения и выводы при замене знака t обычным градиентом. Таким образом, основой обобщения является следующее

Определение 4. Функция f называется дифференцируемой по Адамару в точке x О Rⁿ, если существует вектор tf(x) О Rⁿ, такой что "y О Rⁿ выполнено:

lim (t,yў)® (+0,y)  f(x+tyў)-f(x)t = бtf(x),yс.

Для бесконечномерных задач, когда f - функционал: E® R¹, где E  некоторое функциональное пространство, требуется: tf(x) О Eў для пространства Eў, сопряженного к E, и x,y О E. В гладком случае tf(x) = gradf(x) и можно положить yў тождественно равным y.

В безусловной оптимизации существенную роль играли направления спуска (убывания целевой функции). В условной оптимизации, кроме убывания целевой функции, требуется отслеживать еще и невыход за ограничения. Поэтому вводится понятие возможного или допустимого направления в точке x О X для множества ограничений X как такого вектора y, для которого $t⁰ > 0:  x+ty О X  "t О [0,t⁰]. Замыкание множества всех допустимых направлений в точке x для X дает следующее

Определение 5. Контингентным конусом к множеству X в точке x называется множество векторов

K(X,x)= {y| $ {(tt,yt)}t = 1Ґ:  (tt,yt)® (+0,y),  x+ttyt О X  "t}.

Очевидно, для [^x] П X  K(X,[^x]) = Ж, а для xў О intX  K(X,xў) = Rⁿ. Для x О ¶X в случае гладкой границы конус K(X,x) называется также конусом касательных и соответствует касательным направлениям для ограничений-равенств.

Теорема 1 (общий вид необходимых условий локального минимума в задаче (1)).  Пусть функция f дифференцируема по Адамару, X М Rⁿ,  X № Ж,  x⁰ - точка локального минимума f в задаче (1), тогда "y О K(X,x⁰)  бtf(x⁰),yс і 0.

Доказательство. Выберем y О K(X,x⁰). Для соответствующих ему по определению 5 {t_t,y_t} выполнено x⁰+t_ty_t О X, и, начиная с достаточно большого t,  x⁰+t_ty_t О XЗO_e(x⁰) (ибо t_t® 0), следовательно, по определению 1 f(x⁰+t_ty_t) і f(x⁰). В пределе получим

lim (t,yў)® (+0,y)  f(x0+tyў)-f(x0)t = lim (tt,yt)® (+0,y)  f(x0+tt yt)-f(x0)tt і 0,

и требуемое соотношение вытекает из определения 4.

Содержательно данные условия означают, что среди допустимых направлений в точке локального минимума не должно быть направлений убывания целевой функции (см. утверждение 3 § 8). Однако в таком общем виде этими условиями не удобно пользоваться.

Конкретизируем полученные условия для ограничений неравенств, когда X задается формулой (3). Введем "x О X множество индексов J(x) = {i О M| g_i(x) = 0} - активных ограничений в точке x, т.е. таких неравенств из (3), которые в этой точке выполнены как равенства. И определим множество (конус)

G(x)={y О Rn| бtgj(x),yс Ј 0  "j О J(x)}.

Определение 6. Множество X для ограничений неравенств (3) называется регулярным в точке x О X, если G(x) Н K(X,x).

Теорема 2 (необходимые условия локального минимума с ограничениями неравенствами).  Пусть функции f, g_i "i О M дифференцируемы по Адамару, X № Ж,  x⁰ - точка локального минимума f в задаче (1),(3) и множество X регулярно в точке x⁰. Тогда

$Иj і 0:  t{f(x0)+ е j О J(x0)  Иjgj(x0)} = 0.

(5)

Доказательство. По теореме 1 и из определения регулярности X в x⁰ следует, что бtf(x⁰),yс і 0 для всех y, удовлетворяющих условию бtg_j(x⁰),yс Ј 0  "j О J(x⁰). Значит, по определению 3 § 7, линейное неравенство бtf(x⁰),yс і 0 является следствием системы линейных неравенств {бtg_j(x⁰),yс Ј 0  "j О J(x⁰)}. Приведя это неравенство к стандартному виду б-tf(x⁰),yс Ј 0 и применив афинную лемму Фаркаша (§ 7), получим, что

$Иj і 0:  -tf(x0) = е j О J(x0)  Иjtgj(x0).

Таким образом, для регулярных ограничений необходимым условием локального минимума в гладкой задаче (1),(3) является равенство нулю дифференциала функции в фигурных скобках в (5) для хоть каких-нибудь И_j і 0. Чтобы не записывать в явном виде множество активных ограничений, вводят функцию Лагранжа

L(И,x)= f(x)+ е j О M  Иjgj(x)= f(x)+бИ, _ g   (x0)с

(регулярной) задачи (1),(3), где вектор-функция [`g](·)= (g_j(·)| j О M). Из теоремы 2 следует, что равенство нулю дифференциала функции Лагранжа для И_j і 0 также является необходимым условием локального минимума в регулярной задаче (1),(3), ибо множители Лагранжа И_j, соответствующие неактивным ограничениям, можно взять равными нулю. Последнее условие записывается как

бИ, _ g   (x0)с = 0

(6)

и называется условием дополняющей нежесткости. Итак, доказана

Теорема 3 (принцип оптимальности Лагранжа).  В предположениях теоремы 2 для задачи (1),(3) существует неотрицательный вектор множителей Лагранжа И і [`0], такой, что для x<sup>0</sup> выполнены условия оптимальности - (6) и t<sub>x</sub> L(x<sup>0</sup>,И) = [`0].

Для выпуклых задач (1),(3) данные необходимые условия являются в регулярном случае и достаточными, и может быть доказана

Теорема 4 (Куна, Таккера). Если в задаче (1),(3) функции f,g_j О C¹(Rⁿ) выпуклы и множество X регулярно (в любой точке), то x^* - точка оптимума в этой задаче тогда и только тогда, когда в ней выполнены условия оптимальности для И і [`0].

Доказательство. Необходимость следует из предыдущих теорем, покажем достаточность. Для данного И в точке x^* выполнено условие экстремальности x^* для функции L(·,И). С учетом неотрицательности И эта функция выпукла по x, значит, x^* является точкой ее минимума (см. утверждение 2 § 8). Отсюда и из условия дополняющей нежесткости получим, что f(x^*) = f(x^*)+бИ,[`g](x<sup>*</sup>)с = L(x<sup>*</sup>,И) Ј L(x,И)= f(x)+бИ,[`g](x)с Ј f(x) "x О X (ибо g_j(x) Ј 0 для x, удовлетворяющих ограничениям), что и требуется в определении (2).

Аналогичные теоремам 2-4 утверждения справедливы и для случая, когда X задается ограничениями-равенствами, и для смешанных систем ограничений равенств и неравенств: g_j(x) Ј 0, g_i(x) = 0. Только на соответствующие ограничениям-равенствам множители Лагранжа И_i не надо накладывать условия неотрицательности, а на условие дополняющей нежесткости эти ограничения не влияют (в случае ограничений-равенств вообще опускаем (6) и приходим к классическому правилу множителей Лагранжа).

2. Теперь вспомним, что полученные условия являются значимыми лишь в предположении регулярности ограничений, для которого определение 6 не дает конструктивного способа проверки. В данном пункте будут рассмотрены некоторые достаточные условия регулярности ограничений неравенств (3) для гладких задач.

Кроме G(x), определенного в п.1, введем также множество

G0(x)={y О Rn| бtgj(x),yс < 0  "j О J(x)},

отличающееся заменой нестрогого неравенства строгим. Но это множество уже включается в контингентный конус.

Утверждение 5. В предположении дифференцируемости по Адамару (или обычной дифференцируемости) функций g_j, задающих ограничения (3), G⁰(x) М K(X,x)  "x О X.

Доказательство (от противного).  Пусть существует направление y О G⁰(x), не входящее в K(X,x), т.е. для любой последовательности, фигурирующей в определении 5, найдется подпоследовательность (t_t,y_t)®(+0,y):  x+t_t y_t П X, следовательно, "t $ индекс j, такой что g_j(x+t_t y_t) > 0. Возможных индексов - конечное число, а различных t бесконечно много, значит, найдется ограничение, пусть i-е, которое нарушается бесконечное число раз. Рассмотрим соответствующую подпоследовательность {t_k}:  g_i(x+t_tky_tk) > 0 и, устремляя k®Ґ, получим, что g_i(x) і 0. Но из условия x О X справедливо обратное неравенство, откуда следует равенство, т.е. i О J(x). Однако для этого i по определению 4 будем иметь  бtg_i(x),yс=

= lim (t,yў)® (+0,y)  gi(x+tyў)-gi(x)t = lim k®Ґ  gi(x+ttkytk)-gi(x)ttk і 0.

Пришли к противоречию с y О G⁰(x).

Отсюда получаем следующее условие регулярности:

G(x) = G0(x)   .

(7)

Здесь и далее черта над множеством обозначает его замыкание.

Утверждение 6. В сделанных предположениях условие (7) обеспечивает регулярность X в точке x.

Для доказательства достаточно заметить, что множество K(X,x) является замкнутым, а включение G⁰(x) М K(X,x) приводит к [`(G⁰(x))] Н K(X,x) после взятия операции замыкания.

Утверждение 7. Достаточным для (7) является

G0(x) № Ж.

(8)

Доказательство. Из (8) для алгебраической суммы G и G⁰ следует: G+G⁰ Н G⁰, т.е. [`(G+G<sup>0</sup>)] Н [`(G⁰)], а [`(G<sup>0</sup>)] К [`0] дает G+[`(G⁰)] К G. И из линейности оператора замыкания и замкнутости G получаем (7).

Для выпуклых X выполнение (8) и, следовательно, регулярность (в любой точке) ограничений (3) гарантируется условием Слэйтера ($xў О X:  gў_i(x) < 0  "i О M). Линейные ограничения всегда регулярны (множество G совпадает с контингентным конусом), хотя условие Слэйтера или (8) для них может не выполняться.

Другие типы условий регулярности, а также условия регулярности для смешанных систем ограничений равенств и неравенств см. в [4-6]. В частности, классическим условием регулярности для ограничений-равенств является линейная независимость градиентов ограничений в экстремальной точке.

УПРАЖНЕНИЕ 8. Получить теорему двойственности ЛП как следствие теоремы Куна-Таккера (для случая озЛП).

Условия оптимальности служат основным инструментом теоретического исследования задач условной оптимизации. Чтобы численно (приближенно) найти условный экстремум с их помощью, применяют методы безусловной оптимизации для поиска седловой точки функции Лагранжа или комбинируют штрафную функцию с функцией Лагранжа для получения точного гладкого штрафа. К сожалению, все эти методы останавливаются в первом попавшемся локальном экстремуме. Глобальный оптимум можно искать, перебирая локальные оптимумы, но для задач неодномерной минимизации не понятно, как находить все локальные оптимумы. Некоторые из существующих подходов к решению задач глобальной оптимизации приводятся в следующем параграфе.

Окончание