0
$\begingroup$

I'm reading up on convex optimization this summer and wanted to check my understanding of an example problem.

$$\begin{array}{ll} \text{minimize} & \| x \|_2\\ \text{subject to} & \displaystyle\sum_{i=1}^d x_i \geq 5\end{array}$$

  1. Is this a convex optimization problem?

I think that all norms are convex so $\|x\|$ is convex. I know the other condition is that $\sum_{i=1}^d x_i \geq 5$ needs to be convex, which I think is true. If I randomly think of 2 vectors that satisfy the constraint, any combination of them ($\theta$) and ($1-\theta$) results in another vector that still satisfies it. Not sure how I can mathetically prove this though.

  1. What is the Lagrange dual?

I can rewrite the constraint as $\left(-\sum_{i=1}^d x_i\right) + 5 \leq 0$. Then, the Lagrangian should be $ \|x\| + \lambda\left(\left(-\sum_{i=1}^d x_i\right) + 5\right)$, right? Which means the dual problem then should be something like $$\max_{\lambda \geq0} \min_{\vec{x}'} ||x|| + \lambda\left(\left(-\sum_{i=1}^d x_i\right) + 5\right)$$ is this the correct approach?

  1. Does strong duality hold?

So I know it holds if primal = dual. As far as I know, I can just switch the max and min from the above part to get the primal. As a result, the problems are the same regardless of the order of the max and min operators, correct? So is that why strong duality holds?

Thanks for helping me make sure I understand the fundamentals.

$\endgroup$
  • 1
    $\begingroup$ 1. maybe you can prove that $f(x) = 5-\sum x_i$ is convex. 2. That is the correct approach, but you still need to solve the $\min_x$. 3. Can you relate your answer to Slater's condition. $\endgroup$ – LinAlg Jun 29 '18 at 11:52
  • $\begingroup$ @RodrigodeAzevedo why square the norm if this already is a convex SOCP? $\endgroup$ – Michal Adamaszek Jun 29 '18 at 12:42
  • $\begingroup$ @RodrigodeAzevedo if you solve it as a SOCO problem you also have a clean derivative. $\endgroup$ – LinAlg Jun 29 '18 at 13:44
  • $\begingroup$ @RodrigodeAzevedo convex quadratic optimization is a subset of conic quadratic optimization :) $\endgroup$ – LinAlg Jun 29 '18 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.