A predictor-corrector algorithm for a class of nonlinear saddle point problems

Abstract

An interior path-following algorithm is proposed for solving the nonlinear saddle point problem minimax cT x + φ(x) + bT y - ψ(y) -yT Ax subject to (x, y) ∈ X x Y ⊂ Rn x Rm, where φ(x) and ψ(y) are smooth convex functions and X and Y are boxes (hyperrectangles). This problem is closely related to the models in stochastic programming and optimal control studied by Rockafellar and Wets (Math. Programming Studies, 28 (1986), pp. 63-93; SIAM J. Control Optim., 28 (1990), pp. 810-822). Existence and error-bound results on a central path are derived. Starting from an initial solution near the central path with duality gap O(μ), the algorithm finds an ∈-optimal solution of the problem in O(√m + n| log μ/∈|) iterations if both φ(x) and ψ(y) satisfy a scaled Lipschitz condition.