Алгоритм программирования конуса второго порядка

Определение программирования конуса второго порядка

Задача программирования конуса второго порядка имеет вид

$\min_{x} f^{T} x$

удовлетворяющее ограничениям

$\begin{matrix} ‖ A_{sc} (i) \cdot x - b_{sc} (i) ‖ \leq d_{sc}^{T} (i) \cdot x - γ (i) \\ A \cdot x \leq b \\ Aeq \cdot x = beq \\ фунт \leq x \leq ub . \end{matrix}$

f, x, b, beq, lb, и ub являются векторами и A, и Aeq матрицы. Для каждого i матрица A _sc (i), векторы _b sc (i) и d sc (i) и скалярные γ (i) находятся в ограничении конуса второго порядка, которое вы создаете используяsecondordercone.

Другими словами, задача имеет линейную целевую функцию и линейные ограничения, а также набор конусных ограничений второго порядка вида $‖ A_{sc} (i) \cdot x - b_{sc} (i) ‖ \leq d_{sc}^{T} (i) \cdot x - γ (i)$ .

`coneprog` Алгоритм

coneprog решатель использует алгоритм, описанный в Андерсене, Роосе и Терлаки [1]. Этот метод является алгоритмом внутренней точки, подобным алгоритму линпрога внутренней точки.

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

Алгоритм начинается с того, что помещает задачу в standard form. Алгоритм добавляет неотрицательные переменные slack так, что задача имеет вид

$\min_{x} f^{T} x$

удовлетворяющее ограничениям

$\begin{array}{l} A \cdot x = b \\ x \in K . \end{array}$

Решатель расширяет размеры вектора линейного коэффициента f и матрицы линейных ограничений A чтобы учесть переменные slack.

Область K является перекрестным продуктом Lorentz cones Уравнения 1 и неотрицательной ортантной. Чтобы преобразовать каждый выпуклый конус

$‖ A_{sc} (i) \cdot x - b_{sc} (i) ‖ \leq d_{sc}^{T} (i) \cdot x - γ (i)$

в 1 Уравнения конуса Лоренца создайте вектор-столбец переменных t 1, _t 2,..._{, t} n + 1:

$\begin{matrix} t_{1} = d^{T} x - γ \\ t_{2 : (n + 1)} = A_{sc} x - b_{sc} . \end{matrix}$

Здесь количество переменных, n для каждого i конуса, является количеством строк в A _sc (i). По своему определению, переменный вектор t удовлетворяет неравенству

‖ t_{2 : (n + 1)} ‖ \leq t_{1} .

(1)

Уравнение 1 является определением конуса Лоренца в (n + 1) переменных. Переменные, t появляются в задаче вместо переменных, x в выпуклой области K.

Внутренне алгоритм также использует rotated Lorentz cone в переформуляции ограничений конуса, но эта тема не затрагивает этот случай. Для получения дополнительной информации см. Андерсена, Руса и Терлаки [1].

При добавлении переменных slack алгоритм сводит на нет переменные, при необходимости, и добавляет соответствующие константы так, чтобы:

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

Двойная задача

Двойной конус

$K_{*} = {s : s^{T} x \geq 0 \forall x \in K} .$

Двойственная проблема

$\max_{y} b^{T} y$

таким, что

$A^{T} y + s = f$

для некоторых

$s \in K_{*} .$

Двойственное оптимальное решение является точкой (y, s), которая удовлетворяет двойственным ограничениям и максимизирует двойственную цель.

Однородная самодвойственная рецептура

Чтобы обработать потенциально недопустимые или неограниченные задачи, алгоритм добавляет еще две переменные τ и κ и формулирует задачу как однородную (равную нулю) и двойственную.

\begin{matrix} A x - b τ = 0 \\ A^{T} y + s - f τ = 0 \\ - f^{T} x + b^{T} y - κ = 0 \end{matrix}

(2)

наряду с ограничениями

(x; τ) \in \bar{K}, (s; κ) \in {\bar{K}}_{*} .

(3)

Вот, $\bar{K}$ - K конуса, примыкающая к неотрицательной действительной линии, которая является пространством для (x; τ). Так же ${\bar{K}}_{*}$ является конусом $K_{*}$ примыкает к неотрицательной действительной линии, которая является пространством для (s; κ). В этой формулировке следующая лемма показывает, что τ является масштабированием для возможных решений, и κ является показателем недопустимой задачи.

Лемма ([1] Лемма 2.1)

Позвольте (x, τ, y, s, κ) быть возможным решением Уравнения 2 наряду с ограничениями в Уравнении 3.

x^Ts + τκ = 0.
Если τ > 0, то (x, y, s )/ τ является основной-двойственным оптимальным решением стандартной формы задачи конуса второго порядка.
Если κ > 0, то по крайней мере одно из этих строгих неравенств содержит:
b^Ty > 0
f^Tx < 0.
Если первое неравенство имеет место, то стандартная форма, основная задача конуса второго порядка недопустима. Если удерживается второе неравенство, то стандартная форма, двойственная задача конуса второго порядка недопустима.

Сводные данные, для допустимых задач переменная τ масштабирует решение между исходной задачей стандартной формы и однородной самодвойственной задачей. Для неосуществимых проблем финал повторяет (x, y, s, τ, κ) предоставляет свидетельство о недопустимости для оригинальной стандартной проблемы формы.

Начальная точка

Начальной точкой для итераций является допустимая точка:

x = 1 для каждой неотрицательной переменной, 1 для первой переменной в каждом конусе Лоренца и 0 в противном случае.
y = 0.
s = (1,0,..., 0) для каждого конуса, 1 для каждой неотрицательной переменной.
τ = 1.
κ = 1.

Центральный путь

Алгоритм пытается следовать central path, которая является параметризованным решением следующих уравнений для γ уменьшения с 1 до 0.

\begin{matrix} A x - b τ = γ (A x_{0} - b τ_{0}) \\ A^{T} y + s - c τ = γ (A^{T} y_{0} + s_{0} - f τ_{0}) \\ - f^{T} x + b^{T} y - κ = γ (- f^{T} x_{0} + b^{T} y_{0} - κ_{0}) \\ X S e = γ μ_{0} e \\ τ κ = γ μ_{0} . \end{matrix}

(4)

Каждая переменная с индексом 0 указывает начальную точку переменной.
X и S переменных являются arrow head матрицами, сформированными из векторов x и s, соответственно. Для вектора x = [x 1, x 2,_..., xn] матрица со стрелкой X имеет определение
$X = mat (x) = [\begin{matrix} x_{1} & x_{2 : n}^{T} \\ x_{2 : n} & x_{1} I \end{matrix}] .$
По своему определению X симметрична.
Переменная e является вектором с 1 в каждой координате конуса, соответствующей x 1 координате конуса Лоренца.
Переменная μ 0 имеет определение
$μ_{0} = \frac{x_{0}^{T} s_{0} + τ_{0} κ_{0}}{k + 1},$
где k - количество ненулевых элементов в x 0.

Центральный путь начинается в начальной точке и заканчивается оптимальным решением однородной двойственной задачи.

Андерсен, Роос и Терлаки [1] показывают в Лемме 3.1, что условие комплементарности x^Ts = 0, где x и s находятся в продукте Lorentz cones L, эквивалентно условию

$X_{i} S_{i} e_{i} = S_{i} X_{i} e_{i} = 0$

для каждого i конуса. Здесь _Xi = mat (_xi), _xi является переменной, связанной с i конуса Лоренца, _Si = mat ₍si), и ei является вектором модуля [1,0,0,..., 0] соответствующей размерности. Это обсуждение показывает, что центральный путь удовлетворяет условию комплементарности в своей конечной точке.

Направление поиска

Чтобы получить точки около центрального пути, когда γ параметра уменьшается с 1 до 0, алгоритм использует метод Ньютона. Переменные, чтобы найти маркированы (x, τ, y, s, κ). Позвольте _dx представить направление поиска для переменных x и так далее. Затем шаг Ньютона решает следующую линейную систему, выведенную из уравнения 4.

$\begin{matrix} A d_{x} - b d_{τ} = (γ - 1) (A x_{0} - b τ_{0}) \\ A^{T} d_{y} + d_{s} - f d_{τ} = (γ - 1) (A^{T} y_{0} + s_{0} - f τ_{0}) \\ - f^{T} d_{x} + b^{T} d_{y} - d_{κ} = (γ - 1) (- f^{T} x_{0} + b^{T} y_{0} - κ) \\ X_{0} d_{s} + S_{0} d_{x} = - X_{0} S_{0} e + γ μ_{0} e \\ τ_{0} d_{κ} + κ_{0} d_{t} a u = - τ_{0} κ_{0} + γ μ_{0} . \end{matrix}$

Алгоритм получает свою следующую точку, делая шаг в d направлении.

$[\begin{matrix} x_{1} \\ τ_{1} \\ y_{1} \\ \begin{array}{l} s_{1} \\ κ_{1} \end{array} \end{matrix}] = [\begin{matrix} x_{0} \\ τ_{0} \\ y_{0} \\ \begin{array}{l} s_{0} \\ κ_{0} \end{array} \end{matrix}] + α [\begin{matrix} d_{x} \\ d_{τ} \\ d_{y} \\ \begin{array}{l} d_{s} \\ d_{κ} \end{array} \end{matrix}]$

для некоторого шага $α \in [0, 1]$ .

Для как численной устойчивости, так и ускоренной сходимости алгоритм масштабирует шаг согласно предложению у Нестерова и Тодда [8]. Кроме того, алгоритм корректирует шаг согласно варианту предиктора-корректора Мехротры [7]. (Для получения дополнительной информации см. Андерсена, Руса и Терлаки [1].)

Изменения решателя шага

Предшествующее обсуждение относится к LinearSolver опция со значением 'augmented' указано. Решатель имеет другие значения, которые изменяют вычисление шага в соответствии с различными типами задач.

'auto' (по умолчанию) - coneprog выбирает решатель шага:
- Если задача разрежена, то решатель шага 'prodchol'.
- В противном случае решатель шага 'augmented'.
'normal' - Решатель использует вариант 'augmented' шаг, который подходит, когда проблема является разреженной. См. Андерсена, Руса и Терлаки [1].
'schur' - Решатель использует модифицированный метод Schur для обработки разреженной задачи с несколькими плотными столбцами. Этот способ также подходит для больших конусов. См. Андерсен [2].
'prodchol' - Решатель использует методы, описанные в Goldfarb и Scheinberg ([4] и [5]), для обработки разреженной задачи с несколькими плотными столбцами. Этот способ также подходит для больших конусов.

Итерационные условия отображения и остановки

На каждом k итерации алгоритм вычисляет три меры относительной сходимости:

Основной недопустимость
${Infeas}_{Основной}^{k} = \frac{‖ A x_{k} - b τ_{k} ‖}{\max (1, ‖ A x_{0} - b τ_{0} ‖)} .$
Двойная недопустимость
${Infeas}_{Двойной}^{k} = \frac{‖ A^{T} y_{k} + s_{k} - f τ_{k} ‖}{\max (1, ‖ A^{T} y_{0} + s_{0} - f τ_{0} ‖)} .$
Недопустимость погрешностей
${Infeas}_{Промежуток}^{k} = \frac{| - f^{T} x_{k} + b^{T} y_{k} - κ_{k} |}{\max (1, | - f^{T} x_{0} + b^{T} y_{0} - κ_{0} |)} .$

Можно просмотреть эти три статистики в командной строке, задав итеративное отображение.

options = optimoptions('coneprog','Display','iter');

Все три должны приблизиться к нулю, когда задача допустима, и решатель сходится. Для допустимой задачи _κk переменной приближается к нулю, а _τk переменной - к положительной константе.

Одно условие остановки в некоторой степени связано с недопустимостью зазора. Условие остановки, когда следующая мера оптимальности уменьшается ниже допуска оптимальности.

${Optimality}^{k} = \frac{| f^{T} x_{k} - b^{T} y_{k} |}{τ_{k} + | b^{T} y_{k} |} = \frac{| f^{T} x_{k} / τ_{k} - b^{T} y_{k} / τ_{k} |}{1 + | b^{T} y_{k} / τ_{k} |} .$

Эта статистическая величина измеряет точность целевого значения.

Решатель также останавливает и объявляет задачу недопустимой при следующих условиях. Три меры относительной недопустимости меньше c = ConstraintTolerance, и

$τ_{k} \leq c \max (1, κ_{k}) .$

Если b^T_yk > 0, тогда решатель объявляет, что основная задача недопустима. Если f^T_xk < 0, тогда решатель заявляет, что двойственная задача недопустима.

Алгоритм также останавливается, когда

$μ_{k} \leq c μ_{0}$

$τ_{k} \leq c \max (1, κ_{k}) .$

В этом случае, coneprog сообщает, что задача численно нестабильна (выходной флаг -10).

Оставшееся условие остановки возникает, когда, по крайней мере, одна мера недопустимости больше ConstraintTolerance и вычисленный размер шага слишком мал. В этом случае, coneprog сообщает, что поисковое направление стало слишком маленьким и не могло быть достигнуто никакого дальнейшего прогресса (выходной флаг -7).

Ссылки

[1] Андерсен, Э. Д., К. Роос и Т. Терлаки. О реализации основного-двойственного метода внутренней точки для конической квадратичной оптимизации. Math. Program., Ser. B 95, pp. 249-277 (2003). https://doi.org/10.1007/s10107-002-0349-3

[2] Андерсен, К. Д. Модифицированный метод schur-complement для обработки плотных столбцов в методах interior-point для линейного программирования. Транзакции ACM на математическом программном обеспечении (TOMS), 22 (3): 348-356, 1996.

[3] Бен-Таль, Ахарон и Аркади Немировски. Выпуклая оптимизация в технике: моделирование, анализ, алгоритмы. (1998). Доступно в https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455.2733&rep=rep1&type=pdf.

[4] Голдфарб, Д. и К. Шейнберг. Метод факторизации Холесского продукта для обработки плотных столбцов во внутренних методах точки для линейного программирования. Математическое программирование, 99 (1): 1-34, 2004.

[5] Голдфарб, Д. и К. Шейнберг. Форма продукта факторизации Холесского во внутренних точечных методах для программирования конуса второго порядка. Математическое программирование, 103 (1): 153-179, 2005.

[6] Ло, Чжи-Цюань, Жос Ф. Штурм и Шучжун Чжан. Двойственность и самодвойственность для конического выпуклого программирования. (1996). Доступно в https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.6432

[7] Мехротра, Санджай. «О реализации примитивно-двойственного метода точки». SIAM Journal на 2 оптимизации, № 4 (ноябрь 1992): 575-601. https://doi.org/10.1137/0802028.

[8] Нестеров, Ю. Э. и М. Дж. Тодд. Self-Scaled Barriers and Interior-Point Methods for Convex Programming (неопр.) (недоступная ссылка). Математика операций Исследования 22, № 1 (февраль 1997 года): 1-42. https://doi.org/10.1287/moor.22.1.1.

См. также

coneprog | secondordercone

Документация