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

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

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

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

Определение

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

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

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

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

${ 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 mathbf {x} in mathbb {R} ^ {n}}$ - переменная оптимизации, функция ${ displaystyle f: { mathcal {D}} substeq mathbb {R} ^ {n} to mathbb {R}}$ выпуклый, ${ displaystyle g_ {i}: mathbb {R} ^ {n} to mathbb {R}}$, ${ Displaystyle я = 1, ldots, м}$, выпуклые, и ${ displaystyle h_ {i}: mathbb {R} ^ {n} to mathbb {R}}$, ${ Displaystyle я = 1, ldots, p}$, находятся аффинный.^[12] Это обозначение описывает проблему нахождения ${ displaystyle mathbf {x} in mathbb {R} ^ {n}}$ что сводит к минимуму ${ Displaystyle е ( mathbf {х})}$ среди всего ${ displaystyle mathbf {x}}$ удовлетворение ${ Displaystyle г_ {я} ( mathbf {х}) leq 0}$, ${ Displaystyle я = 1, ldots, м}$ и ${ displaystyle h_ {я} ( mathbf {x}) = 0}$, ${ Displaystyle я = 1, ldots, p}$. Функция ${ displaystyle f}$ - целевая функция задачи, а функции ${ displaystyle g_ {i}}$ и ${ displaystyle h_ {i}}$ - функции ограничения.

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

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

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

Характеристики

Ниже приведены полезные свойства задач выпуклой оптимизации:^[14][12]

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

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

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

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

Примеры

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

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

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

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

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

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

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

${ 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 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}$.

И наоборот, если некоторые ${ displaystyle x}$ в ${ displaystyle X}$ удовлетворяет (1) - (3) для скаляры ${ 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). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике. 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN  978-3-540-42877-0. МИСТЕР  1900016. S2CID  9048698.
• Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные методы внутренней точки в выпуклом программировании. СИАМ.
• Нестеров Юрий. (2004). Вводные лекции по выпуклой оптимизации, Kluwer Academic Publishers
• Рокафеллар, Р. Т. (1970). Выпуклый анализ. Принстон: Издательство Принстонского университета.

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

внешняя ссылка

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