7

Let's say I have an objective function

$$f(x_1,x_2, \cdots, x_n)$$

and $N$ constraints $$x_i \ge 0. $$

I am trying to solve it with KKT conditions. Now the objective function becomes

$$f(x_1,x_2, \cdots, x_n)+ \mu_i(g_i(x)).$$

I want to solve it using a C program so I solved the equation manually for both cases where I take $\mu_i =0$ and the other case when $x_i < 0$ then $x_i = 0$.

So let's say I run the algorithm and take all $\mu_i = 0$ initially and get $x_1 < 0$ (the rest all are positive), so I run the algorithm again with $x_1 = 0$. Now assume that I get $x_2 < 0$ (the rest all are positive). Now I updated with $x_2 = 0$ so here I want to know whether I should take $x_1 =0$ also or whether I need to perform all possible combinations with $x_i =0$ and $\mu_i = 0$ to get the final answer.

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
ooo
  • 1,589
  • 4
  • 12
  • If $x_i = 0$, then $\mu_i \geq 0$ (if strict complementary slackness holds, then $\mu_i > 0$). If $x_i < 0$, then $\mu_i = 0$. Could you please clarify your problem statement to that effect? – Richard Jun 25 '19 at 07:08

1 Answers1

10

If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since the KKT's are the first-order necessary conditions for optimality.

For convex nonlinear optimization, you are better off using sequential quadratic programming or similar (see here for a nice overview over some methods), and then validate using the duality gap and KKT conditions.

Richard
  • 3,459
  • 7
  • 19
  • 2
    Basically, Sequential Quadratic Programming (SQP) is a way of numerically solving the KKT conditions while "rolling downhill". Declare first order optimum when KKT conditions are solved to within a specified tolerance. – Mark L. Stone Jun 25 '19 at 07:56
  • Isn’t SQP a first order tailor expansion on the constraints and then using the Lagrangian as the objective function with the step size and direction as the variable with a fixed $x^*$? – Richard Jun 25 '19 at 07:58
  • And that amounts to numerically solving the KKT conditions. And rolling downhill due to minimizing, with trust region or linesearch at each SQP outer iteration. – Mark L. Stone Jun 25 '19 at 08:43
  • Ahh, ok, now I understand what you mean by “numerically solving the KKT conditions”. Interesting, I never thought of it like that. Always just looked at it as a smart way of doing Taylor expansion and then convexity guarantees optimality. Nifty! – Richard Jun 25 '19 at 08:55
  • Convexity is not required for SQP, although it could be in certain implementations. – Mark L. Stone Jun 25 '19 at 08:57
  • But to get epsilon guarantee I guess you need it. Otherwise you’ll only get a local minimum I guess – Richard Jun 25 '19 at 08:57
  • Could you please drop some tutorial links for that? – ooo Jun 25 '19 at 08:58
  • 2
    @anoop yadav Take a look at https://wiki.mcs.anl.gov/leyffer/images/1/1d/12-SQP.pdf . And yes, in general, SQP is a local optimizer, although it can be used to solve subproblems in a branch and bound global optimizer. – Mark L. Stone Jun 25 '19 at 09:03