1
$\begingroup$

Consider an optimization problem $$ \begin{align} \max_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad & g_i(x) \le0,\,i=1,\ldots,m\\ \quad & h_j(x)=0,\,j=1,\ldots,l\\ \end{align} $$ The (complete) Lagrangian for the above problem is $$ \mathcal{L}(x,\mu,\lambda) = f(x) + \sum_{i=1}^m\mu_ig_i(x) + \sum_{j=1}^l\lambda_jh_j(x) $$ The set of KKT conditions are

1) Stationarity: $\nabla_x\mathcal{L}(x,\mu,\lambda)=0\equiv\nabla f(x) + \sum_{i=1}^m\mu_i\nabla g_i(x) + \sum_{j=1}^l\lambda_j\nabla h_j(x) = 0$

2) Complementary slackness: $\mu_ig_i(x) = 0$ for all $i$

3) Dual feasibility: $\mu_i\ge0$ for all $i$

4) Primal feasibility: $g_i(x)\le0$ and $h_j(x) = 0$ for all $i,j$

BUT we can also form a partial Lagrangian, say $$\mathcal{L}(x,\mu) = f(x) + \sum_{i=1}^m\mu_ig_i(x)$$ by just dualizing the inequality constraints. The partial Lagrangian would have a different set of KKT conditions, right?

Does this mean that we can have many different KKT conditions for the same optimization problem?

Is this the correct way of thinking about KKT conditions? Do they correspond to the optimization problem or the Lagrangian?

$\endgroup$
3
  • $\begingroup$ How is it the same optimization problem if you remove the equality constraints? $\endgroup$ Jun 27, 2015 at 8:43
  • $\begingroup$ @GautamShenoy I am not changing the optimization problem, I am just forming a partial Lagrangian (for an example, see slide 7 of web.stanford.edu/class/ee392o/decomposition_example.pdf) $\endgroup$
    – jonem
    Jun 27, 2015 at 8:52
  • $\begingroup$ KKT and dual problem are different stories. $\endgroup$
    – E.J.
    Jun 28, 2015 at 1:51

1 Answer 1

1
$\begingroup$

You cannot choose to not form the Lagrangian for a set of constraints and have the same KKT conditions. True you can form a partial Lagrangian, minimize it, and achieve the optimal solution. Or form the complete Lagrangian, minimize it, and achieve the (same) optimal solution. But what you state above is not correct.

The KKT conditions are for an optimization problem, not for a Lagrangian or any function. If you would like the same KKT conditions first you need to write the Lagrangian as an optimization problem - namely $\max \mathbb{L(x,\mu)}$ or $\max \mathbb{L(x,\mu, \lambda)}$. Then you would indeed have the same KKT conditions.

$\endgroup$

You must log in to answer this question.

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