A Sufficient Condition for Local Optima to be Globally Optimal

Abstract

Consider an optimization problem with a convex cost function but a non-convex compact feasible set X, and its relaxation with a compact and convex feasible set X̂ ⊃ X. We prove that if from any point x ∈ X̂∖X there is a path connecting x to X along which both the cost function and a Lyapunov-like function are improvable, then any local optimum in X for the original non-convex problem is a global optimum. We use this result to show that, for AC optimal power flow problems, a wellknown sufficient condition for exact relaxation also guarantees that all its local optima are globally optimal. This helps explain the widespread empirical experience that local algorithms for optimal power flow problems often work extremely well.

Additional details