1

In an introductory lecture to SVM (Support vector machine), we are given a review of The inequality constrainted optimization. Which is summarized in a single lecture slide. The slide reads as the following:

The problem

$$ \min\limits_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x}) \quad \text{ subject to } \quad h(\mathbf{x}) \geq c\,. $$

Conceptually the problem is solved as the following:

  1. Write the Lagrangian $$L(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda(h(\mathbf{x}) - c)\,.$$

  2. Introduce the dual function $$ d(\lambda) = \inf\limits_{\mathbf{x}} L(\mathbf{x}, \lambda)\,. $$

  3. Solve the dual problem $$ \lambda^* = \text{arg}\max\limits_{\lambda} d(\lambda)\quad \text{ subject to } \lambda \geq 0\,. $$

  4. The optimal $\mathbf{x}$ (assuming strong dality) is $$\mathbf{x} = \text{arg}\inf\limits_{\mathbf{x}} L(\mathbf{x}, \lambda^*)\,.$$

When $f$ is convex function and $h(\mathbf{x}) \geq 0$ defines convex region of space, this gives the global optimum.

Question

What I am looking for is not necessarily rigorous explanation but rather intuitive interpretation of why each of the steps indeed goes in the "right direction" so that the above interpretation indeed leads to the optimal minimum under the constraints.

In contrast: for equality constrained optimization I do understand the intuition behind the Lagrangian. To outline, the derivatives of the Lagrangian introduce the requirement that at the solution the gradients of the constraint and the objective be parallel.

EDITED This already contain the answer I was looking for, see answer there by @Dan Piponi.

Community
  • 1
them
  • 668
  • 4
  • 15
  • Not quite related to your question, but I need to have a quick review of equality constrained optimization, do you also have a lecture slide for that? =P – Gigili Sep 01 '16 at 09:07
  • @Gigili. On the equality constrained optimization the slide does not say that much on the intuition - take the derivative and solve for the $\lambda$ and $\mathbf{x}$. In more details: $\frac{\partial L(\mathbf{x}, \lambda)}{\partial x_i} = 0\, i=1,2, \ldots, n$ will give you a curve $\mathbf{x} = \gamma(\lambda)$. Reintroduce the constraint $h(\gamma(\mathbf{x})) = c$ , solve for $\lambda^*$ and get the optimal $\mathbf{x} = \gamma(\lambda^*)$. Also you might want to look at [this](http://stats.stackexchange.com/questions/169194/lagrangian-multiplier-role-of-the-constraint-sign) – them Sep 01 '16 at 09:16
  • Yeah, I need the details of those mathematical steps. Thanks anyway. – Gigili Sep 01 '16 at 09:23

0 Answers0