Курс выпуклой оптимизации

Оптимизация

Определение: Найдите лучший элемент из допустимого решения. Вообще говоря, оптимизационные задачи можно записать в следующем виде:

Минимизируем целевую функцию: min f_l(x)

m функций ограничений: st: f_i(x)<=b_i ( i=1...m)

x = [x1...xn]^T

Выпуклое программирование и невыпуклое программирование

Выпуклое программирование удовлетворяет:

Выпуклое программирование относительно легко решить, невыпуклое программирование решить сложнее.

Аффинный набор

Множество c является аффинным множеством.Если x1 и x2 принадлежат множеству c, то связь между x1 и x2 также принадлежит множеству c

Аффинная комбинация: θ_1(x_1)+θ_2(x_2)+...θ_k(x_k) ∈ c ,и

Аффинный пакет: любой набор c, построить наименьший возможный аффинный набор

выпуклое множество

комбинация

Положительно определенный и положительно полуопределенный

Положительно полуопределенное: то есть собственное значение >= 0, но обычно собственное значение слишком сложно найти. мы можем пройти Если X принадлежит R, для любого X мы должны удовлетворять X*A*X^T > 0 , то A положительно полуопределенно.

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

Положительное определение:

Аффинная функция

Аффинная функция — это функция, составленная из полинома первого порядка.Общая форма: f (x) = A x + b. Здесь A — матрица размера m × k, x — вектор ak, а b — вектор m. Фактически, он отражает отношение пространственного отображения от k-мерного к m-мерному. Пусть f — векторная функция (значение), если она может быть выражена как f(x1,x2,...,xn)=A1x1+A2x2+...+Anxn+b, где Ai может быть скаляром или матрицей, тогда она называется f — аффинная функция.

23-24

Обобщенная выпуклая задача

узкая выпуклая задача

Целевая функция выпукла, ограничения неравенства выпуклы, a_i^TX = b_i

является аффинной функцией

Важные свойства Выпуклые задачи: локальный оптимум = глобальный оптимум

Сначала определим локальное оптимальное решение: когдадопустима (т. е. лежит в допустимой области) и существует (R > 0) , так что для всех $(\parallel x-z \parallel_2 \leq R)$ находится в допустимой точке (z) , так что $(f(x) \leq f(z))$ .

Процесс доказательства выглядит следующим образом:

сделатьявляется локальным оптимальным решением, но не глобальным оптимальным решением, поэтому существует допустимая точкасделать f(x) > f(y) , Согласно определению локального оптимального решения не существует допустимой точкиудовлетворить $\parallel x-z \parallel_2 \leq R, f(z) < f(x)$ Однако мы можем построить композицию

z=\theta y + (1-\theta)x, \theta=\frac{R}{2\parallel x-y \parallel_2}

в $\theta$ является фиксированным значением, которое является специальным методом, потому что $\parallel x-y \parallel_2 > R$ ,так какдолжен быть вне локальной области видимости, поэтому $\theta=\frac{R}{2\parallel x-y \parallel_2}$ Диапазон значений от 0 до 1/2. Итак, z — выпуклая комбинация. Поскольку z — выпуклая комбинация, тоЭто также должно быть возможно.

Поскольку это выпуклая задача, мы можем получить: $f(z) = { \theta y + (1-\theta)x }, f(z) \leq (1-θ)f(x) + θf(y)$

так как $\theta=\frac{R}{2\parallel x-y \parallel_2}$ ,так $\parallel x-z \parallel_2= {\theta \parallel x-y \parallel_2 = \frac{R}{2} }$ , Доступный f(y) < f(x) <= f(z) .

так как f(y) < f(x) <= f(z) , очевидно (1-θ)f(x) + θf(y) < f(z)

$f(z) \leq (1-θ)f(x) + θf(y) < f(z)$ , предположение не выполняется, поэтому (x) является глобальным оптимальным решением.

двойная проблема

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

«Три выпуклых»

Прежде всего, давайте посмотрим, что такое выпуклая оптимизация? Помимо различных теорий и алгоритмов выпуклой оптимизации, если рассматривать только модель оптимизации, выпуклая оптимизация: 1. При условии минимизации (максимизации), 2. Целевая функция является выпуклой функцией (вогнутая функция), 3. , а множество допустимых областей, образованных ограничениями, является выпуклым множеством. Все три условия выше должны быть соблюдены. А в мире все постоянно меняется, и он может быть не выпуклым, если нарисована какая-то функция или множество.

Определение выпуклого множества: в евклидовом пространстве для любой точки на линии, соединяющей любые две точки множества, мы можем судить о множестве как о выпуклом выпуклом множестве.

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

Определение положительной полуопределенной матрицы: вещественная симметричная матрица с собственным значением, большим или равным 0. Вещественная симметричная матрица:

Если имеется матрица A n-го порядка, то все элементы матрицы — действительные числа, а транспонирование матрицы A равно самому себе (aij=aji) (i, j — нижние индексы элементов), а все собственные значения, соответствующие матрице, являются действительными числами, тогда А называется вещественной симметричной матрицей.

Положительная полуопределенная матрица: матрица с собственными значениями больше или равными 0.

Достаточные и необходимые условия для выпуклых функций: Для функции с одной переменной ее первая производная больше или равна 0, а для функции с несколькими переменными ее матрица Гессе (матрица Гессе) является полуположительно определенной матрицей. Матрица Гессе:

Позвольте мне выразить свое скромное понимание. Положительно-полуопределенные и положительно-определенные матрицы соглашаются использовать положительно-полуопределенную матрицу в качестве примера: во-первых, положительно-полуопределенная матрица определяется как: где X - вектор, а M - матрица преобразования. Давайте посмотрим на эта проблема с другого способа мышления.В матричном преобразовании это представляет собой преобразование вектора X, мы предполагаем, что преобразованный вектор - это Y, обозначаемый как . Таким образом, полуположительно определенная матрица может быть записана так: Это очень знакомо? Это внутренний продукт двух векторов. В то же время у нас также есть формула: ||X||, ||Y|| представляют собой длину векторов X, Y, то есть угол между ними. Итак, положительная полуопределенная матрица означает, теперь вы понимаете? Интуиция положительно определенных и полуположительно определенных матриц означает, что угол между вектором после его изменения и самим собой меньше или равен 90 градусам.

Выпуклое квадратичное программирование

Есть хорошая статья:блог woo woo woo.cn on.com/xinchen 1111…

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

\begin{align*} min\quad f(x)\\ s.t.\quad h(x) = 0 \end{align*}

При решении этой задачи мы не можем сначала использовать описанный выше метод для нахождения крайней точки f(x), а затем оставить ту, которая удовлетворяет уравнению h(x)=0. Поскольку решение этой проблемы может вообще не быть решением minf(x), они не имеют значения. Тогда нам еще предстоит найти подсказки из самой проблемы:

Как показано на рисунке, окружность относится к изолинии целевой функции f(x, y), спроецированной на плоскость, которая представлена на той же окружности, а черная линия является образом функции условия ограничения h(x, y). )=0. Таким образом, точки пересечения контура и графика функции на самом деле являются точками, удовлетворяющими ограничениям. Тогда крайнюю точку можно взять только в том месте, где линия контура касается образа функции, потому что, если она взята на пересечении, то должны быть другие вещи, идущие вперед или назад по образу h(x). контур , пересекает его, то есть значение f(x,y) также может становиться больше и меньше, поэтому точка пересечения не является крайней точкой, только когда она касается касательной, она может быть крайней точкой (нельзя увеличиваются и уменьшаются одновременно) становятся меньше). Там, где есть касательная, градиент h(x) и градиент f(x,y) должны быть на одной линии. (Подумайте об этом так: градиенты обеих функций в точке касания перпендикулярны касательной плоскости, то есть на прямой линии)

Таким образом, крайняя точка, удовлетворяющая условию, должна удовлетворять: в точке касания выше), а затем комбинируется с исходным уравнением h(x,y)=0, а затем, пока эта система уравнений решена, может быть получено аналитическое решение задачи. Конечно, есть также случаи, когда решение не может быть найдено, и для получения численного решения необходимо использовать такие методы, как метод штрафной функции.

Для удобства и легкости запоминания исходная оптимизационная задача записывается в виде f(x,y)+λh(x,y), а затем получаются частные производные по λ,x,y соответственно, и частные производные равны 0. Это то же самое, что система уравнений, полученная ранее. Этот метод называется методом множителей Лагранжа.

Что делать, если существует несколько ограничений равенства, как показано ниже:

Плоскость и сфера здесь представляют два ограничения h1(x) и h2(x) соответственно, тогда допустимой областью этой задачи является круг, где они пересекаются. Здесь синие стрелки представляют собой градиент плоскости, а черные стрелки представляют собой градиент сферы, тогда градиент пересекающихся окружностей является их линейной комбинацией (просто интуитивно ~), поэтому градиент целевой функции и градиент ограничения в крайней точке линейной комбинации . Итак, удовлетворяйте:

\nabla f(x) = \lambda \sum_{i=1}^{2}\mu_{i}\nabla h_i(x)=\sum_{i=1}^{2}\lambda_{i}\nabla h_i(x)\\ h_1(x)=0\\ h_2(x)=0

То же самое верно для более чем 2 ограничений. Чтобы не забыть, запишите исходную задачу с ограничениями как L(x,λ)=f(x)+∑ni−1λi∇hi(x), затем возьмите частные производные по x, λ и пусть они равны 0. Результат такой же, как и при непосредственном перечислении системы уравнений, как указано выше. Это можно рассматривать как сокращение или двойственную задачу, эта функция называется функцией Лагранжа.

Идя дальше, что, если в задаче есть как ограничения равенства, так и ограничения неравенства? за:

\begin{align*} min \quad f(x)\\ & s.t. \quad h(x) = 0\\ &\quad \quad \quad g(x) \leq 0 \end{align*}

Конечно, также принято, что неравенство ≤, и если оно ≥, просто отмените его. Для этой задачи давайте не будем смотреть на ограничения равенства, для графика ограничений неравенства и целевой функции:

Заштрихованная часть — допустимая область, что означает, что допустимая область изменилась с линии на область. Тогда могут быть две ситуации, когда можно получить крайнюю точку: или где h(x) касается контура Крайние точки f(x) сами находятся в допустимой области.

Потому что, если она не является касательной, то аналогичным образом для любой точки допустимой области, если вы входите или выходите из нее, f (x) обычно становится больше или меньше, поэтому большинство точек не будут крайними точками. Если только точка не находится на стыке и не касается контура, или точка не находится внутри допустимой области, но сама является крайней точкой f(x). Как показано ниже (изображение в Википедии~):

В первом случае ограничение неравенства становится ограничением равенства, и для f(x)+λh(x)+µg(x) используется метод множителей Лагранжа:

\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\ h(x)=0\\ g(x)=0\\ \mu \geq 0

Здесь нужно пояснить, почему не µ≠0, а µ≥0. Последние ограничения сильнее первых. Глядя на график «ограничений-неравенств», мы уже знаем, что допустимая область в задаче находится на стороне g(x)≤0, а градиент g(x) указывает на сторону больше 0, т. е. , это не выполнимый регион. Проблема нахождения заключается в минимальном значении, поэтому градиент f(x) в точке пересечения указывает на одну сторону допустимой области, то есть два градиента должны быть противоположны. Таким образом, можно определить, что коэффициент здесь должен быть больше 0. Ограничение равенства не имеет ограничения на направление градиента h(x), потому что оно не знает направление градиента, так почему же μ может быть равно 0, ведь крайняя точка может быть как раз на g(x).

Во втором случае ограничение неравенства эквивалентно отсутствию, и для f(x)+λh(x) используется метод множителей Лагранжа:

\nabla f(x)+\lambda \nabla h(x)= 0\\ h(x)=0\\ g(x) \leq 0

Лучше всего представить оба случая в одном и том же наборе уравнений. Сравните две задачи, разница в том, что µ≥0 и g(x)=0 в первом случае и µ=0 и g(x)≤0 во втором случае. Объединив два случая, можно записать как µg(x)=0 и µ≥0 и g(x)≤0:

\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x) = 0\\ \mu g(x) = 0\\ \mu \geq 0 \\ h(x)=0\\ g(x) \leq 0

Это условие ККТ. Его смысл в том, что крайняя точка этой оптимизационной задачи должна удовлетворять этой системе уравнений. (Это может быть выполнено, даже если это не экстремальная точка, но не будет ситуации, когда экстремальная точка не выполняется.) Это также необходимое условие для того, чтобы исходная задача оптимизации получила экстремальное значение. точка решена, ее необходимо подставить в проверку. Однако из-за множества ограничений и более сложной ситуации условие ККТ выполняется не для каждой ситуации. Для выполнения условий ККТ требуются некоторые условия регулярности, то есть качество ограничений не должно быть слишком плохим, например:

1. LCQ: Если и h(x), и g(x) являются аффинными функциями вида Ax+b, то экстремальное значение должно удовлетворять условию ККТ.

2.LICQ: функция g(x) в действии (то есть случай, когда g(x) эквивалентен ограничению равенства) и h(x) Градиент функции в экстремальной точке должен быть линейно независимым, тогда экстремальное значение должно удовлетворять условию ККТ.

3. Условие Слейтера: если задача оптимизации является выпуклой задачей оптимизации и хотя бы одна точка удовлетворяет h(x)=0 и g(x)=0, экстремальное значение должно удовлетворять условию ККТ. И удовлетворять сильному свойству двойственности (обсуждаемому ниже).

Условие Слейтера здесь важно, поскольку оно приводит к сильным свойствам двойственности (оно лучше, чем условие ККТ, как мы увидим ниже). Это требует, чтобы исходная задача была задачей выпуклой оптимизации. Так называемая выпуклая оптимизация заключается в том, что функция оптимизации этой задачи оптимизации является выпуклой функцией, а допустимая область представляет собой выпуклое множество. Допустимое выпуклое множество доменных чисел требует, чтобы h(x) также была выпуклой функцией при условии, что h(x)≤0, а g(x) в g(x)≤0 должно иметь форму Ax+b , то есть аффинная функция (например, в двумерном случае допустимая область находится на кривой g(x), тогда g(x) должна быть прямой линией, чтобы удовлетворять определению выпуклого множества).

Есть много других условий, можете посмотреть википедию.

Если существует несколько наборов ограничений равенства gi(x)=0(i=1,..,n), то же верно и для ограничений неравенства hi(x)≠0(i=1,..,n), как пока линейный Просто объедините:

\nabla f(x)+\sum_{i=1}^{n}\lambda_i \nabla h_i(x)+\sum_{i=1}^{n}\mu_i \nabla g_i(x) = 0\\ \mu_i g(x)_i = 0\\ \mu_i \geq 0\\ h_i(x)=0\\ g_i(x) \leq 0\\ i = 1,2,...,n

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

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

Чтобы снять ограничения в задаче, их можно добавить к целевой функции в виде штрафных членов minxf(x)+Mh(x)+Ng(x), где M, N — два больших положительных числа, которые можно использовать в численные решения.Выполнение этого непосредственно является идеей метода штрафной функции. Однако это не является строгим в теоретическом выводе, если только M, N не бесконечны. Итак, перепишите исходную задачу L(x,µ,λ)=minxmaxµ,λf(x)+λh(x)+µg(x) . Эту формулу можно понять так: теперь внешнему слою задается любое значение x0, а затем внутренний слой оптимизирует эту функцию при заданном x0, чтобы сделать ее наименьшей. Затем внешний слой выбирает тот x0, который может заставить внутренний слой получить наибольшее значение, и полученное функциональное выражение:

L(x,\mu,\lambda)= \left\{\begin{matrix} f(x) & (x \quad满足约束)\\ \infty & (x \quad不满足约束)\\ \end{matrix}\right.

Следовательно, x0, выбранный внешним слоем, должен удовлетворять ограничению, иначе max внутреннего слоя сделает µ или λ бесконечным. Внешний слой не будет выбирать значения x, которые давали бы бесконечность внутреннему слою. Это переписывание точно такое же, как исходная ограниченная форма, но форма отличается. Таким образом, можно использовать формулу maxminf(x)≤minmax(f(x)) (это легко понять, minf(x)≤minmaxf(x), а затем есть эта формула), чтобы получить нижнюю границу минимального значения исходной задачи, то есть:

min_{x}max_{\mu,\lambda}f(x) + \lambda h(x) + \mu g(x) \geq max_{\mu,\lambda}min_{x}f(x) + \lambda h(x) + \mu g(x)

Первая — это исходная функция, а вторая — ее нижняя граница. Так зачем вы это делаете?Потому что последняя должна быть выпуклой программой (доказанной в теории), которую лучше решать. Но это всего лишь нижняя граница, и между ними все же есть определенный разрыв. Этот разрыв называется разрывом двойственности. Если двойная ошибка равна 0, это на самом деле очень хорошее свойство, а это означает, что решение исходной задачи может быть напрямую решено путем решения следующей задачи Это свойство называется сильной двойственностью, в противном случае это просто слабая двойственность.

Свойство сильной двойственности — это очень хорошо, но требования также очень строгие, более строгие, чем условие ККТ. Если задача удовлетворяет сильной двойственности, то она также должна удовлетворять условию ККТ, и наоборот. Для этого типа задачи оптимизации связь между условием ККТ, сильной двойственностью и нормативным условием такова:

Чтобы узнать о сильном дуальном запуске KKT, вы можете обратиться к этому блогу.