Lagrange multipliers rule for a general extremum problem with an infinite number of constraints
Lagrange multipliers rule for a general extremum problem with an infinite number of constraints
Annotation
PII
S265838870000173-3-1
DOI
10.33276/S0000173-3-1
Publication type
Article
Status
Published
Authors
Andrei Dmitruk 
Occupation: Leading researcher, Professor
Affiliation: CEMI RAS, Lomonosov Moscow State University, Dept. of Optimal Control
Address: Moscow, Nakhimovsky prospect 47
Nikolai Osmolovskii
Occupation: Professor
Affiliation:
Moscow State University of Civil Engineering, Faculty of Applied Mathematics
University of Technology and Humanities in Radom
Address: Russian Federation, Moscow, 26, Yaroslavskoye Shosse
Edition
Abstract
We consider a General optimization problem in an arbitrary Banach space with equality and inequality constraints, of which the latter are given in the form of convex cones with non-empty internals. The necessary optimality condition is obtained in the form of the Lagrange multiplier rule, which is convenient for application in a wide class of optimization problems. Some special cases and generalizations of the problem are given. As an application, the problem of optimal control with phase and mixed constraints is considered, for which the necessary conditions of the weak minimum are formulated.
Keywords
extremum problem, equality type constraints, in equality type constraints, Lagrange multipliers, Euler—Lagrange equation, state constraints, mixed constraints, adjoint equation, function of bounded variation, Riemann—Stieltjes integral.
Received
03.02.2019
Date of publication
03.02.2019
Number of characters
20061
Number of purchasers
3
Views
244
Readers community rating
1.0 (1 votes)
Cite Download pdf

To download PDF you should sign in

1 Математическое моделирование экономических ситуаций и процессов часто сводится к тем или иным задачам на поиск экстремума некоторой целевой функции при заданных ограничениях. Основной вопрос, который при этом встает – каким условиям должна удовлетворять точка, в которой достигается экстремум (хотя бы локальный)?
2 Наиболее разработанными классами задач являются задачи линейного и выпуклого программирования (см. напр. [1, 2]), в которых ключевые результаты были получены выдающимся советским математиком Л.В. Канторовичем и американскими математиками В. Карушем, Г. Куном и А. Таккером. (Мы не касаемся здесь вопросов численного поиска экстремума.) Важно отметить, что в этих задачах любой локальный минимум является также и глобальным, а необходимые условия минимума первого порядка, как правило (т.е. при некоторых необременительных предположениях) являются и достаточными.
3 В более общей ситуации, когда целевая функция и/или ограничения задачи не выпуклы, локальный минимум, вообще говоря, не является глобальным, и на уровне условий первого порядка (т.е. с использованием информации о значениях только первых производных всех ограничений и целевой функции задачи в данной точке) удается получить лишь необходимые условия минимума. Исторически первой задачей с общими нелинейными ограничениями была классическая задача на условный экстремум, в которой присутствовали лишь ограничения типа равенства, и ответ давался в виде т.н. правила множителей Лагранжа, состоящего в добавлении к целевой функции всех ограничений с неопределенными множителями, и в поиске у полученной функции Лагранжа ее стационарных точек, т.е. точек, удовлетворяющих необходимому условию минимума этой функции уже безо всяких ограничений. Правило множителей Лагранжа (иногда его называют также принципом снятия ограничений) является центральным результатом всей теории экстремума, а сами множители Лагранжа играют ключевую роль в поиске решения задачи, при этом в моделях экономического содержания они есть не что иное, как цены на соответствующие товары и ресурсы.
4 Различным более общим постановкам нелинейных и невыпуклых задач на экстремум посвящено огромное число работ, как отечественных, так и зарубежных, начиная с конца 1940-х годов (Ф.Джон, Л.Гурвиц, Р.В.Гамкрелидзе и Г.Л.Харатишвили, Б.Н.Пшеничный, А.Я.Дубовицкий и А.А.Милютин, А.Д.Иоффе и В.М.Тихомиров, В.А.Якубович и А.С.Матвеев, П.П.Варайя, И.Нагахиса и И.Сакава, С.Курсьюч, Х.Маурер и Й.Цове, Д.О.Норрис, Б.Х.Порсио, Р.Т.Рокафеллар, Е.В.Тамминен, Дж.Ян, и многие др., см. напр. обзорную статью [5]). Не претендуя на абсолютную новизну, рассмотрим здесь некоторую абстрактную постановку, которая охватывает широкий класс задач оптимизации, и дадим необходимое условие локального минимума, которое очень просто формулируется (и несложно доказывается!) и поэтому удобно для применения в конкретных задачах. Мы будем использовать стандартные понятия функционального анализа, которые можно найти напр. в книгах [3, 4].
5 Пусть X, Y и Zi, i=1…,v, есть банаховы (т.е. полные нормированные) пространства, -- замкнутые выпуклые конусы с непустой внутренностью. Как обычно, через будем обозначать пространства линейных непрерывных функционалов над пространствами (т.н. сопряженные пространства), а через -- полярный конус к .
6 Пусть заданы отображения и
7 Рассмотрим следующую задачу на экстремум:
8 (1)
9 Отметим, что обычные скалярные ограничения неравенства , где -- заданные функционалы, также можно представить в виде если взять в качествеконус неположительных чисел. Тогда полярный к нему есть конус неотрицательных чисел.
10 Предположения. 1) Целевая функция F0 и отображения f дифференцируемы по Фреше в некоторой точке а оператор g дифференцируем по Фреше в некоторой окрестности точки x0 и его производная непрерывна в этой точке (предположения гладкости),
11 2) образ производной замкнут в Y (ослабленная регулярность ограничения равенства).
12 Если (т.е. производная имеет полный образ), то говорят, что ограничения равенства регулярны, или невырождены, а оператор g удовлетворяет условию Люстерника [3, 6].
13 Несмотря на то, что все отображения здесь дифференцируемы, задача (1) не является стандартной гладкой задачей, так как каждое ограничение может задаваться бесконечным числом скалярных неравенств (ибо конусы могут не быть конечногранными, а пространства могут быть бесконечномерными). По этой причине задачу (1) можно назвать полугладкой. (В зарубежной литературе такие задачи называются полубесконечными.)
14 Типичное приложение задачи (1) – это задачи оптимального управления с ограничениями на фазовые компоненты процесса вида или со смешанными ограничениями на фазовые и управляющие компоненты (см. [6—8]). Эти неравенства должны выполняться при каждом (или почти каждом) значении t из заданного промежутка поэтому их можно трактовать как принадлежность и к конусам неположительных функций в пространствах и соответственно.
15 В модельных экономических задачах -- это некоторая накопленная, кумулятивная величина (капитал, трудовые ресурсы, запасы сырья, суммарные инвестиции, технический уровень производства, уровень квалификации работников и т.п.), а параметр управления, мгновенная величина (темп инвестиций в производство, найм и увольнение сотрудников в единицу времени, вложения в обучение персонала в единицу времени, скорость расхода и пополнения запасов и т.п.). Если, скажем, это капитал фирмы, то фазовое ограничение (или в нашей «канонической» форме ) -- очень важное условие, означающее, что фирма не должна разориться.
16 А если темп инвестиций, а F(x) - производственная функция, зависящая от капитала x то типичным смешанным ограничением является неравенство т.е. (инвестиции делаются только из текущего дохода, не прибегая к займам). Важность учета подобных ограничений не вызывает сомнений, однако до сих пор правильный с математической точки зрения учет их наблюдается довольно редко, поэтому число корректно решенных задач с такими ограничениями очень невелико.
17 Перейдем к необходимым условиям оптимальности для задачи (1). Индекс назовем активным в точке x0 если (границе конуса Ki) . Через обозначим касательный конус к конусу Ki в произвольной точке z
18 Теорема 1. Пусть x0есть точка локального минимума в задаче (1).
19 Тогда найдутся множители Лагранжа и
20 не все равные нулю, такие что и ,
21 (т.е. каждый есть внешняя нормаль к конусу Ki в точке) ,
22 и при этом функция Лагранжа
23 (2)
24 стационарна в x0:
25 Последнее равенство называется уравнением Эйлера--Лагранжа.
26 Кроме того, если (условие Люстерника), и существует такой что
27 и для всех активных i (условие регулярности ограничений задачи), то и можно положить т.е. реализуется так наз. нормальный случай (в отличие от анормального, когда .
28 (Поясним, что здесь есть линейный функционал на пространстве X, переводящий любой элемент в число . Аналогичный смысл имеет выражение . )
29 Обратим внимание, что условия дополняющей нежесткости здесь не требуются: если индекс i не активный, т.е. то в данной точке автоматически внешняя нормаль
30 Доказательство проводится по известной схеме Дубовицкого—Милютина (см. напр. [6, 7]). Эта схема состоит из двух шагов. На первом шаге делается переход от локального минимума к несовместности системы конусных аппроксимаций всех ограничений и целевого функционала задачи, а на втором шаге эта несовместность переписывается в виде соответствующего уравнения Эйлера—Лагранжа. При этом используются лишь стандартные факты выпуклого анализа (теорема об отделимости, теорема Дубовицкого—Милютина о непересечении конусов, теорема Фаркаша—Минковского о сопряженном конусе к линейному прообразу данного конуса, лемма об аннуляторе ядра сюрьективного оператора), и теорема Люстерника об оценке расстояния до множества решений нелинейного равенства). Детальное изложение доказательства см. в [9, 10].
31 Некоторые важные случаи и обобщения.
32 1) Если конус Ki задается конечным числом линейных неравенств где то функция Лагранжа имеет прежний вид (2), но множители имеют вид при некоторых Однако здесь надо уже учитывать условия дополняющей нежесткости:
33 2) Как известно, любые замкнутые выпуклые конусы Ki с непустой внутренностью могут быть заданы скалярными неравенствами где сублинейные функции на пространствах Zi, у которых ноль не есть минимальное значение. Т.е. задача (1) может иметь такой эквивалентный вид:
34 (3)
35 В этом случае в функции Лагранжа (2) надо полагать где а есть элементы субдифференциала (т.е. субградиенты) функции в точке. Здесь также надо учитывать условия дополняющей нежесткости: а нетривиальным должен быть набор
36 В условиях, обеспечивающих нормальность множителей Лагранжа, можно заменить требование для активных индексов на неравенство для производной функции по направлению
37 3. С другой стороны, можно рассмотреть некоторое обобщение задачи (1), когда вместо конусов Ki, могут фигурировать произвольные выпуклые множества Qi с непустой внутренностью, т.е. можно рассмотреть задачу
38 (4)
39 В этом случае функция Лагранжа по-прежнему имеет вид (2), где -- по-прежнему внешние нормали к множествам Qi в точках (Теперь эти условия задаются неравенствами а условия , справедливые в случае конусов, отсутствуют.)
40 Доказательство необходимого условия остается тем же самым. В условиях, обеспечивающих нормальность множителей Лагранжа (т.е.), под надо понимать, естественно, касательный конус к множеству Qi в точке z, т.е. надо заменить требование на для всех активных индексов.
41 4. Если множества Qi заданы неравенствами где все выпуклые функции, у каждой из которых не есть точка минимума на всем пространстве Zi, т.е. задача имеет вид
42 (5)
43 то т.е. по-прежнему где а ,
44 и тогда функция Лагранжа имеет вид
45 . (6)
46 Условия нетривиальности и дополняющей нежесткости прежние. В условиях, обеспечивающих нормальность множителей Лагранжа, требование для активных индексов, как и в п. 2, можно заменить на неравенство .
47 (Отметим, что если при некотором i функция имеет минимум на всем пространстве Zi в точке то можно гарантировать лишь множители, из которых данное а остальные, в том числе нулевые.)
48 5. Целевая функция F0 так же, как и остальные, может иметь вид где есть гладкое отображение, а выпуклая функция на пространстве у которой не есть точка минимума на всем пространстве (иначе ограничения задачи не играют роли). В этом случае нулевой член в функции Лагранжа будет иметь вид, подобный всем другим i-м членам: , где а,
49 6. Наконец, отметим, что задача (5) с целевой функцией из п. 5 содержит как частный случай стандартную задачу выпуклого программирования (см. [2, 3]) : если при всех пространства все отображения тождественные, а оператор аффинный: где линейный оператор (т.е. где все а заданный вектор, то мы имеем задачу
50 . (7)
51 Здесь множитель есть некоторый вектор из функция Лагранжа
52 (8)
53 где и удовлетворяют указанным в п. 4 свойствам, а уравнение Эйлера—Лагранжа
54 (9)
55 есть не что иное, как субдифференциальная форма теоремы Каруша--Куна—Таккера [3]. Заметим, что в этом «чисто выпуклом» случае функция Лагранжа (8) есть по сути опорная функция к «стандартной» функции Лагранжа задачи (7):
56
57 и равенство (9) означает, что т.е. что функция (в силу ее выпуклости) достигает минимума по всему пространству X в данной точке x0. При этом условия нормальности из п. 4 превращаются в следующие: AX=Rm и существует такой что и для всех активных индексов i выполнено
58 Если ввести аффинное подпространство то с учетом выпуклости функций последнее неравенство эквивалентно тому, что существует для которого Это есть известное условие Слейтера для задачи (7).
59 7. Случай, когда в выпуклой задаче (7) происходит снятие (т.е. включение в функцию Лагранжа) не всех, а лишь части ограничений, легко вытекает из изложенного. Если, скажем, выделить последнее ограничение то при условии, что неравенство задает его регулярным образом (т.е. функция имеет и значения < 0),
60 то минимум по всему пространству X эквивалентен минимуму “укороченной” функции Лагранжа (без члена по множеству Условие Слейтера в этом случае состоит в том, что C есть внутренняя точка множества и существует для которого при всех активных Это гарантирует, что a0>0.
61 Применение к задачам оптимального управления с фазовыми и смешанными ограничениями [8]
62 Пусть на фиксированном отрезке времени задана управляемая система
63 (10)
64 где x(t) есть n-мерная переменная, описывающая состояние системы (она называется фазовой переменной), а u(t) есть n-мерная управляющая переменная (или просто управление). Функция x(t) предполагается липшицевой (т.е. удовлетворяющей неравенству для всех при некотором L, своем для каждой функции), а u(t) -- измеримой и ограниченной.
65 Отметим, что требование измеримости u(t) является формально-математическим (без него нельзя пользоваться необходимыми классическими теоремами), но на практике с неизмеримой функцией мы никогда не встретимся, и даже не сможем ее специально построить (можно лишь доказать существование таких функций). Поэтому фактически u(t) -- любая сколь угодно разрывная функция, требуется лишь, чтобы она была ограниченной (т.е. при некотором C, своем для каждой функции).
66 Пара функций , удовлетворяющая системе (3), называется процессом. Из множества всевозможных процессов отбираются те, для которых выполнены концевые ограничения равенства и неравенства
67 (11)
68 (12)
69 фазовые ограничения
70 (13)
71 и смешанные ограничения на фазовые и управляющие переменные
72 (14)
73 (15)
74 Такие процессы называются допустимыми. Здесь для экономии букв через d(F) и т.п. обозначены размерности вектор-функций и т.п.
75 На множестве всех допустимых процессов требуется минимизировать заданный функционал:
76 (16)
77 Допустимый процесс называется оптимальным в слабом смысле, если он доставляет т.н. слабый минимум, т.е. если найдется такое что для любого другого допустимого процесса , у которого и
78 (т.е. который проходит в трубке вокруг данного процесса), выполняется неравенство
79

80 Наша цель – дать необходимые условия оптимальности для задачи (10)—(16).
81 Установочные функции этой задачи -- предполагаются непрерывно дифференцируемыми по своим переменным (предположение о гладкости). Как правило, это всегда выполнено в практических задачах.
82 Заметим, что в нашей задаче отсутствует общепринятое ограничение типа включения Причина в том, что оно плохо сочетается со смешанными ограничениями. Однако на практике множество U почти всегда может быть задано гладкими ограничениями равенства и неравенства: которые надо трактовать как смешанные.
83 Относительно смешанных ограничений примем предположение об их регулярности, состоящее в следующем. Для любой тройки введем множество активных индексов смешанных ограничений неравенства:
84 Тогда для любого набора градиенты по u
85

86

87 должны быть позитивно-линейно независимы (линейно независимы с неотрицательными коэффициентами при : т.е. не должно существовать множителей таких что и
88 Это предположение, как правило, также выполнено в практических задачах, но все-таки не всегда. (Если оно не выполняется, исследование задачи и даже формулировка результата существенно усложняется, см. [7].)
89 Для формулировки условий оптимальности укажем вид всех множителей Лагранжа в задаче (10)—(16). При целевом функционале (16) и концевых ограничениях (11—12) это будут, как обычно, число и векторы которые формируют концевую функцию Лагранжа
90

91 Можно показать, что множителем при управляемой системе (которую мы запишем в виде равенства будет функция ограниченной вариации (это означает, что она есть разность двух монотонных функций). Она называется сопряженной функцией задачи.
92 Множителями при фазовых ограничениях (13) будут -- обобщенные производные неубывающих функций с условием которые порождают меры на отрезке [0, T]. (Чуть ниже мы поясним, как это понимать.)
93 Наконец, благодаря предположению о регулярности смешанных ограничений (14—15) можно показать [6—8], что множителями при них будут измеримые ограниченные функции и .
94

Таким образом, функция Лагранжа задачи (10)—(16) будет иметь вид:

95 (17)
96 Отметим, что это есть функционал на пространстве пар функций . (Здесь первая сумма состоит из интегралов Римана—Стилтьеса [4] от функций по мере ).
97 Перейдем непосредственно к условиям оптимальности. Пусть процесс слабо оптимален. Относительно него будем предполагать, что его концы не лежат на фазовых границах, а точнее, что
98 (18)
99 В этом случае функции и непрерывны в концах отрезка.
100 Из теоремы 1 следует, что найдутся множители указанного вида, не все равное нулю, из них множители при целевом функционале и ограничениях неравенства неотрицательны:
101 , , (19)
102 удовлетворяют условиям дополняющей нежесткости:
103

104 (20)
105

106 и при этом функция Лагранжа (17) стационарна на паре, т.е. ее производная Фреше Расшифровка этого функционального равенства приводит к следующему окончательному результату (полученному А.Я. Дубовицким и А.А. Милютиным в 1960-х годах, см. [6, 7]).
107 Введем функцию Понтрягина задачи (10)—(16)
108

109 а также расширенную функцию Понтрягина
110

111

112 Теорема 2. Пусть процесс слабо оптимален и удовлетворяет предположению (18). Тогда найдутся множителей Лагранжа указанного вида, для которых выполняются условия неотрицательности (19), дополняющей нежесткости (20), сопряженное уравнение
113 (21)
114 ,
115 условия трансверсальности
116 (22)
117 и условие стационарности по управлению
118 (23)
119

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

122 ,
123

и аналогичное равенство справедливо для значения

124 Условия дополняющей нежесткости говорят о том, что на тех интервалах, где мера не работает: она может работать только при выходе на «фазовую границу», когда
125 Как правило, на практике имеется представление где обе составляющие также неубывают, равны нулю в нуле, при этом функции кусочно-дифференцируемы, а кусочно-постоянны. В тех точках , где имеют скачки (а таких точек конечное число), функция также имеет скачок (возможно, равный нулю), а между этими точками удовлетворяет обыкновенному дифференциальному уравнению, которое получается из (21) заменой обобщенной производной на обычную.
126 Строго говоря [4], у функций может быть еще и третья составляющая: где -- т.н. сингулярная функция (производная которой почти всюду равна нулю, но сама функция не есть константа), однако ни в каких
127 реальных задачах эта составляющая до сих пор не появлялась. Поэтому, хотя теоретически вопрос о ее возможном наличии остается открытым, в практических задачах без какого-либо риска можно ее не учитывать.
128 Обратим внимание, что из-за указанной непривычности множителей при фазовых ограничениях, задачи с такими ограничениями довольно сложны для исследования, и до сих пор решено лишь сравнительно небольшое число подобных задач. В этом отношении задачи с наличием лишь смешанных регулярных ограничений проще, чем задачи с чисто фазовыми, поскольку условия оптимальности для первых формулируются в общеупотребительных терминах, вполне привычных для прикладников.

References

1. D.B. Yudin, E.G. Gol'shtejn. Linejnoe programmirovanie. M., Nauka, 1969.

2. S.I. Zukhovitskij, L.I. Avdeeva. Linejnoe i vypukloe programmirovanie. M., Nauka, 1967.

3. V.M. Alekseev, V.M. Tikhomirov, S.V. Fomin. Optimal'noe upravlenie. M., Nauka, 1979, Fizmatlit, 2005.

4. A.N. Kolmogorov, S.V. Fomin. Ehlementy teorii funktsij i funktsional'nogo analiza. M., Nauka, 1976.

5. R.T. Rockafellar, Lagrange multipliers and optimality // SIAM Review, 1993, v. 35, no. 2, p. 183—238.

6. A.A. Milyutin, A.V. Dmitruk, N.P. Osmolovskij. Printsip maksimuma v optimal'nom upravlenii. Izd-vo mekhmata MGU, 2004, 168 s. http://www.math.msu.su/department/opu/node/139

7. A.V. Dmitruk. On the development of Pontryagin's Maximum principle in the works of A.Ya. Dubovitskii and A.A. Milyutin // Control & Cybernetics, 2009, v. 38, no. 4a, p. 923—958.

8. A.V. Dmitruk, N.P. Osmolovskii. Necessary conditions for a weak minimum in optimal control problems with integral equations subject to state and mixed constraints // SIAM J. on Control and Optimization, v. 52, no. 6, p. 3437—3462 (2014).

9. A. Dmitruk, N. Osmolovskii. A General Lagrange Multipliers Theorem // Constructive Nonsmooth Analysis and Related Topics (CNSA-2017), IEEE Xplore Digital Library, 2017. DOI: 10.1109/CNSA.2017.7973951

10. A.V. Dmitruk, N.P. Osmolovskii. A General Lagrange Multipliers Theorem and Related Questions // Control Systems and Math. Methods in Economics (Feichtinger et al. eds,), Lecture Notes in Economics and Math. Systems, v. 687, p. 165—194, Springer, 2018.