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

Aharon Ben-Tal(abentaltechnion.ac.il)
Ernst Roos(e.j.roostilburguniversity.edu)

Abstract: 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.

Keywords: global optimization, convex maximization, alternating direction

Category 1: Global Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation:

Download: [PDF]

Entry Submitted: 02/25/2021
Entry Accepted: 02/25/2021
Entry Last Modified: 02/25/2021

Modify/Update this entry