I was recently wondering for which common nonconvex problems we have algorithms that are guaranteed to find optimal solutions. The only one I could think of is the singular value decomposition. Are there other nonconvex problems we can solve optimally?
Asked
Active
Viewed 30 times
1
-
Invex problems are a type of problems where the stationarity implies optimality. This type of problems can be solved by algorithms as convex problems are. Other than that, I am not aware of an algorithm that can solve anything more general than that. Fortunatelly, KKT points found by algorithms are almost always local minimizers, since It usually tends to find a monotone sequences of function values – R. W. Prado Dec 09 '21 at 11:23
-
But there are several optimality contitions that be used to measure performance. Sequencial optimality contitions, KKT or not constraint qualifications, Bouligand stationarity. And there are performance measures as well. The stronger the conditon is, less non-minimizers are being persued by the algoritm. – R. W. Prado Dec 09 '21 at 11:35