Parallel and distributed optimization methods for estimation and control in networks

1. Introduction

• Networked estimation and control can be posed as optimization problems whose subsystem interactions couple costs or constraints, often with exploitable sparse structure.Source: §1 · p. 2
• Large size, communication restrictions, or robustness requirements can preclude centralized decisions, requiring local agents to solve subproblems and negotiate toward global optimality.Source: §1 · p. 2
• Centralized algorithms exploit sparsity and may parallelize computation, whereas distributed graph algorithms run across nodes and restrict communication to graph edges.Source: §1 · p. 3
• The paper links estimation and control in networked systems with distributed optimization and surveys three decomposition classes for distributedly coupled problems.Source: §1 · p. 4
• Three estimation and control applications are reformulated as coupled optimization problems, with numerical experiments on parallel and distributed algorithms.Source: §1 · p. 4
• The schemes suggest network architectures and protocols with different convergence speeds and coordination overhead; new methods are more efficient than some classical schemes.Source: §1 · p. 4

2.1. State estimation problem

• In the state-estimation problem, sensors use moving horizon estimation and exchange local estimates of the entire state to asymptotically reach a reliable overall estimate.MHE solves an online minimization at each step, is optimal with respect to its associated cost, and can account for state and noise constraints.Source: §2.1 · p. 5
• For nonlinear state estimation, updating the covariance matrix in a distributed fashion remains an open issue.Source: §2.1 · p. 6
• Eliminating states from the MHE formulation yields an optimization problem with decoupled cost and a common decision variable.The distributed algorithms must use the sensor communication graph to help all sensors asymptotically obtain reliable state estimates.Source: §2.1 · p. 7

2.2. Distributed optimal control problem

• Distributed control is motivated by lower numerical effort from solving low-dimensional problems in parallel and by modularity when adding or removing subsystems.The local controllers account for subsystem interactions and physical constraints.Source: §2.2 · pp. 8–9
• The control problem is recast as decoupled costs with sparse coupled constraints, enabling computation to be distributed among interacting subsystems.The paper motivates this architecture by noting that subsystem controllers can be designed in parallel and modularly.Source: §2.2 · p. 9
• For dynamically coupled subsystems, eliminating states yields a separable convex quadratic program with decoupled costs and coupled constraints (DCCC).Source: §2.2 · p. 11

2.3. Cooperative control problem of dynamically uncoupled systems

• With independent dynamics but a shared goal, the cooperative objective couples subsystem and neighbor states and inputs, yielding coupled costs with decoupled constraints (CCDC).Source: §2.3 · pp. 11–12
• The problem uses relative positions between satellites rather than absolute positions and can be recast as a convex quadratic problem with coupled cost; for all i,j, Hij=0 if |i−j|>3, and sets Xi are polyhedral.Source: §2.3 · p. 13
• Eliminating satellite states and retaining inputs as decision variables makes H positive definite and leaves Xi defined only by linear constraints.Source: §2.3 · p. 14

2.4. Cooperative control problem of dynamically coupled systems

• For coupled dynamics, a positive weighted combination of local costs defines the systemwide objective; eliminating states gives a coupled objective in local controls and decoupled constraints.The weights αi are positive and sum to 1.Source: §2.4 · p. 15
• The cooperative control problem of dynamically coupled systems is a particular case of the CCDC problem.The passage also refers readers to Remark 2.4(ii).Source: §2.4 · p. 15

3. Parallel and distributed optimization algorithms for solving coupled optimization problems

• The paper presents parallel and distributed algorithms for estimation and control optimization problems and analyzes their properties and convergence conditions.The algorithms address problems discussed in Section 2.Source: §3 · p. 15
• Original-problem and dual decompositions offer alternative algorithms, with convergence, local-computation, global-communication, and message-passing tradeoffs shaped by application needs.The section distinguishes decomposing the original optimization problem from decomposing its corresponding dual.Source: §3 · p. 16

3.1. Distributed gradient algorithms for optimization problems of type (DCx)

• Under strong connectivity and a bounded interconnection interval, consensus iterations make agents’ local variables converge to the same state.The bounded-interval condition requires information to be sent at least once every τ consecutive iterations along links in E∞.Source: §3.1 · p. 17
• The distributed projected-gradient method combines neighbor estimates, takes a gradient step on each agent’s objective, and projects onto the feasible set.The method combines consensus with a projected-gradient update.Source: §3.1 · p. 17

Algorithm dgp1

• For Algorithm dgp1, the stated convergence theorem assumes convex objectives with bounded gradients and a convex feasible set.The supplied theorem passage states these assumptions but not its conclusion.Source: Algorithm dgp1 · p. 18

the weights γij

• Under a connected graph of interconnections and the bounded interconnection interval property, distributed projected gradient dgp1 converges to an optimum of (DCx).The passage also assumes the weight matrix is doubly stochastic.Source: the weights γij · p. 18

Algorithm dgp2

• Algorithm dgp2 converges with a constant step size when µ is sufficiently large under assumptions similar to Theorem 3.1.Unlike fixed-topology dgp2, dgp1 and the algorithm in [52] support changing topologies.Source: Algorithm dgp2 · pp. 18–19, the weights γij · p. 18
• Algorithm dgp2 uses fewer gradient iterations than dgp1 in simulations, but requires µ = 10 consensus iterations per gradient iteration.The state-estimation experiment uses 10 or 20 sensors, prediction horizon N = 10 or 20, and fixed weights with µ = 10.Source: Table 1 · p. 20, Algorithm dgp2 · p. 20

3.2. Decomposition algorithms for solving optimization problems (DCCC)

• For separable convex problems with decoupled costs and coupled constraints, the section considers primal and dual decomposition methods.The coupled constraints are specialized to linear form, with convex quadratic local costs, compact convex sets, and Slater’s condition assumed.Source: §3.2 · pp. 20–21

such that PM

• Primal decomposition introduces auxiliary variables to separate coupled linear equality constraints and reduces the problem to an unconstrained convex primal problem (PP).The method defines local subproblem solutions and corresponding Lagrange multipliers for given auxiliary-variable values.Source: such that PM · pp. 21–22

Algorithm primal subgradient (PS)

• Under Assumption 3.3, the primal subgradient algorithm converges because (conv-DCCC) and its primal problem are equivalent.The algorithm uses a step size αk.Source: Algorithm primal subgradient (PS) · p. 22
• The dual fast gradient algorithm uses μ > 0 and strongly convex prox functions, whereas the dual interior-point algorithm uses μ > 0 and barrier functions.Source: Algorithm primal subgradient (PS) · p. 24
• For μ > 0, strongly convex prox functions give the augmented dual a Lipschitz continuous gradient, while barrier prox functions make it self-concordant [28, 29].For convex prox functions and any μ ≥ 0, a subgradient is P_i G_i x_i(μ, λ) − g.Source: Algorithm primal subgradient (PS) · p. 24

Algorithm dual interior-point (DIP)

• Under Assumption 3.3, DS, DFG, and DIP converge for the separable convex problem when the step-size is suitably chosen.Source: Algorithm dual interior-point (DIP) · p. 25

algorithm (DIP) has complexity O

• Primal subgradient maintains coupled-constraint feasibility at every iteration, whereas dual algorithms satisfy it only at convergence, a concern when stopping early in control problems.The coupled constraints represent system dynamics over the prediction horizon, so a dual method may not satisfy those dynamics at an intermediate stopping point.Source: algorithm (DIP) has complexity O · p. 25
• Smoothed dual fast-gradient (DFG) and dual interior-point (DIP) methods require fewer iterations than classical primal or dual subgradient methods.DFG is more appropriate than DIP when there are many coupling constraints, because DIP inverts a square matrix of dimension n_λ at each iteration.Source: algorithm (DIP) has complexity O · p. 26
• Algorithms DS and DFG use neighbor information for distributed updates, while DIP requires a central agent to update multipliers, yielding a star-shaped topology.The distributed updates rely on linear coupling constraints and the communication graph between subsystems.Source: algorithm (DIP) has complexity O · p. 26

3.3. Parallel algorithms for solving optimization problems of type (CCDC)

• For coupled-cost, decoupled-constraint problems, Jacobi updates each variable using other variables’ previous-iteration values, while Gauss–Seidel uses their most recent values.Jacobi subproblems can be solved in parallel; Gauss–Seidel can also be parallelized when a coloring scheme applies.Source: §3.3 · p. 27

Algorithm Gauss-Seidel

• Under a contraction assumption, Jacobi and Gauss–Seidel are well defined and converge linearly to the CCDC minimum; Gauss–Seidel also permits convexity-based conditions.Those relaxed conditions require differentiable convexity and strict convexity in each coordinate with the others fixed; if the objective is nondifferentiable, either algorithm can stop at a nonoptimal corner point.Source: Algorithm Gauss-Seidel · p. 28
• In, CCDC is decomposed into agent-local subproblems that retain terms dependent on each agent’s variable and are solved iteratively using feasible directions.Source: Algorithm Gauss-Seidel · p. 29
• Both algorithms work better for large σ.The paper states this for the satellite-formation example.Source: Algorithm Gauss-Seidel · p. 30
• Local iterations require relatively low effort but converge more slowly and involve high communication among neighboring agents.Source: Algorithm Gauss-Seidel · p. 30
• Tables 1–3 indicate that obtaining an optimal solution requires many iterations, while a satisfactory suboptimal solution can justify stopping earlier.Such a solution can preserve fundamental system properties such as robustness and stability.Source: Algorithm Gauss-Seidel · p. 30

• Three estimation and process-control applications for networked systems lead to coupled optimization problems with structure that decomposition algorithms can exploit.Source: §4 · p. 30
• The paper develops a systematic framework for parallel and distributed algorithms, each trading off convergence speed, message-passing amount, and distributed computation architecture.Source: §4 · pp. 30–31
• Numerical experiments are provided for several parallel and distributed algorithms.Source: §4 · p. 31