Выпуклая оптимизация — Convex optimization
Выпуклая оптимизация — это подраздел математической оптимизации , изучающий проблему минимизации выпуклых функций над выпуклыми множествами . Многие классы задач выпуклой оптимизации допускают алгоритмы с полиномиальным временем, тогда как математическая оптимизация, как правило, NP-трудна .
Выпуклая оптимизация имеет приложения в широком диапазоне дисциплин, таких как системы автоматического управления , оценка и обработка сигналов , связь и сети, проектирование электронных схем , анализ и моделирование данных, финансы , статистика ( оптимальный экспериментальный дизайн ) и структурная оптимизация , где концепция аппроксимации оказалась эффективной. Благодаря последним достижениям в вычислениях и алгоритмах оптимизации выпуклое программирование почти так же просто, как линейное программирование .
СОДЕРЖАНИЕ
Определение
Конкретно, задача выпуклой оптимизации — это проблема нахождения некоторого достижения Икс * ∈ C <\ displaystyle \ mathbf
где целевая функция является выпуклой, как и допустимое множество . Если такая точка существует, она называется оптимальной точкой или решением ; множество всех оптимальных точек называется оптимальным множеством . Если снизу неограничен над или нижняя грань не достигается, то задача оптимизации называется неограниченной . В противном случае, если — пустое множество, то проблема считается невыполнимой . ж : D ⊆ р п → р <\ displaystyle f: <\ mathcal
Стандартная форма
Задача выпуклой оптимизации имеет стандартную форму, если ее записать как
Допустимое множество оптимизационной задачи состоит из всех точек, удовлетворяющих ограничениям. Это множество выпукло, потому что выпукло, множества подуровней выпуклых функций выпуклы, аффинные множества выпуклы, а пересечение выпуклых множеств выпукло. C <\ displaystyle C>Икс ∈ D <\ displaystyle \ mathbf
Решением задачи выпуклой оптимизации является достижение любой точки . В общем, задача выпуклой оптимизации может иметь ноль, одно или несколько решений. Икс ∈ C <\ displaystyle \ mathbf
Многие задачи оптимизации могут быть эквивалентно сформулированы в этой стандартной форме. Например, проблема максимизации вогнутой функции может быть переформулирована эквивалентно как проблема минимизации выпуклой функции . Проблема максимизации вогнутой функции над выпуклым множеством обычно называется проблемой выпуклой оптимизации. ж <\ displaystyle f>— ж
Характеристики
Ниже приведены полезные свойства задач выпуклой оптимизации:
- каждый локальный минимум — это глобальный минимум ;
- оптимальный набор — выпуклый;
- если целевая функция строго выпуклая, то задача имеет не более одной оптимальной точки.
Эти результаты используются в теории выпуклой минимизации наряду с геометрическими понятиями функционального анализа (в гильбертовых пространствах), такими как теорема Гильберта о проекции, теорема о разделяющей гиперплоскости и лемма Фаркаша .
Приложения
Бен-Хайн и Элишаков (1990), Элишаков и др. (1994) применили выпуклый анализ к модели неопределенности .
Следующие классы задач являются задачами выпуклой оптимизации или могут быть сведены к задачам выпуклой оптимизации с помощью простых преобразований:
Выпуклая оптимизация имеет следующие практические применения.
- оптимизация портфеля
- анализ риска наихудшего случая
- оптимальная реклама
- вариации статистической регрессии (включая регуляризацию и квантильную регрессию )
- подгонка модели (особенно мультиклассовая классификация )
- оптимизация производства электроэнергии
Множители Лагранжа
Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме функцией стоимости и ограничениями неравенства для . Тогда домен : ж ( Икс ) <\ displaystyle f (x)>грамм я ( Икс ) ≤ 0 <\ Displaystyle g_ <я>(х) \ leq 0> 1 ≤ я ≤ м <\ Displaystyle 1 \ Leq я \ Leq м>Икс <\ Displaystyle <\ mathcal
Функция Лагранжа для задачи есть
Для каждой точки в который сводит к минимуму более , существует действительные числа , называемых множителями Лагранжа , которые удовлетворяют эти условия одновременно: Икс <\ displaystyle x>Икс <\ displaystyle X>ж <\ displaystyle f>Икс <\ displaystyle X>λ 0 , λ 1 , … , λ м , <\ displaystyle \ lambda _ <0>, \ lambda _ <1>, \ ldots, \ lambda _
Если существует «строго допустимая точка», то есть точка, удовлетворяющая z
тогда приведенное выше утверждение может быть усилено, чтобы требовать этого . λ 0 знак равно 1 <\ displaystyle \ lambda _ <0>= 1>
Алгоритмы
Неограниченную выпуклую оптимизацию можно легко решить с помощью градиентного спуска (особый случай наискорейшего спуска ) или метода Ньютона в сочетании с линейным поиском подходящего размера шага; можно математически доказать, что они быстро сходятся, особенно последний метод. Выпуклая оптимизация с ограничениями линейного равенства также может быть решена с использованием методов матрицы KKT , если целевая функция является квадратичной функцией (которая обобщается на вариант метода Ньютона, который работает, даже если точка инициализации не удовлетворяет ограничениям), но также может обычно решается путем устранения ограничений равенства с помощью линейной алгебры или решения двойственной задачи. Наконец, выпуклая оптимизация как с ограничениями линейного равенства, так и с ограничениями выпуклого неравенства может быть решена путем применения метода безусловной выпуклой оптимизации к целевой функции плюс члены логарифмического барьера . (Когда исходная точка невозможна, то есть не удовлетворяет ограничениям, этому предшествуют так называемые методы фазы I , которые либо находят допустимую точку, либо показывают, что ее не существует. Методы фазы I обычно заключаются в сокращении объема поиска, о котором идет речь. к еще одной задаче выпуклой оптимизации.)
Задачи выпуклой оптимизации также могут быть решены следующими современными методами:
- Связанные методы (Вулф, Лемарешаль, Кивьель) и
- Методы субградиентного проецирования (Поляк),
- Методы внутренней точки , которые используют самосогласованные барьерные функции и саморегулирующиеся барьерные функции.
Субградиентные методы могут быть легко реализованы и поэтому широко используются. Двойные субградиентные методы — это субградиентные методы, применяемые к двойной задаче . Метод смещения плюс штраф аналогичен методу двойного субградиента, но требует усреднения по времени основных переменных.
Реализации
Выпуклая оптимизация и связанные с ней алгоритмы реализованы в следующих программах:
| Программа | Язык | Описание | СОПО ? | Ссылка |
|---|---|---|---|---|
| CVX | MATLAB | Интерфейсы с решателями SeDuMi и SDPT3; предназначен только для выражения задач выпуклой оптимизации. | да | |
| CVXMOD | Python | Интерфейс с решателем CVXOPT. | да | |
| CVXPY | Python | |||
| CVXR | р | да | ||
| ЯЛМИП | MATLAB | Интерфейсы с решателями CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON; также поддерживает целочисленную и нелинейную оптимизацию и некоторую невыпуклую оптимизацию. Может выполнять надежную оптимизацию с неопределенностью в ограничениях LP / SOCP / SDP. | да | |
| Лаборатория LMI | MATLAB | Выражает и решает задачи полуопределенного программирования (так называемые «линейные матричные неравенства»). | Нет | |
| Переводчик LMIlab | Преобразует лабораторные задачи LMI в задачи SDP. | да | ||
| xLMI | MATLAB | Подобно лаборатории LMI, но использует решатель SeDuMi. | да | |
| ЦЕЛИ | Может выполнять надежную оптимизацию в линейном программировании (с MOSEK для решения конусного программирования второго порядка) и смешанном целочисленном линейном программировании . Пакет моделирования для LP + SDP и робастных версий. | Нет | ||
| РИМ | Система моделирования для надежной оптимизации. Поддерживает устойчивую к распределению оптимизацию и наборы неопределенностей . | да | ||
| ГЛОПТИПОЛИЯ | MATLAB | да | ||
| СОСТУЛЫ | Система моделирования для полиномиальной оптимизации . Использует SDPT3 и SeDuMi. Требуется набор инструментов для символьных вычислений. | да | ||
| SparsePOP | Система моделирования для полиномиальной оптимизации. Использует решатели SDPA или SeDuMi. | да | ||
| CPLEX | Поддерживает первично-двойные методы для LP + SOCP. Может решать задачи LP, QP, SOCP и смешанного целочисленного линейного программирования. | Нет | ||
| CSDP | C | Поддерживает первично-двойные методы для LP + SDP. Доступны интерфейсы для MATLAB, R и Python. Доступна параллельная версия. Решатель SDP. | да | |
| CVXOPT | Python | Поддерживает первично-двойные методы для LP + SOCP + SDP. Используется шкала Нестерова-Тодда. Интерфейсы к MOSEK и DSDP. | да | |
| МОСЕК | Поддерживает первично-двойные методы для LP + SOCP. | Нет | ||
| SeDuMi | MATLAB, MEX | Решает LP + SOCP + SDP. Поддерживает первично-двойные методы для LP + SOCP + SDP. | да | |
| СДПА | C ++ | Решает LP + SDP. Поддерживает первично-двойные методы для LP + SDP. Доступны версии с параллельной и повышенной точностью. | да | |
| SDPT3 | MATLAB, MEX | Решает LP + SOCP + SDP. Поддерживает первично-двойные методы для LP + SOCP + SDP. | да | |
| ConicBundle | Поддерживает универсальные коды для LP + SOCP + SDP. Использует метод пакета. Специальная поддержка ограничений SDP и SOCP. | да | ||
| DSDP | Поддерживает универсальные коды для LP + SDP. Использует метод двойной внутренней точки. | да | ||
| LOQO | Поддерживает универсальные коды для SOCP, которую он рассматривает как проблему нелинейного программирования. | Нет | ||
| ПЕННОН | Поддерживает универсальные коды. Использует расширенный лагранжев метод, особенно для задач с ограничениями SDP. | Нет | ||
| SDPLR | Поддерживает универсальные коды. Использует факторизацию низкого ранга с расширенным лагранжевым методом. | да | ||
| GAMS | Система моделирования для линейных, нелинейных, смешанных целочисленных линейных / нелинейных задач и задач конусного программирования второго порядка. | Нет | ||
| Глоптиполи3 | Система моделирования для полиномиальной оптимизации. | да | ||
| Услуги по оптимизации | Стандарт XML для кодирования задач оптимизации и решений. |
Расширения
Расширения выпуклой оптимизации включают оптимизацию двояковыпуклых , псевдовыпуклых и квазивыпуклых функций. Расширения теории выпуклого анализа и итерационных методов приближенного решения невыпуклых задач минимизации происходят в области обобщенной выпуклости , также известной как абстрактный выпуклый анализ.
Источник
3.1. Элементы выпуклого анализа
Множество 
называется выпуклым, если с любыми двумя точками
оно содержит отрезок, их соединяющий. Иначе это определение можно сформулировать так: множество
выпукло, если
точка
при всех
. На рис. 3.1.1 представлена геометрическая иллюстрация выпуклого и невыпуклого множеств.
Рис. 3.1.1. Геометрическая иллюстрация выпуклого (а) и невыпуклого (б) множеств
Пространство 
образует выпуклое множество. Пустое множество и множество, состоящее из одной точки, удобно считать выпуклыми. Тогда из определения выпуклого множества следует, что пересечение любого числа выпуклых множеств является выпуклым множеством.
Функция 
, определенная на выпуклом множестве
, называется выпуклой на этом множестве, если
выполнено неравенство
(3.1.1)
На рис. 3.1.2 в качестве примера приведен график выпуклой функции одной переменной 
. Выпуклую функцию можно определить как функцию,
Рис. 3.1.2. Пример выпуклой функции одной переменной
над графиком которой – выпуклое множество.
Функция 
называется вогнутой на выпуклом множестве
, если функция
выпукла на
. Вогнутую функцию можно определить также как функцию, под графиком которой – выпуклое множество.
Существуют подклассы выпуклых функций. Так, функция 
, определенная на выпуклом множестве
, называется строго выпуклой на
, если
и
равенство в (3.1.1) имеет место только при
и
.
Функция 
называется строго вогнутой на выпуклом множестве
, если функция
строго выпукла на
.
Например, функция одной переменной 
является одновременно выпуклой и вогнутой на
, однако не является ни строго выпуклой, ни строго вогнутой.
Функция 
, определенная на выпуклом множестве
, называется сильно выпуклой (сильно выпуклой с константой
) на
, если
выполнено неравенство
(3.1.2)
где 
,
– евклидова норма (длина вектора):
(3.1.3)
Функция 
, определенная на выпуклом множестве
, называется сильно вогнутой на этом множестве, если функция
сильно выпукла на
.
Функция, сильно выпуклая на множестве 
, является выпуклой и строго выпуклой на этом множестве.
Пример 3.1.1. Показать, что функция одной переменной 
сильно выпукла на
.
Левая часть неравенства (3.1.2) в данном случае принимает вид:
. (3.1.4)
Вычитая выражение (3.1.4) из первых двух слагаемых правой части неравенства (3.1.2), получим:
Таким образом, неравенство (3.1.2) превращается в тождественное равенство при 
и, следовательно, функция 
является сильно выпуклой на 
с константой
.
В практических задачах важное значение имеет выяснение наличия у исследуемых функций свойств выпуклых функций, либо их отсутствия.
Рассмотрим некоторые теоремы, которые могут быть использованы для проверки выпуклости функций.
Пусть функции 
– выпуклы на множестве
и числа
неотрицательны. Тогда функция
выпукла на множестве 
. Читателю предлагается доказать эту теорему самостоятельно.
Дана функция 
, обладающая следующими свойствами:
1) функция 
определена на множестве
,
– выпуклое множество;
2) функция 
выпукла по
;
3) функция 
ограничена сверху по
.
Тогда функция 
выпукла на множестве
.
Доказательство. Для любых точек 
и для любого
можно записать:
Таким образом, неравенство (3.1.1) выполнено, и, следовательно, теорема доказана.
В случае 
функций одной переменной
, рассматривая индекс
в качестве аналога переменной
из теоремы 3.1.2, завершающую часть формулировки этой теоремы можно записать в виде заключения о выпуклости функции
На рис. 3.1.3 представлены графики двух выпуклых функций одной переменной 
и
. График, показанный сплошной линией, является графиком функции
,
которая согласно теореме 3.1.2 является выпуклой.
Пусть функция 
выпукла на выпуклом множестве
, а функция
выпукла и монотонно не убывает на выпуклом множестве
, причем
. Тогда функция
выпукла на множестве
.
Рис. 3.1.3. Пример применения теоремы 3.1.2 для случая двух функций одной переменной
Доказательство. 
и
можно записать:
(3.1.5)
Первое из приведенных неравенств справедливо на том основании, что, во-первых,
так как функция 
выпукла, и, во-вторых, что функция
монотонно не убывает. Справедливость второго неравенства в (3.1.5) объясняется выпуклостью функции
. Теорема доказана.
Применение рассмотренных теорем к решению практических задач продемонстрируем на следующем примере.
Пример 3.1.2. Выяснить, является ли выпуклой функция
Функция 
является выпуклой по теореме 3.1.2. Функция
выпукла в соответствии с теоремой 3.1.1. Наконец, функция
, где
, является выпуклой по теореме 3.1.3. Таким обрзом, заданная в примере функция выпукла.
Следующую теорему читателю предлагается доказать самостоятельно.
1. Пусть функция 
является строго выпуклой на выпуклом множестве
. Тогда
функция
строго выпукла на
.
2. Пусть функция 
является сильно выпуклой с константой
на выпуклом множестве
. Тогда
функция
сильно выпукла с константой
на
.
3. Пусть функция 
выпукла на выпуклом множестве
, а функция
сильно выпукла с константой
на
. Тогда функция
является сильно выпуклой с константой
на
.
4. Пусть функция 
выпукла на выпуклом множестве
, а функция
строго выпукла на
. Тогда функция
является строго выпуклой на
.
Заметим, что линейная функция 
является одновременно выпуклой и вогнутой на выпуклом множестве
и что только линейные функции обладают таким свойством. При этом линейная функция не является ни строго выпуклой (вогнутой), ни сильно выпуклой (вогнутой). Всякая сильно выпуклая функция является строго выпуклой, но не наоборот. Например, функция
строго выпукла на
, но не является сильно выпуклой.
Источник
Задача выпуклого программирования
Определение 1: Функция f(x), определенная на выпуклом множестве Х, называется выпуклой, если для любых точек и из этого множества и любого справедливо неравенство:
Если в этом соотношении при и любых и Х ( ≠ ) имеет место строгое неравенство, то f(x) называется строго выпуклой.
Определение 2: Функция f(x), определенная на выпуклом множестве Х, называется вогнутой, если для любых точек и из этого множества и любого справедливо неравенство:
Если в этом соотношении при и любых и Х ( ≠ ) имеет место строгое неравенство, то f(x) называется строго вогнутой.
Определение 3: Задача математического программирования
в которой либо целевая функция, либо ограничения, либо то и другое нелинейны, называется нелинейной.
Класс задач нелинейного математического программирования очень велик. Общих универсальных методов нет. Однако, есть задачи нелинейного программирования, для которых есть методы решения. Один из таких типов задач являются задачи выпуклого программирования.
В теории выпуклого программирования в качестве основной обычно рассматривается задача минимизации выпуклой функции n переменных при ограничениях ( ), ( ), где функции предполагаются выпуклыми.
Если и являются вогнутыми, то имеем задачу максимизации при ограничениях ( ), ( ).
Метод множителей Лагранжа
Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого).
Рассмотрим классическую задачу оптимизации
От основной задачи выпуклого программирования в данной постановке задача отличается тем, что в системе ограничений нет неравенств и нет ограничения неотрицательности для переменных.
Классический подход к решению данной задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функции локальный экстремум на множестве точек, удовлетворяющих системе ограничений (для задачи выпуклого программирования найденная точка будет и глобальным экстремум).
Предположим, что в точке функция имеет локальный условный экстремум и ранг матрицы
равен m. Тогда необходимые условия запишутся в виде:
есть функция Лагранжа, – множители Лагранжа.
Алгоритм решения задачи методом множителей Лагранжа:
1. Составить функцию Лагранжа.
2. Найти частные производные функции Лагранжа по всем переменным и приравнять их к нулю. Получим систему из n+m уравнений с n+m неизвестными. Решив полученную систему, вычислим стационарные токи функции Лагранжа.
3. Из стационарных точек, взятых без , выбрать точки, в которых функция имеет условный локальный экстремумы при наличии ограничений.
Пример: Решить задачу математического программирования, используя метод множителей Лагранжа.
Будем решать задачу без учета неотрицательности переменных.
1. Составим функцию Лагранжа.
2. Найдем ее частные производные по .
Приравняв производные к нулю, получим систему:
Получена стационарная точка (91, 89). С помощью вторых производных легко доказать, что в полученной точке функция достигает условный локальный экстремум. Данная точка является точкой минимума функции.
Градиентные методы
Градиентным методом можно решать любую нелинейную задачу. При этом находится локальный экстремум. Целесообразнее же этот метод используют при решении задач выпуклого программирования.
Будем рассматривать задачу максимизации нелинейной дифференцируемой функции . Суть градиентного поиска точки максимума:
Возьмем произвольную точку из области допустимых значений. C помощью градиента функции в точке ( Определим направление, в котором возрастает с наибольшей скоростью. Затем сделав небольшой шаг в найденном направлении, перейдем в новую точку . Далее снова определяем наилучшее направление для перехода в очередную точку и т.д.
Поисковая траектория представляет собой ломаную . Таким образом, надо построить последовательность так, чтобы она сходилась к точке максимума. Для точек последовательности выполняются условия
Градиентные методы, как правило, позволяют найти точные решения за бесконечное число шагов и лишь в некоторых случаях за конечное. В связи с этим градиентные методы относят к приближенным методам решения.
Источник
3.3. Выпуклое программирование
Функция называется выпуклой на выпуклом множестве , если для любых точек и произвольного числа выполняется неравенство:
Функция называется вогнутой на выпуклом множестве , если для любых точек и произвольного числа выполняется неравенство:
Иногда выпуклую функцию называют выпуклой вниз в отличие от вогнутой функции, которую иногда называют выпуклой вверх. Смысл этих названий ясен из геометрического изображения типичной выпуклой (рис. 3.3) и вогнутой (рис. 3.4) функции.
Рис. 3.3. Выпуклая функция
Рис. 3.4. Вогнутая функция
Подчеркнем, что определения выпуклой и вогнутой функций имеют смысл только для выпуклого множества X, так как только в этом случае точка обязательно принадлежит Х.
Задачей выпуклого программирования называется частный случай общей задачи математического программирования (3.7), (3.8), когда целевая функция и функции ограничений являются вогнутыми на выпуклом множестве R.
Так как задача максимизации функции эквивалентна задаче минимизации этой функции со знаком «минус», ограничение эквивалентно неравенству и из вогнутости следует выпуклость и наоборот. Отсюда
задачей выпуклого программирования называется также задача минимизации выпуклой функции при ограничениях:
где – выпуклые функции; R – выпуклое множество. Это просто другая форма задачи.
Следует обратить внимание, что если задача выпуклого программирования формулируется как задача на максимум, то целевая функция обязательно вогнута, а если формулируется как задача на минимум – то выпукла, Если ограничения записываются в виде , то функции ограничений вогнуты, если ограничения записываются в виде , то функции ограничений выпуклы. Эта связь обусловлена наличием определенных свойств у задачи выпуклого программирования, которые при нарушении такой связи могут отсутствовать. Два основных таких свойства сформулированы в следующей лемме.
Множество допустимых планов задачи выпуклого программирования
является выпуклым. Любой локальный максимум вогнутой функции на Х является глобальным.
Если бы функции ограничений были выпуклы, то для определяемого множества Х (3.14) выпуклость уже бы не следовала. В этом случае можно доказать выпуклость множества:
Если бы целевая функция была выпукла, то утверждение леммы относительно ее максимумов стало бы неверным, однако аналогичное утверждение можно было бы доказать для минимумов.
Функция называется строго выпуклой на выпуклом множестве , если для любых точек , и произвольного числа выполняется неравенство .
Функция называется строго вогнутой на выпуклом множестве , если для любых точек , и произвольного числа выполняется неравенство:
Сумма выпуклых (вогнутых) функций выпукла (вогнута). Произведение выпуклой (вогнутой) функции на положительное число выпукло (вогнуто). Сумма выпуклой (вогнутой) и строго выпуклой (строго вогнутой) функций строго выпукла (строго вогнута).
Если функция строго вогнута (строго выпукла) на выпуклом множестве Х, то у нее может быть только одна точка максимума (минимума).
Доказательство
Предположим противное, т.е. что существует две точки , , являющиеся точками максимума строго вогнутой функции на Х. Обозначив , имеем . Тогда для любого справедливо:
т.е. пришли к противоречию. Аналогично доказывается для минимума строго выпуклой функции.
Линейная функция представляет собой единственный пример одновременно выпуклой и вогнутой функции, значит, она не является строго выпуклой (строго вогнутой). Квадратичная функция может быть не выпуклой (вогнутой), а может быть строго выпуклой (строго вогнутой); все это определяется матрицей D. Элементы матрицы D представляют собой вторые частные производные квадратичной функции, т.е.
Обозначим матрицу вторых частных производных через .
Для того чтобы квадратичная функция была выпуклой (вогнутой) на всем пространстве , необходимо и достаточно, чтобы матрица D была положительно (отрицательно) определена. Если D положительно (отрицательно) определена, т.е.
то строго выпукла (строго вогнута).
Задача максимизации (минимизации) квадратичной функции при линейных ограничениях, где D – отрицательно (положительно) определенная матрица, причем D T =D, называется задачей квадратичного программирования.
Из леммы вытекает, что рассмотренная в разделе 2 задача линейного программирования, как и задача квадратичного программирования, представляет собой частный случай задачи выпуклого программирования.
Бывают функции, которые выпуклы по одной группе переменных и вогнуты по другой. Такие функции представляют собой один из основных классов функций, у которых заведомо существует седловая точка.
(О существовании седловой точки у вогнуто-выпуклой функции). Пусть X и Y суть выпуклые замкнутые ограниченные подмножества конечномерных евклидовых пространств, а функция – непрерывна по и , вогнута по и выпукла по , тогда имеет на седловую точку.
Рассмотрим функцию Лагранжа для задачи выпуклого программирования:
определенную на прямом произведении , где . Эта функция в силу вогнутости , является вогнутой по и линейной, а следовательно, выпуклой по .
Однако нельзя утверждать на основании теоремы 1, что она имеет седловую точку, так как множество R не обязательно является замкнутым и ограниченным, а Y заведомо неограниченно. Тем не менее, можно ожидать, что при некоторых условиях седловая точка все же будет существовать.
Наиболее известной теоремой, относящейся к этому вопросу, является теорема Куна-Таккера, которая устанавливает связь между существованием решения задачи выпуклого программирования и седловой точки у функции Лагранжа при выполнении условия Слейтера: задача выпуклого программирования удовлетворяет условию Слейтера, если существует такая точка , что выполняется условие: .
Теорема Куна-Таккера
Если задача выпуклого программирования удовлетворяет условию Слейтера, то необходимым и достаточным условием оптимальности плана является существование такого , что пара является седловой точкой функции Лагранжа (3.15) на .
То, что условие Слейтера является существенным, показывает следующий пример.
Дана задача выпуклого программирования:
Здесь, очевидно, что x = 0 есть решение задачи, но у функции Лагранжа седловой точки нет, так как внешняя грань в минимаксной задаче не достигается:
Разбиение ограничений в задаче выпуклого программирования на и , как уже говорилось, является условным. Поэтому обычно под R понимается множество простого вида, это либо все пространство En, либо неотрицательный ортант, либо параллелепипед. Сложность же задачи выпуклого программирования определяется системой ограничений:
Так как седловая точка функции Лагранжа ищется на произведении множеств , где Y также является множеством простого вида (неотрицательным ортантом), то смысл теоремы Куна-Таккера состоит в сведении задачи поиска экстремума функции со сложными ограничениями на переменные к задаче поиска экстремума новой функции с простыми ограничениями.
Если множество R совпадает с En, то условия экстремума, как известно, имеют вид:
Причем эти условия являются не только необходимыми, для того чтобы функция достигала в точке максимума по , но и достаточными. Это – важное свойство вогнутых функций, а для задачи выпуклого программирования вогнута по .
Для того чтобы непрерывно дифференцируемая вогнутая функция имела в точке максимум на En, необходимо и достаточно, чтобы градиент функции в точке был равен нулю, т.е. .
Вспомним, что градиент функции равен:
Таким образом, для нахождения седловой точки функции Лагранжа на произведении , а следовательно, и для нахождения решения задачи выпуклого программирования при R=En надо решить систему уравнений (3.16). Но в этой системе n уравнений, а неизвестных n+m, так как помимо n-мерного вектора нам неизвестен и m-мерный вектор множителей Лагранжа . Однако для седловой точки функции Лагранжа выполняется очень важное свойство:
Из уравнения (3.17) вытекает, что либо , либо , либо то и другое одновременно. Это свойство аналогично второй теореме двойственности (подразд. 2.5) линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными.
Таким образом, только те множители Лагранжа могут быть отличны от нуля, которые соответствуют активным в точке ограничениям. С учетом этого свойства для нахождения решения задачи выпуклого программирования рассмотрим следующий способ.
Это множество представляет собой совокупность индексов активных в точке ограничений. Тогда можно утверждать в силу сказанного выше, что . Поэтому для определения и ненулевых имеем систему уравнений:
Число неизвестных и число уравнений в этой системе совпадают, поэтому, в принципе, находя решение системы (3.18), тем самым решим исходную задачу выпуклого программирования. Система (3.18) представляет собой необходимые и
достаточные условия оптимальности для задачи выпуклого программирования в случае, когда R = En.
Если R является неотрицательным ортантом, т.е.
то для каждой компоненты решения задачи выпуклого программирования возможны две альтернативы: либо , либо . Для первой альтернативы условия оптимальности совпадают со случаем R=En, т.е. имеют вид (3.16) (при данном j). Для второй альтернативы это не так.
Если является компонентой точки максимума функции по в области , то можно утверждать, что необходимо (а для вогнутой функции и достаточно) только выполнения неравенства
т.е. функция должна не возрастать по при движении внутрь области .
Но так как , то можно записать:
Объединяя обе альтернативы, т.е. учитывая выражения (3.16), (3.19), (3.20) для задачи выпуклого программирования в случае, можно представить в виде
Так как , то из условий (3.21) следует, что либо , либо . Таким образом, как и в случае R=En, имеем n уравнений, которые вместе с уравнениями для активных ограничений определяют и .
Найти при ограничении .
Здесь . Функция линейная и поэтому максимум достигается на границе допустимого множества. Используя условия (3.18), имеем систему трех уравнений с тремя неизвестными:
(другое решение дает минимум).
В общем случае, когда R – произвольное выпуклое множество, необходимые и достаточные условия оптимальности для задачи выпуклого программирования формулируются с помощью производных по направлению.
Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00
Источник