Consider the following constrained optimization problem.

$$\begin{array}{ll} \text{minimize} & f(w)\\ \text{subject to} & g_{i}(w) \leq 0\\ & h_{j}(w) = 0\end{array}$$

The equivalent Lagrangian formulation is:

$$\min_w \max_{\alpha_{i} \geq 0, \,\beta_{j}} \ f(w) \ + \ \sum_{i} \alpha_{i}g_{i}(w) \ + \ \sum_{j} \beta_{j}h_{j}(w), \qquad \alpha_{i} \geq 0$$

I have a few questions on this:

  1. In the Lagrangian we still have constraint on $\alpha$'s which have to be satisfied. How is this a conversion to unconstrained optimization then?

  2. If there were only inequality constraints then the number of constraints also don't change in the new formulation, how is this a simplification then?

  • 3
    $\begingroup$ Without inequality constraint you get optimization problem with more variables (old variables + constraints) but no constraints. Inequality constraint makes it more tricky, but still you have a simpler constraint. $\endgroup$ – Roger Vadim Dec 20 '19 at 13:40
  • $\begingroup$ Instead of computing the whole thing $g_{i}(w)$, you already have $\alpha_{i}$, is that what you mean by simple constraint? $\endgroup$ – Silpara Dec 27 '19 at 18:18
  • $\begingroup$ Yes, instead of solving inequality $g_i(w) \leq 0$ with potentially non-linear function $g_i(w)$ you have simply $\alpha \leq 0$. Take, for example, $g_i(w) = w^5 + 5w^4 - w^2 +7$. $\endgroup$ – Roger Vadim Dec 27 '19 at 18:24

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.