Lagrangian Dual with Absolute Value constraint

568 Views Asked by At

Given the optimization problem below where $Q \in R^{n \times n}$: $$ \min \ x^TQx + c^Tx \\ \mathbb{-1} \leq x \leq \mathbb{1}$$

The problem in standard form is: $$\min \ f(x) \\ st \ Ax \leq b$$

where

$$A = \pmatrix{I_n \\ -I_n} \in R^{2n \times n}, \ b= \mathbb{1} \in R^{2n} \text{ and } f(x)=x^TQx + c^Tx$$

I need to show that the Lagragian dual problem is: $$\underset{\lambda}{\max} \ -\frac{1}{2}(\lambda-c)^TQ^{-1}(\lambda-c) - \lVert \lambda \lVert _1$$


My attempt at the solution.

The dual function is: $$g(x,\lambda)= \underset{x}{\min} x^TQx + c^Tx + \lambda^T(b-Ax) \\ \Rightarrow \ 2Qx + c = A^T\lambda$$ This gives $x^*=\frac{1}{2}Q^{-1}(A^T\lambda-c)$

Plugging into the dual function: $$g(x^*,\lambda) = [\frac{1}{2}Q^{-1}(A^T\lambda-c)^T]Q[\frac{1}{2}Q^{-1}(A^T\lambda-c)]+(\lambda^TA - c^T)*(\frac{1}{2}(A^T\lambda-c)Q^{-1} + \lambda^Tb \\ =-1/4(A^T\lambda-c)^TQ^{-1}(A^T\lambda-c) + \lambda^Tb$$

From this I get an incorrect Lagrangian dual problem:

$$\underset{x}{\min} f(x) \ st \ Ax \leq b = \underset{\lambda}{\max} -1/4(A^T\lambda-c)^TQ^{-1}(A^T\lambda-c) + \lambda^Tb$$

I'm not quite sure how to go from here since the $A^T\lambda$ does not simplify to $\lambda$ nor does the $\lambda^Tb$ simplify to the L1 norm. Was my approach completely wrong?