Beyond local optimality conditions: the case of maximizing a convex function

In this paper, we design an algorithm for maximizing a convex function over a convex feasible set. The algorithm consists of two phases: in phase 1 a feasible solution is obtained that is used as an initial starting point in phase 2. In the latter, a biconvex problem equivalent to the original problem is solved by employing an alternating direction method. The main contribution of the paper is connected to the first phase. We identify a kind of global optimality condition which says that ``The maximizer of a convex objective function is the furthest point from the minimizer''. Using this principle, we develop several ways to compute this `furthest point', focusing on methods that lead to computationally efficient algorithms. The performance of the overall algorithm is tested on a wide variety of problems, demonstrating its efficiency.

Article

Download

View Beyond local optimality conditions: the case of maximizing a convex function