Проблема программирования конуса второго порядка имеет вид
с учетом ограничений
A⋅x≤bAeq⋅x=beqlb≤x≤ub.
f, x, b, beq, lb и ub - векторы, а A и Aeq - матрицы. Для каждого i матрица Asc (i), векторы bsc (i) и dsc (i) и скаляр γ (i) находятся в ограничении конуса второго порядка, которое создается с помощьюsecondordercone.
Другими словами, задача имеет линейную целевую функцию и линейные ограничения, а также набор конических ограничений второго порядка вида ⋅x−γ (i).
coneprog Алгоритм coneprog решатель использует алгоритм, описанный в Andersen, Roos и Terlaky [1]. Этот метод представляет собой алгоритм внутренней точки, аналогичный алгоритму внутренней точки linprog.
Алгоритм начинается с размещения проблемы в стандартном виде. Алгоритм добавляет неотрицательные переменные слабости, так что проблема имеет вид
с учетом ограничений
Решатель расширяет размеры вектора линейных коэффициентов f и матрицы линейных ограничений A для учета переменных ослабления.
Область K является перекрестным произведением уравнения 1 колбочек Лоренца и неотрицательного ортанта. Преобразование каждого выпуклого конуса
⋅x−γ (i)
к конусу Лоренца Уравнение 1, создайте вектор-столбец переменных t1, t2,..., tn + 1:
Ascx − bsc.
Здесь число переменных n для каждого конуса i является числом строк в Asc (i). По своему определению вектор переменной t удовлетворяет неравенству
| ‖ ≤t1. | (1) |
Уравнение 1 - определение конуса Лоренца в (n + 1) переменных. Переменные t появляются в задаче вместо переменных x в выпуклой области K.
Внутри алгоритм также использует повернутый конус Лоренца при переформулировании ограничений конуса, но в этом разделе этот случай не рассматривается. Подробнее см. Андерсен, Роос и Терлаки [1].
При добавлении переменных слабости алгоритм при необходимости сводит переменные на нет и добавляет соответствующие константы так, что:
Переменные только с одной границей имеют нижнюю границу, равную нулю.
Переменные с двумя границами имеют нижнюю границу нуля и, используя переменную ослабления, не имеют верхней границы.
Переменные без границ помещаются в конус Лоренца с переменной ослабления в качестве зависимой переменной. Эта переменная слабости не является частью какого-либо другого выражения, цели или ограничения.
Двойной конус
}.
Двойная проблема
такой, что
= f
для некоторых
Двойное оптимальное решение - это точка (y, s), которая удовлетворяет двойственным ограничениям и максимизирует двойную цель.
Чтобы справиться с потенциально неосуществимыми или неограниченными проблемами, алгоритм добавляет ещё две переменные startи startи формулирует задачу как однородную (равную нулю) и самовращённую.
| fTx + bTy − start= 0 | (2) |
вместе с ограничениями
| ∈K¯ *. | (3) |
Здесь ve - конус К, примыкающий к неотрицательной вещественной прямой, которая является пространством для (x; start). Dw * - это конус K *, примыкающий к неотрицательной вещественной прямой, которая является пространством для (s; В этой формулировке следующая аннотация показывает, что τ - вычисление для выполнимых решений, и κ - индикатор неосуществимой проблемы.
Лемма ([1] Лемма 2.1)
Позвольте (x, τ, y, s, κ) быть выполнимым решением Уравнения 2 наряду с ограничениями в Уравнении 3.
xTs + start, = 0.
Если start> 0, то (x, y, s )/startявляется первично-двойственным оптимальным решением стандартной задачи конуса второго порядка.
Если 0, то, по крайней мере, одно из этих строгих неравенств имеет:
bTy > 0
fTx < 0.
Если первое неравенство сохраняется, то стандартная форма, основная проблема конуса второго порядка неосуществима. Если второе неравенство сохраняется, то стандартная форма, двойственная проблема конуса второго порядка неосуществима.
Подводя итог, можно сказать, что для выполнимых задач переменная startмасштабирует решение между исходной стандартной задачей формы и однородной самостоятельной задачей. Для неосуществимых проблем финал повторяет (x, y, s, τ, κ) предоставляет свидетельство о infeasibility для оригинальной стандартной проблемы формы.
Начальная точка итераций является возможной точкой:
x = 1 для каждой неотрицательной переменной, 1 для первой переменной в каждом конусе Лоренца и 0 в противном случае.
y = 0.
s = (1,0,..., 0) для каждого конуса, 1 для каждой неотрицательной переменной.
τ = 1.
κ = 1.
Алгоритм пытается следовать по центральному пути, который является параметризованным решением для следующих уравнений для γ, уменьшающихся от 1 к 0.
| (4) |
Каждая переменная с индексом 0 указывает начальную точку переменной.
Переменные X и S представляют собой матрицы стрелок, сформированные из векторов x и s соответственно. Для вектора x = [x1, x2,..., xn] матрица стрелки X имеет определение
nx1I].
По своему определению X симметричен.
Переменная e является вектором с 1 в каждой конической координате, соответствующей координате конуса Лоренца x1.
Переменная (мк0) имеет определение
где k - число ненулевых элементов в x0.
Центральная траектория начинается в начальной точке и заканчивается оптимальным решением однородной задачи самоподключения.
Андерсен, Роос и Терлаки [1] показывают в Lemma 3.1, что условие комплементарности xTs = 0, где x и s находятся в произведении конусов Lorentz L, эквивалентно условию
= 0
Здесь Xi = мат (xi), xi - переменная, связанная с конусом Лоренца i, Si = мат (si), и ei - единичный вектор [1,0,0,..., 0] соответствующей размерности. Это обсуждение показывает, что центральный путь удовлетворяет условию комплементарности в его конечной точке.
Чтобы получить точки вблизи центрального пути, когда параметр γ уменьшается от 1 к 0, алгоритм использует метод Ньютона. Переменные, чтобы найти маркированы (x, τ, y, s, κ). Пусть dx представляет направление поиска для переменных x и так далее. Затем шаг Ньютона решает следующую линейную систему, полученную из уравнения 4.
X0ds) S0dx + X0S0e = − + γ pci0e
Алгоритм получает свою следующую точку, делая шаг в направлении d.
для некоторого шага ].
Как для числовой устойчивости, так и для ускоренной сходимости алгоритм масштабирует шаг по предложению Нестерова и Тодда [8]. Также алгоритм корректирует шаг согласно варианту предиктора-корректора Мехротры [7]. (Для получения дополнительной информации см. Андерсен, Роос и Терлаки [1].)
Предыдущее обсуждение относится к LinearSolver параметр со значением 'augmented' указано. Решатель имеет другие значения, которые изменяют расчет шага в соответствии с различными типами проблем.
'auto' (по умолчанию) - coneprog выбирает решатель шагов:
Если проблема разрежена, решателем шага является 'prodchol'.
В противном случае решателем шага является 'augmented'.
'normal' - Решатель использует вариант 'augmented' этап, который подходит, когда проблема разрежена. Смотрите Андерсен, Роос и Терлаки [1].
'schur' - Решатель использует модифицированный метод дополнения Шура для обработки разреженной проблемы с несколькими плотными столбцами. Этот способ также подходит для больших конусов. См. Андерсен [2].
'prodchol' - Решатель использует методы, описанные в Goldfarb и Scheinberg ([4] и [5]) для решения разреженной проблемы с несколькими плотными столбцами. Этот способ также подходит для больших конусов.
При каждой итерации k алгоритм вычисляет три относительных измерения сходимости:
Первичная несходимость
bstart0 ‖).
Двойная несходимость
fstart0 ‖).
Несходимость разрыва
fTx0 + bTy0 − λ 0 |).
Эти три статистические данные можно просмотреть в командной строке, указав итеративное отображение.
options = optimoptions('coneprog','Display','iter');
Все три должны приближаться к нулю, когда задача выполнима и решатель сходится. Для выполнимой задачи, переменная λ k приближается к нулю, а переменная (,) приближается к положительной константе.
Одно условие остановки в некоторой степени связано с несходимостью разрыва. Условие остановки - это когда следующая мера оптимальности уменьшается ниже допуска оптимальности.
bTyk/startk | 1 + | bTyk/startk |.
Эта статистика измеряет точность целевого значения.
Решатель также останавливается и объявляет проблему неосуществимой при следующих условиях. Три показателя относительной несходимости меньше, чем c = ConstraintTolerance, и
).
Если bTyk > 0, то решатель объявляет, что основная задача неосуществима. Если fTxk < 0, то решатель объявляет, что двойственная задача неосуществима.
Алгоритм также останавливается, когда
и
).
В этом случае 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] Андерсен, К. Д. Модифицированный метод шур-комплемента для обработки плотных столбцов в методах внутренних точек для линейного программирования. Транзакции 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] Мехротра, Санджай. «О применении метода первичных и двойственных внутренних точек». Журнал СИАМ по оптимизации 2, № 4 (ноябрь 1992 года): 575-601. https://doi.org/10.1137/0802028.
[8] Нестеров, Ю. Э. и М. Дж. Тодд. «Саморазмерные барьеры и методы внутренних точек для выпуклого программирования». Математика операций Исследование 22, № 1 (февраль 1997): 1-42. https://doi.org/10.1287/moor.22.1.1.