Разрыв дуальности - Duality gap

В проблемы оптимизации в Прикладная математика, то разрыв дуальности разница между первичные и двойные решения. Если ${ displaystyle d ^ {*}}$ оптимальное двойное значение и ${ displaystyle p ^ {*}}$ оптимальное прямое значение, то разрыв двойственности равен ${ displaystyle p ^ {*} - d ^ {*}}$. Это значение всегда больше или равно 0 (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда сильная двойственность держит. В противном случае разрыв строго положительный и слабая двойственность держит.^[1]

В общем даны два двойные пары отделенный локально выпуклые пространства ${ Displaystyle влево (Х, Х ^ {*} вправо)}$ и ${ Displaystyle влево (Y, Y ^ {*} вправо)}$. Тогда с учетом функции ${ displaystyle f: X to mathbb {R} cup {+ infty }}$, мы можем определить основную задачу как

${ Displaystyle Inf _ {х в X} е (х). ,}$

Если есть условия ограничения, их можно встроить в функцию ${ displaystyle f}$ позволяя ${ displaystyle f = f + I _ { text {constraints}}}$ куда ${ displaystyle I}$ это индикаторная функция. Тогда пусть ${ displaystyle F: X times Y to mathbb {R} cup {+ infty }}$ быть функция возмущения такой, что ${ Displaystyle F (х, 0) = е (х)}$. В разрыв дуальности разница дается

${ displaystyle inf _ {x in X} [F (x, 0)] - sup _ {y ^ {*} in Y ^ {*}} [- F ^ {*} (0, y ^ {*})]}$

куда ${ displaystyle F ^ {*}}$ это выпуклый сопряженный в обеих переменных.^[2][3][4]

В вычислительной оптимизация часто сообщается о другом «пробеле двойственности», который представляет собой разницу в значении между любым двойственным решением и значением возможной, но неоптимальной итерации для основной задачи. Этот альтернативный «разрыв двойственности» количественно определяет несоответствие между значением текущей допустимой, но субоптимальной итерации для основной задачи и значением двойственной задачи; значение двойственной задачи в условиях регулярности равно значению выпуклая релаксация прямой задачи: выпуклая релаксация - это проблема, возникающая при замене невыпуклого допустимого множества его замкнутым выпуклый корпус и заменой невыпуклой функции ее выпуклой закрытие, то есть функция, имеющая эпиграф это замкнутая выпуклая оболочка исходной прямой целевой функции.^{[5][6][7][8][9][10][11][12][13]}

Рекомендации