# Obtaining the Lagrangian dual by relaxation

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.

• Just to clear up my doubt here, are you sure that you have the objective function of the dual written correctly? Since the primal has a minimization objective, the dual should have a maximization one. – learning Nov 1 '17 at 21:23
• @learning To me, it looks wrong as well, but its the answer provided not by me, so I posted this here to seek some clarification. – Stoner Nov 1 '17 at 21:36