PaperlayerView exact revision on arXiv

Source-linked AI summary

On feasibility, stability and performance in distributed model predictive control

Pontus Giselsson, Anders Rantzer

arXiv:1302.1974v2math.OC

TL;DR

Dual-decomposition DMPC needs to limit algorithm iterations while still obtaining feasible solutions and closed-loop stability. This paper proposes a stopping condition using adaptive constraint tightening and a control-horizon method. Its numerical example reports significantly fewer iterations while guaranteeing feasibility, stability, and prespecified performance.

  • Problem

    Dual-decomposition DMPC needs finite-iteration feasible solutions and stability guarantees, but standard MPC proofs using centralized terminal costs and constraints do not apply.

    Source: §I · p. 1, A. Main ideas · p. 3

  • Method

    The paper combines a control-horizon analysis without terminal costs or constraints with adaptive constraint tightening in a stopping condition for distributed optimization.

    Source: §I · p. 2, A. Main ideas · p. 4

  • Results

    The numerical example shows that the stopping condition can significantly reduce iterations needed to achieve feasibility, stability, and prespecified closed-loop performance.

    Source: §VI · p. 8, §V · p. 8

  • Takeaways & Limitations

    The proposed stopping condition permits finite-iteration termination while retaining guarantees of optimization feasibility, closed-loop stability, and prespecified performance.

    Source: §I · p. 2, §VI · p. 8

Abstract

from arXiv · show

In distributed model predictive control (DMPC), where a centralized optimization problem is solved in distributed fashion using dual decomposition, it is important to keep the number of iterations in the solution algorithm, i.e. the amount of communication between subsystems, as small as possible. At the same time, the number of iterations must be enough to give a feasible solution to the optimization problem and to guarantee stability of the closed loop system. In this paper, a stopping condition to the distributed optimization algorithm that guarantees these properties, is presented. The stopping condition is based on two theoretical contributions. First, since the optimization problem is solved using dual decomposition, standard techniques to prove stability in model predictive control (MPC), i.e. with a terminal cost and a terminal constraint set that involve all state variables, do not apply. For the case without a terminal cost or a terminal constraint set, we present a new method to quantify the control horizon needed to ensure stability and a prespecified performance. Second, the stopping condition is based on a novel adaptive constraint tightening approach. Using this adaptive constraint tightening approach, we guarantee that a primal feasible solution to the optimization problem is found and that closed loop stability and performance is obtained. Numerical examples show that the number of iterations needed to guarantee feasibility of the optimization problem, stability and a prespecified performance of the closed-loop system can be reduced significantly using the proposed stopping condition.

I. INTRODUCTION

The introduction situates this work among DMPC approaches and identifies stability guarantees for dual-decomposition methods as a key challenge. The paper addresses it with a stopping condition and an MPC setup solved through distributed optimization.

I. INTRODUCTION

  • Earlier dual-decomposition DMPC work generally lacks stability proofs, and the cited proof relies on a restrictive terminal point constraint to the origin.Standard MPC stability techniques use terminal costs and constraint sets involving all state variables, which are incompatible with dual decomposition.Source: §I · p. 1
  • The paper develops a control-horizon method and adaptive constraint tightening for a stopping condition intended to secure feasibility, stability, and prespecified performance.The introduction says the horizon method can verify its controllability assumption via an MILP and relates that assumption's parameter explicitly to closed-loop performance.Source: §I · pp. 1–2

II. PROBLEM SETUP AND PRELIMINARIES

  • The setup uses sparse linear dynamics and bounded local state and input polytopes, with neighboring subsystem interactions represented by sparse system matrices.The local state and control variables are partitioned by subsystem, and the global constraint sets are products of the local sets.Source: §II · p. 2
  • A finite-horizon quadratic MPC problem without terminal cost or terminal constraint is formulated and solved through the dual problem using a distributed accelerated-gradient algorithm.The paper uses the algorithm in [19] for simplicity and notes that dual ascent or ADMM can also solve the sparse optimization problem in distributed fashion.Source: §II · pp. 2–3

A. Notation

This section establishes notation for the paper's optimal solutions and iteration-dependent sequences.

A. Notation

  • The optimal state and control sequences are indexed by the initial state and constraint tightening, while iteration-specific sequences are indexed by algorithm iteration.The initial-state and tightening arguments are omitted when the meaning is unambiguous.Source: A. Notation · p. 3

B. Definitions and assumptions

The stopping-condition analysis combines a control-horizon performance test with finite-iteration feasibility through tightened constraints. The tightening is adjusted to relate the dual-function value to the original problem's value function.

A. Main ideas

  • A control horizon is selected to ensure the desired decrease in the optimal value function, which supports stability and a prespecified closed-loop performance.The paper's stopping test compares a lower bound on the current value function with an upper bound on the next-step value from a feasible candidate.Source: A. Main ideas · pp. 3–4

III. STOPPING CONDITION

  • The feedback controller's stopping test uses a primal feasible solution for the next step together with a dual-function lower bound to certify the performance condition.The feasible candidate is constructed using the shifted control sequence after applying the first control action.Source: A. Main ideas · p. 4

A. Main ideas

  • Constraint tightening enables a feasible solution after finitely many dual iterations, while adaptation bounds the gap between tightened- and original-constraint value functions.The text motivates tightening because duality-based methods guarantee primal feasibility only in the limit; the adapted test yields the stated stability and performance condition when α > ǫ.Source: A. Main ideas · p. 4

B. The stopping condition

The stopping condition tests when the distributed algorithm can stop while preserving feasibility, stability, and specified performance. Its parameters govern the performance target, constraint tightening, optimality tolerance, and frequency of stopping tests.

B. The stopping condition

  • Algorithm 1 adapts constraint tightening and tests the stopping condition after batches of distributed optimization iterations.It initializes the algorithm deterministically and reduces δ when the tightening must be adjusted.Source: B. The stopping condition · p. 4
  • The performance parameter α specifies the desired closed-loop performance, with larger α requiring a longer control horizon.The algorithm also uses an initial tightening δ_init, a relative optimality tolerance ε, and an iteration batch size Δk.Source: B. The stopping condition · pp. 4–5
  • Φ_N compares the first and last stage costs, while prior exponential controllability bounds imply Φ_N ≤ Cσ^(N−1).The paper introduces lemmas to support the stopping-condition theorem.Source: B. The stopping condition · p. 5
  • The stopping condition defines a feedback law whose domain includes the interior of the feasible initial-state set.The theorem also gives a performance guarantee when its stated conditions hold.Source: B. The stopping condition · p. 5

C. Feasibility, stability and performance

The feedback law yields one-step feasibility and defines a recursively feasible set. On that set, the stated conditions guarantee convergence to the origin and the specified closed-loop performance.

C. Feasibility, stability and performance

  • For every state in the interior of X0_N, the next state is feasible under ν_N when α satisfies the stated condition.This one-step feasibility supports the definition of the recursively feasible set.Source: C. Feasibility, stability and… · p. 5
  • On X_rf, the closed loop converges to the origin and achieves the specified performance when α > ε satisfies the stated condition.X_rf is the region of attraction for ν_N.Source: C. Feasibility, stability and… · p. 5
  • The control horizon N must be selected so its controllability parameter Φ_N meets the condition for the chosen α and tolerance ε.Computing Φ_N is addressed in the following section.Source: C. Feasibility, stability and… · p. 6

IV. OFFLINE CONTROLLABILITY VERIFICATION

The offline analysis identifies a control horizon whose controllability parameter supports the chosen performance guarantee. Under the stated assumptions, such a horizon exists when Φ_α > 0.

IV. OFFLINE CONTROLLABILITY VERIFICATION

  • If Φ_α > 0 for the selected α and ε, there exists a horizon N with Φ_N ≤ Φ_α.This is the condition used for the stability and performance results.Source: §IV · p. 6
  • Without terminal constraints, the finite-horizon problem is feasible for every horizon N, and controllability bounds the value-function sequence.As N grows, the difference between successive value functions becomes arbitrarily small, yielding a sufficiently small Φ_N.Source: §IV · p. 6
  • The choice of α constrains ε and Φ_α; a larger ε requires a smaller Φ_α and therefore a longer horizon.The paper addresses computing N and Φ_N to guarantee the selected performance.Source: §IV · p. 6

A. Exact verification of controllability parameter

The section tests whether a chosen horizon meets the controllability bound required for the desired performance. It also describes converting the test into a mixed-integer linear program.

A. Exact verification of controllability parameter

  • The test asks whether the controllability parameter Φ_N for horizon N satisfies Φ_N ≤ Φ_α for the chosen performance target.The proposition establishes Φ_N ≤ Φ_α when its optimization test meets the stated condition.Source: A. Exact verification of… · p. 6
  • The optimization formulation includes upper- and lower-level primal and dual feasibility, stationarity, and complementarity conditions.Its variables include β, μ, λ, s, x̄, and y.Source: A. Exact verification of… · p. 7
  • The bilevel test can be reformulated as a single-level indefinite quadratic program with complementarity constraints and then as a MILP.The reformulation uses sufficient and necessary KKT conditions for the lower-level problem.Source: A. Exact verification of… · pp. 6–7
  • If the chosen horizon fails the bound, one proposed heuristic guesses a longer horizon using an exponential controllability assumption.It selects the smallest N satisfying Cσ^(N−1) ≤ Φ_α, with C and σ estimated from the previous test solution.Source: A. Exact verification of… · p. 7

B. Controllability parameter estimation

The section estimates a control horizon from a controllability parameter, then evaluates the stopping condition in a numerical example. The example reports fewer iterations with suitable initial constraint tightening, and the conclusion states that the condition guarantees feasibility, stability, and prespecified performance.

B. Controllability parameter estimation

  • A sampled worst-case estimate ˆΦN can guide the initial horizon choice; the horizon may be increased adaptively when the controllability assumption fails.For large systems, the adaptive scheme holds the horizon fixed between increases.Source: B. Controllability parameter estimation · p. 7

V. NUMERICAL EXAMPLE

  • In the numerical example, the smallest horizon satisfying ΦN(0.01) ≤ 0.51 is N(0.01) = 6.The example uses κ = 1.22 and tolerance ǫ = 0.005.Source: §V · p. 7
  • The simulation uses 1,000 uniformly sampled initial conditions; Table I reports mean and maximum iterations and average termination tightening.Source: §V · p. 8, Table I · p. 8
  • A suitable initial tightening significantly reduces average iterations; 50% tightening is as efficient as 5%, and reductions in tightening indicate early infeasibility detection.For initial tightening above 10%, iteration counts are not significantly affected.Source: §V · p. 8

VI. CONCLUSIONS

  • The stopping condition guarantees optimization feasibility, closed-loop stability, and prespecified performance, while the example shows it can significantly reduce the iterations needed.Source: §VI · p. 8

A. Proof for Lemma 2

The proof of Lemma 2 uses convergence of primal variables to establish eventual constraint satisfaction and finite objective values. The following proof introduces iterate and optimum vectors to support a cost comparison for Lemma 3.

A. Proof for Lemma 2

  • Primal-variable convergence implies that the trajectory constraints are eventually satisfied and the associated objective values converge, supporting the finite-iteration claim in Lemma 2.Source: A. Proof for Lemma 2 · p. 9

B. Proof for Lemma 3

  • The Lemma 3 proof compares iterate and optimum vectors under feasibility conditions, using the quadratic cost matrix H to bound the cost difference.Source: B. Proof for Lemma 3 · p. 9

C. Proof for Lemma 4

The proof uses duality and convergence-rate arguments to establish a finite-iteration bound for the case considered in Lemma 4.

C. Proof for Lemma 4

  • When the tightened primal problem has infinite value, the theorem of alternatives implies that its dual problem is unbounded and yields a feasible dual pair.Source: C. Proof for Lemma 4 · p. 9
  • The proof applies a convergence-rate result to that feasible pair to obtain the required inequality after finitely many iterations.Source: C. Proof for Lemma 4 · p. 9

D. Proof for Theorem 1

The proof establishes termination of the adaptive tightening loop for initial states in the interior of the specified domain. It does so by showing that sufficiently small tightening and finite algorithm iterations satisfy the loop conditions.

D. Proof for Theorem 1

  • For every initial state in int(X0_N), the loop terminates after finite tightening reductions and finite algorithm iterations, defining νN on that domain.Source: D. Proof for Theorem 1 · pp. 9–10
  • The tightening is reduced geometrically as δ = 2^-lδinit, and sufficiently small δ makes the required loop inequalities hold.Source: D. Proof for Theorem 1 · p. 10
  • The proof shows that small enough tightening makes the next state feasible and satisfies the performance condition for a finite algorithm iterate.Source: D. Proof for Theorem 1 · p. 10
  • The resulting controller has domain containing int(X0_N), and the proof establishes the stated value-function bound for its successor state.Source: D. Proof for Theorem 1 · pp. 9, 11
Loading 1302.1974v2…