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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Февраль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Выпуклая оптимизация - это подраздел математической оптимизации , изучающий проблему минимизации выпуклых функций над выпуклыми множествами . Многие классы задач выпуклой оптимизации допускают алгоритмы с полиномиальным временем ^[1], тогда как математическая оптимизация в целом NP-трудна . ^{[2] [3] [4]}

Выпуклая оптимизация имеет приложения в широком диапазоне дисциплин, таких как системы автоматического управления , оценка и обработка сигналов , связь и сети, проектирование электронных схем , ^[5] анализ и моделирование данных, финансы , статистика ( оптимальный экспериментальный план ), ^[6] и структурная оптимизация , где концепция аппроксимации доказала свою эффективность. ^{[7] [8]} С учетом последних достижений в вычислениях и алгоритмах оптимизации выпуклое программирование почти так же просто, как линейное программирование .^[9]

Определение [ править ]

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

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

${\ Displaystyle \ Inf \ {е (\ mathbf {x}): \ mathbf {x} \ in C \}}$,

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

Стандартная форма [ править ]

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

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&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{aligned}}}$

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

Допустимое множество оптимизационной задачи состоит из всех точек, удовлетворяющих ограничениям. Это множество выпукло, потому что выпукло, множества подуровней выпуклых функций выпуклы, аффинные множества выпуклы, а пересечение выпуклых множеств выпукло. ^[13]${\displaystyle C}$${\displaystyle \mathbf {x} \in {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$

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

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

Свойства [ править ]

Следующие полезные свойства задач выпуклой оптимизации: ^{[14] [12]}

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

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

Анализ неопределенности [ править ]

Бен-Хайн и Элишаков ^[15] (1990), Элишаков и др. ^[16] (1994) применили выпуклый анализ к модели неопределенности .

Примеры [ править ]

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

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

Множители Лагранжа [ править ]

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

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

Функция Лагранжа для задачи есть

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

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

1. ${\displaystyle x}$сводит к минимуму все${\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}$${\displaystyle y\in X,}$
2. ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}$ по крайней мере с одним ${\displaystyle \lambda _{k}>0,}$
3. ${\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}$ (дополнительная расслабленность).

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

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

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

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

Алгоритмы [ править ]

Задачи выпуклой оптимизации решаются следующими современными методами: ^[18]

• Связанные методы (Вулф, Лемарешаль, Кивьель) и
• Методы субградиентного проецирования (Поляк),
• Методы внутренних точек , ^[1] , которые используют самостоятельно согласные барьерных функций ^[19] и само-регулярным барьерных функций. ^[20]
• Режущие методы
• Эллипсоидный метод
• Субградиентный метод
• Двойные субградиенты и метод смещения плюс штраф

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

Расширения [ править ]

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

См. Также [ править ]

• Двойственность
• Условия Каруша – Куна – Таккера.
• Проблема оптимизации
• Проксимальный градиентный метод

Заметки [ править ]

Ссылки [ править ]

• Bertsekas, Dimitri P .; Недич, Анджелиа; Оздаглар, Асуман (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.

• Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3. Проверено 15 октября 2011 года .

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

• Хириар-Уррути, Жан-Батист, и Лемарешаль, Клод . (2004). Основы выпуклого анализа . Берлин: Springer.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 305 . Берлин: Springer-Verlag. С. xviii + 417. ISBN 978-3-540-56850-6. Руководство по ремонту  1261420 .
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Выпуклый анализ и алгоритмы минимизации, Том II: Расширенная теория и методы связки . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306 . Берлин: Springer-Verlag. С. xviii + 346. ISBN 978-3-540-56852-0. Руководство по ремонту  1295240 .
• Кивель, Кшиштоф К. (1985). Методы спуска для недифференцируемой оптимизации . Конспект лекций по математике. Нью-Йорк: Springer-Verlag. ISBN 978-3-540-15642-0.
• Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: документы из Весенней школы состоялись в Шлоссе Dagstuhl, 15-19 мая 2000 года . Конспект лекций по информатике. 2241 . Берлин: Springer-Verlag. С. 112–156. DOI : 10.1007 / 3-540-45586-8_4 . ISBN 978-3-540-42877-0. MR  1900016 . S2CID  9048698 .
• Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные методы внутренней точки в выпуклом программировании . СИАМ.
• Нестеров, Юрий. (2004). Вводные лекции по выпуклой оптимизации , Kluwer Academic Publishers
• Рокафеллар, RT (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета.

• Рущинский, Анджей (2006). Нелинейная оптимизация . Издательство Принстонского университета.
• Schmit, LA; Флери, C. 1980: Структурный синтез путем объединения концепций приближения и двойственных методов . J. Amer. Inst. Аэронавт. Астронавт 18, 1252-1260 гг.

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с выпуклой оптимизацией .

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