SIAM Journal on Control and Optimization, Vol.35, No.2, 532-551, 1997
A Predictor-Corrector Algorithm for a Class of Nonlinear Saddle-Point Problems
An interior path-following algorithm is proposed for solving the nonlinear saddle point problem minimax c(T) x + phi(x) + b(T)y - psi(y) - y(T) Ax subject to (x,y) is an element of chi gamma subset of R(n) x R(m), where phi(s) and psi(y) are smooth convex functions and chi and gamma 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(mu), the algorithm finds an epsilon-optimal solution of the problem in O(root m+nlog mu/epsilon) iterations if both phi(x) and psi(y) satisfy a scaled Lipschitz condition.
Keywords:LINEAR-QUADRATIC PROBLEMS;COMPLEMENTARITY-PROBLEMS;DISCRETE-TIME;CONVERGENCE;COMPLEXITY;PROGRAMS;PATH