Obtaining the Lagrangian dual by relaxation

48 Views Asked by At

A soft question:

Given the optimization problem:

\begin{equation*} \begin{aligned} & \text{minimize} & & x_2\\ & \text{s.t.} & & 18x_1 + 11x_2 \geq 33\\ &&& 10x_1 -18x_2 \leq 9\\ &&& x_1,x_2 \in\{0,1,2,3\} \end{aligned} \end{equation*}

By relaxing the first constraint, we obtain the Lagrangian dual as follows:

\begin{equation*} \begin{aligned} & \text{minimize} & & x_2\\ & \text{s.t.} & & 18x_1 + 11x_2 \geq 33\\ &&& conv(10x_1 -18x_2 \leq 9, \hspace{2mm} x_1,x_2 \in\{0,1,2,3\}) \end{aligned} \end{equation*}

$\iff$

\begin{equation*} \begin{aligned} & \text{minimize} & & x_2\\ & \text{s.t.} & & 18x_1 + 11x_2 \geq 33\\ &&& x_1 - 2x_2 \leq 0\\ &&& x_1 -x_2 \leq 1 \\ &&& x_1\leq3\\ &&& x_2 \leq3 \end{aligned} \end{equation*}

So my question is, how did the author derive the Lagrangian dual above? I was told to use the equation $w_{LD}=max\{cx:Dx\leq d,x\in conv(X)\}$, but am unsure how the last LP was obtained.