7
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Richard
    Jun 25, 2019 at 7:08

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Jun 25, 2019 at 7:56
  • $\begingroup$ 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^*$? $\endgroup$
    – Richard
    Jun 25, 2019 at 7:58
  • $\begingroup$ 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. $\endgroup$
    – Mark L. Stone
    Jun 25, 2019 at 8:43
  • $\begingroup$ 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! $\endgroup$
    – Richard
    Jun 25, 2019 at 8:55
  • 2
    $\begingroup$ @anoop yadav Take a look at 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. $\endgroup$
    – Mark L. Stone
    Jun 25, 2019 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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