Adjoint-Based Predictor-Corrector Sequential Convex Programming for Parametric Nonlinear Optimization

Quoc Tran-Dinh, Dinh Quoc Tran, Carlo Savorgnan, Moritz DiehlSIAM J. Optim 2012 · DOI

TL;DR

This paper introduces a novel algorithmic framework, APCSCP, for efficiently solving parametric nonlinear optimization problems. It leverages adjoint methods and a predictor-corrector approach to significantly speed up computations, particularly in real-time applications like nonlinear model predictive control, by performing only one iteration of a convex subproblem per parameter update.

What Problem Does This Paper Address?

Many real-world applications, such as nonlinear model predictive control (NMPC), require solving a sequence of optimization problems where a parameter changes over time. Traditionally, each problem is solved to full convergence, which can be computationally prohibitive for real-time systems. This paper addresses the challenge of efficiently obtaining approximate solutions for these sequential problems, especially when the parameter changes slowly. The goal is to reduce the computational burden by avoiding full convergence at each step, while still maintaining accuracy and stability. This is particularly relevant for problems with complex structures (e.g., conic constraints) where standard optimization methods might struggle.

Methods

The core contribution is the Adjoint-Based Predictor-Corrector Sequential Convex Programming (APCSCP) algorithm. It combines three key ideas:

  • Sequential Convex Programming (SCP): This technique tackles nonconvex problems by iteratively solving a sequence of convex approximations. It focuses on convexifying only the non-convex parts of the problem while preserving structures amenable to efficient convex optimization.
  • Predictor-Corrector Path-Following: Inspired by methods for solving systems of equations, this approach uses a "predictor" step to estimate the solution for the next parameter value and a "corrector" step to refine this estimate. In this context, it means taking one step of a Newton-like method to get an initial guess for the next parameter.
  • Adjoint-Based Optimization: This method aims to reduce the computational cost of calculating derivatives. Instead of computing full Jacobian matrices, it uses adjoint derivatives, which can be significantly cheaper to evaluate, especially for large-scale problems. This is crucial for real-time applications where derivative computations can dominate the overall time.

The algorithm iteratively solves a convex subproblem for the next parameter value, using the previous solution as a starting point. The adjoint method is used to efficiently compute necessary terms for the update. Two variants are presented: one for general nonlinear programming and another specifically for online parametric problems.

Datasets

The paper uses a benchmark problem from the control of a hydro power plant for numerical evaluation. This problem involves a complex dynamic system with 259 states and 10 controls, discretized using the method of lines. The problem is formulated as a nonlinear programming problem suitable for the proposed SCP framework. No new datasets were introduced; rather, a realistic application scenario was used.

Key Insights and Ideas

  • Efficiency through Approximation: The core insight is that for slowly varying parameters, full convergence at each step is often unnecessary. APCSCP achieves significant speedups by performing only one iteration of a convex subproblem, leveraging the predictor-corrector idea.
  • Adjoint Methods for Derivative Efficiency: The use of adjoint methods is a critical component for making the algorithm practical. It drastically reduces the computational cost associated with derivative calculations, which is often a bottleneck in large-scale optimization.
  • Bridging Theory and Practice: The paper provides theoretical guarantees (contraction estimates, stability of tracking error) for the proposed algorithm, bridging the gap between theoretical optimization concepts and practical real-time implementation needs.
  • Handling Complex Constraints: SCP's ability to handle general convex structures (like conic constraints) makes APCSCP applicable to a wider range of problems than methods that rely solely on quadratic approximations.

Key Results

  • Significant Speedup: The APCSCP algorithm demonstrated a substantial reduction in computation time compared to other methods. In the hydro power plant example, APCSCP was approximately 6 times faster than PCSCP (a variant without approximated Jacobians) and significantly faster than a full NMPC approach.
  • Good Tracking Performance: The algorithm showed good tracking error performance, staying close to the true solution trajectory for the parametric problems.
  • Feasibility and Stability: The proposed methods preserve feasibility and offer theoretical guarantees for the stability of the approximation error.
  • Comparison with Existing Methods: APCSCP was compared against Full-NMPC, PCSCP, and RTGN (Real-Time Gauss-Newton). APCSCP achieved comparable accuracy to PCSCP and Full-NMPC while being much faster. RTGN showed oscillations and issues with terminal constraints.

Limitations and Future Work

  • Assumptions: The theoretical guarantees rely on assumptions such as strong regularity of the optimization problem and Lipschitz continuity of derivatives. These conditions can be difficult to verify in practice.
  • Approximation Quality: While APCSCP is fast, it provides approximate solutions. The accuracy depends on the step size of parameter changes and the quality of the approximations used.
  • Future Work: The authors suggest extending the theory and applying the framework to other problem classes, particularly those involving robust control and optimization with second-order cone and semidefinite constraints, where SCP can offer advantages. They also mention the potential for developing more sophisticated update strategies for matrices within the algorithm.

Summary updated

BibTeX
@article{trandinh2012adjoint,
  author = {Quoc Tran-Dinh and Dinh Quoc Tran and Carlo Savorgnan and Moritz Diehl},
  title = {{Adjoint-Based Predictor-Corrector Sequential Convex Programming for Parametric Nonlinear Optimization}},
  journal = {SIAM J. Optim},
  year = {2012},
  doi = {10.1137/110844349},
}
Figure