Duality Results and Dual Bundle Methods Based on the Dual Method of Centers for Minimax Fractional Programs
Karima Boufi, Ahmed Roubi · SIAM Journal on Optimization · 2019
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. However, 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 rate of convergence of these algorithms. As is the case for dual algorithms, the proposed methods generate a sequence of values that converges from below to the minimal value of the GFP, and a sequence of approximate solutions that converges to a solution of the dual problem. For certain classes of problems, the convergence is at least linear.