A Moving Balls Approximation Method for Smooth Constrained Minimization

Marc Teboulle
Tel Aviv University
Mathematical Sciences

We introduce a new algorithm for smooth constrained minimization. It relies on a simple
geometric idea and generates a sequence of feasible interior points that
approximates the constraints set by a sequence of adequate balls, and is accordingly called
the Moving Ball Approximation algorithm (MBA). The scheme uses first order data information,
and enjoys computational simplicity. Theoretical and computational properties of MBA in its
primal and dual forms are presented, and convergence and global rate of convergence results
are established for nonconvex and convex problems. Extension of MBA is also developed
to solve variational inequalities. . Some initial numerical experiments illustrate the viability
and performance of the algorithm when compared to some existing state-of-the-art optimization
methods/software. This is joint work with A. Auslender (Lyon) and R. Shefi (Tel Aviv).

Presentation (PDF File)

Back to Workshop II: Numerical Methods for Continuous Optimization