Прикладная выпуклая оптимизация. Выпуклая оптимизация

5. ВЫПУКЛЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ

где G замкнутая ограниченная область, граница которой задана уравне-

ниями gi (x)= 0,i =1,2,...,m..

Решение задачи состоит из следующих этапов:

1) находим все стационарные точки функции f, лежащие внутри областиG :х1,х2,...,хL;

2) методом множителей Лагранжа решаем следующую задачу на условный экстремум:

L(x)= f (x)+ ∑λi (hi (x)− zi2 )→ min,

i=1

инаходим условно-стационарныеточкиxL+1,...,xS из необходимых условий:

∂L	= 0,i =1,2,...,m,	∂L	= gi (x)= 0,

∂xi		∂λi

∂L = −2 λi zi =0; ∂zi

3)из стационарных точек х1,x2,...,хL выбираем те, в которых выполняются достаточные условия локального минимума:хL1,хL2,...,хLk ;

4)сравнивая значения функции f в точкаххL1,хL2,...,хLk с ее значениями вусловно-стационарныхточкахxL+1,...,xS, находим

min f (x).

x G

5.1. Постановка задачи

Выпуклой задачей (или задачей выпуклого программирования) называется следующая задача оптимизации:

f (x)→ min;gi (x)≤ 0,	i =1,2,...,m;
x G Rn ,	(5.1)
	48

где f,g1,g2,....,gm – выпуклые функции, заданные на выпуклом и замкнутом множествеG .

Точка х, принадлежащая множествуG и удовлетворяющая неравенствамgi (x) ≤ 0, i =1,2,..., m; . называется допустимой в задаче (5.1).

Теорема 5.1:

Если функция f определена и выпукла на выпуклом множествеG Rn, то в выпуклой задаче локальный минимум является и глобальным.

Пусть х – точка локального минимума функцииf, т.е.ε0 > 0 такое,

что

f (x€) ≤ f(x) x G∩U(x€,ε0 ).

Возьмем произвольную фиксированную точку x'G. Из условия выпуклости множестваG следует, что точка

€	+ (1	−λ)x'	λ (0,1)
x = λx

принадлежит множеству G. При

λ ≥1− x'ε−x€,

где

ε < min{ε0 ,x'−x€},

получаем

x'−x€ = λx'+(1− λ)x'−x€ = (1− λ)(x'−x€) ≤ (1− λ)x'−x€

≤ 1 −1 −x'ε−x€x'−x€=x'ε−x€x'−x€=ε <ε0 ,

что означает

x U (x€,ε0 )

и, следовательно,

€	€	€	+ (1	−λ)x').
f (x)≤ f (x) или	f (x) ≤	f (λx	+ (1	−λ)x').

По условию функция f выпукла. Поэтому последнее неравенство примет вид

f (x€)≤ λf (x€)+ (1− λ)f (x').

В частности, при

λ =1 −x'ε−x€

имеем

f (x€)≤ 1− x'ε−x€ f (x€)+ 1− 1− x'ε−x€ f (x').

Отсюда

ε	€	ε	f (x'),
€	€	€
€	f (x) ≤	€
x'−x		x'−x

или

f (x€)≤ f (x').

Так как х' – произвольная точка множестваG, то из последнего неравенства следует, чтох – точка глобального минимума функцииf наG.

В дальнейшем в выпуклых задачах оптимизации, говоря "минимум", будем, подразумевать глобальный минимум.

Пример 5:

Функция

f (x1, x2 ) = x12 + x22

выпукла на R2, (0,0) – точка локального минимума функцииf, она же и точка глобального минимумаf наR2

(f (0,0)= 0≤ x12 + x22 (x1,x2 )R2 ).

5.2.Условия оптимальности в выпуклых задачах

Ввыпуклых задачах оптимизации важное место занимает функция Лагранжа и понятие так называемой седловой точки функции Лагранжа.

П = G × R+m

Пусть – декартово произведение множества G (области определения функцийf (x) иg(х),i=1,2,...,m, в задаче (5.1)) и множестваm-мерныхвекторов с неотрицательными координатами

Rm ={λ = (λ ,λ ,...,λ )Rm			λ ≥ 0,i =1,2,...,m }.
Rm ={λ = (λ ,λ ,...,λ )Rm			λ ≥ 0,i =1,2,...,m }.
+	1 2	m	i
Функция
	L(x,λ)= f (x)+ (λ,g(x)), (x,λ)П,			(5.2)

где

(λ,g(x))= ∑λi gi (x)

i=1

– скалярное произведение векторов λ иg(х), называется функцией Лагранжа для выпуклой задачи оптимизации (5.1).

Точка (x*,λ* ) П, называетсяседловой точкой функции ЛагранжаL(x,λ), (x,λ) П, если выполняются неравенства

L(x,λ)≤ L(x,λ* )≤ L(x,λ* ),	x G, λ R+m	(5.3)
Условие (5.3) может быть записано также следующим образом
L(x,λ )= min maxL(x,λ)= max minL(x,λ).
x G λ R+m	λ R+m x G

Пример 6:

Функция Лагранжа для выпуклой задачи (5.1) при

n=1,m=1,f (x)=6 –x,g(x)=х/2 – 1

имеет вид

x
L(x,λ)= 6− x + λ		−1 ,	x R+, λ R+
	5

иимеет седловую точку (5,5). Ее график изображен на рисунке 5.

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

L(x,λ). Что же касается выпуклой задачи оптимизации, то ее решение сводится к отысканию седловой точки функции Лагранжа.

Теорема 5.2:

Если пара (x*,λ*) – седловая точка функции Лагранжа (5.2), тох* – точка глобального минимума в задаче (5.1), т.е.

f(x* )= minf (x).

Пусть (x*,λ*) – некоторая седловая точка функции Лагранжа. Из

(5.2) и (5.3) получаем

f (x* )+ (λ,g(x* ))≤ f (x* )+ (λ,g(x ))≤ f (x)+ (λ*,g(x)).		(5.4)
Из левой части неравенства (5.4) следует, что
(λ,g(x* ))≤ (λ,g(x )).		(5.5)
Отсюда
(λ − λ,g(x ))≤ 0,
или в развернутом виде
m
∑(λi − λi )gi (x )≤ 0.		(5.6)
i=1
Поскольку λ*i ≥ 0 ,i=1,2,...,m,	неравенство (5.6) имеет место, если
gi (x* )≤ 0,	i =1,2,...,m.

Итак, gi(х*)≤ 0 и, кроме того,

m ∑λ*i gi

i =1

Равенство (5.6) справедливо,

т.е.

m ∑λ*i gi

i =1

λ*i ≥ 0 , поэтому

(x* )≤ 0.

в частности, и для

(x* )≥ 0.

(5.7)

λi = 0 ,i=1,2,...,m,

(5.8)

Сравнивая неравенства (5.7) и (5.8), будем иметь

∑λ*i gi (x* )= 0,

i =1

т.е.

(λ,g(x ))= 0.	(5.9)
Так как
x G gi (x)≤ 0,i =1,2,...,m и λi ≥ 0,	i =1,2,...,m,
то
m
∑λ*i gi (x)≤ 0,
i=1
или
(λ*,g(x))≤ 0.	(5.10)

Неравенство (5.4) имеет место x G , поэтому из его правой части и из(5.9)-(5.10)получим

f (x* )≤ f (x)+ (λ*,g(x))≤ f (x)x G.

Следовательно, х* – точка глобального минимума.

Теорема 5.3:

Для того чтобы пара (х*,λ*) являлась седловой точкой функции Лагранжа (5.2), необходимо и достаточно выполнение условий

L(x,λ )= minL(x,λ* ),		(5.11)
x G
gi (x* )≤ 0,	i =1,2,...,m,	(5.12)
λi gi (x )= 0,	i =1,2,...,m .	(5.13)

Необходимость. Пусть (х*,λ*) – седловая точка функции (5.2). Тогда по определению

L(x*,λ* )≤ L(x,λ* )x G,

что означает справедливость равенства (5.11).

Выполнение условий (5.12) и (5.13) было показано при доказательстве теоремы (5.2).

Достаточность. Пусть выполнены условия (5.11)-(5.13).Равенство (5.11) влечет справедливость правой части неравенства (5.3)x G. До-

кажем выполнение левой части неравенства (5.3) для всех λ R+m . Для

этого рассмотрим произвольные неотрицательные числа λ1,λ2,…,λm, Очевидно,

λ g	(x*)≤ 0,i =1,2,...,m.
i i

Поэтому, используя неравенства (5.12) и (5.13), можно записать:

λ g	(x* )≤ λ*g	(x* ),i =1,2,...,m.
i i	i

Следовательно,

f (x* ) + (λi g(x* ))≤ f(x*) + (λ*g(x* )),

что означает справедливость левой части неравенства (5.3).

Следует отметить, что теоремы 5.2 и 5.3 получены без каких-либопредположений о свойствах функцийf , g1, g2 ,..., gm и структуре множестваG.

В соответствии с теоремой 5.2, если удастся найти седловую точку функции Лагранжа (5.2), то тем самым будет решена задача (5.1), в которой все функции f иgi ,i=1,2,...,m, а также множествоG могут иметь различную природу, причемх* будет точкой глобального минимума. Если теоретически такой подход безупречен, то его реализация на практике возможна не всегда. Дело в том, что если функцииf,gi,i=1,2,...,m, и множествоG не выпуклы, то функция Лагранжа не всегда имеет седловые точки. Более того, даже если указанные функции и множество выпуклы и оптимальное решение задачи (5.1) существует, то в некоторых "вырожденных" случаях соответствующая функция Лагранжа может не иметь ни одной седловой точки.

Подтверждением последнего может служить следующая задача, в которой


n =1,m =1,	f (x) = −x;
g(x) = x2 ≤ 0, G= {x R		x ≥ 0}

Здесь функции f (x) = −x,	g1(x) = x2 и множествоG выпуклы.

Единственная точка х*=0 удовлетворяет ограничениям задачи; она же является и точкой глобального минимума. Однако функция ЛагранжаL(x,λ) =–х+λх2 не имеет седловых точек (не выполняется необходимые

studfiles.net

optimization - Выпуклая оптимизация CVX-esque в R?

ОК, поэтому короткий ответ на этот вопрос: действительно нет очень удовлетворительного способа справиться с этим в R. Я закончил работу над соответствующими частями в Matlab с некоторым неудобным промахом между этими двумя системами и, вероятно, перенесет все к Matlab в конце концов. (Мой текущий подход предшествует ответу, отправленному пользователем2439686. На практике моя проблема была бы столь же неудобной с использованием CVXfromR, но она действительно выглядит как полезный пакет в целом, поэтому я собираюсь принять этот ответ.)

R ресурсов для этого довольно тонкие на земле, но блога Vincent Zoonekynd, о котором он упомянул в комментариях, определенно стоит прочитать.

Решатель SOCP, содержащийся в R-пакете DWD, переносится с решателя Matlab SDPT3 (за вычетом частей SDP), поэтому программный интерфейс в основном тот же. Однако, по крайней мере, в моих тестах он работает намного медленнее и в значительной степени падает на проблемы с несколькими тысячами vars + ограничений, тогда как SDPT3 решает их через несколько секунд. (Я не сделал вполне справедливого сравнения по этому поводу, потому что CVX делает некоторые изящные преобразования в проблеме, чтобы сделать его более эффективным, в то время как в R я использую довольно наивное определение, но все же.)

Другая возможная альтернатива, особенно если вы имеете право на получение академической лицензии, заключается в использовании коммерческого Mosek решателя, который имеет R Rmosek. Мне еще предстоит попробовать это, но в какой-то момент это может пойти.

(Как и в остальном, другой решатель, связанный с CVX, SeDuMi, полностью не справляется с одной и той же проблемой, авторы CVX не шучу, когда предлагают попробовать несколько решателей. Кроме того, в значительном подмножестве случаев SDTP3 должен переключиться с Cholesky на LU-декомпозицию, что делает порядки обработки медленнее, только с очень незначительным улучшением цели по сравнению с этапами, предшествующими LU. Я счел целесообразным уменьшить запрошенную точность, чтобы избежать этого, но YMMV.)

qaru.site

Прикладная выпуклая оптимизация — ФУПМ

Курс от лаборатории Премолаб и базовый курс от кафедры Вычислительной математики.

Занятия проходят по пятницам в 303 КПМ в 15:30. Лектор: П.Е.Двуреченский

Внимание! В ближайшую пятницу, 3 октября, занятия не будет.

Программа курса:

1. Основные понятия и определения теории оптимизации. Знакомство с программным продуктом CVX. Простейшие задачи выпуклого программирования. Модель линейной регрессии. Задача об оптимальном портфеле ценных бумаг.

2. Начальные сведения о робастной оптимизации. Задача о поиске оптимального портфеля ценных бумаг в робастном случае. Задание ограничений на вероятности события в CVX.

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

4. Арбитраж на рынке ценных бумаг и теорема об альтернативах. Статистический арбитраж.

5. Аппроксимация данного вектора разреженным. Задача о выделении тренда в финансовых временных рядах с помощью L1-фильтрации. Регуляризация и пенализация. Работа индексных фондов и аппроксимация данного вектора разреженным с помощью L1-пенализации.

6. Об алгоритмах решения задач выпуклой оптимизации: Прямо-двойственный алгоритм внутренней точки.

7. Оптимизация и статистика. Построение оптимальных классификаторов. Оптимизация и метод максимума правдоподобия.

8. Оптимизация и статистика II. Обнаружение гармонического сигнала в шуме.

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

10. Контроль за риском инвестирования при неполной информации о матрице ковариации активов и worst-case анализ.

11. Задача о ранжировании интернет-страниц (Page Rank) и ее вариации. Google и выпуклая оптимизация.

12. Поиск равновесия макросистем. Задачи линейно-энтропийного программирования. Современная выпуклая оптимизация.

Ознакомиться с учебной программой курса можно по ссылке.

mipt.ru

Выпуклая оптимизация • ru.knowledgr.com

Выпуклая минимизация, подполе оптимизации, изучает проблему уменьшения выпуклых функций по выпуклым наборам. Собственность выпуклости может сделать оптимизацию в некотором смысле «легче», чем общий случай - например, любой местный минимум должен быть глобальным минимумом.

Учитывая реальное векторное пространство вместе с выпуклой, функцией с реальным знаком

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

: для всех.

Выпуклость делает мощные инструменты из выпуклого анализа применимыми. В конечно-размерных местах normed Hahn-банаховая теорема и существование подградиентов приводят к особенно удовлетворяющей теории необходимых и достаточных условий для optimality, теория дуальности, обобщая это для линейного программирования и эффективных вычислительных методов.

выпуклой минимизации есть применения в широком диапазоне дисциплин, такие как системы автоматического управления, оценка и обработка сигнала, коммуникации и сети, дизайн электронной схемы, анализ данных и моделирование, статистика (оптимальный дизайн), и финансы. С недавними улучшениями вычисления и теории оптимизации, выпуклая минимизация почти столь же прямая как линейное программирование. Много проблем оптимизации могут быть повторно сформулированы как выпуклые проблемы минимизации. Например, проблема увеличения вогнутой функции f может быть повторно сформулирована эквивалентно как проблема уменьшения функции-f, который выпукл.

Выпуклая проблема оптимизации

Проблема оптимизации (также называемый математической программной проблемой или проблемой минимизации) нахождения некоторых таким образом, что

то

, где выполнимый набор и цель, называют выпуклым, если закрытый выпуклый набор и выпукл на.

Альтернативно, проблема оптимизации на форме

&\\operatorname {минимизируют} & & f (x) \\

&\\operatorname {подвергают \; к }\

& &g_i (x) \leq 0, \quad i = 1, \dots, m

назван выпуклым, если функции выпуклы.

Теория

Следующие заявления верны о выпуклой проблеме минимизации:

если местный минимум существует, то это - глобальный минимум.
набор всех (глобальных) минимумов выпукл.
для каждой строго выпуклой функции, если у функции есть минимум, то минимум уникален.

Эти результаты используются теорией выпуклой минимизации наряду с геометрическими понятиями от функционального анализа (в местах Hilbert), таких как теорема проектирования Hilbert, отделяющаяся теорема гиперсамолета и аннотация Фаркаша.

Стандартная форма

Стандартная форма - обычная и самая интуитивная форма описания выпуклой проблемы минимизации. Это состоит из следующих трех частей:

Выпуклая функция, которая будет минимизирована по переменной
Ограничения неравенства формы, где функции - выпуклый
Ограничения равенства формы, где функции аффинные. На практике термины, «линейные» и «аффинные», часто используются попеременно. Такие ограничения могут быть выражены в форме, где вектор колонки и действительное число.

Выпуклая проблема минимизации таким образом написана как

&\\комплект нижнего белья {x} {\\operatorname {минимизируют}} & & f (x) \\

&\\operatorname {подвергают \; к }\

& &g_i (x) \leq 0, \quad i = 1, \dots, m \\

&&&h_i (x) = 0, \quad i = 1, \dots, p.

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

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

Примеры

Следующие проблемы - все выпуклые проблемы минимизации или могут быть преобразованы в выпуклые проблемы минимизаций через замену переменных:

Наименьшие квадраты

Линейное программирование

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

Квадратным образом ограниченная Выпукло-квадратная минимизация с выпуклыми квадратными ограничениями

Коническая оптимизация

Геометрическое программирование

Второй конус заказа, программируя

Полуопределенное программирование

Множители Лагранжа

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

Лагранжевая функция для проблемы -

:L (x,λ, ...,λ) = λf (x) + λg (x) +... + λg (x).

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

это удовлетворяет эти условия одновременно:

x минимизирует L (y, λ, λ..., λ) по всему y в X,
λ ≥ 0, λ ≥ 0..., λ ≥ 0, с по крайней мере одним

>0,

λg (x) = 0..., λg (x) = 0 (дополнительный застой).

Если там существует «строго допустимая точка», т.е., пункт z, удовлетворяющий

:g (z) (z) =1.

С другой стороны, если некоторый x в X удовлетворяет 1-3 для скаляров λ..., λ с λ = 1, то x несомненно минимизирует f более чем X.

Методы

Выпуклые проблемы минимизации могут быть решены следующими современными методами:

Другие методы интереса:

Методы режущего самолета

Эллиптический метод

Метод подградиента

Двойные подградиенты и метод дрейфа плюс штраф

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

Выпуклая минимизация с хорошей сложностью: самосогласующиеся барьеры

Эффективность повторяющихся методов плоха для класса выпуклых проблем, потому что этот класс включает «плохих парней», минимум которых не может быть приближен без большого количества оценок подградиента и функции; таким образом, чтобы иметь практически привлекательные результаты эффективности, необходимо сделать дополнительные ограничения на класс проблем. Два таких класса - проблемы специальные барьерные функции, сначала самосогласующиеся барьерные функции, согласно теории Нестерова и Немировския и вторых саморегулярных барьерных функций согласно теории Terlaky и соавторов.

Квазивыпуклая минимизация

Проблемы с выпуклыми наборами уровня могут быть эффективно минимизированы в теории.

Юрий Нестеров доказал, что квазивыпуклые проблемы минимизации могли быть решены эффективно, и его результаты были расширены Kiwiel. Однако такие теоретически «эффективные» методы используют «расходящийся ряд» stepsize правила, которые были сначала развиты для классических методов подградиента. Классические методы подградиента, используя правила расходящегося ряда намного медленнее, чем современные методы выпуклой минимизации, таковы как методы проектирования подградиента, методы связки спуска, и несглаживают методы фильтра.

Решение даже близко-к-выпуклому, но невыпуклые проблемы может быть в вычислительном отношении тяжелым. Уменьшение функции unimodal тяжело, независимо от гладкости функции, согласно результатам Иванова.

Выпуклая максимизация

Традиционно, определение выпуклой проблемы оптимизации (мы вспоминаем) требует, чтобы объективная функция f, чтобы быть минимизированной и выполнимый набор была выпукла. В особом случае линейного программирования (LP) объективная функция и вогнутая и выпуклая, и таким образом, LP может также рассмотреть проблему увеличения объективной функции без беспорядка. Однако для большинства выпуклых проблем минимизации, объективная функция не вогнутая, и поэтому проблема, и затем такие проблемы сформулированы в стандартной форме выпуклых проблем оптимизации, то есть, минимизировав выпуклую объективную функцию.

Для нелинейной выпуклой минимизации связанной проблемой максимизации, полученной, заменяя supremum оператором infimum оператора, не является проблема выпуклой оптимизации, как традиционно определено. Однако это изучено в более крупной области выпуклой оптимизации как проблема выпуклой максимизации.

Выпуклая проблема максимизации особенно важна для изучения существования максимумов. Рассмотрите ограничение выпуклой функции к компактному выпуклому набору: Затем на том наборе функция достигает своего ограниченного максимума только на границе. Такие результаты, названные «максимальные принципы», полезны в теории гармонических функций, потенциальной теории и частичных отличительных уравнениях.

Проблема уменьшения квадратного многомерного полиномиала на кубе NP-трудная. Фактически, в квадратной проблеме минимизации, если у матрицы есть только одно отрицательное собственное значение, NP-трудное.

Расширения

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

Расширения выпуклых функций включают двояковыпуклые, псевдовыпуклые, и квазивыпуклые функции. Частичные расширения теории выпуклого анализа и повторяющихся методов для того, чтобы приблизительно решить невыпуклые проблемы минимизации происходят в области обобщенной выпуклости («абстрактный выпуклый анализ»).

См. также

Условия Karush–Kuhn–Tucker

Проблема оптимизации

Ближайший метод градиента

Примечания

Borwein, Джонатан, и Льюис, Эдриан. (2000). Выпуклый анализ и нелинейная оптимизация. Спрингер.
Hiriart-Urruty, Жан-Батист, и Лемэречел, Клод. (2004). Основные принципы Выпуклого анализа. Берлин: Спрингер.
Нестеров, Y. и Nemirovsky, A. (1994). 'Методы полиномиала внутренней точки в выпуклом программировании. СИАМ
Нестеров, Юрий. (2004). Вводные лекции по выпуклой оптимизации, Kluwer академические издатели

Внешние ссылки

ru.knowledgr.com

Прикладная выпуклая оптимизация — ФУПМ

Курс от лаборатории Премолаб и базовый курс от кафедры Вычислительной математики.

Занятия проходят по пятницам в 303 КПМ в 15:30. Лектор: П.Е.Двуреченский

Внимание! В ближайшую пятницу, 3 октября, занятия не будет.

Программа курса:

4. Арбитраж на рынке ценных бумаг и теорема об альтернативах. Статистический арбитраж.

6. Об алгоритмах решения задач выпуклой оптимизации: Прямо-двойственный алгоритм внутренней точки.

8. Оптимизация и статистика II. Обнаружение гармонического сигнала в шуме.

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

10. Контроль за риском инвестирования при неполной информации о матрице ковариации активов и worst-case анализ.

11. Задача о ранжировании интернет-страниц (Page Rank) и ее вариации. Google и выпуклая оптимизация.

Ознакомиться с учебной программой курса можно по ссылке.

olymp.mipt.ru

9. Выпуклая оптимизация 9. 1. Функция f,

9. Выпуклая оптимизация 9. 1. Функция f, определенная на выпуклом множестве называется выпуклой, если Если же из строгих неравенств всегда сле для строгие, то функция f называется строго выпуклой. Например, линейная форма – функции, выпуклые на

9. 2. Функция одной переменной выпукла точки плоскости, лежащие над её графиком y образуют выпуклое множество. y = f (x) x Дифференцируемая на промежутке функция y = f (x) выпукла на этом промежутке её производная оказывается неубывающей на нём (или если существует).

9. 3. Функция f , заданная на выпуклом множестве, выпукла тогда и только тогда, когда её надграфик множество – выпукло. 9. 4. Пусть fi – выпуклые функции, определенные на выпуклом множестве Ω , Тогда – выпуклая функция. Если при этом хотя бы одно слагаемое – строго выпуклая функция, то такова же и вся сумма.

9. 5. О выпуклости сложных Если функций. y = h(t) – выпуклая неубывающая функция одной переменной, определенная на множестве значений выпуклой функции то сложная функция – выпуклая. Если к тому же f – строго выпуклая функция, а функция y = h(t) – возрастающая, то функция ψ строго выпукла на множестве Ω (выпуклом). Аналогичные утверждения верны, если имеется k выпуклых функций и выпуклая функция k переменных, возрастающая по каждой из них.

9. 6. Проведем прямую через две точки Если – выпуклое множество, то промежуток. Для любой определенной на Ω функции имеем сечение f – функцию переменной t , заданную на промежутке Для того, чтобы функция была выпуклой [строго выпуклой] необходимо и достаточно, чтобы выпуклой [строго выпуклой] было любое её сечение.

9. 7. Дифференцируемая функция f , определенная на выпуклом множестве Ω, выпукла Условиями строгой выпуклости являются строгие нер 9. 8. Если функция f дважды дифференцируема, рассматривают – матрицу Гессе, в i-ой строке j-ом столбце которой записывают – значение второй производной в точке

9. 9. Для того, чтобы дважды дифференцируемая на открытом выпуклом множестве Ω функция f была выпуклой, необходимо и достаточно, чтобы её матрица Гессе была неотрицательно определена в любой точке – второй дифференциал функции f оказывается неотрицательно определенной квадратичной формой. Если является положительно определенной в любой точке, то f – строго выпуклая функция.

Симметрическая матрица является положительно определенной тогда и только тогда, когда все её угловые миноры положительны. 9. 10. Пример. Строгая выпуклость квадратичной фун следует из положительной определенности её матрицы Гессе:

9. 11. Необходимым и достаточным условием неотрицательной определенности симметрической матрицы является неотрицательность всех её диагональных миноров. Минор матрицы называют диагональным, если он получен из матрицы выделением строк и столбцов с одинаковыми номерами.

9. 12. Пример. Проверим выпуклость квадратичной фу Т. к. её матрица Гессе не является положительно определенной, но все диагональные миноры первого и второго порядка положительны.

9. 13. Для квадратичной функции положительная определенность матрицы Гессе является не только достаточным, но и необходимым условием строгой выпуклости. 9. 14. Свойства матрицы Гессе удобно проверять, зная её собственные значения: если все они неотрицательны, то матрица оказывается неотрицательно определенной; у положительно определенной все собственные значения должны быть положительны.

present5.com

Методы выпуклой оптимизации - PDF

Транскрипт

1 Nesterov-final 2010/4/5 18:26 page 1 #1 Ю. Е. Нестеров Методы выпуклой оптимизации Издательство МЦНМО г. Москва

2 Nesterov-final 2010/4/5 18:26 page 2 #2

3 Nesterov-final 2010/4/5 18:26 page 3 #3 Оглавление Предисловие 7 Благодарности 13 Введение 15 1 Нелинейная оптимизация Задачи нелинейной оптимизации Общая формулировка задачи Эффективность численных методов Оценки вычислительной сложности задач глобальной оптимизации Визитные карточки областей оптимизации Локальные методы безусловной оптимизации Релаксация и аппроксимация Классы дифференцируемых функций Градиентный метод Метод Ньютона Методы первого порядка в нелинейной оптимизации Градиентный метод и метод Ньютона: в чем разница? Сопряженные градиенты Условная минимизация Гладкая выпуклая оптимизация Минимизация гладких функций Гладкие выпуклые функции Нижние границы аналитической сложности для класса,1 L ( n )

4 Nesterov-final 2010/4/5 18:26 page 4 #4 Оглавление Сильно выпуклые функции Нижние границы аналитической сложности для класса,1 µ,l (n ) Градиентный метод Оптимальные методы Оптимальные методы Выпуклые множества Градиентное отображение Методы минимизации на простых множествах Задача минимизации функций с гладкими компонентами Минимаксная задача Градиентное отображение Методы минимизации для минимаксной задачи Оптимизация при функциональных ограничениях Метод условной минимизации Негладкая выпуклая оптимизация Выпуклые функции общего вида Мотивировка и определения Операции с выпуклыми функциями Непрерывность и дифференцируемость Теоремы отделимости Субградиенты Вычисление субградиентов Методы негладкой минимизации Нижние границы сложности для общего случая Основная лемма Субградиентный метод Минимизация при функциональных ограничениях Границы сложности в конечномерном случае Методы отсекающей гиперплоскости Методы с полной информацией Модель негладкой функции Метод Келли Метод уровней Условная минимизация

5 Nesterov-final 2010/4/5 18:26 page 5 #5 Оглавление 4 Структурная оптимизация Самосогласованные функции Концепция «черного ящика» в выпуклой оптимизации Как работает метод Ньютона? Определение самосогласованной функции Основные неравенства Минимизация самосогласованных функций Самосогласованные барьеры Мотивировка Определение самосогласованных барьеров Основные неравенства Метод отслеживания траектории Нахождение аналитического центра Задачи с функциональными ограничениями Приложения структурной оптимизации Границы параметров самосогласованных барьеров Линейная и квадратичная оптимизация Полуопределенная оптимизация Экстремальные эллипсоиды Сепарабельная оптимизация Выбор схемы минимизации Библиографический комментарий 275 Литература 277 5

6 Nesterov-final 2010/4/5 18:26 page 6 #6

7 Nesterov-final 2010/4/5 18:26 page 7 #7 Предисловие редактора Новая эра в нелинейной оптимизации открылась выдающейся статьей Н. Кармаркара, появившейся в середине 1980-х гг. Значение этой работы, в которой предлагался новый полиномиальный алгоритм для задач линейной оптимизации, состояло не только в установлении границ вычислительной сложности. В то время совершенно замечательной особенностью этого алгоритма являлось то, что теоретические оценки его высокой эффективности блестяще подтверждались результатами численных экспериментов. Этот необычный по тем временам факт радикально изменил стиль и направление исследований в области нелинейной оптимизации. С тех пор появление новых методов все чаще стало сопровождаться теоретическим анализом их вычислительной сложности, который теперь обычно рассматривается как более веское доказательство их качества, чем численные эксперименты. В новой и быстро развивающейся области оптимизации, получившей название полиномиальные методы внутренней точки, такое обоснование стало обязательной нормой. Основные результаты первых пятнадцати лет серьезных исследований вошли в монографии [12, 14, 16 19]. Однако эти книги труднодоступны российскому читателю. Более того, они не решают задачи изложения нового взгляда на предмет и цели выпуклой оптимизации. Дело в том, что к тому времени лишь теория методов внутренней точки для задач линейной оптимизации была разработана достаточно подробно, а общая теория самосогласованных функций существовала в печатном виде лишь в форме монографии [12]. Кроме того, было понятно, что новая теория методов внутренней точки представляет собой только часть общей теории выпуклой оптимизации технически довольно сложной дисциплины, включающей такие разделы, как границы вычислительной сложности, оптимальные методы и т. д.

8 Nesterov-final 2010/4/5 18:26 page 8 #8 Предисловие Автор настоящей книги, предлагаемой вниманию читателя, предпринял попытку преодолеть все эти трудности и изложить сложные вопросы в элементарной форме. На мой взгляд, попытка оказалась успешной. Ю. Е. Нестеров внес выдающийся вклад в развитие современной теории и методов выпуклой оптимизации. Еще в 80-е годы прошлого века он развил теорию эффективных методов оптимизации; см. [11]. Позже он совместно с А. С. Немировским предложил новый подход, основанный на самосогласованных функциях и барьерах (см. [12]), что привело к созданию полиномиальных методов оптимизации. В последние годы он опубликовал много работ, посвященных усовершенствованию методов для основных классов оптимизационных задач. Это помогло ему умело произвести отбор материала для книги. Ключевыми стали такие понятия, как вычислительная сложность оптимизационных задач и гарантированная эффективность численных методов, подкрепленная анализом границ сложности. При этом жесткие рамки объема книги обусловили прагматизм изложения каждое понятие или факт, приводимые в монографии, абсолютно необходимы для полноценного анализа по крайней мере одной оптимизационной схемы. До некоторой степени удивительным оказалось то, что при изложении совершенно не потребовалось сведений из теории двойственности, и поэтому этот раздел полностью опущен. Основная цель книги добиться правильного понимания сложности различных задач оптимизации, и цель эта выбрана не случайно. Пользователи постоянно интересуются тем, какой численный метод наиболее разумен для оптимизационных моделей, которыми они заняты. Оказывается, если модель построена без учета возможностей численных процедур, то шансы найти приемлемое численное решение близки к нулю. Что бы ни создавал человек в любой области своей деятельности, он знает заранее, почему действует так, а не иначе, и что собирается делать с тем, что получится. И лишь в области численного моделирования картина почему-то совершенно иная: сначала создается модель, а затем начинаются поиски численного метода. Если учесть сложность оптимизационных задач, становится ясно, что шансы на успех при таком подходе крайне невелики. Книга состоит из четырех глав: которые в большой степени независимы друг от друга и могут использоваться самостоятельно. Книга рассчитана на широкую аудиторию; от читателя предполагаются 8

9 Nesterov-final 2010/4/5 18:26 page 9 #9 Предисловие лишь знания в объеме стандартных университетских курсов математического анализа и линейной алгебры. Включенный в книгу краткий библиографический комментарий призван помочь более близкому ознакомлению с предметом. Английский вариант книги (Nesterov Yu. «Introductory lectures on convex optimizatin: a basic course») был выпущен издательством Kluwer в 2004 г. и встретил заинтересованный отклик. Я надеюсь, что издание монографии Ю. Е. Нестерова на русском языке будет заметным событием и даст возможность российским читателям впервые познакомиться с новым перспективным направлением исследований. Б. Т. Поляк 9

10 Nesterov-final 2010/4/5 18:26 page 10 #10

11 Nesterov-final 2010/4/5 18:26 page 11 #11 Моей жене Светлане

12 Nesterov-final 2010/4/5 18:26 page 12 #12

13 Nesterov-final 2010/4/5 18:26 page 13 #13 Благодарности Эта книга отражает основные достижения в выпуклой оптимизации научном направлении, в котором мне довелось работать более 25 лет. В течение этого времени я имел редкую возможность свободного общения и сотрудничества со многими выдающимися учеными в этой области; им я выражаю свою глубокую признательность. Мне посчастливилось начать свою научную карьеру в Москве, в период максимального размаха научной деятельности в Советском Союзе. В этот момент в одном городе оказались собранными практически все выдающиеся умы трехсотмиллионной страны. Встречи и научные контакты с А. Антипиным, Ю. Евтушенко, Е. Гольштейном, А. Иоффе, В. Кармановым, Л. Хачияном, Р. Поляком, В. Пшеничным, Н. Шором, Н. Третьяковым, Ф. Васильевым, Д. Юдиным и, конечно же, с А. Немировским и Б. Поляком оказали определяющее влияние на формирование моих научных интересов и на выбор направления исследований. Как выяснилось потом, момент моего переезда на Запад тоже был весьма специфическим. В нелинейной оптимизации только что началась эра методов внутренней точки. Новые статьи со свежими идеями появлялись почти каждый день, и многочисленные конференции открывали редкую возможность для интересных научных контактов и активной совместной работы. Я очень благодарен моим коллегам, таким как Курт Анштрейхер, Альфред Ауслендер, Аарон Бен-Тал, Стивен Бойд, Кловис Гонзага, Дональд Гольдфарб, Жан-Луи Гоффен, Осман Гуллер, Иньюй Е, Кеннет Кортанек, Клод Лемарешаль, Оливер Мангасарян, Флориан Потра, Джеймс Ренегар, Корнелиус Рооз, Тамаш Терлаки, Андреас Титц, Майкл Тодд, Левент Тунсел, Роберт Фрёйнд, Флориан Ярре, за стимулирующие обсуждения и плодотворное сотрудничество. Особую благодарность мне хотелось бы выразить Жану-Филиппу Виалу, подтолкнувшему меня к написанию этой книги.

14 Nesterov-final 2010/4/5 18:26 page 14 #14 Благодарности В конце концов, мне повезло обосноваться в Центре исследования операций и эконометрики (CORE) в Лувэн-ла-Нёве, Бельгия, который при ближайшем рассмотрении оказался миниатюрной копией моего родного института ЦЭМИ РАН (Москва). Замечательные условия работы в этом научном центре и исключительное окружение помогали мне все эти годы. Трудно переоценить значение той атмосферы научных исследований, которую продолжают неустанно поддерживать мои коллеги из CORE и Центра системных исследований и прикладной механики (CESAME): Винсент Блондель, Ив Жене, Мишель Геверс, Этьен Лут, Ив Пошэ, Ив Смеерс, Поль Ван Доорен, Лоуренс Вулси. Моя работа в течение многих лет финансировались Бельгийской общенациональной программой по развитию фундаментальных исследований, созданной по инициативе правительства Бельгии и Комитета по научной политике. Я признателен Б. Т. Поляку и Московскому центру непрерывного математического образования за смелую инициативу перевода и издания этой книги на русском языке. 14

15 Nesterov-final 2010/4/5 18:26 page 15 #15 Введение Задачи оптимизации совершенно естественно возникают в различных прикладных областях. Во многих жизненных ситуациях у нас появляется желание или необходимость организовать свою деятельность наилучшим из возможных способов. Это намерение, облеченное в математическую форму, приобретает вид той или иной оптимизационной задачи. В зависимости от конкретной области приложения это может быть задача оптимального управления или задача оптимального размещения, составление оптимальной диеты или задача оптимального раскроя. Однако уже следующий шаг нахождение решения поставленной модельной задачи совсем нетривиален. На первый взгляд, все выглядит просто: на рынке имеется огромное количество легкодоступных коммерческих программных оптимизационных пакетов, и любой пользователь может получить «решение» задачи простым нажатием на иконку на экране своего персонального компьютера. Вопрос заключается в том, что именно он получит в качестве решения и насколько можно доверять результату. Одна из целей данной книги показать, что, несмотря на всю свою привлекательность, «решения» общих оптимизационных задач, получаемые таким образом, очень часто не соответствуют ожиданиям доверчивого пользователя. На мой взгляд, главное, что следует знать каждому работающему с оптимизационными моделями, это то, что задачи оптимизации, вообще говоря, численно неразрешимы. Это утверждение, часто не упоминаемое в стандартных курсах по оптимизации, крайне необходимо для понимания теории оптимизации и ее развития как в прошлом, так и в будущем. Во многих практических приложениях процесс формализации и приведения реальной проблемы к какому-либо стандарному виду требует большого времени и усилий. Поэтому исследователь должен иметь ясное представление о свойствах модели, которую

16 Nesterov-final 2010/4/5 18:26 page 16 #16 Введение он строит. На этапе моделирования обычно применяются различные средства для аппроксимации реального явления, и при этом совершенно необходимо осознавать, к каким вычислительным последствиям приведет каждое из принимаемых решений. Очень часто приходится выбирать между «хорошей» модельной задачей, которую не удается решить, 1 и «плохой» задачей, решение которой заведомо возможно. Какая из них лучше? В действительности ответ часто может быть подсказан вычислительной практикой. Дело в том, что в настоящее время наиболее распространенные оптимизационные модели по-прежнему представлены задачами линейной оптимизации. Крайне маловероятно, чтобы такие модели могли адекватно описывать явления нашего нелинейного мира; тем не менее, они весьма популярны, поскольку практики предпочитают иметь дело с разрешимыми задачами. Разумеется, очень часто линейная аппроксимация оказывается грубой, но зато обычно удается предсказать последствия такого плохого приближения и внести поправку в интерпретацию полученного результата. По-видимому, на практике такой подход предпочтительнее попыток решения общей нелинейной задачи без какойлибо гарантии на успех. Другая цель настоящего курса обсуждение численных методов для разрешимых нелинейных задач, а именно задач выпуклой оптимизации. Развитие теории выпуклой оптимизации в последние годы протекало бурно и захватывающе. Сегодня она представлена несколькими «соперничающими» направлениями, имеющими свои сильные и слабые стороны. Мы подробно обсудим их свойства, принимая во внимание и историческую ретроспективу; точнее говоря, мы попытаемся понять внутреннюю логику развития каждого из этих направлений. До сих пор основные результаты развития теории выпуклой оптимизации можно найти лишь в специальных журналах или научных монографиях, однако, по моему мнению, она уже созрела настолько, что ее можно донести до конечного пользователя, будь то специалист по организации производства, экономист или студент той или иной специализации. С другой стороны, я надеюсь, что книга будет интересна и специалистам в теории оптимизации, так как в ней содержится большое количе- 1 Точнее, которую можно пытаться решать. 16

17 Nesterov-final 2010/4/5 18:26 page 17 #17 Введение ство материала, никогда не публиковавшегося в виде законченной монографии. Я попытаюсь убедить читателя в том, что для успешного применения оптимизационных формулировок задач необходимо иметь определенные сведения из теории оптимизации, которая помогает понять, чего можно и чего нельзя достигнуть при решении задачи оптимизации. Элементы этой простой философии нетрудно найти в каждой главе предлагаемой книги. Мы постараемся показать, что выпуклая оптимизация является отличным примером законченной прикладной теории, которая проста, легка в изучении и может быть весьма полезной при решении практических задач. Эту книгу можно также рассматривать как курс лекций, в котором мы обсуждаем наиболее эффективные современные схемы оптимизации и устанавливаем границы их эффективности. Курс является автономным, и мы доказываем все необходимые результаты, рассчитывая на то, что доказательства, рассуждения и соображения не будут представлять трудности даже для студентов-старшекурсников. Книга состоит из четырех относительно независимых глав, каждая из которых включает в себя три параграфа. Материал каждого параграфа примерно соответствует объему двухчасовой лекции, поэтому книга может почти без изменений использоваться при чтении односеместрового курса. Первая глава посвящена общим задачам оптимизации. В 1.1 обсуждается терминология и вводятся понятия оракула, черного ящика, функциональной модели оптимизационной задачи и сложности итеративных схем общего вида. Мы покажем, что задачи глобальной оптимизации «нерешаемы», и обсудим основные характерные черты различных разделов теории оптимизации. В 1.2 рассматриваются две принципиальные схемы локальной безусловной минимизации: градиентный метод и метод Ньютона. Мы установим их локальную скорость сходимости и обсудим возможные неприятности (расходимость, сходимость к седловой точке). В 1.3 мы сравним структуры градиентного метода и метода Ньютона. Это приведет нас к идее переменной метрики, и мы опишем далее семейства квазиньютоновских методов и методов сопряженных градиентов. Завершается глава анализом схем последовательной безусловной минимизации. 17

18 Nesterov-final 2010/4/5 18:26 page 18 #18 Введение Во второй главе рассматриваются методы гладкой выпуклой оптимизации. В 2.1 анализируются основные причины упомянутых выше трудностей; в результате этого анализа мы придем к двум удобным классам функций: гладким выпуклым и гладким сильно выпуклым. Для соответствующих задач безусловной минимизации будут установлены нижние границы сложности. В заключение параграфа мы проанализируем градиентный метод и покажем, что он не является оптимальным. Оптимальные методы для задач гладкой выпуклой минимизации обсуждаются в 2.2. Изложение начинается с задач безусловной минимизации. Далее вводятся выпуклые множества и определяется понятие градиентного отображения для задач минимизации с простыми ограничениями. Мы покажем, что градиентное отображение формально заменяет шаг градиентного метода в оптимизационных схемах. В 2.3 обсуждаются более сложные задачи, включающие несколько гладких выпуклых функций, а именно минимаксная задача и задача условной минимизации. Для обеих задач вводится понятие градиентного отображения и приводятся оптимальные схемы минимизации. Третья глава посвящена теории негладкой выпуклой оптимизации. Не предполагая у читателя наличия специальных знаний по выпуклому анализу, мы начинаем главу 3.1, в котором компактно излагаются все необходимые для дальнейшего сведения. Конечной целью этого параграфа является обоснование правил вычисления субградиентов выпуклой функции. Следующий 3.2 начинается с установления нижних границ сложности для задач негладкой оптимизации. Далее предлагается общая схема анализа сложности соответствующих методов, которая потом применяется для нахождения скорости сходимости субградиентного метода, метода центра тяжести и метода эллипсоидов. Мы также обсудим некоторые методы отсекающей гиперплоскости. Параграф 3.3 посвящен схемам минимизации, в которых используется кусочно линейная модель выпуклой функции. Мы рассмотрим метод Келли и покажем, что он может быть чрезвычайно медленным. Наконец, мы опишем так называемый метод уровней и обоснуем оценки его эффективности на задачах безусловной и условной минимизации. В четвертой главе рассматриваются задачи выпуклой минимизации, имеющие явную структуру. Сначала в 4.1 мы обсудим определенную противоречивость концепции черного ящика примени- 18

19 Nesterov-final 2010/4/5 18:26 page 19 #19 Введение тельно к задаче выпуклой минимизации. Мы определим барьер для оптимизационной задачи исходя из понятия самосогласованной функции. Для таких функций оракул второго порядка не является локальным; их можно легко минимизировать с помощью метода Ньютона. Мы изучим свойства таких функций и оценим скорость сходимости метода Ньютона. В 4.2 вводятся самосогласованные барьеры подкласс самосогласованных функций, удобных для применения схем последовательной безусловной минимизации. Далее мы изучаем свойства таких барьеров и находим оценку эффективности схемы отслеживания траектории. В 4.3 приведено несколько примеров оптимизационных задач, для которых удается построить самосогласованный барьер, так что к этим задачам применима схема отслеживания траектории. Здесь рассматриваются задачи линейной и квадратичной оптимизации, задачи полуопределенной оптимизации, сепарабельной и геометрической оптимизации, задачи с экстремальными эллипсоидами и задачи аппроксимации в l p -нормах. Глава и вся книга завершаются сравнением метода внутренней точки и метода негладкой оптимизации применительно к решению конкретной оптимизационной задачи. 19

20 Nesterov-final 2010/4/5 18:26 page 20 #20

21 Nesterov-final 2010/4/5 18:26 page 21 #21 Глава 1 Нелинейная оптимизация 1.1. Задачи нелинейной оптимизации Общая формулировка задачи. Примеры задач оптимизации. Черный ящик и итеративные методы. Аналитическая и арифметическая сложность. Метод перебора на равномерной сетке. Нижние оценки вычислительной сложности. Нижние оценки для глобальной оптимизации. Правила игры Общая формулировка задачи Обозначим через x вещественный вектор размерности n: x= x (1),, x (n) T n, а через S некоторое множество из пространства n. Пусть f 0 (x),, f m (x) являются вещественнозначными функциями от x. В этой книге мы будем, как правило, рассматривать один из вариантов следующей общей задачи минимизации: min f 0 (x) при f j (x) & 0, j= 1,, m, x S, (1.1) где в качестве бинарного отношения & берется,либо=. В дальнейшем f 0 (x) будем называть целевой функцией нашей задачи, а векторную функцию f (x)= f 1 (x),, f m (x) T вектором функциональных ограничений. Множество S называется базовым допустимым множеством, а множество Q= x S f j (x)0, j= 1,, m называется просто допустимым множеством задачи (1.1). Для определенности мы всегда будем рассматривать задачи минимизации.

22 Nesterov-final 2010/4/5 18:26 page 22 #22 Глава 1. Нелинейная оптимизация Любая задача максимизации может быть переписана в этом виде с помощью изменения знака целевой функции. Приведем названия некоторых важных типов задач минимизации. Условные задачи: Q n. Безусловные задачи: Q n. Гладкие задачи: все функции f j (x) дифференцируемы. Негладкие задачи: существует по крайней мере одна недифференцируемая компонента f k (x). Задачи с линейными ограничениями: все функциональные ограничения являются линейными функциями: f j (x)= n i=1 a (i) j x (i) + b j a j, x + b j, j= 1,, m (здесь, обозначает скалярное произведение), а базовое множество S является многогранником. Если f 0 (x) также является линейной функцией, то задача (1.1) называется задачей линейной оптимизации. Если функция f 0 (x) является квадратичной, то задача (1.1) называется задачей квадратичной оптимизации. Если все функции f j квадратичные, то мы получаем задачу квадратичной оптимизации с квадратичными ограничениями. Существует также классификация задач, основанная на свойствах их допустимых множеств. Задача (1.1) называется допустимой, если Q. Задача (1.1) называется строго допустимой, если существует такой вектор x int Q, что f j (x)<0 (или> 0) для всех ограничений-неравенств и f j (x)=0 для всех ограничений-равенств (условие Слэйтера). Наконец, можно говорить о различных типах решений задачи (1.1). точка x называется оптимальным глобальным решением задачи (1.1), если f 0 (x ) f 0 (x) для всех x Q (глобальный минимум). В этом случае f 0 (x ) называется (глобальным) оптимальным значением задачи. 22

23 Nesterov-final 2010/4/5 18:26 page 23 # Задачи нелинейной оптимизации точка x называется локальным решением задачи (1.1), если для всех x int Q Q выполнено неравенство f 0 (x ) f 0 (x) (локальный минимум). Покажем на нескольких примерах, как могут возникать задачи оптимизации. Пример Обозначим через x (1),, x (n) параметры проектирования. По ним мы сможем вычислить значения некоторых характеристик нашего решения: f 0 (x),, f m (x). В качестве таких характеристик можно взять, например, стоимость проекта, количество необходимых ресурсов, надежность системы и т. д. Затем самую важную характеристику f 0 (x) мы выбираем в качестве целевой функции. Остальным характеристикам разрешается меняться в определенных пределах: a j f j (x) b j. Таким образом, возникает следующая задача: min f 0 (x) при a j f j (x) b j, j= 1,, m, x S, где множество S определяет структурные ограничения, такие как, например, естественный интервал изменения, неотрицательность значений и т. д. Пример Пусть наша исходная задача состоит в следующем: найти такое x n, что f j (x)= a j, j= 1,, m. (1.2) В этом случае можно перейти к следующей задаче минимизации: m 2 fj (x) a j min j=1 возможно, даже при некоторых дополнительных ограничениях на x. Если оптимальное значение в этой задаче равно нулю, то и исходная задача (1.2) разрешима. Заметим, что постановка (1.2) является почти универсальной задачей численного анализа. К такому виду приводятся системы обыкновенных дифференциальных уравнений и уравнений в частных производных, задачи поиска равновесных решений и многие другие. x, 23

24 Nesterov-final 2010/4/5 18:26 page 24 #24 Глава 1. Нелинейная оптимизация Пример Иногда переменные проектирования x (1),, x (n) по своему смыслу должны быть целыми числами. Это условие может быть записано с помощью следующего ограничения: sin(πx (i) )=0, i= 1,, n. Таким образом, общая задача нелинейной оптимизации включает в себя как частный случай задачи целочисленной оптимизации: min f 0 (x) min при a j f j (x) b j, j= 1,, m, x S, sin(πx (i) )=0, i= 1,, n. После рассмотренных примеров становится понятным оптимизм пионеров нелинейной оптимизации, который легко распознается в работах 50-х и 60-х гг. XX в. Наше первое впечатление, конечно же, должно было бы быть таким: Нелинейная оптимизация является очень важной и многообещающей прикладной наукой. Она покрывает почти все нужды теории исследования операций и различных областей численного анализа. С другой стороны, после просмотра тех же самых примеров, особенно примеров и 1.1.3, у более опытного читателя могли бы зародиться некоторые сомнения. Действительно, окружающая нас действительность слишком сложна для того, чтобы надеяться на существование универсального средства от всех болезней. Здоровый скептицизм должен привести нас к следующей догадке: Задачи нелинейной оптимизации, в их самой общей форме, являются численно неразрешимыми. Однако неподтвержденные догадки никогда особенно не ценились в математических науках. Поэтому трудно переоценить значение теории, созданной в середине 70-х годов, которая позволила доказать вышеупомянутое предположение. Это доказательство настолько просто и поучительно, что мы никак не можем опустить его в нашем курсе. Но прежде всего мы должны ввести специальную терминологию, необходимую для обсуждения подобных вопросов. 24

25 Nesterov-final 2010/4/5 18:26 page 25 # Задачи нелинейной оптимизации Эффективность численных методов Представим себе следующую ситуацию: мы собираемся решить некоторую задачу. Нам известно, что для решения задач такого типа разработано много различных численных методов. И, конечно же, нам бы хотелось применить метод, который является наилучшим для нашей задачи. Как нам его найти? Оказывается, такая постановка вопроса просто неправомерна, т. е. победителя в подобном соревновании обнаружить нетрудно, но мы вряд ли захотим (и сможем) воспользоваться его услугами. Действительно, представим себе «метод» решения задачи (1.1), который только и умеет, что сообщать пользователю, что глобальный оптимум достигается в точке x = 0. Конечно же, такой ответ неверен для всех задач, кроме тех, у которых оптимальное решение на самом деле есть нуль. И для таких задач эффективность подобного метода превзойти просто невозможно. Таким образом, невозможно разумно определить наилучший метод решения отдельной задачи. Однако это можно сделать для некоторого класса задач. Действительно, обычно численные методы разрабатываются для решения многих однотипных задач с близкими характеристиками. Поэтому эффективность метода на всем классе задач можно считать естественной характеристикой его качества. Так как мы собираемся говорить об эффективности метода на классе, приходится предполагать, что наш метод с самого начала не имеет полной информации о решаемой задаче. Заранее известная численному методу «часть» задачи называется моделью решаемой задачи. Для обозначения модели мы будем использовать символ Σ. Обычно в модель включаются формулировка задачи, описание свойств функциональных компонент и т. д. Для того чтобы распознать задачу среди всех прочих задач из данного класса (и тем самым решить ее), численный метод должен уметь накапливать специфическую информацию о решаемой задаче. Этот процесс удобно описывать с помощью понятия оракула. Оракул проще всего представить в виде некоторого устройства, которое 25

docplayer.ru