Can successive approximation method get global optimum solutions?

#1

My objective function involves “log”,and cvx says that “Successive approximation method to be employed”.Although the problem can be solved,I wonder whether the answer is optimum.

(Denis Rosset) #2

To convince yourself, verify that your problem is convex using the DCP rules of CVX.

All the local optima of a convex problem are global optima. This does not mean that the solution is unique, but that all solutions lead to the same objective value.

(Mark L. Stone) #3

This approach has proven surprisingly effective for many problems. However, as with many heuristic approaches, it is not perfect. It will sometimes fail to converge even for problems known to have solutions

The bottom line, unfortunately, is that we cannot guarantee that the successive approximation approach will successfully handle your specific models. If you encounter problems, you are invited to submit a bug report, but we will not be able to promise a fix.

It is possible, and perhaps “usual”, that the successive approximation method converges to a (the) correct solution (global optimum). It is possible for it to not converge. Is it possible for it to (appear to) converge to a solution which is not a global optimum of the original problem?

(Denis Rosset) #4

Ooh yes, thanks for the precision.

What about the support in CVX3 for the SCS and ECOS solvers?

#5

You mean that if the method converges to get a solution,it’s probably global optimum?I also substitute the solution into the KKT conditions and it perfectly satisfies.So can I say I get global optimum solution here?

#6

??I don’t know about the solvers you mentioned.

(Mark L. Stone) #7

If the solution satisfies sufficient conditions for global optimum, then it’s a global optimum.

(Denis Rosset) #8

I’ve been able to solve problems involving both semidefinite and exponential cones through SCS. But I don’t know if CVX 3 can translate automatically the formulations (I’ve done some manual processing to make it work).