Since the strict complementarity condition (between the Lagrange multipliers and the inequality constraints) is not guaranteed for the optimal solution of a quadratic programming problem, I wonder if how I can have the closest solution to the optimal one which holds the strict complementarity condition.
The problem with the use of interior-point methods for complementarity problems is that there isn't an interior solution at the optimal. You can relax the complementarity conditions using i.e. the smoothed Fisher-Burmeister equation. It also enables you to compute good valid bounds by means of convex relaxation, if necessary conditions hold. That way, you can validate the solution of the local minimizer, i.e. IPOPT.
Thanks Leonardo. Actually, my problem is a normal QP; however, I need to find the best solution (which is the closest possible one to the optimal solution) which holds the strict complementarity condition btw the Lagrange multipliers and inequality constraints. It means that, unlike the KKT conditions, the multipliers and the constraints cannot be simultaneously zero. Although it can be done by searching around the optimal point to find such a point, I am looking for any better method.
More comments would be appreciated.
That problem you are describing is not well-posed - in fact it has no optimal solution: if the optimal solution is at a boundary and you require a near-by strictly feasible solution, then there exist no "closest" point. Compare this with minimizing 1/x over, say, x >= 1: there is a minimal value (0) but no optimal solution - you can get as close as you like though. You simply have to pose the problem in a different way.
Thank you very much Michael. What about min x^2; s.t. x>= 0? Its minimum value is 0 at x = 0 and the corresponding multiplier is also 0. I think this problem is well-defined; however, the optimal solution does not hold the SCC. In this case, by my understanding, if I slightly increase x, I will have a close solution to the optimal one which also holds the SCC.
More comments would be appreciated.
As you can see from your own example, there exists no "nearest" or "closest" solution. That would be equivalent to asking what the projection is on an open set - there is an optimal least value (0) but no solution, since however close you produce a point I can find one even closer by taking the mean value of the "open" boundary and the point you give me.
It's a problem without a solution. IF I have understood you right. :-) Otherwise, I'm wrong! :-)
Yes, I think you are right.
Therefore, you mean that the problem of finding the "closest" point is ill-defined, as it is, and it couldn't have a solution and in order to find a close point to the optimal solution which holds the SCC I need to move towards, let's say, the Chebyshev centre step-by-step and check the SCC criteria.
Would you please let me know if you agree with that?
Many thanks.
I think you need to define a criteria for as clpse as possible before the problem becomes a well possed. This criteria may be from your problem or a constraint on the solution
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Control Theory
- Control Systems