PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational Complexity of Inexact Gradient Augmented Lagrangian Methods: Application to Constrained MPC

Valentin Nedelcu, Ion Necoara, Quoc Tran Dinh

arXiv:1302.4355v1math.OC

TL;DR

Constrained MPC and other convex problems with complicating constraints need computationally certifiable solutions, while existing analyses leave gaps in full primal-and-dual rates for inexact gradient schemes. This paper applies inexact gradient and fast-gradient methods to the augmented-Lagrangian dual, establishing accuracy relations and suboptimality and feasibility estimates for approximate solutions.

  • Problem

    For inexact dual methods, prior work lacks full convergence-rate estimates for both gradient and fast-gradient schemes covering primal and dual suboptimality and primal feasibility violation.

    Source: §1 · p. 2

  • Method

    The paper uses augmented-Lagrangian dual gradient and fast-gradient methods with inexact information, solving inner problems to a specified accuracy and recovering approximate primal solutions by averaging.

    Source: §1 · p. 2

  • Results

    The analysis gives relations between inner and outer accuracy and estimates of primal and dual suboptimality and primal infeasibility for both algorithms.

    Source: §1 · pp. 2–3, §6 · p. 22

  • Takeaways & Limitations

    The methods are specialized and tested for constrained linear MPC problems, with bounds on the number of inner and outer iterations.

    Source: §1 · p. 3, §6 · p. 22

    Exact computational complexity comparisons between solvers require equivalent stopping criteria, such as maximum constraint violation.

    Source: §5.2 · p. 22

Abstract

from arXiv · show

We study the computational complexity certification of inexact gradient augmented Lagrangian methods for solving convex optimization problems with complicated constraints. We solve the augmented Lagrangian dual problem that arises from the relaxation of complicating constraints with gradient and fast gradient methods based on inexact first order information. Moreover, since the exact solution of the augmented Lagrangian primal problem is hard to compute in practice, we solve this problem up to some given inner accuracy. We derive relations between the inner and the outer accuracy of the primal and dual problems and we give a full convergence rate analysis for both gradient and fast gradient algorithms. We provide estimates on the primal and dual suboptimality and on primal feasibility violation of the generated approximate primal and dual solutions. Our analysis relies on the Lipschitz property of the dual function and on inexact dual gradients. We also discuss implementation aspects of the proposed algorithms on constrained model predictive control problems for embedded linear systems.

1. Introduction.

The paper develops inexact augmented-Lagrangian dual gradient methods to certify approximate solutions of convex problems with complicating constraints, motivated by constrained MPC on embedded systems. It addresses the lack of full primal-and-dual convergence estimates for both gradient schemes and fast gradient schemes using inexact information.

1. Introduction.

  • Embedded MPC requires solving a constrained optimal-control problem at each sampling instant, while short sampling times call for tight iteration bounds and simple computations.First-order methods are presented as more suitable for embedded systems than second-order methods with complex matrix-inversion iterations.Source: §1 · p. 1
  • For convex optimization problems, the proposed inexact dual gradient and fast-gradient schemes have full convergence-rate analyses yielding error estimates for constraint violation and the costs of primal and dual solutions.The inexact dual gradient algorithm has O(1/εout) iterations and finds an εout-optimal solution when inner problems are solved with εin of order O(εout).Source: §1 · pp. 2–3
  • Prior analyses often focus on dual variables, exact information, or only the dual gradient method, leaving full primal-and-dual rates for both inexact schemes unaddressed.The paper generates approximate primal solutions by averaging and allows the inner problems to be solved only up to a specified accuracy.Source: §1 · p. 2

1.2. Augmented Lagrangian framework.

  • The augmented dual is an equivalent smooth outer problem: its gradient is Lipschitz continuous even when the primal objective is not strongly convex.This framework underlies the inexact gradient and fast-gradient algorithms used to recover approximate primal solutions.Source: §1 · p. 2, §1.2 · p. 5

1.1. A motivating example: Linear MPC problems with state-input

  • The motivating linear MPC formulation uses convex, possibly nonsmooth stage and terminal costs with hard state and input constraints, without requiring strongly convex costs.The prediction-horizon problem is recast as a convex optimization problem with linear equality constraints and a simple set.Source: §1.1 · pp. 3–4

1.2. Augmented Lagrangian framework.

  • The augmented-Lagrangian framework moves complicating equality constraints into the cost, avoiding direct projection onto the difficult feasible set and enabling dual first-order methods.The target is an approximate primal-dual pair with bounds of order εout on dual suboptimality, primal infeasibility, and primal suboptimality.Source: §1.2 · pp. 4–5

2. Complexity estimates of solving the inner problems.

Because exact inner minimizers are difficult to compute, the paper studies approximate solutions and stopping rules for the augmented Lagrangian primal subproblem. It relates alternative accuracy criteria and gives iteration-complexity results for computing an approximate inner solution.

2. Complexity estimates of solving the inner problems.

  • An inner accuracy εin measures the suboptimality of an approximate solution when an exact minimizer is difficult to compute.The paper considers several ways to characterize εin-optimality.Source: §2 · p. 6
  • The stopping rules characterize inner accuracy through objective suboptimality, distance to the optimal-solution set, or first-order optimality conditions.The distance criterion asks whether the approximate point is near Z*(λ); the first-order criterion bounds its gradient inner product over Z.Source: §2 · p. 6
  • For polyhedral Z, verifying a stopping rule can reduce to a quadratic optimization problem over active constraints; for box constraints it is separable and takes O(p̃) operations.Here p̃ is the number of active constraints at the approximate solution.Source: §2 · p. 7
  • On bounded Z, the distance-to-optimality criterion implies the first-order criterion; with strong convexity, it also implies objective suboptimality.The paper also relates other stopping criteria, while the distance bound from objective suboptimality uses strong convexity.Source: §2 · pp. 7–8
  • A fast gradient scheme has an iteration-complexity bound for reaching the stated objective-accuracy criterion, with a separate bound when the inner objective is strongly convex.The supplied theorem states these cases but does not provide the bound expressions.Source: §2 · p. 8
  • For nonsmooth f, the paper notes projected-subgradient complexity and improved rates when f has a suitable structure.The passage does not provide the rate expressions.Source: §2 · p. 8

3. Complexity estimates of solving the outer problem using approximate dual gradients.

The paper analyzes augmented Lagrangian dual gradient and fast gradient methods that use approximate inner solutions and inexact dual information. For both methods it derives bounds on dual suboptimality, primal feasibility violation, and primal suboptimality.

3. Complexity estimates of solving the outer problem using approximate dual gradients.

  • The outer methods use approximate augmented-dual values and gradients derived from inexact solutions of the inner problem.The paper develops complexity certificates for both dual gradient and dual fast gradient methods.Source: §3 · p. 8

3.1. Inexact dual gradient method.

  • The inexact dual gradient method analyzes dual suboptimality and constructs an averaged primal sequence for bounding feasibility violation and primal suboptimality.Its convergence analysis is summarized with parameter choices for a specified outer accuracy.Source: §3.1 · pp. 10–11
  • For the inexact dual gradient method, the paper gives choices of outer iteration count and inner accuracy that yield bounds on the dual and primal quantities.The stated estimates cover dual suboptimality, primal infeasibility, and primal suboptimality.Source: §3.1 · p. 12

3.2. Inexact dual fast gradient method.

  • The inexact dual fast gradient scheme extends fast gradient analysis to inexact information and uses its sequence relations to derive estimates for primal and dual quantities.The paper identifies this extension as a basis for bounds on dual and primal suboptimality and primal infeasibility.Source: §3.2 · p. 13
  • For the fast gradient method, the analysis bounds dual suboptimality, primal feasibility violation, and primal suboptimality for its averaged primal sequence.The paper also gives parameter choices yielding the three bounds for a specified outer accuracy.Source: §3.2 · pp. 13–15

4. Complexity certification for linear MPC problems.

For linear MPC with quadratic costs, the augmented Lagrangian makes each inner problem strongly convex, supporting fast-gradient solution. The section uses this structure and bounds on problem parameters to certify iteration and computational costs.

4.1. Implementation aspects for MPC problems.

  • With linear MPC and quadratic stage and final costs, the augmented Lagrangian is strongly convex in the primal variable, even when the stage and final cost matrices are only positive semidefinite.The argument uses the positive-definite input-cost matrix R together with the dynamics and penalty term.Source: §4.1 · p. 16
  • A fast-gradient scheme solves the inner problems in a linear number of iterations; its bound depends on the strong-convexity and gradient-Lipschitz constants and the diameter of the feasible set.For box or Euclidean-ball constraints, the relevant set diameters can be computed explicitly.Source: §4.1 · p. 17
  • The outer-iteration bounds require a bound on the norm of an optimal dual solution, obtained under an assumption that attainable constraint residuals contain a ball around zero.The section also notes bounds for polyhedral MPC sets from prior work.Source: §4.1 · p. 17

4.2. Total complexity of solving MPC problems.

  • For IDGM and IDFGM, the section estimates inner and outer iteration counts and per-iteration flop costs under a zero dual initialization and inner stopping criterion (2.4).The iteration estimates use the MPC strong-convexity and smoothness properties; the section distinguishes the two outer algorithms.Source: §4.2 · pp. 17–18

5. Numerical experiments.

Numerical experiments apply IDGM and IDFGM to practical MPC systems and compare solver times on random QPs. IDFGM is faster but less robust than IDGM in the ball-on-plate simulations, while solver-time comparisons vary with the QP formulation.

5.1.1. Ball on plate system.

  • For prediction horizon N = 5, the IDFGM state and input trajectories drove the system to equilibrium; similar trajectories were obtained with both algorithms.Only the IDFGM trajectories are shown.Source: §5.1.1 · p. 19, Figure 5.2 · p. 20
  • With outer accuracy fixed at εout = 10^-3, IDGM was less sensitive than IDFGM to inner accuracy; if εin was too large, the desired suboptimality could not be ensured in finitely many iterations.The authors attribute IDFGM's greater sensitivity to its accumulation of errors.Source: §5.1.1 · p. 20, Figure 5.3 · p. 20
  • In the ball-on-plate simulations, IDFGM performed better than IDGM, and the derived sampled bounds approximated the observed outer iterations; overall, IDFGM was faster but less robust.The comparison of bounds and observed iterations was reported as evidence that the bounds were tight.Source: §5.1.1 · pp. 19–20

5.1.2. Oscillating masses.

  • IDFGM outperformed Alg. 1 in, especially as problem dimension increased; Gurobi was much faster on sparse QPs, while CPU times were comparable on dense QPs.Table 5.1 reports average and maximum CPU time and iteration counts for the compared methods.Source: §5.1.2 · p. 21, Table 5.1 · p. 21

6. Conclusions.

The paper proposes inexact dual gradient and fast-gradient methods for augmented Lagrangian duals, solving inner problems to finite accuracy. It derives accuracy relations and estimates for primal and dual suboptimality and feasibility violation, and tests implementation aspects on embedded linear MPC examples.

6. Conclusions.

  • The proposed methods use inexact gradient or fast-gradient schemes and derive estimates for primal and dual suboptimality and feasibility violation.The inner subproblems are solved only up to a specified accuracy.Source: §6 · p. 22
Loading 1302.4355v1…