0
$\begingroup$

I'm working through an SVM tutorial (from Andrew Ng Stanford course notes). In the brief coverage of Lagrange duality. The primal optimization problem is stated $$ \min_{w} \theta_{\mathcal{P}}(w) = \min_{w} \max_{\alpha, \beta \::\: \alpha_{i} \ge 0} \mathcal{L}(w,\alpha,\beta) $$

The dual optimization problem is stated

$$ \max_{\alpha, \beta \::\: \alpha_{i} \ge 0} \theta_{\mathcal{D}}(\alpha,\beta) = \max_{\alpha, \beta \::\: \alpha_{i} \ge 0} \min_{w} \mathcal{L}(w,\alpha,\beta) $$

Under the appropriate conditions (convex objective, convex inequalities, affine equalities), it's noted that $w^{*}, \alpha^{*}, \beta^{*}$ can be found such that $w^{*}$ is the primal solution and $\alpha^{*}, \beta^{*}$ are the solution to the dual problem and that they satisfy the KKT conditions. One KKT condition in particular is that

$$ \alpha_{i}^{*} \ge 0. $$

Why is this condition notable considering that a constraint was $\alpha_{i} \ge 0$?

$\endgroup$
6
  • $\begingroup$ $\alpha_i$ are the dual variables corresponding to the INEQUALITY constraints, thus non-negative. You might want to learn more about Duality Theory (stanford.edu/~boyd/cvxbook, Chapter 5). $\endgroup$
    – f10w
    May 26, 2015 at 0:22
  • $\begingroup$ Thanks @Khue - I could definitely stand to learn more for sure! However, I believe you may have missed the intent of my question. I understand why $\alpha_{i} \ge 0$ is required by the inequality constraints, I just don't understand why it would be worth nothing in the KKT conditions that $\alpha_{i}^{*} \ge 0$ since that was already a posed constraint. It feels like saying "the solution is a solution." $\endgroup$ May 26, 2015 at 0:26
  • 1
    $\begingroup$ The constraints are part of the KKT conditions, by definition. The idea of KKT conditions (for convex problems) is that: if you solve this system of equations/inequations, independently of the original optimization problem (i.e. forget everything about the original optimization problem: objective function, constraints, etc...), then the obtained solutions are the solutions to the primal and dual of the original optimization problem. $\endgroup$
    – f10w
    May 26, 2015 at 0:40
  • 1
    $\begingroup$ (Thus the constraints of the original problem should be added to the KKT conditions because we want to find solutions that satisfy these constraints.) $\endgroup$
    – f10w
    May 26, 2015 at 0:43
  • $\begingroup$ @Khue That actually makes perfect sense. I appreciate it! Now, if you made your comment an answer, I could accept it. :-) $\endgroup$ May 26, 2015 at 0:55

1 Answer 1

3
$\begingroup$

The constraints are part of the KKT conditions, by definition.

The idea of KKT conditions (for convex problems) is that: if you solve this system of equations/inequations, independently of the original optimization problem (i.e. forget everything about the original optimization problem: objective function, constraints, etc...), then the obtained solutions are the solutions to the primal and dual of the original optimization problem.

Thus the constraints of the original problem should be added to the KKT conditions because we want to find solutions that satisfy these constraints.

$\endgroup$
1
  • $\begingroup$ Yep, it's really that simple! ;-) Well written. $\endgroup$ May 26, 2015 at 1:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .