Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время, как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени, математическая оптимизация в общем случае NP — трудна.
Выпуклое программирование находит применение в целом ряде дисциплин, таких как автоматические системы управления, оценка и обработка сигналов, коммуникации и сети, схемотехника, анализ данных и моделирование, финансы, статистика () и . Развитие вычислительной техники и алгоритмов оптимизации сделало выпуклое программирование почти столь же простым как линейное программирование.
Определение Задача выпуклого программирования — это задача оптимизации, в которой целевая функция является выпуклой функцией и область допустимых решений выпукла. Функция , отображающая некоторое подмножество в , является выпуклой, если область определения выпукла и для всех , и всех в их области определения . Множество выпукло, если для всех его элементов и любого также и принадлежит множеству.
В частности, задачей выпуклого программирования является задача нахождения некоторого , на котором достигается , где целевая функция выпукла, как и множество допустимых решений . Если такая точка существует, её называют оптимальной точкой. Множество всех оптимальных точек называется оптимальным множеством. Если не ограничена на или инфимум не достигается, говорят, что оптимизации не ограничена. Если же пусто, говорят о недопустимой задаче.
Стандартная форма Говорят, что задача выпуклого программирования представлена в стандартной форме, если она записана как
Минимизировать При условиях
где является переменной оптимизации, функции выпуклы, а функции аффинны .
В этих терминах функция является целевой функцией задачи, а функции и именуются функциями ограничений. Допустимое множество решений задачи оптимизации — это множество, состоящее из всех точек , удовлетворяющих условиям и . Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множеством.
Многие задачи оптимизации можно привести к этой стандартной форме. Например, задача максимизации вогнутой функции может быть переформулирована эквивалентно как задача минимизации выпуклой функции , так что о задаче максимизации вогнутой функции на выпуклом множестве часто говорят как о задаче выпуклого программирования
Свойства Полезные свойства задач выпуклого программирования: любой локальный минимум является глобальным минимумом; оптимальное множество выпукло; если целевая функция сильно выпукла, проблема имеет максимум одну оптимальную точку.
Эти результаты используются в теории выпуклой минимизации вместе с геометрическими понятиями из функционального анализа (на гильбертовых пространствах), такими как , теорема об опорной гиперплоскости и лемма Фаркаша.
Примеры
Следующие классы задач являются задачами выпуклого программирования или могут быть сведены к задачам выпуклого программирования путём простых преобразований: Метод наименьших квадратов Линейное программирование Выпуклая квадратичная оптимизация с линейными ограничениями
Геометрическое программирование
Полуопределённое программирование Принцип максимума энтропии с подходящими ограничениями
Метод множителей Лагранжа Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме с функцией цены и ограничениям-неравенствам для . Тогда область определения равна:
Функция Лагранжа для задачи
Для любой точки из , которая минимизирует на , существуют вещественные числа , называемые множителями Лагранжа, для которых выполняются одновременно условия:
минимизирует над всеми по меньшей мере с одним (дополняющая нежёсткость).
Если существует «сильная допустимая точка», то есть точка , удовлетворяющая
то утверждение выше может быть усилено до требования .
И обратно, если некоторое из удовлетворяет условиям (1)-(3) для скаляров с , то определённо минимизирует на .
Алгоритмы Задачи выпуклого программирования решаются следующими современными методами:О методах выпуклого программирования см. книги Ирриарта-Уррути и Лемерикала (несколько книг) и книги Рушчиньского, Берцекаса, а также Бойда и Вандерберге (методы внутренней точки). Методы пучков субградиентов} (Вольф, Лемерикал, Кивель), Субградиентные проекционные методы (Поляк), Метод внутренней точки, использующий самосогласованные барьерные функции и саморегулярные барьерные функции. Метод секущих плоскостей Метод эллипсоидов Субградиентные методы
Субградиентные методы могут быть реализованы просто, потому они широко используются. Двойственные субградиентные методы — это субградиентные методы, применённые к двойственной задаче. аналогичен двойственному субградиентному методу, но использует среднее по времени от основных переменных.
Расширения Расширения выпуклого программирования включают оптимизацию , псевдовыпуклых и квазивыпуклых функций. Расширения теории выпуклого анализа и итеративные методы для приблизительного решения невыпуклых задач оптимизации встречаются в области обобщённой выпуклости, известной как абстрактный выпуклый анализ.
См. также Двойственность Условия Каруша — Куна — Таккера Оптимизация (математика) Метод проксимального градиента
Примечания
Литература
Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. — , Наука, 1976. — 189 c. Каменев Г. К. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007, 230 с. ISBN 5-201-09876-2. Каменев Г. К. Численное исследование эффективности методов полиэдральной аппроксимации выпуклых тел. М: Изд. ВЦ РАН, 2010, 118с. ISBN 978-5-91601-043-5.
Ссылки Stephen Boyd, Lieven Vandenberghe, Convex optimization (pdf) EE364a: Convex Optimization I, EE364b: Convex Optimization II, Страница курса оксфордского университета 6.253: Convex Analysis and Optimization, страница курса MIT OCW Brian Borchers, An overview of software for convex optimization
Категория:Теория оптимизации Категория:Выпуклый анализ Категория:Выпуклая оптимизация