A Second Order Primal-Dual Method for Nonsmooth Convex Composite Optimization

• Published in: IEEE transactions on automatic control 2022-08, Vol.67 (8), p.4061-4076
• Main Authors: Dhingra, Neil K., Khong, Sei Zhen, Jovanovic, Mihailo R.
• Format: Article
• Language: English
• Subjects: Algorithms; Control design; control system synthesis; Control systems design; Convergence; design optimization; distributed algorithms; gradient methods; Jacobian matrices; Linear programming; Newton method; Operators (mathematics); Optimization; optimization methods; Predictive control; Saddle points; Search problems
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/TAC.2021.3115449

We develop a second order primal-dual method for optimization problems in which the objective function is given by the sum of a strongly convex twice differentiable term and a possibly nondifferentiable convex regularizer. After introducing an auxiliary variable, we utilize the proximal operator of the nonsmooth regularizer to transform the associated augmented Lagrangian into a function that is once, but not twice, continuously differentiable. The saddle point of this function corresponds to the solution of the original optimization problem. We employ a generalization of the Hessian to define second-order updates on this function and prove global exponential stability of the corresponding differential inclusion. Furthermore, we develop a globally convergent customized algorithm that utilizes the primal-dual augmented Lagrangian as a merit function. We show that the search direction can be computed efficiently and prove quadratic/superlinear asymptotic convergence. We use the \ell _1-regularized model predictive control problem and the problem of designing a distributed controller for a spatially invariant system to demonstrate the merits and the effectiveness of our method.