Approximate Dual Bundle Methods for Minimax Fractional Programs

What is it about?

We propose new duality results for generalized fractional programs (GFP) for a wide class of problems, not limited only to the convex case. Our approach does not use Lagrangian duality, but only an equivalent form of the GFP. We present a general approximating scheme, based on the proximal point algorithm, for solving this dual program. We take advantage of the convexity property of the dual, independently of the primal properties, to build implementable bundle methods with the support of the general scheme.

Featured Image

Why is it important?

It is well known that the principal difficulty with the duality is the evaluation of the dual function. To mitigate this difficulty, we propose bundle methods that need only approximate values and approximate subgradients of the objective dual function. We prove the convergence and the linear rate of convergence of these algorithms.