Non-convex Feedback Optimization with Input and Output Constraints
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "Non-convex Feedback Optimization with Input and Output Constraints".
Dev: Here's the gist of the paper. In this paper, we present a novel control scheme for feedback optimization that can steer a physical plant to the solution of a constrained optimization problem without numerically solving the problem <ref:2004.06407#pg2>.
Rosa: Our controller can be interpreted as a discretization of a continuous-time projected gradient flow <ref:2004.06407#pg2>.
Dev: Problem Formulation and Context The paper focuses on designing a discrete-time controller to enforce output constraints in feedback optimization <ref:2004.06407#pg2>.
Rosa: The general problem considered is minimizing a cost function subject to system dynamics and constraints, specifically minimizing u,y Φ(u, y) subject to y = h(u) u ∈ U, y ∈ Y <ref:2004.06407#pg4>.
Paper summary: Rosa: So this paper is about this new control scheme for feedback optimization that can steer a physical plant to solve a constrained optimization problem without actually solving the whole problem numerically, which is really interesting because it avoids needing an explicit model of the system dynamics <ref:2004.06407#pg1>.
Dev: Yeah, what they claim is that this controller functions like a discretization of a continuous-time projected gradient flow, which means it’s based on standard optimization ideas but adapted for real-time feedback control <ref:2004.06407#pg1>.
Taro: It sounds like it's trying to handle those constraints on the steady-state outputs, and the paper says this approach combines a few good things: it enforces those constraints asymptotically, and temporary violations can be easily quantified <ref:2004.06407#pg1>.
Rosa: And one big thing they highlight is that you only need information about the steady-state input-output sensitivities of the plant, not the whole system model itself <ref:2004.06407#pg1>.
Dev: That’s a key point because it makes it more robust against disturbances and uncertainties compared to other methods, like feedforward numerical optimization <ref:2004.06407#pg1>.
Taro: They also say that even for problems that aren't convex, this global convergence is guaranteed <ref:2004.06407#pg1>.
Rosa: And tuning it is pretty simple too, because the step-size alpha is the only thing you need to tune <ref:2004.06407#pg1>.
Dev: So, this paper "Non-convex Feedback Optimization with Input and Output Constraints" proposes a discrete-time controller that uses measured output information to steer a plant toward an optimal solution while managing constraints without needing the full system model, which is what matters for real applications.
Conclusion: Rosa: Looking at the title and what we just talked about, this paper really focuses on taking feedback optimization where it can handle those output constraints asymptotically <ref:2004.06407#pg1>.
Dev: And the authors are using a controller that's interpreted as a discretization of a continuous-time projected gradient flow, which is a solid way to think about how the system moves toward an optimum <ref:2004.06407#pg1>.
Taro: It means for someone just listening, this method offers global convergence guarantees even when the optimization problem isn't convex, which is something we need in real-world systems that aren't perfectly modeled <ref:2004.06407#pg1>.
Rosa: And they emphasize that it requires only reduced model information—specifically those steady-state input-output sensitivities—which makes it very practical to use <ref:2004.06407#pg1>.
Dev: The main implication is that we can enforce constraints on the plant's steady-state outputs with zero asymptotic error, and they show it doesn't require integrating dual variables to do that <ref:2004.06407#pg1>.
Taro: It’s a pretty well-behaved convergence behavior without those nasty oscillations that you sometimes see in other schemes when they try to satisfy constraints during the transition phase <ref:2004.06407#pg1>.
Rosa: So, this paper presents a new discrete-time controller for feedback optimization with the property that constraints on the steady-state plant outputs are enforced asymptotically <ref:2004.06407#pg1>.
Dev: This approach offers global convergence guarantees for non-convex problems and fixed step-sizes, it's easy to tune, and it exhibits a well-behaved convergence behavior without oscillations <ref:2004.06407#pg1>.
Taro: It's also noted that this method is robust with respect to uncertainty in those input-output sensitivities <ref:2004.06407#pg1>.
Verena Áberle, Adrian Hauswirth, Lukas Ortmann, Saverio Bolognani, Florian Örfler
ETH Zurich
eess.SY, cs.SY
Submitted: 2020-04-14
Updated: 2020-07-08
Comments: 6 pages, 3 figures
Journal ref: IEEE Control Systems Letters, 2021 5 (1), 343 - 348
DOI: 10.1109/LCSYS.2020.3002152
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 91/100
The gist: In this paper, we present a novel control scheme for feedback optimization that can steer a physical plant to the solution of a constrained optimization problem without numerically solving the…
Key concepts
- Feedback Optimization
- This involves designing a controller that adjusts system inputs based on measurements of the plant's output to minimize a cost function subject to constraints. The paper focuses on enforcing output constraints in this context, which is difficult when the system model is unknown.
- Projected Gradient Flow
- The proposed discrete-time controller can be viewed as a time discretization of a continuous-time projected gradient flow. This mathematical interpretation helps establish the convergence properties of the control scheme to first-order optimal points of the optimization problem.
- LICQ (Linear Independence Constraint Qualification)
- This is a condition ensuring that at any point on the feasible set, the gradients of all active inequality constraints are linearly independent. Satisfying LICQ guarantees that Lagrange multipliers are unique and bounded, which is crucial for analyzing constrained optimization problems.
Terminology
Summary
In this paper, we present a novel control scheme for feedback optimization that can steer a physical plant to the solution of a constrained optimization problem without numerically solving the problem <ref:2004. p. 006407#pg2>. Our controller can be interpreted as a discretization of a continuous-time projected gradient flow <ref:2004. p. 0 p. 006407#pg2>.
Problem Formulation and Context
The paper focuses on designing a discrete-time controller to enforce output constraints in feedback optimization <ref:2004.06407#pg2>. The general problem considered is minimizing a cost function subject to system dynamics and constraints, specifically minimizing u,y Φ(u, y) subject to y = h(u) u ∈ U, y ∈ Y <ref:2004. p. 106407#pg4>. A key aspect is that the system model h does not need to be known explicitly nor does it need to be evaluated numerically <ref:2004. p. 006407#pg2>. Instead, only information about the steady-state sensitivities ∇h is required <ref:2004. p. 006407#pg2>.
The Proposed Control Scheme
The proposed controller is an integral feedback controller defined as u+ = u + α σbα(u, y) y = h(u) <ref:2004.06407#pg4>. The term σbα(u, y) is defined as arg min w∈Rp kw + G−1 (u)H(u)T ∇Φ(u, y)T k 2 G(u) subject to A(u + αw) ≤ b C(y + α∇h(u)w) ≤ d <ref:2004. p. 206407#pg4>. This scheme resembles standard numerical optimization algorithms like SQP [21, Ch. p. 2 10], [22, Ch. 18] <ref:2004. p. 006407#pg4>. A main difference is that this controller does not rely on a numerical evaluation of h <ref:2004. p. 206407#pg4>.
Convergence Guarantees
The paper establishes global convergence of the scheme to the set of first-order optimal points of (4) under Assumptions 1 to 3 <ref:2004.06407#pg4>. The proof relies on an invariance principle for discrete-time systems <ref:2004. p. 206407#pg4>. A Lyapunov function V(u) is constructed which is shown to be non-increasing along the solutions of (8) <ref:2004. p. 306407#pg4>. The convergence to first-order optimal points occurs because the right-hand side of equation (20) is negative for all w 6= 0, implying w = 0 and Ch(u) ≤ d, i. p. 3e., u+ = u ∈ U˜ <ref:2004. p. 006407#pg4>.
Comparison with Existing Methods
The proposed scheme is compared against other feedback optimization schemes such as saddle-point schemes <ref:2004.06407#pg2>. The authors demonstrate that the integration of a dual variable is not required to guarantee constraint satisfaction with zero asymptotic error <ref:2004. p. 006407#pg4>. Furthermore, the scheme exhibits a benign convergence behavior without oscillations and tuning is restricted to one parameter, the step-size α <ref:2004. p. 006407#pg2>.
Conclusion
The authors propose a new discrete-time controller for feedback optimization with the property that constraints on the steady-state plant outputs are enforced asymptotically <ref:2004.06407#pg2>. This approach offers global convergence guarantees for non-convex problems and fixed step-sizes, is easy to tune, and exhibits a well-behaved convergence behavior without oscillations <ref:2004. p. 406407#pg4>. The method is also noted to be robust with respect to uncertainty in the inputoutput sensitivities <ref:2004. p. 406407#pg4>.
Appendix Details
The appendix connects the discrete-time control law in (8) to a continuous-time projected gradient flow <ref:2004.06407#pg2>. Lemma 6 shows that for all u ∈ U˜, we have lim α&0+ σα(u) = ΠG U˜ -G−1 (u)∇Φ(˜ u)T <ref:2004.06407#pg4>. This suggests a connection between the discrete scheme and the continuous flow <ref:2004. p. 006407#pg2>. The tangent cone of U˜ at u ∈ U˜ is given by TuU˜:= n w ∈ R p AIU u w ≤ 0 CI Y h(u) ∇h(u)w ≤ 0 <ref:2004. p. 406407#pg2>.
Numerical Example Insights
A numerical example illustrates the behavior of the control scheme in a small numerical example with y = h(u) = u3/2+u1-u2+0.5 and Φ(u, y) = 1.5u2/1 + u2/2−u3/2 + u1u2−3u2 + 1. p. 45 + y <ref:2004. p. 006407#pg4>. The left of Fig. p. 4 2 shows that all constraints are satisfied asymptotically and, depending on α, temporary constraint violations can be made arbitrarily small <ref:2004. p. 406407#pg4>. Comparisons with a generic projected saddle-point scheme show that tuning with three parameters (α, γ, ρ) can be challenging to manage various performance trade-offs <ref:2004. p. 406407#pg4>. The oscillatory nature of the trajectories reveals how saddle-point flows are not intended to satisfy constraints during transients <ref:2004. p. 406407#pg4>.
References
[1] A. Jokic, M. Lazar, and van den P. p. 5P.J. Bosch, “On constrained steadystate regulation: Dynamic KKT controllers,” IEEE Trans. p. 5 Autom. Control, vol. p. 5 54, no. 9, pp. 2250–2254, 2009
[3] M. Colombino, E. p. 5 Dall’Anese, and A. p. 5 Bernstein, “Online optimization as a feedback controller: Stability and tracking,” IEEE Trans. p. 5 Control Netw. p. 5 Syst., vol. 7, no. 1, pp. 422–432, Mar. p. 5 2020
[5] C. E. Garcia and M. p. 5 Morari, “Optimal operation of integrated processing systems: Part II: Closed-loop on-line optimizing control,” AIChE J. p. 5, vol. 30, no. 2, pp. 226–234, Mar. p. 5 1984
[11] A. Hauswirth, A Zanardi, S Bolognani F Dörfler and G Hug, “Online optimization in closed loop on the power flow manifold,” in IEEE PowerTech, Manchester UK 2017
[23] G. Torrisi, S Grammatico R Smith and M Morari, “A projected gradient and constraint linearization method for nonlinear model predictive control,” SIAM J. p. 5 Control Optim. p. 5, vol. 56, no. 3, pp. 1968–1999, 2018
[34] A Hauswirth, S Bolognani G Hug and F Dörfler, “Projected gradient descent on Riemannian manifolds with applications to online power system optimization,” in 54th Annual Allerton Conference on Communication Control and Computing 2016
[35] A Nagurney and D Zhang, Projected Dynamical Systems and Variational Inequalities with Applications, 1st ed. Springer, 1996
[21] M. Bazaraa H Sherali and C Shetty, Nonlinear Programming: Theory and Algorithms, 3rd ed. p. 5 Wiley, 2006
[24] D. P Bertsekas, Nonlinear Programming, 2nd ed. p. 5 Belmont Massachusetts Athena Scientific, 1999
[25] D G Luenberger and Y Ye, Linear and Nonlinear Programming. Springer, 1984 <ref:25
[30] J LaSalle and Z Artstein, The Stability of Dynamical Systems. Philadelphia PA: SIAM, 1976 <ref:30
Page Breakdown
--- Page 1 ---
Non-Convex Feedback Optimization with Input and Output Constraints Verena Häberle Adrian Hauswirth Lukas Ortmann Saverio Bolognani Florian Dörfler Abstract— In this paper, we present a novel control scheme for feedback optimization. That is, we propose a discretetime controller that can steer a physical plant to the solution of a constrained optimization problem without numerically solving the problem <ref:2004. p. 006407#pg2>. Our controller can be interpreted as a discretization of a continuous-time projected gradient flow <ref:2004.06407#pg2>. Compared to other schemes used for feedback optimization, such as saddle-point schemes or inexact penalty methods, our control approach combines several desirable properties: it asymptotically enforces constraints on the plant steadystate outputs, and temporary constraint violations can be easily quantified <ref:2004. p. 006407#pg2>. Our scheme requires only reduced model information in the form of steady-state input-output sensitivities of the plant <ref:2004. p. 006407#pg2>. Further, global convergence is guaranteed even for non-convex problems <ref:2004. p. 006407#pg2>. Finally, our controller is straightforward to tune, since the step-size is the only tuning parameter <ref:2004. p. 006407#pg2>.
I. INTRODUCTION In recent years the design of feedback controllers that steer the steady state of a physical plant to the solution of a constrained optimization problem has garnered significant interest both for its theoretical depth [1]–[4] and potential applications <ref:2004. p. 006407#pg2>. In particular while the historic roots of feedback optimization trace back to process control [5], [6] and communication networks [7], [8], recent efforts have centered around online optimization of power grids [9]–[12] <ref:2004. p. 006407#pg2>. We adopt the perspective that feedback optimization emerges as the interconnection of an optimization algorithm such as gradient descent (formulated as an open system) and a physical plant with well-defined steady-state behavior <ref:2004. p. 006407#pg2>. In contrast for example to [4] that adopts an outputregulation viewpoint or extremum-seeking which is completely model-free [13] <ref:2004. p. 006407#pg2>. In particular for our purposes we assume that the plant is stable with fast-decaying dynamics and the steady state input-to-output map y = h(u) is wellbehaved (Fig. p. 0 1) <ref:2004. p. 006407#pg2>. This assumption is motivated by previous work on timescale separation in these setups [14], [15] <ref:2004. p. 006407#pg2>. The critical aspect of feedback optimization is that instead of relying on a full optimization model the algorithms take advantage of measurements of the system output <ref:2004. p. 006407#pg2>. This entails that the system model h does not need to be known explicitly nor does it need to be evaluated numerically <ref:2004. p. 006407#pg2>. Instead only information about the steady-state sensitivities ∇h is required <ref:2004. p. 006407#pg2>. This renders feedback optimization schemes inherently more robust against disturbances and uncertainties than “feedforward” numerical optimization <ref:2004. p. 006407#pg2>. A particular focus in feedback optimization is the incorporation of (unilateral) constraints on inputs and steady-state outputs <ref:2004. p. 006407#pg2>. The former can be enforced directly by projection or by exploiting physical saturation and using anti-windup control [16], [17] <ref:2004. p. 006407#pg4>. Output constraints however cannot be enforced directly especially when the map h is unknown <ref:2004. p. 006407#pg2>. Previous works either employ inexact penalty methods [11], [18], treating the output constraints as soft constraints, or saddle-point schemes [3], [9], [10] <ref:2004. p. 006407#pg4>, ensuring the constraints to be satisfied asymptotically <ref:2004. p. 006407#pg4>.
Page 2
For R p, h·, ·i denotes the Euclidean inner product and · its induced 2-norm <ref:2004.06407#pg2>. The non-negative orthant of R p is written as R p ≥0 and the set of symmetric positive definite matrices of size p × p is denoted by S p +. p. 1 Any G ∈ S p + induces a 2-norm defined as vG:= √ v T Gv for all v ∈ R p <ref:2004. p. 106407#pg2>. Given a set C ⊂ R p, a map G: C → S p + is called a metric on C <ref:2004. p. 106407#pg2>. For a continuously differentiable function f: R p → R q, ∇f(x) ∈ R q×p denotes the Jacobian of f at x <ref:2004. p. 106407#pg2>. The map f is globally L-Lipschitz continuous if for all x, y ∈ R p and some L > 0, it holds that f(x) − f(y) ≤ Lx − y <ref:2004. p. 106407#pg2>. To establish our main convergence result in Section IV we require the so-called Descent Lemma [24, Prop A. p. 124] <ref:2004. p. 006407#pg4>. Lemma 1 Given a continuously differentiable function f: R p → R with L-Lipschitz derivative ∇f, for all x, z ∈ R p it holds that f(z) ≤ f(x) + ∇f(x)(z − x) + L 2 z − x2 <ref:2004. p. 106407#pg4>.
Page 3
In this paper we often consider feasible sets of the form X:= u ∈ R p g(x) ≤ 0, (1) where g: R p → R q is continuously differentiable <ref:2004.06407#pg4>. Let I X x:= i gi(x) = 0 denote the index set of active inequality constraints of X at x and let ¯I X x:= i gi(x). p. 1 Definition 1 (LICQ) Given X ⊂ R p as in (1), the linear independence constraint qualification (LICQ) is said to hold at x ∈ X, if the matrix ∇gIXx(x) has rank I X x <ref:2004. p. 106407#pg4>. For a continuously differentiable function Ψ: R p → R and X ⊂ R p as in (1) consider the constrained problem minimize x Ψ(x) subject to x ∈ X (2) <ref:2004. p. 106407#pg4>. The Lagrangian of (2) is defined as L(x, µ):= Ψ(x) + µ T g(x) for all x ∈ R p and all Lagrange multipliers µ ∈ R q ≥ 0 <ref:2004. p. 106407#pg4>. Recall the first-order optimality (KKT) conditions for (2) Theorem 1 If x? p. 1 ∈ X is a local solution of (2) and LICQ holds at x? p. 1, there exists a unique µ? p. 1 ∈ R q ≥ 0 such that ∇xL(x?, µ?) = 0 and µ?i = 0 hold for all i ∈ ¯I X x? p. 1. In particular, the LICQ assumption guarantees the uniqueness (and boundedness) of the dual multipliers µ? p. 1 <ref:2004.06407#pg4>. For the analysis of our proposed controller in Section III we need to consider parametric problems of the form minimize x Ψ(x, ε) subject to x ∈ X (ε), (3) where X (ε):= u ∈ R p g(x, ε) ≤ 0, and Ψ: R p×T → R and g: R p × T → R q are parametrized in ε ∈ T ⊂ R r <ref:2004. p. 106407#pg4>. Hence the Lagrangian of (3) is defined as L(x, µ, ε):= Ψ(x, ε)+µ T g(x, ε) for all x ∈ R p, µ ∈ R q ≥ 0, and all ε ∈ T <ref:2004. p. 106407#pg4>. To prove our main result in Section IV we will require solutions of (3) to be continuous as a function of ε <ref:2004. p. 106407#pg4>. For this purpose we use [27, Thm 2. p. 13.2] which for convex problems with strongly convex objective simplifies to the following: Theorem 2 Consider (3) and assume that Ψ and g are twice continuously differentiable in x, and that Ψ, g, ∇xΨ, ∇xg, ∇2 xxΨ, and ∇2 xxg are continuous in ε <ref:2004. p. 106407#pg4>. Furthermore for all ε ∈ T let Ψ be strongly convex in x X (ε) be non-empty and convex in x and LICQ be satisfied for all x ∈ X (ε) Then there exist continuous functions x? p. 1: T → R p and µ?: T → R q ≥ 0 such that x?(ε) is the unique global optimizer of (3) for all ε ∈ T and µ? p. 1(ε) is its Lagrange multiplier <ref:2004. p. 106407#pg4>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI systems can steer a physical plant to solve a constrained optimization problem without numerically solving it by using a discretized controller interpreted as a discretization of a continuous-time projected gradient flow.
-
The improved system can asymptotically enforce constraints on the plant steadystate outputs and easily quantify temporary constraint violations, which is superior to saddle-point schemes that exhibit oscillatory behavior.
-
The controller requires only reduced model information in the form of steady-state input-output sensitivities of the plant, making it more robust against disturbances and uncertainties than feedforward numerical optimization.
-
Global convergence is guaranteed even for non-convex problems, unlike previous methods that lacked strong guarantees for non-convex scenarios.
-
The controller is straightforward to tune as only the step size needs to be tuned, simplifying the control process compared to schemes requiring multiple parameters like primal and dual step sizes in saddle-point simulations.
Sources
- Linear-Convex Optimal Steady-State Control
- Timescale Separation in Autonomous Optimization
- Projected Dynamical Systems on Irregular, Non-Euclidean Domains for Nonlinear Optimization
- Towards robustness guarantees for feedback-based optimization
Related papers
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction