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

редактировать

Подполе математической оптимизации

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

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

Содержание

1 Определение
- 1.1 Стандартная форма
2 Свойства
3 Анализ неопределенности
4 Примеры
5 Множители Лагранжа
6 Алгоритмы
7 Расширения
8 См. Также
9 Примечания
10 Ссылки
11 Внешние ссылки

Определение

Задача выпуклой оптимизации - это задача оптимизации, в которой целевая функция является выпуклой функцией, а допустимым набором является выпуклый набор. Функция $f {\ displaystyle f}$ $f$ , отображающая некоторое подмножество $R n {\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ в $R ∪ {± ∞} {\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}$ ${\ displaystyle \ mathbb {R} \ чашка \ {\ pm \ infty \}}$ является выпуклым, если его область определения выпуклая и для всех $θ ∈ [0, 1] {\ displaystyle \ theta \ in [0,1]}$ $\ theta \ in [0,1]$ и всех $x, y {\ displaystyle x, y}$ $x, y$ в его домене выполняется следующее условие: $е (θ Икс + (1 - θ) Y) ≤ θ е (Икс) + (1 - θ) f (Y) {\ Displaystyle F (\ theta x + (1- \ theta) y) \ Leq \ theta f (x) + (1- \ theta) f (y)}$ ${ \ displaystyle f (\ theta x + (1- \ theta) y) \ leq \ theta f (x) + (1- \ theta) f (y)}$ . Множество S является выпуклым, если для всех элементов $x, y ∈ S {\ displaystyle x, y \ in S}$ $x, y \ in S$ и всех $θ ∈ [0, 1] {\ displaystyle \ theta \ in [0,1]}$ $\ theta \ in [0,1]$ , мы имеем, что $θ x + (1 - θ) y ∈ S {\ displaystyle \ theta x + (1- \ theta) y \ in S}$ ${\ displaystyle \ theta x + (1- \ theta) y \ in S}$ .

Конкретно, задача выпуклой оптимизации - это проблема поиска некоторого $x ∗ ∈ C {\ displaystyle \ mathbf {x ^ {\ ast}} \ in C}$ ${\ displaystyle \ mathbf {x ^ { \ ast}} \ в C}$ с достижением

inf { е (х): x ∈ C} {\ displaystyle \ inf \ {f (\ mathbf {x}): \ mathbf {x} \ in C \}}

{\ displaystyle \ inf \ {е (\ mathbf {x}): \ mathbf {x} \ in C \}}

где целевая функция $f: D ⊆ R n → R {\ displaystyle f: {\ mathcal {D}} \ substeq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle f: {\ mathcal {D}} \ substeq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ выпукло, как и допустимое множество $С {\ Displaystyle C}$ $C$ . Если такая точка существует, она называется оптимальной точкой или решением; множество всех оптимальных точек называется оптимальным множеством. Если $f {\ displaystyle f}$ $f$ не ограничен снизу более $C {\ displaystyle C}$ $C$ или нижняя грань не достигается, тогда проблема оптимизации называется безграничный. В противном случае, если $C {\ displaystyle C}$ $C$ является пустым набором, проблема считается недопустимой.

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

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

минимизировать xf (x) subjecttogi (x) ≤ 0, i = 1,…, mhi (x) = 0, i = 1,…, p, {\ displaystyle {\ begin {align} {\ underset {\ mathbf {x}} {\ operatorname {minim}}} f (\ mathbf {x}) \\ \ operatorname {subject \ to} g_ {i} (\ mathbf {x }) \ leq 0, \ quad i = 1, \ dots, m \\ h_ {i} (\ mathbf {x}) = 0, \ quad i = 1, \ dots, p, \ end {выровнено}}}

{\ displaystyle {\ begin {align} {\ underset {\ mathbf {x}} {\ operatorname {minim}}} f (\ mathbf {x}) \\ \ operatorname {subject \ to} g_ {i} (\ mathbf {x }) \ leq 0, \ quad i = 1, \ dots, m \\ h_ {i} (\ mathbf {x}) = 0, \ quad i = 1, \ dots, p, \ end {выровнено}}}

где $x ∈ R n {\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ $\ mathbf {x} \ in \ mathbb {R} ^ {n}$ - переменная оптимизации, функция $f: D ⊆ R n → R {\ displaystyle f: {\ mathcal {D}} \ substeq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle f: {\ mathcal {D}} \ substeq \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ выпукло, $gi: R n → R {\ displaystyle g_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle g_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$ , $i = 1,…, m {\ displaystyle i = 1, \ ldots, m }$ ${\ displaystyle i = 1, \ ldots, m}$ , выпуклые, и $hi: R n → R {\ displaystyle h_ {i}: \ mathbb { R} ^ {n} \ to \ mathbb {R}}$ ${\ displaystyle h_ {i}: \ mathbb {R} ^ {n} \ to \ mathbb { R}}$ , $i = 1,…, p {\ displaystyle i = 1, \ ldots, p}$ ${\ displaystyle i = 1, \ ldots, p}$ , являются аффинными. Это обозначение описывает проблему поиска $x ∈ R n {\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}$ $\ mathbf {x} \ in \ mathbb {R} ^ {n}$ , который минимизирует $f (x) { \ displaystyle f (\ mathbf {x})}$ $f (\ mathbf {x})$ среди всех $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ удовлетворяющих $gi (x) ≤ 0 {\ displaystyle g_ {i} (\ mathbf {x}) \ leq 0}$ ${\ displaystyle g_ {i} (\ mathbf {x}) \ leq 0}$ , $i = 1,…, m {\ displaystyle i = 1, \ ldots, m}$ ${\ displaystyle i = 1, \ ldots, m}$ и $hi ( х) = 0 {\ displaystyle h_ {i} (\ mathbf {x}) = 0}$ ${\ displaystyle h_ {i} (\ mathbf {x}) = 0}$ , $i = 1,…, p {\ displaystyle i = 1, \ ldots, p}$ ${\ displaystyle i = 1, \ ldots, p}$ . Функция $f {\ displaystyle f}$ $f$ является целевой функцией задачи, а функции $gi {\ displaystyle g_ {i}}$ $g_ {i}$ и $привет {\ displaystyle h_ {i}}$ $h_ {i}$ - это функции ограничения.

Возможный набор $C {\ displaystyle C}$ $C$ задачи оптимизации состоит из всех точек $x ∈ D {\ displaystyle \ mathbf {x} \ in {\ mathcal {D}}}$ $\ mathbf {x} \ in \ mathcal {D}$ удовлетворяет ограничениям. Это множество выпукло, потому что $D {\ displaystyle {\ mathcal {D}}}$ ${\ mathcal {D}}$ выпукло, подуровни выпуклых функций выпуклы, аффинные множества выпуклы и пересечение выпуклых множеств является выпуклым.

Решением задачи выпуклой оптимизации является любая точка $x ∈ C {\ displaystyle \ mathbf {x} \ in C}$ ${\ displaystyle \ mathbf {x} \ in C}$ с достижением $inf {е (х): x ∈ C} {\ displaystyle \ inf \ {f (\ mathbf {x}): \ mathbf {x} \ in C \}}$ ${\ displaystyle \ inf \ {е (\ mathbf {x}): \ mathbf {x} \ in C \}}$ . В общем, задача выпуклой оптимизации может иметь ноль, одно или несколько решений.

Многие задачи оптимизации могут быть эквивалентно сформулированы в этой стандартной форме. Например, проблема максимизации вогнутой функции $f {\ displaystyle f}$ $f$ может быть эквивалентно переформулирована как проблема минимизации выпуклой функции $- f {\ displaystyle -f}$ $-f$ . Задачу максимизации вогнутой функции над выпуклым множеством обычно называют задачей выпуклой оптимизации.

Свойства

Следующие полезные свойства задач выпуклой оптимизации:

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

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

Анализ неопределенности

Бен- Hain and Elishakoff (1990), Elishakoff et al. (1994) применили выпуклый анализ к неопределенности модели .

Примеры

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

Иерархия задачи выпуклой оптимизации. (LP: линейная программа, QP: квадратичная программа, SOCP программа конуса второго порядка, SDP: полуопределенная программа, CP: программа конуса.)

Метод наименьших квадратов
Линейное программирование
Выпуклая квадратичная минимизация с линейными ограничениями
Квадратичная минимизация с выпуклыми квадратичными ограничениями
Коническая оптимизация
Геометрическое программирование
Конусное программирование второго порядка
Полуопределенное программирование
Максимизация энтропии с соответствующими ограничениями

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

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме функцией затрат $f (x) {\ displaystyle f (x)}$ $f(x)$ и ограничениями неравенства $gi (x) ≤ 0 {\ displaystyle g_ {i} (x) \ leq 0}$ $g_i (x) \ leq 0$ для $1 ≤ i ≤ m {\ displaystyle 1 \ leq i \ leq m}$ ${\ displaystyle 1 \ leq i \ leq m}$ . Тогда домен $X {\ displaystyle {\ mathcal {X}}}$ ${\ mathcal {X}}$ равен:

X = {x ∈ X | g 1 (x),…, g m (x) ≤ 0}. {\ displaystyle {\ mathcal {X}} = \ left \ {x \ in X \ vert g_ {1} (x), \ ldots, g_ {m} (x) \ leq 0 \ right \}.}

{\ displaystyle {\ mathcal {X}} = \ left \ {x \ in X \ vert g_ {1} (x), \ ldots, g_ {m} (x) \ leq 0 \ right \}.}

Функция Лагранжа для задачи равна

L (x, λ 0, λ 1,…, λ m) = λ 0 f (x) + λ 1 g 1 (x) + ⋯ + λ mgm (x). {\ Displaystyle L (х, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m}) = \ lambda _ {0} f (x) + \ lambda _ {1} g_ {1} (x) + \ cdots + \ lambda _ {m} g_ {m} (x).}

{\ displaystyle L (x, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m}) = \ lambda _ {0} е (х) + \ lambda _ {1} g_ {1} (x) + \ cdots + \ lambda _ {m} g_ {m} (x).}

Для каждой точки $x {\ displaystyle x}$ $x$ в $X {\ displaystyle X}$ $X$ , который минимизирует $f {\ displaystyle f}$ $f$ на $X {\ displaystyle X}$ $X$ , существуют действительные числа $λ 0, λ 1,…, λ m, {\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m},}$ ${\ displaystyle \ лямбда _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m},}$ называется множители Лагранжа, которые одновременно удовлетворяют этим условиям:

$x {\ displaystyle x}$ $x$ минимизирует $L (y, λ 0, λ 1,…, λ m) {\ displaystyle L (y, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m})}$ ${\ displaystyle L (y, \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m})}$ по всем $y ∈ X, {\ displaystyle y \ в X,}$ ${\ displaystyle y \ in X,}$
$λ 0, λ 1,…, λ м ≥ 0, {\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldots, \ lambda _ {m} \ geq 0, }$ ${\ displaystyle \ lambda _ {0}, \ lambda _ {1}, \ ldot s, \ lambda _ {m} \ geq 0,}$ хотя бы с одним $λ k>0, {\ displaystyle \ lambda _ {k}>0,}$ $\lambda _{k}>0,$
$λ 1 г 1 (x) = ⋯ = λ mgm (x) = 0 {\ displaystyle \ lambda _ {1} g_ {1} (x) = \ cdots = \ lambda _ {m} g_ {m} (x) = 0}$ ${\ displaystyle \ lambda _ {1 } g_ {1} (x) = \ cdots = \ lambda _ {m} g_ {m} (x) = 0}$ (дополнительная расслабленность).

Если существует «строго допустимая точка», то есть точка $z {\ displaystyle z}$ $z$ удовлетворяет

g 1 (z),…, gm (z) < 0, {\displaystyle g_{1}(z),\ldots,g_{m}(z)<0,}

{\ displaystyle g_ {1} (z), \ ldots, g_ {м} (г) <0,}

, то приведенное выше утверждение можно усилить, потребовав, чтобы $λ 0 = 1 {\ displaystyle \ lambda _ {0} = 1}$ ${\ displaystyle \ lambda _ {0} = 1}$ .

И наоборот, если некоторый $x {\ displaystyle x}$ $x$ в $X {\ displaystyle X}$ $X$ удовлетворяет ( 1) - (3) для скаляров $λ 0,…, λ m {\ displaystyle \ lambda _ {0}, \ ldots, \ lambda _ {m}}$ ${\ displaystyle \ lambda _ {0}, \ ldots, \ lambda _ {m}}$ с $λ 0 = 1 {\ displaystyle \ lambda _ {0} = 1}$ ${\ displaystyle \ lambda _ {0} = 1}$ тогда $x {\ displaystyle x}$ $x$ обязательно минимизирует $f {\ displaystyle f}$ $f$ over $X {\ displaystyle X}$ $X$ .

Алгоритмы

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

Связанные методы (Wol fe, Lemaréchal, Kiwiel) и
методы субградиентной проекции (Polyak),
методы внутренней точки, которые используют самосогласованные барьерные функции и самосогласованные регулярные барьерные функции.
Методы секущей плоскости
Эллипсоидный метод
Субградиентный метод
Двойные субградиенты и метод смещения плюс штраф

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

Расширения

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

См. Также

Примечания

^ Нестеров и Немировский 1994
^Мурти, Катта; Кабади, Сантош (1987). «Некоторые NP-полные задачи квадратичного и нелинейного программирования». Математическое программирование. 39 (2): 117–129. DOI : 10.1007 / BF02592948. HDL : 2027,42 / 6740. S2CID 30500771.
^Сахни, С. «Проблемы, связанные с вычислениями», в SIAM Journal on Computing, 3, 262-279, 1974.
^Квадратичное программирование с одним отрицательным собственным значением - NP -hard, Панос М. Пардалос и Стивен А. Вавасис в Журнале глобальной оптимизации, том 1, номер 1, 1991, стр.15-22.
^Boyd Vandenberghe 2004, стр. 17
^Критенсен / Кларбринг, гл. 4.
^Boyd Vandenberghe 2004
^Schmit, L.A.; Флери, C. 1980: структурный синтез путем объединения концепций приближения и двойственных методов. J. Amer. Inst. Аэронавт. Astronaut 18, 1252-1260
^Boyd Vandenberghe 2004, стр. 8
^Хириарт-Уррути, Жан-Батист; Лемарешаль, Клод (1996). Выпуклый анализ и алгоритмы минимизации: основы. п. 291. ISBN 9783540568506.
^Бен-Тал, Аарон; Немировский, Аркадий Семенович (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения. С. 335–336. ISBN 9780898714913.
^ Boyd Vandenberghe 2004, гл. 4
^Boyd Vandenberghe 2004, гл. 2
^Рокафеллар Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF). SIAM Обзор. 35 (2): 183–238. CiteSeerX 10.1.1.161.7209. doi : 10.1137 / 1035044.
^Бен Хаим Й. и Элишаков И., Выпуклые модели неопределенности в прикладной механике, издательство Elsevier Science Publishers, Амстердам, 1990
^I. Елисаков, И. Линь Ю.К. и Чжу Л.П. Вероятностное и выпуклое моделирование структур с акустическим возбуждением, издательство Elsevier Science Publishers, Амстердам, 1994 г.
^Агравал, Акшай; Verschueren, Робин; Даймонд, Стивен; Бойд, Стивен (2018). «Система перезаписи для задач выпуклой оптимизации» (PDF). Контроль и решение. 5 (1): 42–60. arXiv : 1709.04494. DOI : 10.1080 / 23307706.2017.1397554. S2CID 67856259.
^О методах выпуклой минимизации см. Тома Хириарта-Уррути и Лемарешала (комплект) и учебники Рущинского, Берцекаса, а также Бойд и Ванденберге (внутренняя точка).
^Нестеров Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренней точки в выпуклом программировании. Общество промышленной и прикладной математики. ISBN 978-0898715156.
^Пэн, Джиминг; Роос, Корнелис; Терлаки, Тамаш (2002). «Саморегулируемые функции и новые направления поиска для линейной и полуопределенной оптимизации». Математическое программирование. 93 (1): 129–171. doi : 10.1007 / s101070200296. ISSN 0025-5610. S2CID 28882966.
^Бертсекас

Ссылки

Бертсекас, Дмитрий П.; Недич, Анжелиа; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация. Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-45-8.
Берцекас, Дмитрий П. (2009). Теория выпуклой оптимизации. Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-31-1.
Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации. Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1.

Boyd, Stephen P.; Ванденберге, Ливен (2004). Convex Optimization (PDF). Издательство Кембриджского университета. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. CS1 maint: ref = harv (ссылка )

Борвейн, Джонатан и Льюис, Адриан. (2000). Выпуклый анализ и нелинейная оптимизация. Springer.
Christensen, Peter W.; Андерс Кларбринг (2008). Введение в структурную оптимизацию. 153 . Springer Science Business Media. ISBN 9781402086663.

Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). Основы выпуклого анализа. Berlin: Springer.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Выпуклый анализ и алгоритмы минимизации, Том I: Основы. Grundlehren der Mathematischen Wissenschaften [Фундаментальные принципы математических наук]. 305 . Berlin: Springer-Verlag. Pp. Xviii + 417. ISBN 978-3-540-56850-6. MR 1261420.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Анализ выпуклости и алгоритмы минимизации, Том II: Расширенная теория и методы связки. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306 . Берлин: Springer-Verlag. С. xviii + 346. ISBN 978-3-540-56852-0. MR 1295240. CS1 maint: ref = harv (ссылка )
Kiwiel, Krzysztof C. ( 1985). Методы спуска для недифференцируемой оптимизации. Конспект лекций по математике. Нью-Йорк: Springer-Verlag. ISBN 978-3-540-15642-0. CS1 maint: ref = harv (ссылка )
Lemaréchal, Claude (2001). «Лагранжева релаксация». В книге Михаэля Юнгера и Дениса Наддефа (ред.). Вычислительная комбинаторная оптимизация: статьи из Весенняя школа, проходившая в Шлос Дагштуль, 15–19 мая 2000 г. Лекционные заметки по информатике. 2241 . Berlin: Springer-Verlag. pp. 112–156. doi : 10.1007 / 3-540-45586-8_4. ISBN 978-3-540-42877-0. MR 1900016. S2CID 9048698.
Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные методы внутренней точки в выпуклом программировании. SIAM. CS1 maint: ref = harv (link )
Нестеров, Юрий. (2004) Вводные лекции по выпуклой оптимизации, Kluwer Acade. mic Publishers
Рокафеллар, Р. Т. (1970). Выпуклый анализ. Princeton: Princeton University Press.

Ruszczyński, Andrzej (2006). Нелинейная оптимизация. Princeton University Press.
Schmit, L.A.; Флери, C. 1980: Структурный синтез путем объединения концепций приближения и двойственных методов. J. Amer. Inst. Аэронавт. Astronaut 18, 1252-1260

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

Викискладе есть медиафайлы, связанные с Convex Optimization.

EE364a: Convex Optimization I и EE364b: Convex Optimization II, Домашние страницы Стэнфордского курса
6.253: Convex Analysis and Optimization, домашняя страница курса MIT OCW
Брайан Борчерс, Обзор программного обеспечения для выпуклой оптимизации