|
I am solving a nonlinear problem using KKT conditions and I get a point as an optimal solution. I have two questions:
My feeling tells me that there might be another solutions that cannot be driven from KKT is that correct? and if yes how can I find them? |
|
David is correct - any optimal solution which is regular (i.e., satisfies a constraint qualification condition) must satisfy the necessary KKT conditions. There are certain classes of problems for which the KKT conditions are sufficient to guarantee optimality. An obvious example where this holds is an LP, and more generally these have to do with convexity. For more information on convex optimization a good reference is Convex Optimization by Boyd and Vandenberghe, which is freely available here. 1
What if the point is not regular? it can be optimum but not necessarily a KKT point (example optimizing any function on the constraints set that consist of two circles that only have one point in common, on the other hand the feasible set only contains one point)
(Apr 30 '10 at 04:20)
Mark ♦
Good catch Mark, my initial post wasn't worded very well concerning the regularity of the solution. I updated the post accordingly.
(Apr 30 '10 at 13:15)
AndyT
|
|
Just to add to the excellent answers... To check if your KKT point is a true optimum (not a saddle point or a maximizer), you can check the Second-Order Sufficient Optimality Conditions (SSOC). Generally this involves a projection of the Hessian of the Lagrangian to the null-space of the active-set constraint Jacobian, and checking to see if that quantity is positive definite. This is often not easy to do, so there are other indirect ways, such as checking the inertia of the KKT matrix, and ensuring that the inertia tells you that the matrix is positive definite. If you have a convex problem and the KKT point is unique, then your optimum is unique. If you have a nonconvex problem, there is no way to easily check if your KKT point is unique except by means of a deterministic global optimization algorithm (NP-hard), which typically uses a branch and bound method to search the space. I know, it's tough, but that's the way it is. |
|
I'm not an expert, but wikipedia has a summary that looks ok - there are academic reference listed so you can check it from there. Briefly:
Somebody familiar with this topic may be able to expand (or correct me if I've misunderstood). |
