Интуитивное / неформальное доказательство LP Duality?

19

Что было бы хорошим неофициальным / интуитивно понятным доказательством того, что «удар по теме» о дуальности ЛП? Как лучше всего показать, что минимизированная целевая функция действительно является минимальной с интуитивным способом понимания границ?

То, как меня учили, дуальность привела только к одному пониманию, которое, я уверен, разделяют МНОГИЕ люди, которых я знаю: для каждой соответствующей проблемы минимизации есть эквивалентная проблема максимизации, которая может быть получена путем обращения ограничений неравенства. Период. Это «заключение» дуальности - это то, что, кажется, придерживается, но не «почему это так» (т.е. как / почему существует ограничение на оптимальное решение).

Есть ли способ поиграть с неравенствами просто для того, чтобы «показать» нижнюю / верхнюю границу оптимума, что может послужить мотивацией для доказательства?

Я просмотрел книгу Чватала и несколько других, но не нашел ничего, что можно было бы понять абсолютным новичкам в LP. Самое близкое, что я получил, было из книги Вазирани об алгоритмах, где он говорит о «умножении неравенств на некоторые магические числа, которые показывают границу» - я не уверен, как воспроизвести эффект для произвольного LP.

кандидат наук
источник
5
В этом ответе по математике я расскажу пошаговый пример того, откуда возникает дуал - и почему - для проблемы, которая имеет большинство различных возможностей, которые могут возникнуть с LP. Возможно, это может помочь?
Майк Спиви
2
Не уверен, почему вы думаете, что аргумент Вазирани не работает для общего LP. Лично мне это объяснение нравится больше всего.
Суреш Венкат
1
Вы спрашиваете о слабой дуальности или сильной дуальности?
Цуеши Ито
7
Вы можете получить геометрическую интуицию, визуализируя (скажем, в 2d), что означает брать линейную комбинацию ограничений. Например, нарисуйте ограничения и y 1 на плоскости. Линейные комбинации этих ограничений дают вам a x + b y a + b для любого a , b 0x1y1ax+bya+ba,b0, Нарисуйте это, чтобы увидеть это. Как правило, линейная комбинация ограничений дает вам опорные полупространства многогранников. Теперь спросите, почему одного из этих вспомогательных полупространств всегда достаточно, чтобы ограничить стоимость? Если вы видите это, это сильная двойственность.
Нил Янг
@MikeSpivey - Я хотел бы, чтобы ваш комментарий был ответом :)
PhD

Ответы:

19

В соответствии с пожеланием OP, вот ответ math.SE, на который я ссылаюсь в своем комментарии выше.


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

Предположим, у нас есть основная задача следующим образом.

Primal={max    5x16x2   s.t.    2x1x2=1              x1+3x29    x10}

Теперь предположим, что мы хотим использовать ограничения простого числа как способ найти верхнюю границу для оптимального значения простого числа. Если мы умножим первое ограничение на , второе ограничение на 1 и сложим их вместе, мы получим 9 ( 2 x 1 - x 2 ) + 1 ( x 1 + 3 x 2 ) для левой стороны и 9 ( 1 ) + 1 ( 9 ) для правой стороны. Поскольку первое ограничение является равенством, а второе - неравенством, это подразумевает919(2x1x2)+1(x1+3x2)9(1)+1(9) Но так как x 10 , также верно, что 5 x 119 x 1 , и поэтому 5 x 1 - 6 x 219 x 1 - 6 x 218. Поэтому , 18 - верхняя граница оптимального значения основной задачи.
19x16x218.
x105x119x1
5x16x219x16x218.
18

Конечно, мы можем сделать лучше, чем это, хотя. Вместо того, чтобы просто угадывать и 1 как множители, давайте позволим им быть переменными. Таким образом, мы ищем множители y 1 и y 2, чтобы заставить 5 x 1 - 6 x 2y 1 ( 2 x 1 - x 2 ) + y 2 ( x 1 + 3 x 2 ) y 1 ( 1 ) + у 291y1y2

5x16x2y1(2x1x2)+y2(x1+3x2)y1(1)+y2(9).

y1y2


5x16x2y1(2x1x2)+y2(x1+3x2)

x1x2x155x105x12y1+y25

x2x26x26x26x2x2 .y1+3y2=6


Второе неравенство : y1(2x1x2)+y2(x1+3x2)y1(1)+y2(9)

y1y2y1y1y1y2y2y20

y1+9y2


y1y2

Minimize y1+9y2subject to 2y1+y25y1+3y2=6y20.

И это двойственное.


Вероятно, стоит обобщить значение этого аргумента для всех возможных форм первичного и двойственного. Следующая таблица взята из р. 214 Введение в исследование операций , 8-е издание, Хиллиер и Либерман. Они называют это методом SOB, где SOB обозначает «Разумный», «Нечетный» или «Причудливый», в зависимости от того, насколько вероятно найти это конкретное ограничение или ограничение переменной в задаче максимизации или минимизации.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint
Майк Спиви
источник
7

xx=BxxCCBminCBB=minCBB

ffS,Of(S)(11/e)f(O)fff(O)=1f(S)minf(S)=11/e11/ef(S)11/e

Это оставляет открытым вопрос о том, почему сильная двойственность действительно имеет место. Существует два доказательства этого факта для линейного программирования: одно включает симплексный алгоритм, другое - лемму Фаркаша. Лемма Фаркаса, вероятно, является «правильным» способом понимания ситуации, сводя все к некоторому интуитивному геометрическому факту. Тем не менее, я признаюсь, что эта интуиция проходит через мою голову.

В более общих ситуациях (скажем, полуопределенное программирование) вам нужно использовать более общие условия Каруша-Куна-Такера (форма множителей Лагранжа), чтобы получить двойственное и условия сильной двойственности. Это рассматривается в текстах по нелинейной или выпуклой оптимизации.

Юваль Фильмус
источник