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

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

Коническая проблема программирования второго порядка имеет форму

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

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

$\begin{matrix} ‖ A_{sc} (i) \cdot x - b_{sc} (i) ‖ \leq d_{кв/см}^{T} (i) \cdot x - γ (i) \\ A \cdot x \leq b \\ Aeq \cdot x = beq \\ lb \leq x \leq ub . \end{matrix}$

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

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

`coneprog` Алгоритм

coneprog решатель использует алгоритм, описанный в Андерсене, Кенгуру и Terlaky [1]. Этот метод является алгоритмом внутренней точки, похожим на Внутреннюю точку linprog Алгоритм.

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

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

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

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

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

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

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

$‖ A_{sc} (i) \cdot x - b_{sc} (i) ‖ \leq d_{кв/см}^{T} (i) \cdot x - γ (i)$

к уравнению 1 конуса Лоренца создайте вектор-столбец переменных t ₁, t ₂, …, t _{n +1}:

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

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

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

(1)

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

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

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

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

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

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

$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 ₁, x ₂, …, _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 ₁ координата конуса Лоренца.
Переменная μ ₀ имеет определение
$μ_{0} = \frac{x_{0}^{T} s_{0} + τ_{0} κ_{0}}{k + 1},$
где k является количеством ненулевых элементов в x ₀.

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

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

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

для каждого конического i. Здесь _Xi = циновка (_xi), _xi является переменной, сопоставленной с конусом Лоренца i, _Si = циновка (_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]. (Для получения дальнейшей информации смотрите Андерсена, Кенгуру и Terlaky [1].)

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

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

'auto' (значение по умолчанию) — coneprog выбирает решатель шага:
- Если проблема разреженна, решателем шага является 'prodchol'.
- В противном случае решателем шага является 'augmented'.
'normal' — Решатель использует вариант 'augmented' шаг, который подходит, когда проблема разреженна. Смотрите Андерсена, Кенгуру и Terlaky [1].
'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] Андерсен, E. D., C. Кенгуру и Т. Терлэки. При реализации основного двойного метода внутренней точки для конической квадратичной оптимизации. Математика. Программа., Сер. B 95, стр 249–277 (2003). https://doi.org/10.1007/s10107-002-0349-3

[2] Андерсен, K. D. Модифицированный дополнительный Шуром метод для обработки плотных столбцов в методах внутренней точки для линейного программирования. Транзакции на Mathematical Software (TOMS) ACM, 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] Goldfarb, D. и К. Шайнберг. Метод факторизации Холесского формы продукта для обработки плотных столбцов в методах внутренней точки для линейного программирования. Математическое программирование, 99 (1):1–34, 2004.

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

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

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

[8] Нестеров, Ю. E. и М. Дж. Тодд. “Самомасштабированные Барьеры и Методы внутренней точки для Выпуклого программирования”. Математика Исследования операций 22, № 1 (февраль 1997): 1–42. https://doi.org/10.1287/moor.22.1.1.

Смотрите также

coneprog | secondordercone

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