Online Feedback Equilibrium Seeking Giuseppe Belgioioso Dominic Liao-McPherson Mathias Hudoba de Badyn Saverio Bolognani Roy S. Smith John Lygeros and Florian D orfler

2025-05-02 0 0 1.88MB 16 页 10玖币
侵权投诉
Online Feedback Equilibrium Seeking
Giuseppe Belgioioso*, Dominic Liao-McPherson*, Mathias Hudoba de Badyn,
Saverio Bolognani, Roy S. Smith, John Lygeros, and Florian D¨
orfler
Abstract—This paper proposes a unifying design framework
for dynamic feedback controllers that track solution trajectories
of time-varying generalized equations, such as local minimizers
of nonlinear programs or competitive equilibria (e.g., Nash) of
non-cooperative games. Inspired by the feedback optimization
paradigm, the core idea of the proposed approach is to re-purpose
classic iterative algorithms for solving generalized equations
(e.g., Josephy–Newton, forward-backward splitting) as dynamic
feedback controllers by integrating online measurements of
the continuous-time nonlinear plant. Sufficient conditions for
closed-loop stability and robustness of the algorithm-plant cyber-
physical interconnection are derived in a sampled-data setting
by combining and tailoring results from (monotone) operator,
fixed-point, and nonlinear systems theory. Numerical simulations
on smart building automation and competitive supply-chain
management are presented to support the theoretical findings.
I. INTRODUCTION
Online feedback optimization (FO) [1] is an emerging con-
trol paradigm for optimal steady-state operation of complex
systems based on their direct closed-loop interconnection with
optimization algorithms. FO controllers can handle control
objectives beyond set-point regulation, typically tracking (a-
priori unknown) solution trajectories of time-varying con-
strained optimization problems. In recent years, FO controllers
have been proposed for a wide variety of problem settings [1]–
[7]. These can be categorized by the type of control objective
(e.g., convex or nonconvex) and constraints (e.g., hard or
soft), the dynamics of the plant (e.g., nonlinear, linear, or
algebraic), the type of algorithm (discrete or continuous-time),
and the stability analysis (e.g., continuous-time, discrete-time,
or hybrid), see [1] for a comprehensive list. FO has found
widespread application in various domains, including power
systems (e.g., for optimal power reserve dispatch [2], [3], or
frequency regulation in AC grids [4], [5]), communication
networks (e.g., for network congestion control [6]), and trans-
portation systems (e.g., for ramp metering control [7]).
These large-scale engineering infrastructures comprise mul-
tiple subsystems with local decision authority and preferences,
commonly known as agents. These agents are typically self-
interested, hence, a more general notion of “efficiency” is
needed to model desirable (i.e., safe, locally optimal, and
strategically stable) operating points for such systems, motivat-
ing the use of game-theoretic equilibria (e.g., Nash, Wardrop)
[8]. A timely example are modern supply-chain systems,
*These authors contributed equally to this work. G. Belgioioso, S. Bolog-
nani, R. Smith, J. Lygeros, and F. D¨
orfler are with the ETH Z¨
urich
Automatic Control Laboratory, {gbelgioioso, bsaverio, rsmith,
jlygeros, dorfler}@ethz.ch. D. Liao-McPherson is with the Uni-
versity of British Columbia, dliaomcp@mech.ubc.ca. M. Hudoba de
Badyn is with the University of Oslo, mathias.hudoba@its.uio.no.
This work is supported by the SNSF via NCCR Automation (Grant 180545).
whereas suppliers, manufacturers, and retailers compete over
the available resources (e.g., raw materials, market demand)
to maximize their local profits [9], [10].
There are several classes of control approaches for driving
non-cooperative multi-agent systems to steady-state configura-
tions given by game-theoretic equilibria. One class uses first-
order algorithms and builds on operator-theoretic and passivity
arguments [11]–[13]. Passivity is leveraged in [11] to design
a distributed feedback control law to drive agents with single-
integrator dynamics to a steady-state operating point given by
a Nash equilibrium (NE). This approach is extended to multi-
integrator agents affected by partially-known disturbances in
[12]. The case of games with coupling constraints and agents
with mixed-order integrator dynamics is considered for the first
time in [7]. All the these works consider agents coupled via
their objective functions (and constraints) but with decoupled
dynamics and use continuous-time flows.
A second class of methods are sampled-data approaches
based on the model-free extremum seeking (ES) framework,
for finding optima [14], game-theoretic equilibria [15], [16],
and solutions to dynamic inclusions (which subsume the two
previous cases) [17], [18]. In [15], an ES controller is designed
for NE seeking in games in which the agents have nonlinear
decoupled dynamics. The extension to games with coupling
constraints is presented in [16]. In both cases, practical stabil-
ity is proven in the disturbance-free case. In [17], a general
framework is developed for the design and analysis of a class
ES controllers applicable to optimization as well as non-
cooperative games. Practical stability is established by relying
on the mathematical framework of hybrid dynamic inclusions.
To accelerate convergence, [18] extends the previous frame-
work from periodic to event-triggered sampled-data control.
These methods require nominal stability of the plant and,
typically, time-scale separation assumptions.
A third class of methods are extensions of economic model
predictive control to non-cooperative systems, including multi-
objective MPC [19] and various flavours of game-theoretic
MPC [20], [21]. Unlike the first-order or ES methods, these
consider transient operation and can handle unstable systems.
In exchange, they require dynamic models of the plant and
are typically computationally heavier due to the need to find
accurate equilibria of trajectory games at each sampling time.
In this paper, we propose feedback equilibrium seeking
(FES), an extension of FO that seeks to drive pre-stabilized
dynamical systems to “efficient” operating points encoded by
time-varying generalized equations (GEs). GEs contain con-
strained optimization as a special case and can model a broad
range of equilibrium problems (e.g., Nash, Wardrop). FES con-
trollers are most similar to the first class of control approaches
discussed above [11]–[13]. They are typically based on first-
arXiv:2210.12088v3 [math.OC] 14 Feb 2024
order methods and require an (approximate) steady-state input-
output sensitivity of the plant, which is assumed to stable. As a
result, they are faster than model-free ES methods; on the other
hand, they are slower but computationally lighter than MPC-
based methods, and require only static models. Therefore, FES
controllers occupy a unique middle ground between ES and
MPC. Their greatest advantage emerges in situations where
steady-state input-output sensitivity information is available,
but detailed dynamic models are lacking. Such conditions are
commonly found in sectors like power systems and process
optimization [2]–[5]. Unlike [11]–[13], our framework en-
compasses a broad class of algorithms and systems beyond
continuous-time flows and multi-integrators. Moreover, we
use discrete-time algorithms which is especially relevant for
embedded distributed implementations, as communication in
multi-agent engineering networks is a discrete process.
Some other recent works [22], [23] study the problem of
tracking time-varying generalized NEs (GNEs) with discrete-
time algorithms. A distributed algorithm for tracking the solu-
tion trajectory of an exogenously varying strongly monotone
game is developed in [22] and extended to monotone games in
[23]. In [24], a GNE-seeking algorithm is adapted for online
operation by integrating measurements from a physical system,
however, the plant is treated as an algebraic map. All the
above works neglect dynamic interactions between the plant
and the algorithm (either the variation is exogenous or the
plant is algebraic) while we consider closed-loop stability in
the sampled-data case. This is significant as digital control of
continuous-time plants is currently the dominant paradigm.
Our contribution to this area of research is threefold:
(i) We propose a general framework for designing FES
controllers for continuous-time pre-stabilized nonlinear
systems by tapping into a broad class of first- and second-
order discrete-time algorithms for generalized equations.
This class is broad, and include many optimization
and game-theoretic algorithms (e.g., sequential convex
programming (SCP), proximal-gradient) as special cases.
(ii) We derive sufficient conditions for stability and robust-
ness of the sampled-data algorithm-plant interconnection.
Specifically, we prove practical input-to-state stability
(Def. 1) of the closed loop with respect to exogenous dis-
turbances, under three fundamental conditions: 1. robust
stability of the plant, 2. strong regularity of the control
objective, and 3. robust convergence of the iterative algo-
rithm. Moreover, we prove a sharper notion of input-to-
state stability if an additional small-gain condition holds.
As by-product of our analysis, we also demonstrate that
some popular classes of algorithms are not suitable for
constructing sampled-data FES (or FO) controllers.
(iii) We showcase the utility of our framework by design-
ing two novel controllers based on a SCP algorithm
for nonconvex nonsmooth optimization, and a forward-
backward splitting controller for distributed Nash equi-
librium seeking in dynamically-coupled games. Further,
we illustrate their effectiveness through numerical simu-
lations on smart building and supply chain examples.
We build on our preliminary work [25] which addresses the
Fig. 1. In feedback equilibrium seeking, measurements from a countinuous-
time dynamical system are incorporated into a discrete-time equilibrium
seeking algorithm resulting in a coupled sampled-data cyber-physical system.
special case of strongly monotone GEs, globally linearly con-
vergent algorithms, and exponentially stable plants. Our results
here provide a significant extension that allows non-monotone
GEs, locally-stable nonlinear plants and non-linearly locally
convergent algorithms. This algorithmic extension is partic-
ularly important since it captures many practically relevant
cases, such as algorithms for nonconvex optimization, which
are not globally convergent, and primal-dual and distributed al-
gorithms which typically exhibit sub-linear convergence only.
II. PRELIMINARIES
Basic notation: Denote by Iand id the identity matrix and
operator, respectively; by lim and sup the limit and essential
suprema, respectively. Given P=P0and xRn,
|x|P:= xP x with the convention |x|=|x|I.
Systems Theory: Continuous-time signals are denoted by
Ln={f:R0Rn}and sequences by n={f:
Z0Rn}. Given xLnand yn, we consider
the signal/sequence norms x= supt0|x(t)|and y=
supk0|yk|. A function γ:R0R0is of class Kif
it is continuous, strictly increasing, and satisfies γ(0) = 0.
If it is also unbounded, then γ∈ K. Similarly, a function
σ:R0R0is said to be of class Lif it is continuous,
strictly decreasing, and satisfies σ(s)0as s→ ∞. A
function β:R0×R0R0is of class KL if β(·, s)∈ K
for each fixed s0and β(r, ·)∈ L for fixed r. Class K
functions obey a weak triangle inequality [26, Lemma 10]:
a, b 0and α∈ K, α(a+b)α(2a) + α(2b).(1)
For γ1, γ2:RR,γ1γ2denotes the composition. Given
ξRn,uLmand f:Rn×RmRn,xLnis a
solution of the initial value problem
˙x(t) = f(x(t), u(t)), x(0) = ξ. (2)
If it is uniformly continuous, obeys the initial condition and
satisfies the differential equation almost everywhere.
Definition 1 (LISpS [27]).Consider a system
x(t) = f(x(t), u(t)), x(0) = ξ(3)
with solution x(t, ξ, u)(where either x(t) = ˙x(t)and tR0
or x(t) = x(t+ 1) and tZ0) and let ¯xbe a reference
signal. The system (3) is said to be Locally Input-to-State
Practically Stable (LISpS) about ¯xwith respect to uif there
exists ϵ > 0,β∈ KL,γ∈ K, and b > 0such that,
t0,|x(t, ξ, u)¯x(t)| ≤ β(|ξ¯x(0)|, t) + γ(u) + b,
provided |ξ| ≤ ϵand u∥ ≤ ϵ. If b= 0 then (3) is Locally
Input-to-State Stable (LISS) about ¯xwith respect to u.
Operator Theory [28]: Given a closed convex set Rn,
ι:Rn→ {0,∞} denotes its indicator function, N: Ω
Rnis its normal cone operator, and proj:Rnis the
Euclidean projection onto . A set-valued mapping F:Rn
Rnis µ-strongly monotone, if (uv)(xy)µxy2
for all x̸=yRn,u∈ F(x),v∈ F(y), and monotone if
µ= 0;fix(F) = {xRn|x∈ F(x)}and zer(F) = {x
Rn|0∈ F(x)}denote the set of fixed points and of zeros of
F. For a convex function f:RnR,f :RnRndenotes
the subdifferential mapping in the sense of convex analysis.
Definition 2 (Strong Regularity [29]).A set-valued mapping
Ψ : RnRnis said to be strongly regular at (x, y)if and
only if yΨ(x)and there exist neighborhoods Uof xand
Vof ysuch that the truncated inverse mapping ˜
Ψ1:V7→
Ψ1(V)Uis a Lipschitz continuous function on V.
III. PROBLEM SETTING
We consider the problem of efficiently operating a physical
plant described by the following nonlinear state-space system
˙x(t) = f(x(t), u(t), w(t)),(4a)
y(t) = g(x(t), w(t)) (4b)
where xLnxis the state, yLnyis the output, uLnuis
the control input, with u(t)∈ U for all tR0, and wLnw
is a disturbance satisfying w(t)∈ W for all tR0.
We adopt the “stabilize-then-optimize” paradigm, and as-
sume that (4) is stable1and has a steady-state map p:
U × W Rnxsatisfying f(p(u, w), u, w)=0for all
u∈ U, w ∈ W and a steady-state input-output map
h(u, w) = g(p(u, w), w).(5)
Formally, we assume the system (4) satisfies the following
properties that ensure its solution trajectories and steady-state
mappings are well defined.
Assumption 1 (Robust Stability of the Plant (4) with respect
to parameter variations).(i) fis locally Lipschitz; (ii) gis
globally Lg-Lipschitz; (iii) wis continuously differentiable,
and ˙wLnwsatisfies ˙w<; (iv) Wand Uare
compact and convex; (v) (4) is LISS [27], namely, there exists
1If the physical plant (4) is not stable, it can be pre-stabilized by replacing
f(x, u, w)with f(x, k(x, v), w), where vis the new input (for example, a
reference command) and kis a stabilizing controller.
ϵx, ϵw, α3, α4, α5>0, a continuously differentiable function
V, and σ1∈ K such that for any constant u∈ U
α3|xp(u, w)|2V(x, u, w)α4|xp(u, w)|2,
˙
V(x(t), u, w(t)) ≤ −α5V(x(t), u, w(t)) + σ1(|˙w(t)|),
if V(x(t), u, w(t)) ϵxand |˙w(t)| ≤ ϵw.
Our control objective is to design an output feedback con-
troller that drives (4) and maintain it near efficient operating
conditions. We encode “efficiency” using the following struc-
tured generalized equation (GE), parameterized by w∈ W:
0G(z, s) + A(z)(efficiency objective) (6a)
s=h(u, w),(steady-state map) (6b)
u=q(z),(ctrl state to input map)(6c)
where zRnzis an auxiliary variable, sis the steady-state
output of (4), G:Rnz×RnyRnzis a single-valued
mapping2,A:RnzRnzis a set-valued mapping, and
q:Rnz→ U is the output mapping. The notion of efficiency
encoded in the GE (6) is flexible and encompasses a wide
variety of useful objectives, notably constrained optimization
(e.g., minimizing energy consumption as described in VII-A)
and generalized Nash equilibria. The auxiliary variable zis the
internal state of the controller, and it also allows the modelling
of optimality and equilibrium conditions that involve dual
variables, such as KKT critical points. Two concrete examples
are provided at the end of this section.
Our control objective is to maintain the system (4) near
solutions of (6); we must impose some regularity conditions
to ensure that this is a well-defined problem. Substituting (6b)
and (6c) into (6a) yields the following compact GE:
0G(z, w) + A(z),(7)
where G(z, w) = G(z, h(q(z), w)). The parameter-to-solution
mapping S:W Rnzis defined as
S(w) = {zRnz|0G(z, w) + A(z)}.(8)
For a given wLnw, the set of solution trajectories is
S(w) = {zLnz| ∀t0, z(t)S(w(t))}.(9)
The following assumption ensures that tracking solution tra-
jectories in Sis a well-posed problem.
Assumption 2 (Strong Regularity of the GE).(i) qis globally
Lq-Lipschitz continuous, (ii) Gis continuously differentiable,
and (iii) the mapping G(·, w) + A(·)in (7) is strongly regular
at all points satisfying zS(w), for all w∈ W.
Conditions for strong regularity are context-dependent, as
detailed later in this section with two examples. In optimiza-
tion contexts, it reduces to having a strong local minimizer
and unique dual variables, which follows by second-order
sufficient conditions and suitable constraint qualifications.
In general, the set S(w)can be complex and multi-valued,
thankfully Assumption 2 imposes some structure on S(w).
2For notational simplicity Gdoes not depend on w, this is without loss of
generality since wcan be included in s.
Theorem 1. [30, Theorem 3.2] Under Assumption 2, for
any wLnw, there exist mLipschitz continuous mappings
¯ziLnz,i∈ {1, . . . , m}, such that S(w) = {¯z1,...,¯zm}.
Remark 1. Theorem 1 demonstrates that the solution map
consists of misolated w-parameterized trajectories called
“branches”. These branches generalize the notion of a isolated
local solution of a GE (in the context of optimization, a strict
local minimizer) to a parameterized setting. Our analysis will
eventually establish tracking error bounds and the existence
of a region of attraction around each branch.
We can now formally state our control problem.
Problem. Design an output feedback controller so that the
system (4) tracks the input and output trajectories3u=q(z)
and y=h(u, w), for some z∈ S(w)and wLnw.
The GE (6) allows us to naturally express complex control
objectives, e.g., constraints can be readily encoded into A
using normal cone operators (see Example 1.A). Similarly
to FO [1], we assume that the dynamic model of the plant
(4) is unknown and that the exogenous disturbance wis not
measurable. However, the output ycan be measured and the
input-output steady-state sensitivity uh(u, w), or an approxi-
mation of it, is available. Robustness of FO controllers to static
input-output modelling error is analytically studied in [31] and
experimentally in [32]. The inability to measure wis common
in practical applications. For example, in power systems, w
represents variable micro-generation and uncontrollable loads
caused by consumers drawing power from the grid.
Example 1.A. Nonlinear Programming (NLP)
Consider the w-parameterized nonlinear program (NLP)
min
ξ,u ϕ(ξ, u) + φ(ξ)(10a)
s.t. ξ=h(u, w), u ∈ U (10b)
where ϕ:Rny×RnuRand hare twice continuously
differentiable, and φ:RnyR∪ {∞} is a proper lower
semicontinuous convex function [28, Def. 9.12], e.g., an 1-
norm. We assume that (10) is always feasible, namely,
{(ξ, u)|ξDom φ, u ∈ U, ξ =h(u, w)} ̸=,w∈ W.
The associated partial Lagrangian function is
L(ξ, u, λ, w) = ϕ(ξ, u) + λ(h(u, w)ξ),(11)
where λRny
0is a dual variable, and the KKTs for (10) are
0∈ ∇ξL(ξ, u, λ, w) + φ(ξ)
0∈ ∇uL(ξ, u, λ, w) + NU(u)
0 = λL(ξ, u, λ, w) = h(u, w)ξ
(12)
This is a special case of the GE in (6), with z= (ξ, u, λ),
0
ξL(ξ, u, λ, w)
uL(ξ, u, λ, w)
sξ
| {z }
G(z,s)
+
φ(ξ)
NU(u)
0
| {z }
A(z)
,(13)
3With an abuse of notation, we extend the mappings hand qto take signals
as arguments, in the sense of u(t) = q(z(t)) for all tR0.
s=h(u, w)and q(z) = [0 I0]z. The following statement
provides sufficient conditions for strong regularity of (13).
Lemma 1. Consider any w∈ W, a KKT point ¯z= (¯
ξ, ¯u, ¯
λ)
S(w), and let ζ= (ξ, u). Then, the condensed GE (7) associ-
ated with (13) is strongly regular at ¯zif ζ2
ζL(¯z, w)ζ > 0
for all ζ= (ξ, u)satisfying ξ=uh(¯u, w)u.
Proof. The proof is identical to that of [33, Theorem 7].
The condition in Lemma 1 is known as a second order
sufficient condition and can be checked numerically4if ¯zis
known. Conditions of this type are standard in the analysis of
Newton’s method and sequential quadratic programming, see
e.g., [34, Theorem 1.13, Theorem 4.14].
Example 2.A. Generalized Nash Equilibrium Problems
Consider a set of Nagents labelled by i∈ I:={1, . . . , N }.
Each agent i∈ I chooses a control action uifrom a polyhedral
set Ui:= {ξRni|Biξbi}, and has a cost function
Ji(ui, s)that depends on its own action, ui, and the actions
of other agents, ui= (u1, . . . , ui1, ui+1, . . . , uN), through
the steady state of the physical system s=h(u, w), where u=
(u1, . . . , uN). Moreover, the actions of all agents are linked
via affine coupling constraints of the form Au b, modelling
limited availability of shared resources [8]. The agents are
self-interested and want to optimize their own local cost. The
resulting collection of the Nparameterized inter-dependent
optimization problems constitutes a parametrized game:
i∈ I :(min
ui
Ji(ui, h(u, w)) =: Ji(ui, ui, w)
s.t. Au b, ui∈ Ui
(14)
From a game-theoretic perspective, a relevant solution concept
for (14) is the generalized Nash equilibrium, where no agent
can unilaterally reduce its cost [35].
Definition 3. A feasible action profile ¯u= (¯u1,...,¯uN)is a
generalized Nash equilibrium (GNE) of the game (14) if
Ji(¯ui,¯ui, w)min
ui∈Ui{Ji(ui,¯ui, w)|A(ui,¯ui)b},
holds for all agents i∈ I.
If each Jiis continuously differentiable and convex with
respect to ui, a GNE can be found by solving a system of
coupled KKT conditions of the problems (14) [35, Th. 4.8]:
(0∈ ∇uiJi(ui, ui, w) + A
iλ+NUi(ui),i∈ I
0bAu +NRm
0(λ),(15)
where λRmis a dual variable associated with the coupling
constraints Aub0. The set of solutions to (15) is a special
subclass of GNEs, known as variational GNEs (v-GNEs) [35].
To write (15) in a compact form, we define the pseudo-
gradient F(u, w) = F(u, h(u, w)) = [uiJi(ui, h(u, w))]i∈I
obtained by stacking up the partial gradients of the local cost
functions Ji, i.e., uiJi(ui, h(u, w)) =: Fi(u, h(u, w)). The
4Specifically, if Zis a basis for the nullspace of [I− ∇uh(¯u, w)] then
the regularity condition is equivalent to ZT2
ζL(¯z, w)Z0which can be
checked using e.g., a Cholesky factorization.
摘要:

OnlineFeedbackEquilibriumSeekingGiuseppeBelgioioso*,DominicLiao-McPherson*,MathiasHudobadeBadyn,SaverioBolognani,RoyS.Smith,JohnLygeros,andFlorianD¨orflerAbstract—Thispaperproposesaunifyingdesignframeworkfordynamicfeedbackcontrollersthattracksolutiontrajectoriesoftime-varyinggeneralizedequations,suc...

展开>> 收起<<
Online Feedback Equilibrium Seeking Giuseppe Belgioioso Dominic Liao-McPherson Mathias Hudoba de Badyn Saverio Bolognani Roy S. Smith John Lygeros and Florian D orfler.pdf

共16页,预览4页

还剩页未读, 继续阅读

声明:本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知玖贝云文库,我们立即给予删除!
分类:图书资源 价格:10玖币 属性:16 页 大小:1.88MB 格式:PDF 时间:2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务
/ 16
客服
关注