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

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

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

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

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

linear-programming primal-dual кандидат наук
источник

В этом ответе по математике я расскажу пошаговый пример того, откуда возникает дуал - и почему - для проблемы, которая имеет большинство различных возможностей, которые могут возникнуть с LP. Возможно, это может помочь?

Майк Спиви

Не уверен, почему вы думаете, что аргумент Вазирани не работает для общего LP. Лично мне это объяснение нравится больше всего.

Суреш Венкат

Вы спрашиваете о слабой дуальности или сильной дуальности?

Цуеши Ито

Вы можете получить геометрическую интуицию, визуализируя (скажем, в 2d), что означает брать линейную комбинацию ограничений. Например, нарисуйте ограничения

на плоскости. Линейные комбинации этих ограничений дают вам

для любого

x \leq 1

$x \le 1$

y \leq 1

$y \le 1$

a x + b y \leq a + b

$ax + by \le a + b$

a, b \geq 0

$a,b \ge 0$ , Нарисуйте это, чтобы увидеть это. Как правило, линейная комбинация ограничений дает вам опорные полупространства многогранников. Теперь спросите, почему одного из этих вспомогательных полупространств всегда достаточно, чтобы ограничить стоимость? Если вы видите это, это сильная двойственность.

Нил Янг

@MikeSpivey - Я хотел бы, чтобы ваш комментарий был ответом :)

PhD

Ответы:

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

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

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

P r i m a l = {\begin{matrix} max 5 x_{1} - 6 x_{2} \\ s . t . 2 x_{1} - x_{2} = 1 \\ x_{1} + 3 x_{2} \leq 9 \\ x_{1} \geq 0 \end{matrix}}

$Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$

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

, второе ограничение на

и сложим их вместе, мы получим

для левой стороны и

для правой стороны. Поскольку первое ограничение является равенством, а второе - неравенством, это подразумевает

9

$9$

1

$1$

9 (2 x_{1} - x_{2}) + 1 (x_{1} + 3 x_{2})

$9(2x_1 - x_2) + 1(x_1 +3 x_2)$

9 (1) + 1 (9)

$9(1) + 1(9)$

Но так как

, также верно, что

, и поэтому

Поэтому ,

- верхняя граница оптимального значения основной задачи.

19 x_{1} - 6 x_{2} \leq 18.

$19x_1 - 6x_2 \leq 18.$

x_{1} \geq 0

$x_1 \geq 0$

5 x_{1} \leq 19 x_{1}

$5x_1 \leq 19x_1$

5 x_{1} - 6 x_{2} \leq 19 x_{1} - 6 x_{2} \leq 18.

$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$

18

$18$

Конечно, мы можем сделать лучше, чем это, хотя. Вместо того, чтобы просто угадывать и как множители, давайте позволим им быть переменными. Таким образом, мы ищем множители и чтобы заставить $9$ $1$ $y_1$ $y_2$

5 x_{1} - 6 x_{2} \leq y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9) .

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$

$y_1$ $y_2$

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

$x_1$ $x_2$ $x_1$ $5$ $5$ $x_1 \geq 0$ $5$ $x_1$ $2y_1 + y_2 \geq 5$

$x_2$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $x_2$ . $-y_1 + 3y_2 = -6$

Второе неравенство :

y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9)

$y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

$y_1$ $y_2$ $y_1$ $y_1$ $y_1$ $y_2$ $y_2$ $y_2 \geq 0$

$y_1 + 9y_2$

$y_1$ $y_2$

\begin{aligned} Minimize y_{1} + 9 y_{2} \\ subject to 2 y_{1} + y_{2} & \geq 5 \\ - y_{1} + 3 y_{2} & = - 6 \\ y_{2} & \geq 0. \end{aligned}

$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$

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

Вероятно, стоит обобщить значение этого аргумента для всех возможных форм первичного и двойственного. Следующая таблица взята из р. 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

Майк Спиви
источник

$x$ $x = B$ $x$ $x \leq C$ $C$ $B \leq \min C$ $B$ $B = \min C$ $B$ $B$

$f$ $f$ $S,O$ $f(S) \geq (1-1/e) f(O)$ $f$ $f$ $f(O) = 1$ $f(S)$ $\min f(S) = 1-1/e$ $1-1/e$ $f(S) \geq 1-1/e$

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

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

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