A new fast method to compute saddle-points in constrained optimization and applications

The solution of the augmented Lagrangian related system (A+rBTB)u=f is a key ingredient of many iterative algorithms for the solution of saddle-point problems in constrained optimization with quasi-Newton methods. However, such problems are ill-conditioned when the penalty parameter ε=1/r>0ε=1/r>0 tends to zero, whereas the error vanishes as O(ε)O(ε). We present a new fast method based on a splitting penalty scheme to solve such problems with a judicious prediction–correction method. We prove that, due to the adapted right-hand side  , the solution of the correction step only requires the approximation of operators independent of εε, when εε is taken sufficiently small. Hence, the proposed method is as cheaper as εε tends to zero. We apply the two-step scheme to efficiently solve the saddle-point problem with a penalty method. Indeed, that fully justifies the interest of the vector penalty-projection methods recently proposed by Angot et al. (2008) [19] to solve the unsteady incompressible Navier–Stokes equations, for which we give the stability result and some quasi-optimal error estimates. Moreover, the numerical experiments confirm both the theoretical analysis and the efficiency of the proposed method which produces a fast splitting solution to augmented Lagrangian or penalty problems, possibly used as a suitable preconditioner to the fully coupled system.