Dual optimization problem, decomposition.

Question

I have the following problem:
$\min x_1 ^ 2 + x_2 ^2$
s.t.
$x_1 + x_2 \ge 1$
$x_1 \ge 0$
$x_2 \ge 0$
I have three inequality constraints, so my lagrangian would be
$L = x_1 ^2 + x_2 ^2 + \lambda_1 (-x_1 - x_2 + 1) + \lambda _2 (-x_1) + \lambda _3 (-x_2)$ now if I wanted to find the dual form I would minimize $L$ over $x$ and obtain $L_{dual} ( \lambda )$. My lecturer, though, proposes a different approach to this problem, namely he chooses
$L = x_1 ^2 + x_2 ^2 + \lambda (-x_1 - x_2 + 1)$, seemingly ignoring the non-negativity constraints, then he cleverly finds the dual form as $L_{dual} = \underset{x_1 \ge 0}{min} \{x_1 ^2 - \lambda x_1 \} + \underset{x_2 \ge 0}{min} \{x_2 ^2- \lambda x_2 \} $. I don't understand where it comes from. If it has some simple derivation or reasoning behind it I would be interested in finding more about this method, as it seems very convenient in some cases. If this is very complex though, I would be grateful just for providing me with some intuition.

Answer 1

You can add the convex indicator function to the objective function, taking the value 0 if $x_1\geq 0$ and $\infty$ otherwise; and another indicator function for $x_2$. This replaces the constraints and results in the formulation of your lecturer: $$L = x_1^2 + x_2^2 + \delta(x_1|R_+) + \delta(x_2|R_+) + \lambda(-x_1-x_2+1)$$ $$\begin{align} &\min_x \{ x_1^2 + x_2^2 + \delta(x_1|R_+) + \delta(x_2|R_+) + \lambda(-x_1-x_2+1) \} \\ = \; & \lambda + \min_{x_1} \{ x_1^2 + \delta(x_1|R_+) - \lambda x_1 \} + \min_{x_2} \{ x_2^2 + \delta(x_2|R_+) - \lambda x_2 \} \\ = \; & \lambda + \min_{x_1 \geq 0} \{ x_1^2 - \lambda x_1 \} + \min_{x_2 \geq 0} \{ x_2^2 - \lambda x_2 \} \end{align}$$