Extending Linear Conditioning to Convex-Concave Optimization: Finite Convergence of the Proximal Point Algorithm
摘要
This paper delves into the finite termination of the proximal point algorithm (PPA) within the realm of convex-concave optimization, extending the well-established concept of linear conditioning from convex to convex-concave functions. The study builds on both the foundational work of Auslender and Crouzeix who introduced the concept of well-behaved asymptotically convex functions, and Polyak’s examination of linearly conditioned convex functions also known as functions with a sharp minimum. We give several equivalent definitions of the linear conditioning property and we use them to prove the finite convergence of the proximal point algorithm.