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$
  • $\begingroup$ How is it the same optimization problem if you remove the equality constraints? $\endgroup$ – Gautam Shenoy Jun 27 '15 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 '15 at 8:52
  • $\begingroup$ KKT and dual problem are different stories. $\endgroup$ – E.J. Jun 28 '15 at 1:51
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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.