Optimization Algorithm Design via Electric Circuits
Authors: Stephen P. Boyd
Tetiana Parshakova
Ernest K. Ryu
Jaewook J. Suh
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Convex optimization
Distributed optimization
Decentralized optimization
ADMM
Alternating direction method of multipliers
PG-EXTRA
Performance estimation problem
Continuous-time analysis
first-order optimization
proximal methods
Primary area: optimization
TL;DR: We design optimization algorithms using electric RLC circuits.

Abstract: We present a novel methodology for convex optimization algorithm design using ideas from electric RLC circuits. Given an optimization problem, the first stage of the methodology is to design an appropriate electric circuit whose continuous-time dynamics converge to the solution of the optimization problem at hand. Then, the second stage is an automated, computer-assisted discretization of the continuous-time dynamics, yielding a provably convergent discrete-time algorithm. Our methodology recovers many classical (distributed) optimization algorithms and enables users to quickly design and explore a wide range of new algorithms with convergence guarantees.

Optimization Algorithm Design via Electric Circuits
Stephen P. Boyd Stanford University
Tetiana Parshakova" Stanford University
Ernest K. Ryu UCLA
Jaewook J. Suh' Rice University
Abstract
We present a novel methodology for convex optimization algorithm design using ideas from electric RLC circuits. Given an optimization problem, the first stage of the methodology is to design an appropriate electric circuit whose continuous- time dynamics converge the solution of the optimization problem hand. Then, the second stage is an automated, computer-assisted discretization of the continuous- time dynamics, yielding a provably convergent discrete- algorithm. Our methodology recovers many classical (distributed) optimization algorithms and enables users to quickly design and explore a wide range new algorithms with convergence guarantees.
Introduction
In the classical literature of optimization theory, optimization algorithms designed with the goal of establishing fast worst-case convergence guarantees. However, these methods, designed with the pessimistic framework of worst-case analysis, often exhibit slow practical performance. In the modern machine learning literature, optimizers are designed with the goal of obtaining fast empirical performance set of practical problems of interest. However, these methods, designed without consideration of the feasibility of a convergence analysis, tend to be much more difficult to analyze theoretically, and such methods sometimes even fail converge under nice idealized assumptions such as convexity [92, 131].
In this work, present novel methodology for convex optimization algorithm design using ideas from electric RLC (resistoriidductorcccaaicc circuits and the performance estimation problem [54, 150]. (To clarify, our proposal does not involve building physical circuit.) Specifically, our methodology provides a quick and systematic recipe for designing new, provably convergent optimization algorithms, including distributed optimization algorithms. The ease of the methodology enables users to quickly explore a wide range of algorithms with convergence guarantees.
Optimization problem formulation.
We consider the standard-fone optimization problem minimize
f(x)
subject to x E R(ET), )
where x E R" is the optimization variable, f: R + R U foo} is closed, convex, and proper, and E E Rm Assume we have n nets N1...., Nr forming partition of (1....,m} m). More specifically, we let E E Rn be a selection matrix defined as
+1 if E N₂ otherwise.
Eg
Our goal is to find primal-dual solution satisfying the KKT conditions [126, Theorem 28.3]
E @f(x), R(ET), E
(3)
As show through examples, this standard-form problem (1) conveniently models many optimiza- tion problem setups of practical interest.
"Lead authors (author list ordered alphabetically)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In the analysis and design of optimization algorithms, standard approach is to consider continuous- time model of a given algorithm, corresponding to the limit of small stepsizes [124, 79, 6, 156, 143, 93, 86, 137]. Our work is based on the key observation that such continuous-time models can be interpreted as RLC circuits connected to the subdifferential operator θf, which we interpret as nonlinear resistor. We expand on this observation and propose a general methodology for designing optimization algorithms by designing RLC circuits that relax to the nets defined by E.
Example. Problem (1) represents a general form of distributed optimization, where the constraints enforce consensus among the primal variables, An example is the so-called consensus problem [30, $7]
minimize Bioony NER ERT/NN subject to I1
fi + ...4-.. (xNN
IN,,
where (#1,-... EN) is the decision variable, the objective function f(x) f1(11) (N(NN) is block-separable, and ET ....../ I) Rmxm/NN Refer to sections $E and $F, for an overview of classical splitting methods and decentralized methods for solving (1).
1.1 Preliminaries and Notation
We generally follow the standard definitions and notations of convex optimization [31, 118, 23, 119, 129]. Consider the extended-valued function f: R" R {oo). We say f is closed if its epigraph is closed set in R and proper if its value is finite somewhere. We say f is CCP if it closed, convex, and proper. For > we say f is R-smooth
is finite and differentiable
everywhere and f[v ff(y)] < R|| - yll for all x, R" For μ > 0. say f is u-strongly convex f(x)- - (n/2)[==|] is convex. Let (y)
[y== sup, (y. z) - fxx) denote 0 and CCP f. define the R-Moreau envelope of as
the Fenchel conjugate of f. For R
"f(x) = inf=er" {f(=) + 2R || = = One can show [23, Proposition 13.24] that the R-Moreau
envelope is given by "f (f" | 112) If is 1/ Rmooth,,
define [23, Theorem 18.15]
the R-pre-Morent envelope of as
-f - | 1??),
which is defined such that (²{)= S.
Due to the limited space, we defer the review of prior works to $A of the appendix.
1.2 Contributions
Our work presents two technical novelties, one in continuous time and the other in discrete time. The first is the observation that many standard optimization algorithms can be interpreted as discretizations of electric RLC circuits connected to the subdifferential operator 0f. The second is the use of the performance estimation problem obtain an automated recipe for discretizing convergent continuous- time dynamics into convergent discrete-tin time algorithms, and we provide code implementing our automatic discretization methodology.
By combining these two insights, we provide a quick and systematic methodology for designing new, provably convergent optimization algorithms, including distributed optimization algorithms. We provide an open-source package that implements automatic discretization of our circuits:
https://githhh wtt.gth.......cgggeeeeeeemmeeeee http:///ggp/ppp.iiaaaiiiooooooo http:/iiitttaiiiiiiiiiiiiiee circuits
Continuous-time optimization with circuits
2.1 Interconnects
We now describe two types of electric circuits that we call static and dynamic interconnects. Both interconnects have terminals, and we will later connect them to the inputs of Òf.

---

Static interconnect. The static interconnect is a set of (ideal) wires connecting terminals and forming nets. See Figure for an example. Let z E R" be a vector of terminal potentials and y e RT be a vector of currents leaving the terminals. Using matrix E E Raxm as defined in (2), we can ex- press Kirchhoff's voltage law (KVL) as R(FTT) and Kirchhoff's current law (KCL) as y E (F).. In other words, the static interconnect enforces the relationship
Static interconnect
(x, ( ((ET) x (B)..
(4)
Dynamic interconnect. The dynamic intercon- nect is RLC circuit with terminals and I ground node. We assume all inductances and capac- itances have values in (0, oo) while the resistances have values in [0, oo). (A 0-ohm resistor is an ideal wire. We do not permit ideal wire loop.) Each RLC component has two (scalar-valued) terminals: the + and terminals.
N2
Figure 1: Example of static interconnect,
m 5, Ni = (1,3), N2 = (2, 42. NN. = {5).
Denote the number of nodes the RLC circuit by т. Connect nodes .. ... to terminals 2, m. and let the last node, node be the ground node. (This implies 2 + 1.) Denote the number RLC components by a. We describe the topology with a reduced node incidence matrix (with the bottom row corresponding to the ground node removed) A E ( defined as
+1 if node connects to terminal of component j
Ag
if node connects to terminal of component j otherwise.
See Figure 2 for example.
Dynamic interconnect
81
R1
R2
Rs
L
L2
C1
C2 0
1
0
0
1
0
0
890
322
0
+1
0
0
0
0
0 0
La
88
3
0
0
0
0
0
3
A
0
0
+1
0
0
844
0
0
0
0
0
-1
+1
01
85
-1
0
0
+1
+1
0
8
7
0
-1
-1
0
0
+1
0
C9
Figure 2: Example a dynamic interconnect with 7 = 8 nodes, o = 7 RLC components, m = terminals, and 1 ground node. Reduced node incidence matrix A is provided. (R2 and R3 0-ohm resistors.) This dynamic interconnect admissible with respect to the static interconnect of Figure 1.
The ground node is designated to have 0 potential, and the potential of any node is the potential relative to ground. The vollage across component the difference of potentials between the and terminals. The current through a component is defined as the current flowing from the + terminal the terminal.
Let x E Rd be the potentials at the m terminals, which are connected to nodes 1, 1,..., m. and y E R" be the currents leaving the terminals. Denote the node potential vector with the ground node excluded (since the potential at ground is 0) by
E R
So, E RT-1-m denotes the potentials at the non-terminal nodes. Denote the vector of voltages by Rd and the vector of currents by i R". Then, the currents and voltages of the dynamic

---

interconnect satisfy the following V-I relations
x e (KVL)
ii Ai
(KCL)
(ii) C = At
(v) De d dt ve (Capacitor)
(iii) DR DRiv (Resistor)
(iv) Vc De (Inductor)
where DR, De, and De diagonal matrices respectively with resistances, inductances, and capacitances values the diagonals.
Admissibility. When an RLC circuit reaches equilibrium, voltages across inductors and currents through capacitors are O. We say a dynamic interconnect is admissible relaxes to the static interconnect equilibrium. Mathematically, this condition is expressed as
(z. v)
Ai
0 -0= AT
x c
= DRİR, 0, = = R(ET) x (E)).
As an example, the dynamic interconnect of Figure admissible with respect to the static intercon- nect of Figure 1.
2.2 Composing interconnects with f
We view the subdifferential operator Of as an m-terminal electric device that is also grounded. Let E Rnh be the potentials at the m terminals (excluding ground) and y E RTh be the currents flowing into the terminals. The f operator enforces the V-I relation
y E 0f(x).
We connect the terminals of 0f to the terminals of the static and dynamic interconnects. Immediately, connecting the static interconnect with 0 enforces the V-I relations (4) and y E 0f(x), which combine be the optimality condition (3). Therefore, the potentials at the m terminals vector in R" m is an optimal x* E RD solving (I). To clarify, connecting the static interconnect with 0f leads static circuit in the sense that the potential z and current y do not depend on time.
Statie interconnect
vi
21
1/5
x
y5
3/
Figure 3: The static interconnect of Figure 1 connected with 0f. The potentials the terminals is an optimal x* e R" solving (I),
Next, we compose (connect) the dynamic interconnect with 0f. Due to capacitors and inductors, this circuit is dynamic in the sense that the voltages u(t) and æxt) and currents i(t) and y(t) depend on time, although we often omit explicitly writing the t-dependence for notational convenience. Then, the V-I relations the dynamic interconnect combined with y E af(x) leads to the V-I relation
{(,,0) BE @f0(()), Ai [
x
AT
(5)
c
VR DRiR, vc Dr d DeTic ic, ic De te (0,
d
where v(t) (1), (z))), ve(()) E Rº, i(l) (()(() (r(t) E R" and y(t) E Rd for oo).
R Re)e())
E RT-

---

Dynamic interconnect
su(())
sx(()
#2(f)
sa(e)
ma(t)
of
su(()
m4())
us(()
xz(f))
Figure 4: The dynamic interconnect of Figure 2 connected with 0f. The potentials at the terminals satisfy x(1) + for an optimal x R solving (1) under the conditions Theorem 2.2.
Under appropriate conditions, the dynamics (5) is mathematically well-posed in the sense that there exist unique Lipschitz- continuous curves utt), i(t), ætt), and y(t) satisfying the V-I relation (5) as hipschitz-omminuouss
formalized in the following Theorem 2.1. The proof, which utilizes the machinery of monotone operator theory [21, 23, 129], is provided in şB of the appendix.
Theorem 2.1. Assume p-strongly convex and M- -smooth. Suppose (v") , 10, ,,,,,"" ,38) satisfy
0
A
o AT
DR gd vf(x²).
Then there unique Lipschitz continuous curve (v, i, y): 00 20) - R x R R R" satisfying the conditions in (5) and the initial condition (v(0), ((0), (00), v()) = (v x .8))
Equillibrium yields primal-dual solution. With the dynamic interconnect composed with Of. we generically expect the circuit state (v(1), i(t), æ(t), v(t)) to converge (relax) to an equilibrium state. The admissibility condition ensures that at such equilibrium, (ær, y) will be primal-dual solution. We formally state this fact as Theorem C.2 of the Appendix.
2.3 Energy dissipation
Let (v*, ""","", xxx,,," ,²))") be equilibrium of an admissible dynamic interconnect composed with 0f. Since the voltages across resistors and inductors and the currents through capacitors are zero under equilibrium, we have
-² -'= v2,, v = (0, 0, o2),
==
(2 i2) = (0, 12, 0).
(We formally show this in Theorem C.2 of the appendix.) Define the energy the circuit at time as
1
{() こ ||ec(t) vBll + [lic(t) i
(6)
which is dissipative (non- (non-increasing) quantity:
d 3 = (ve vē, ic - it) + (ic - i2, VC. - v2)
dt
| 11 (xr x y²) S 0.
Here, we use i = 0 and vz = and the fact that the power dissipated by the resistors and 0f must come from the energy stored in the capacitors and inductors. This dissipativity property leads the following continuous-time convergence.
Theorem 2.2. Assume f: R R is strongly convex and smooth. Assume the dynamic interconnect admissible, and let , be a primal-dual solution pair. Let (v(t), (o(t), v()), be curve satisfying (5). Then,
lim (x(1),(()) (x", 10000
Theorem 2.2 largely follows as a corollary of Theorem 2.1. The formal proof is provided in &D of the appendix. In $4, we present systematic framework for finding discretized versions of Theorem 2.2 the corresponding discretized algorithms.
5

---

Circuits for classical algorithms
In this section, present circuits recovering the classical Nesterov acceleration, decentralized ADMM, and PG-EXTRA. For additional examples and detailed derivations, refer to $E and &F the appendix, where provide circuits and analyses of classical algorithms such gradient descent [35], proximal point method [125]. proximal gradient method [42], primal decomposition [72, 140), dual decomposition [59, 96, 63, 142], Douglas-Rachford splitting [123, 53, 101], Davis-Yin splitting [46], decentralized gradient descent [116, 171], and diffusion [33, 34].
Multi-wire notation. We start by quickly introducing the multi- wire notation depicted Figure 5. When optimizing f: R + R and using the m-terminal device 0f. interconnects that have the same RLC circuit across each net, i.e.. the dynamic interconnect consists of m identical copies of the same RLC circuit for the m coordinates of x e RT this case, we use the diagonal-line notation depicted in Figure 5.
will often use dynamic
m
Figure 5: Multi-wire notation.
Moreau envelope. We use the following simple identity throughout this work: 0f composed with resistor is equivalent to (x))
R
Rf
To clarify, the equivalence means the two circuits impose the same V-I relation the pins of To see this, note [i) = (x a)] + = prox (x)] and use the identity for the gradient of the Moreau envelope conclude
(=f(x)= 1 (x nr (x))
1 1 -
R
R
See $E.1 of the appendix for further details.
3.1 Nesterov acceleration
Let f: Th R be 1/ R-smooth convex function. Then, the circuit corresponding the classical Nesterov acceleration is given below.
R
R
R
V
0f
0000
0000
The use of a negative resistor R may seem unconventional, but the fact that this circuit is stable easier see consider the equivalent circuit with the pre-Moreau envelope f. f.i.e,, is the convex function such that Ri- = f. clarify, negative resistors satisfy the same V-I relations of the standard resistors but with negative slope. Negative resistors have also been considered in [153].
The V-I relations of this circuit lead the ODE
d² R
dt" x. ( R22
d
R
dia x
+
L ((())
v((=) =
LC
If we set R = LL/C which can be interpreted as an instance of critical damping [164, 174, 40], L B and C = 2/H,, we recover the Nesterov ODE [162]
&
Te 22 Vf(x) = 0.
We also quickly point out that other choices parameters lead to the high-resolution ODE introduced in [136]. See $E.3 of the appendix for further details.

---

3.2 Decentralized ADMM
Let fi..... fN: R" + R {oc} be CCP functions. Consider a decentralized optimization setup with graph G. We provide the full description of the decentralized setup and notations in $F of the appendix. Define r be the neighbors of in graph G. For simplicity, we only illustrate the circuit related to nodes and I, where and l are directly connected through an edge in the graph G.
The circuit corresponding decentralized ADMM [74, 71, 70, 157, 139] is given below.
ffz
Of
mm
200
f.
R
0000
F.
R
0000
f.
R
F.
R
In the following, the left column presents the dynamics of the continuous-ting circuit and the right column presents the discretization with stepsize L/ R, recovering the standard decentralized ADMM:
0j
1
Σ KET
RRic + est)
a k+1 1
rTl
(RiZ + ex)
TET
2j (POX(R//T,D1A) (az)
(roX(n/II)D1, (a))
eg 2 + 21)
5 A+1
2 (e) + +2tt1)
di icu 7 (ey) m.))
d2 t2zt + [ [e// let1 - 22/ 1
for every node 1, N and every edge (i,) in graph G.
3.3 PG-EXTRA
Let fI...., RT + RUfoo be CCP functions and f1, ... hyy : R be convex M -ssmohhh functions. Consider a decentralized optimization setup with graph G. The circuit corresponding to PG-EXTRA [138] is given below.
Of
m
WW
Vhu
Lp
Ry
0f,
Vh
R
-R
Define the mixing matrix W E R
N
with
1
EIET
R₁i
R
if
W
if IeT,
R2
otherwise.
7

---

In the following, the left column presents the V-I relations for the continuous-time circuit and the right column presents the discretization with stepsize 2. recovering the standard PG-EXTRA:
= proxRs RfG
Σ
Waa - RV)5(1z) ws)
2 = prox R1
Σ W W (V),(
N
d dt
Σ Wattn
w k41 = w
(1) Σ W Wssat)
w, Bzz
for every node ,,... N and every edge (i,1) in graph G.
4 Automatic discretization
We discretize the continuous-times dynamics given by the circuit with an admissible dynamic intereon- nect using two-stage Runge-Kutte method with parameters a, 8 and stepsize h >> 0. The explicit form of the discretization is stated in ÅG of the appendix. Let {(r*, 8², x. ] be the iterates generated by the discretized algorithm. Then the energy stored in the circuit at time kh is
E = vb +
1 2 2 -2
To guarantee convergence of the discretized algorithm, we search for discretization parameters that ensure the & & ... sequence is dissipative in the following sense. Specifically, we say the algorithm or the discretization is sufficiently dissipative if there is an 1j > such that
(8) holds for all k = 1,2, ..... This requirement is analogous to the "sufficient decrease" conditions in optimization [31, 121]. The following Lemma 4.1, which proof we provide in $G of the appendix, states that sufficient dissipativity ensures convergence under suitable conditions.
Ex+1 E + n/(x* - x², v² v²} S O.
Lemma 4.1. Assume f: Rm + RU {oo} is a strictly convex function and the dynamic interconnect explicitly stated in $G of the ap-
is admissible. If the two-stage Runge-Kunte discretization, pendix, generates a discrete-time sequence {(x*, i ,x, ,a*,y") ]== satisfying the sufficient dissipativity condition (8), then x² converges to a primal solution.
We find such discretization with the following automated methodology. Given a discretization characterized by (a, h), the dissipativity condition (8) for given v) > implied if the optimal value of the following optimization problem is non-positive:
maximize subject to
E- El + nk xx,x"""" 1²- -v")
E, 1 1lu@ vellipe - S (1,2)
(v) i xx ,y is feasible initial point
(u2 12, x², y is generated by discrete optimization method from initial point
FE
where f, 1 x., y² v", ,",,",, xx, 3y" are the decision variables and F is a family of functions (e.g., L-smooth convex) that the algorithm is to be applied to. Here, is homogeneous with respect to & (i.e., (8) essentially has no k-dependence), and therefore it is sufficient verify the condition for k out that (9) can be solved exactly as a semidefinite program (SDP) for many commonly considered function classes F. This technique was initially proposed the performance estimation problem (PEP) [54, 150], a computer-aided methodology for constructing convergence proofs of first-order optimization methods. See, e.g., PEPit [76] package that implements PEP in Python.
using the fact that (8)
but for all feasible initial points (u ; sr ,y²). It turns
Further, (9) can be posed as nonconvex quadratically constrained quadratic problem (QCQP) with only few tens of variables and such problems be solved exactly with spatial maucchandd-ount algorithms [2, 102, 80, 98, 45].
In conclusion, we can solve non-convex QCQP to find provably convergent discretization of the continuous-ting circuit with an admissible dynamic interconnect. We use the Ipopt [155, 9] solver. Further details are provided in SG of the appendix.
8

---

Example. Consider the following example circuit for the minimization of a convex function f. Let Ri R₂ R3 1, and C₁ C₂ 10.
Cs
C1
Rl
7
as
With our automatic discretization methodology, we find the sufficiently dissipative parameters
6.66,
h = 6.66,
0, B == 1.
The resulting provably convergent algorithm
x² = prox (1)) 3² = 2(x x²
w k+1 wº 0.33
-033 * + +3w*)
s+1 W² 0010.1 +3w*).
is provably convergent under the condition that f is strictly convex, SH for details.
Experiments
5
In this section, we use our methodology to obtain a new algorithm and experiment with it specific problem instance. Consider a decentralized optimization problem with communication graph G with N nodes and 7 edges, as shown in Figure 8. Specifically, we consider the optimization problem
Figure 8: Underlying graph G.
minimize ZER100
Eie(4.5) (||x- bill2 + || be bell)) Eig(4.5) ||x bell2,
where each agent E (1...., 6) holds the vector b, E R 100 To leverage the strong convexity fa and Js, we propose modification to the DADMM circuit described in $F.3. Given that circuit with a capacitor and inductor corresponds to momentum method (see $3.1), and momentum is known accelerate convergence for strongly convex functions [124], we add a capacitor to 645 to DADMM circuit as shown in the left column of Figure 9. We then discretize the circuit and refer the the resulting algorithm DADMM+C. We apply DADMM+C problem and observe a speedup as shown in the right columns of Figure 9. The relative error for DADMM+C decreases to 10 10 in 66 iterations, for DADMM in 87 iterations and for P-EXTRA in 294 iterations. For further details, see II.1 of the appendix.
the decentralized optimization
"Our pipeline has a final verification stage that numerically checks whether point returned by the Ipopt solver is indeed feasible for the small QCQP. Strictly speaking, our theoretical convergence guarantee relies the correctness of this numerical verification of feasibility.

---

0f4
0ʃ
100
PEXTRA Cheatt DADMM
10
If(a") 11"""
10-5
10
10-20
C
20
100
Iteration
Figure 9: (Left) Circuit of DADMM+C. Compared to the DADMM circuit of SF3,, the DADMM+C circuit has an additional capacitor. (Right) Relative error ff(²)) -
f f vs. iteration count.
Further, we define general version of the DADMM+C method for any connected graph and establish a general convergence proof Lemma I.1 of $1.1.1 of the appendix. This convergence analysis demonstrates how convergence proof. Finally, we provide another set of similar experiments $1.2 of the appendix.
methodology discover new family of methods with classical
6 Conclusion
In this work, we present a novel approach to optimization algorithm design using ideas from electric RLC circuits. The continuous-ting RLC circuit models combined with the automatic discretization method provide foundation for designing algorithms that inherently possess convergence guarantees. Further, provide code implementing the automatic discretization. Our framework opens the door to future research by applying this methodology to a broader range of optimization problems and extending the problem other setups, such the stochastic optimization setup.
Acknowledgments and Disclosure of Funding
This work supported by the Samsung Science and Technology Foundation (Project Number SSTT-BA2101-00 01-0),, the National Research Foundation of Korea (NRF) grant funded by the Korean government (No.RS-200 N0..SS-2024-00221220 We thank Hangjun Cho for the helpful discussions on the continuous-time analysis. We also thank anonymous reviewers for the highly constructive feedback.
RS-2024-004061277) and the Oliger Memorial Fellowship.
References
[1] Abbas and H. Attouch. Dynamical systems and with the sum of convex subdifferential and monotone cocoercive operator. Optimization. A Journal of Mathematical Programming and Operations Research, (110):2223-25522 2015.
algorithms associated
[2] T. Achterberg and F. Towle. Non-Convex Quadratic Optimization: Gurobi 9.0. 2020. https:
/ //www. www.ggurbii. com/ htt.:/rsouuceeeeee convex wwwroriuuurrtitiiioo quaddratic-oopiiiiizatiioo/ wwt.iioatiiooo.o/ooooooom
[3] S. Adly and H. Attouch. Finite convergence of proximal-gradient inertial algorithms combining dry friction with Hessian-driven damping. SIAM Journal on Optimization, 303))2134-2166, 2020.
[4] Agarwal, C. Fiscko, Kar, L.. Pileggi, and Sinopoli. equivalent eircuit workflow for unconstrained optimization. arXiv preprint arXiv:2305.14061 2023.
10

---

[5] A. Agarwal and L. Pileggi. An equivalent circuit approach to distributed optimization. arXiv preprint WXXiv2305.14607. 2023.
[6] F. Alvarez. On the minimizing property of a second order dissipative system in hilbert spaces. SIAM Journal on Control and Optimization, 38(4): 1119, 2000.
[7] F. Alvarez and H. Attouch. An inertial proximal method for maximal monotone operators via discretization of nonlinear oscillator with damping. Set-Valued Analysis, 9(1):311,, 2001.
[8] F. Alvarez, H. Attouch, Bolte, and Redont. A second-order gradient-like dissipative dynamical system with fessian-drrven damping Application to optimization and mechanics. Journal de Mathématiques Pures Appliquées, (8))77477777, 2002.
[9] J. Andersson, J. Gillis, G. Horn, J. Rawlings, and M. Diehl. CasADi: software framework for nonlinear optimization and optimal control. Mathematical Programming Computation, 11:1 11:1-6, 2019.
[10] V. Apidopoulos, J.-F. Aujol, and C. Dossal. The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b S 3. SIAM Journal on Optimization, 2811:5551-574 2018.
[11] H. Attouch and Alvarez. The heavy ball with friction dynamical system for convex con- strained minimization problems. Belgian- Belgian-French- French- Conference on Optimization, 1998.
[12] H. Attouch, Z. Chbani. J. Fadili, and H. Riahi. First-order optimization algorithms via inertial systems with Hessian driven damping. Mathematical Programming. 2020.
[13] H. Attouch, Z. Chbani, J. Peypouquet, and Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, 168(1):123-175, 2018.
[14] H. Attouch, Z. Chbani, and H. Riahi. Fast proximal methods via time scaling of damped inertial dynamics. SIAM Journal on Optimization, 29(3)22227-2555 2019.
[15] H. Attouch, 7. Chbani, and H. Riahi. Rate of convergence of the Nesterov accelerated gradient method in the subcritical case a 3. ESAIM: Control, Optimisation and Calculus of Variations, 25:2, 2019.
[16] H. Attouch and M.-O. Czarnecki. Asymptotic control and stabilization of nonlinear oscillators with non-isolated equilibria. Journal of Differential Equations, 179(1):278-310, 2002.
[17] H. Attouch, X. Goudou, and Redont. The heavy ball with friction method, I. The continuous dynamical system: Global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system. Communications in Contemporary Muthematics, 02(01):1-34, 2000.
[18] H. Attouch and S. C. László. Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators. SIAM Journal on Optimization, 30(4):3252-3283, 2020.
[19] H. Attouch and J. Peypouquet. Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators. Mathematical Programming, 174(1):391-44 2019.
[20] H. Attouch, J. Peypouquet, and Redont. A dynamical approach to an inertial forward- backward algorithm for convex minimization. SIAM Journal on Optimization, 24(1):232-256. 2014.
[21] J.-P. Aubin and A. Cellina. Differential Inclusions: Set- Valued Maps and Viability Theory, volume 264. Springer Science & Business Media, 2012.
[22] M. Barré, A. B. Taylor, and F. Bach. Principled analyses and design of first-order methods with inexact proximal operators. Mathematical Programming, 201(1):185-230, 2023.
[23] H. Bauschke and P. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer International Publishing, second edition, 2017.
11

---

[24] M. Betancourt, M. I. Jordan, and A. C. Wilson. On symplectic optimization. arxXiv:802.03355. 2018.
[25] R. I. Bot and E. R. Csetnek. Convergence rates for forward backwarrd dynamical systems asso- ciated with strongly monotone inclusions. Journal of Mathematical Analysis and Applications, 457(2): 111e1135-11555 1152, 2018.
[26] R. Bot, E. R. Csetnek, and D. Nguyen. Fast Optimistic Gradient Descent Ascent (OGDA) method continuous and discrete time. Foundations of Computational Mathematicx, 2023.
[27] R. I. Bot and D. A. Hulett. Second order splitting dynamics with vanishing damping for additively structured monotone inclusions. Journal of Dynamics and Differential Equations, 2022.
[28] S. Boyd. Distributed optimization: Analysis and synthesis via circuits. Lecture Note EE364b, Stanford University, 2010.
[29] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2011.
[30] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trendso in Machine learning, 3(1):1-122, 2011.
[31] S. Boyd and L. Vandenherghe. Convex Optimization. Cambridge University Press, 2004.
[32] R. E. Bruck. Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. Journal of Functional Analysis, 18(1):15-26, 1975.
[33] F. S. Cattivelli, C. Lopes, and A. H. Sayed. diffusion rls scheme for distributed estimation over adaptive networks. In Signal Processing Advances in Wireless Communicationss 2007.
[34] F. Cattivelli and A. H. Sayed. Diffusion LMS strategies for distributed estimation. IEEE Transactions on Signal Processing, 58(3): 2010.
[35] A.-L. Cauchy. Méthode générale pour la résolution des systémes d' é'quutttion simultanées. Comptes Rendus Hebbdomadaires des Séances de l'Académie des Sciences, 25:536-538, 1847.
[36] T. Chaffey, S. Banert, P. Giselsson, and R. Pates. Circuit analysis using monotone+skew splitting. European Journal of Control, 74:100854, 2023.
[37] T. Chaffey and A. Padoan. Circuit model reduction with scaled relative graphs. Conference on Decision and Control (CDC), pages 6530-6533 2022.
[38] T. Chaffey and R. Sepulchre. Monotone RLC circuits. European Control Conference, 2021.
[39] T. Chaffey and R. Sepulchre. Monotone one-port circuits. IEEE Transactions on Automatic Control, 69(2):783-799) 2024.
[40] S. Chen, B. Shi, and Y.-X. Yuan. On underdamped Nesterov's acceleration. arXiv:2304.14644 2023.
[41] L. Chua and G.-N. Lin. Nonlinear programming without computation. IEEE Transactions Circuits and Systems, 11(2):12-1882 1984.
[42] P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation, 4(4): 1200, 2005.
[43] E. R. Csetnek, Y. Malitsky, and M. K. Tam. Shadow Douglas-Rachford splitting for monotone inclusions. Applied Mathematics & Optimization, 80(3):665-678, 2019.
[44] S. Cyrus, B. Hu, B. Van Scoy, and I.. Lessard. robust accelerated optimization algorithm for strongly convex functions. American Control Conference (ACC), pages 1376-1381, 2018.
12

---

[45] S. Das Gupta, B. P. G. Van Parys, and E. K. Ryu. Branch-and mou-d performance estima- tion programming: A unified methodology for constructing optimal optimization methods. Mathematical Programming. 2023.
[46] D. Davis and W. Yin. A three-operator splitting scheme and its optimization applications. Set- Valued and Variational Analysis, 25(():829- 888, 2017.
[47] G. B. De Luca and E. Silverstein. Born-infeld (BI) for AI: Energy-conserving descent (ECD) for optimization. International Conference on Machine Learning. 162, 2022.
[48] J. B. Dennis. Mathematical Programming and Electrical Networks. PhD thesis, Massachusetts Institute of Technology, 1959.
[49] C. A. Desoer and Katzenelson. Nonlinear RLC networks. Bell System Technical Journal, 44(1):161-198, 1965.
[50] C. A. Desoer and E. S. Kuh. Basic Circuit Theory. Electronic Engineering McGraw-Hill, 1969.
[51] C. A. Desoer and F. F. Wu. Nonlinear monotone networks. Mathematics, 26(2):315-333, 1974.
SIAM Journal on Applied
[52] J. Diakonikolas and M. Jordan. Generalized momentum-base methods: A Hamiltonian perspective. SIAM Journal on Optimizaaiion, 31(1):915-944) 2021.
[53] J. Douglas and H. H. Rachford. On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society, 82(2):421-439, 1956.
[54] Y. Drori and M. Teboulle. Performance first-order methods for smooth convex minimization: A novel approach. Mathematical Programming, 145(1):451-482, 2014.
[55] J. Duffin. Nonlinear networks. I. Bulletin of the American Mathematical Society, 52(10))833-
838, 1946.
[56] J. Eckstein and D. P. Bertsekas. On the Douglas- Rachford point algorithm for maximal monotone operators. Mathematical Programming. 55(1):293-318, 1992.
Rachlos-Rachford splitting method and the proximal
[57] L. Euler. Institutiones Calculi Differentialis. Petropolis, 1755.
[58] M. Even, Berthier, F. Bach, N. Flammarion, H. Hendrikx, Gaillard, L. Massoulié, and A. Taylor. Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms. Neural Information Processing Systems, 2021.
[59] H. Everett. Generalized Lagrange multiplier method for solving problems of optimum alloca- tion of resources. Operations Research, 11(3):399-417, 1963.
[60] M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado. Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM Journal on Optimization, 28(3):2654-2689, 2018.
[61] K. Feng. On difference schemes and symplectic geometry. Proceedings of the 5th International Symposium on Differential Geometry and Differential Equations, pages 42-58, 1984.
[62] S. Fiori. Quasi-geodesic neural learning algorithms over the orthogonal group: tutorial. Journal of Machine Learning Research, 6(26):743-781, 2005.
[63] M. I.. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 50(1 supplllmmmmmm) 1861-1871, 2004.
[64] G. França, M. I. Jordan, and R. Vidal. On dissipative symplectic integration with applications to gradient-based optimization. Journal of Statistical Mechanics: Theory and Experiment, 2424(4) 2021.
13

---

[65] G. França, D. Robinson, and R. Vidal. ADMM and accelerated ADMM as continuous dynamical systems. International Conference on Machine Learning. 2018.
[66] G. França, D. P. Robinson, and R. Vidal. Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization. Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplimary Topics, 103(5):05330,, 2021.
[67] G. França, D. P. Robinson, and R. Vidal. A nonsmooth dynamical systems perspective on accelerated extensions of ADMM. IEEE Transactions on Automatic Control, 686)):996-22778, 2023.
[68] G. França, J. Sulam, D. Robinson, and R. Vidal. Conformal symplectic and relativistic optimization. Neural Information Processing Systems, 2020.
[69] França, J. Sulam, D. Robinson, and Vidal. Conformal symplectic and relativistic optimization. Journal of Statistical Mechanics: Theory and Experiment, 2020( (22; 124088, 2020.
[70] D. Gabay. Chapter IX applications of the method multipliers to variational inequalities. In M. Fortin and R. Glowinski, editors, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary- Caanary-VValue Value Problems, volume 15 of Studies in Mathematics and Its Applications, pages 299-331, Elsevier, 1983.
[71] Gabay and B. Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications, 2(1):17-40, 1976.
[72] A. M. Geoffrion. Primal resource-directive approaches for optimizing nonlinear decomposable systems. Operations Research, 18(3):375-403, 1970.
[73] B. Gharesifard and J. Cortés. Distributed continuous-tims convex optimization weight- balanced digraphs. IEEE Transactions on Automatic Control, 59(3):781-786, 2014.
[74] R. Glowinski and A. Marroco. Sur I' l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-duulité d'une classe de problèmes de Dirichlet non linéaires. Revue Française d' d'Automatique, Informatique, Recherche Opérationnelle. Analyse Numérique, 9(2):41-76, 1975.
[75] Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity, International Conference on Artificial Intelligence and Statistics, 2022.
[76] B. Goujaud, C. Moucer, F. Glineur, J. M. Hendrickx, A. B. Taylor, and A. Dieuleveut. PEPit: Computer-assisted worst-case analyses of first-order optimization methods in Python. Mathe- matical Programming Computation, 16(3):337-367) 2024.
[77] E. Hairer, C. Lubich, and W. Gerhard. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer, 2 edition, 2006.
[78] S. Hassan Moggaadda and M. R. Jovanović. Proximal gradient flow and Douglas Douglas-Rachfoo Rachford splitting dynamics: Global exponential stability via integral quadratic constraints. Automatica, 123: 109311, 2021.
[79] U. Helmke and J. Moore. Optimization and dynamical systems. Proceedings of the IEEE, 84(6):907-, 1996.
[80] R. Horst and H. Tuy. Global Optimization: Deterministic Approaches. Springer Science & Business Media, 2013.
[81] B. Hu and L. Lessard. Dissipativity theory for Nesterov's 's accelerated method. International Conference on Machine Learning. 2017.
[82] T. H. Hughes. Passivity and electric circuits: behavioral approach. IFAC-PapersOnnLine, 50(L):15500-1550, 2017.
14

---

[83] A. Iserles. A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, 2009.
[84] U. Jang, S. D. Gupta, and E. K. Ryu. Computer-assisted design of accelerated composite optimization methods: OptSTA. urXiv:2305.15700 2023.
[85] Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002.
[86] S. S. Kia, Cortés, and S. Martínez. Distributed convex optimization via continuous- time coordination algorithms with discrete-time communication. Automatica,
2015.
[87] Kim. Accelerated proximal point method for maximally monotone operators. Mathematical P Programming, 190(1-2)577-87 2021.
[88] D. Kim and A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1-2):81-1)) 2016.
[89] D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 2021.
188(1))192-22)
[90] J. Kim and Yang. Convergence analysis of ODE models for accelerated first-order methods via positive semidefinite kernels. Neural Information Processing Systems, 2023.
[91] J. Kim and Yang. Unifying Nesterov's accelerated gradient methods for convex and strongly convex objective functions. International Conference on Machine Learning, 2023.
[92] D. P. Kingma J. J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
[93] W. Krichene, A. Bayen, and P. L. Bartlett. Accelerated mirror descent in continuous and discrete time. Neural Information Processing Systems, 2015.
[94] W. Kutta. Beitrag /ur Nühhrungsseesenn Integration Totaler Differentiagleiccunngen Teubner, 1901.
[95] S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex--noncocaave minimax problems. Neural Information Processing Systems, 2021.
[96] C. Lemaréchal. Lagrangian relaxation. In M. Jünger and D. Naddef, editors, Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, Lecture Notes in Computer Science, pages 112-156. Springer, Berlin, Heidelberg, 2001.
[97] L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
[98] L. Liberti. Introduction to global optimization. Ecole Polytechnique, 2008.
[99] F. Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):005- 418, 2021.
[100] P. Lin, W. Ren, and J. A. Farrell. Distributed continuous-time optimization: Nonuniform gradient gains, finite-time convergence, and convex constraint set. IEEE Transactions on Automatic Control, 62(5):2239 2253, 2017.
[101] P. L.. Lions and Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):664-99) 979, 1979.
[102] M. Locatelli and F. Schoen. Global Optimization: Theory, Algorithms, and Applications. SIAM, 2013.
[103] H. Lu. An Orsssriuoo ODE framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems. Mathematical Programming, 194(1):1011-1112, 2022.
15

---

[104] J. Lu and C. Y. Tang, Zero-gradt paro-gradient-sun sum algorithms for distributed convex optimization: The continuous-tin case. IEEE Transactions on Automatic Control, 57(9):2348 2012.
[105] C. J. Maddison, D. Paulin, W. Teh, B, O'Donoghue, and A. Doucet. Hamiltonian descent methods. 1rXv::809.005422 2018.
[106] J. C. Maxwell, Treatise on Electricity and Magnetism, volume 1. Oxford: Clarendon Press, 1873.
[107] R. McL.cchlan and M. Perlmutter. Conformal Hamiltonian systems. Journal of Geometry and Physics, 39(4))276-300, 2001.
[108] A. Megretski and A. Rantzer. System analysis via integral quadratic constraints.
1EEE
Transactions Automatic Control, 42(6):819-830, 1997.
[109] W. Millar. CXVI. Some general theorems for non non-linear systems possessing resistance. Philosophical Magazine and Journal of Science, ((333):1150-111 1951.
[110] G. Minty, Solving steady-state nonlinear networks of 'monotone' elements. IRE Transactions on Circuit Theory, 8(2)999-04,, 1961.
[111] G. J. Minty. Monotone networks. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 257(1289) 1960.
[112] J. Minty. On the maximal domain of "monotone" function. The Michigan Mathematical Journal, 8(2):135-133) 137, 1961.
[113] C. Moucer, A. Taylor, and F. Bach. A systematic approach to Lyapunov analyses of continuous- time models in convex optimization. SIAM Journal on Optimization, 33(3):1558-1533 2023.
[114] M. Muehlebach and M. Jordan. A dynamical systems perspective on Nesterov acceleration. International Conference on Machine Learning, 00119-0-09//019-06-155
[115] M. Muchlebach and M. I. Jordan. Optimization with momentum: Dynamical, control-theoretic, and symplectic perspectives. Journal of Machine Learning Research, 22(73):1-50, 2021.
[116] A. Nedic and A. Ozdaglar. Distributed Subgradient Methods for Multi-Agent Optimization. IEEE Transactions on Automatic Control, 54( :1:4666, 2009.
[117] Y. Nesterov. A method of solving convex programming problem with convergence rate O(1/k²) Doklady Akademii Nauk SSSR, 269 1983.
[118] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004.
[119] Y. Nesterov. Lectures on Convex Optimization. Springer, 2 edition, 2018.
[120] R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. Jordan. A general analysis of the convergence of ADMM. International Conference on Machine Learning. 2015.
[121] J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
[122] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning, 2022.
[123] W. Peaceman and J. Rachford, H. H. The numerical solution of parabolic and elliptic differential equations. Journal of the Society for Industrial and Applied Mathematics, 3(1):28- 41, 1955.
[124] B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physies, 4(5):1-17, 1964.
[125] T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898 1976.
[126] T. Rockafellar. Convex analysis, volume 11. Princeton University Press, 1997.
16

---

[127] C. Runge. Ueber die numerische Auflösung von Differentialgleeihungen. Mathematischhe Annalen, 46(2):167-178, 1895.
[128] D. Ruth. A canonical integration technique. IEEE Transactions on Nuclear Science, 30(4):2669-20) -6771, 1983.
[129] E. Ryu and W. Yin. Large-Scale Convex Optimization via Monotone Operators. Cambridge University Press, 2022.
[130] E. K. Ryu, A. B. Taylor, C. Bergeling, and P. Giselsson. Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal Optimization, (0(3):2211-22711 2020.
[131] S. K. Sashank J. Reddi, Satyen Kale. On the convergence of Adam and beyond. International Conference on Learning Representations, 2018.
[132] K. Sawant, D. Nguyen, A. Liu, J. Poon, and S. Dhople. A cobrid-comppting solution to nonlinear optimization problems. IEEE Transactions on Circuits and Systems I: Regular Pupers, 71(12):5555-6568 2024.
[133] J. Schropp and I. Singer. A dynamical systems approach constrained minimization. Numeri- cal Functional Analysis and Optimization, 21 21(3-4):537-551 2000.
[134] D. Scieur, V. Roulet, F. Bach, and A. d' Aspremont. Integration methods and optimization algorithms. Neural Information Processing Systems, 2017.
[135] S. Seshu and M. B. Reed. Linear Graphs and Electrical Networks. Addison- -eellyy Series in Behavioral Science: Quantitative Methods. Addison-Weste Publishing Company, 1961.
[136] B. Shi, S. Du, W. Su, and M. Jordan. Acceleration via symplectic discretization of high- resolution differential equations. Neural Information Processing Systems, 2019.
[137] Shi, S. Du, M. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, 2021.
[138) W. Shi, Q Ling, G. Wu, and W. Yin. A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing, 63(22)x6013-6023, 2015.
[139] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin. On the linear convergence the ADMM in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62(7): 1750- 1761, 2014.
[140] G. J. Silverman. Primal decomposition of mathematical programs by resource allocation: I. Basic theory and direction-fimm finding procedure. Operations Research, 20(1):58-74 1972.
[141] C. S. Simon Michalowsky and C. Ebenbauer. Robust and structure exploiting optimisation algorithms: An integral quadratic constraint approach. International Journal of Control, 94(1 1)229622977, 2021.
[142] D. Sontag, A. Globerson, and T. Jaakkola. Introduction to dual decomposition for inference. In S. Sra, S. Nowozin, and S. J. Wright, editors, Optimization for Machine Learning, pages 119-254. The Massachusetts Institute of Technology Press, 2011.
[143] W. Su, Boyd, and E. J. Candès. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Neural Information Processing Systems, 2014.
[144] W. Su, S. Boyd, and E. J. Candès. A differential equation for modeling Nesterov's 's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1 1-33, 2016.
[145] J. J. Suh, J. Park, and E. K. Ryu. Continuous-time analysis of anchor acceleration. Neural Information Processing Systems, 2023.
[146] J. J. Suh, G. Roh, and E. K. Ryu. Continuous-time analysis of AGM via conservation laws in dilated coordinate systems. International Conference on Machine Learning, 2022.
17

---

[147] A. Sundararajan, B. Van Scoy, and L. Lessard. Analysis and design of first-order distributed optimization algorithms over vire-iayying graphs. IEEE Transactions on Control of Network Systems, 7(4):1597-1608, 2020.
[148] A. Taylor and F. Bach. Stochastic first-order methods: Non-asymptotic and computer-aides analyses via potential functions. Conference on Learning Theory, 0022200222-99---0
[149] A. Taylor and Y. Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programming, 199(-5))55,,594, 2023.
[150] B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(():307-345, 2017.
[151] K. Ushiyama, S. Sato, and T. Matsuo. A unified discretization framework for differential equation approach with Lyapunov arguments for convex optimization. Neural Information Processing Systems, 2023.
[152] B. Van Scoy, R. A. Freeman, and K. M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2018
[153] S. Vichik and F. Borrelli. Solving linear and quadratic programs with an analog circuit. Computers & Chemical Engineering, 70:160-171, 2014.
[154] R. D. Vogelaere. Methods of integration which preserve the contact transformation property of the hamilton equations. 1956.
[155] A. Wächter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106:25-57, 2006.
[156] J. Wang and Elia. Control approach to distributed optimization. Annual Allerton Conference Communication, Control, and Computing, 2010.
[157] E. Wei and Ozdaglar. On the O(1/k) convergence of asynchronous distributed alternating direction method of multipliers. Global Conference on Signal and Information Processing, 2013.
[158] A. Wibisono, A. C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, 113(47): 2016.
[159] J. C. Willems. The Generation of Lyapunov Functions for Input-Output Stable Systems. SIAM Journal on Control, 9()::105-134 1971.
[160] J. C. Willems. Dissipative dynamical systems part I: General theory. Archive for Rational Mechanics and Analysis, 45(5):321-351, 1972.
[161] A. C. Wilson, L. Mackey, and A. Wibisono. Accelerating rescaled gradient descent: Fast optimization of smooth functions. Neural Information Processing Systems, 2019.
[162] A. C. Wilson, B. Recht, and M. I. Jordan. A Lyapumov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-33 2021.
[163] G. Wilson. Quadratic programming analogs. IEEE Transactions on Circuits and Systems, 33(9):907-911, 1986.
[164] L. Yang, R. Arora, V. braverman, and T. Zhao. The physical systems behind optimization algorithms. Neural Information Processing Systems, 31, 2018.
[165] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson. A survey of distributed optimization. Annual Reviews Control, 47:278-305, 2019.
18

---

[166] T. Yoon, J. Kim, J. J. Suh, and E. K. Ryu. Optimal acceleration for minimax and ixxed-point problems is not unique. International Conference on Machine Learning. 2024.
[167] T. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with (11/k2) rate on squared gradient norm. International Conference on Machine Learning, 2021.
[168] Y. Yu and B. Agıkmeşe. arXiv:2003.06943 2020.
RC circuits based distributed conditional gradient method.
[169] Y. Yu and Açıkmeşe. RLC circuits- distributed mirror descent method. IEEE Control Systems Letters, 4(3):548-553, 2020.
[170] H. Yuan, Y. Zhou, C. J. Li, and Q. Sun. Differential inclusions for modeling nonsmooth ADMM variants: A continuous limit theory. International Conference on Machine Learning, 2019.
[171] K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1885 2016.
[172] J. Zhang, A. Mokhtari, S. Sra, and A. Jadbabaie. Direct Runge- Kutta discretization achieves acceleration. Neural Information Processing Systems, 2018.
[173] J. Zhang, S. Sra, and A. Jadbabaie. Acceleration in first order quasi-strongly convex optimiza- tion by ODE discretization. Conference on Decision and Control, 2019.
[174) P. Zhang, A. Orvieto, and H. Daneshmand. Rethinking the variational interpretation of accelerated optimization methods. Neural Information Processing Systems, 2021.
19

---

A Prior works
Distributed optimization as RLC circuits. This work started a lecture for the Stanford University EE 364b class given in 2010 [28]. The lecture proposed the idea of relating dis- tributed optimization algorithms to the dynamics of RLC circuits. Different from the prior studies [48, 163, 41, 153, 132], that consider solving specific optimization problems through implementing physical circuits, our focus is on using insights from circuit theory to design new algorithms, without any consideration of implementing physical circuits. The follow-up works [168, 169, 4, 5]. have built upon this setup [28].
Optimization algorithms from continuous-time dynamics. Relating continuous- time dynamics described by ordinary differential equation (ODE) with optimization algorithm is a technique with a long history [32, 79, 6. 133, 62]. The continuous-time dynamics related to Polyak's 's heavy ball method [124] were studied by [11, 17, 8, 16). The ODE model for Nesterov acceleration [117] was introduced by [143, 144], analyses for generalized cases were followed by [10, 13, 15], and the ODE model for Nesterov accelcration for strongly convex function (NAG-CC) was introduced in [162]. Together with [93], the studies by [143, 144] initiated continuous- time analyses of accelerated first-order methods and inspired much follow-up works such as [158, 19, 1 115, 52, 58, 162, 18, 27, 146, 91, 145, 26). As further refined continuous-time model preserving more information from the discretization, the high-resolution ODE for NAG-SC was introduced in [137], and was further developed by [103].
In addition to accelerated methods, various topics and methods in optimization have been studied in continuous-time framework. Contimuous- dynamics related to splitting methods were studied by [20, 1, 25, 43, 66. 78]. [65] studied continuous-time dynamics of ADMM [74, 71, 70, 56, 29], and provided an accelerated ADMM by discretizing the ODE model combined with [143]. The analyses were furthermore generalized to differential inclusions by [170, 67]. There numerous works of continuous-timg time analyses for distributed optimization, [156, 104, 73, 86, 100] to name a few, and we refer the readers the survey paper [165] for comprehensive overview.
Computer-assisted analysis of optimization algorithms. There has been lines of work automating the analysis of optimization methods using semidefinite programs (SDP). One line of work is performance estimation problems (PEP) introduced by [54], which provides a systematic way to obtain worst-case performance guarantees of given fixed-step first-order method. The range and technique of utilizing PEP have been further developed by [150, 148, 130, 1 113, 90], and many efficient algorithms with tight analyses utilizing PEP are discovered [88, 99, 87, 89, 167, 95, 122, 75, 149, 84, 22, 166].
Another line of work is approach adapting integral quadratic constraints (IQC) [108]. IQCs are a powerful analysis method control theory for analyzing interconnected dynamical systems with nonlinear feedback. This approach was first adapted for analyzing first-order optimization algorithms by [97] and followed by [60]. Analyses based on IQC have lead to tight bounds for well-known algorithms [120, 81]. IQC has also been utilized to develop new fast algorithms with tight convergence rates [152, 44, 147, 141].
Recently, an extension of PEP to leveraging quadratic constrained quadratic programs (QCQP) was introduced by [45]. Treating the step-sizes as optimization variables, this work furthermore provides systematic computer-assisted methodology to optimize the step-sizes. Our work adapts this approach to finding appropriate discretizations. To the best of our knowledge, our proposal is the first instance of using computer-assisted methodologies to find discretizations of continuous-time dynamics.
bassiss-bases approaches to designing optimization algorithms. Optimization methods ob- tained by discretizing conformal Hamiltonian dynamics [107] were considered by [105]. Studying structure- peetuurepreeerving discretizations for conformal (dissipative) Hamiltonian systems, [68, 69] ana- lyzed symplectic structure of Nesterov and heavy ball, and introduced Relativistic Gradient Descent (RGD) by adopting ideas from special relativity. Based on relativistic Born-Infeld (BI) dynamics, [47] considered a class of frictionless, energy conserinn system and introduced Bouncing BI (BBI) algorithm as a discretization.
Our work is based on nonlinear resistive electric circuits, the study of which dates back to [55]. The stationary condition for nonlinear networks were considered by [109], generalizing theorems of Maxwell [106] for linear networks. The study of nonlinear resistive networks influenced the
20

---

refinement of the concept of maximal monotonicity [111, 112, 110], which is now fundamental concept in convex optimization. rell-posedness of the solutions for nonlinear networks was studied by [49, 51], but only for one-descent nonlinear resistors. Recently, the study of nonlinear electrical circuits was revisited by [38, 37, 36, 39] using contemporary methods of convex optimization. However, their main focus was on circuits, not on designing new optimization algorithms. To the best of our knowledge, our work is the first to introduce generalized framework for designing optimization methods based on electric circuits.
Discretization. Continuous-time analyses of optimization algorithms must eventually contend with the issue of discretizing the dynamics into discrete-ting algorithm. Discretization of differential equations is a subject of numerical analysis, and it has a long history, even dating back to Euler [57]. Standard discretization schemes such as Euler, Runge-Kutta [127, 94] and symplectic integrators [154, 128, 61], have rich body of research analyzing their convergence [77, 83] for example. However, these theories in numerical analysis primarily focus the convergence of the discretized sequence to the trajectory of the solution flow in differential equations throughout a finite time-interval, which differs from the focus of optimization. Therefore, directly applying standard discretization schemes from numerical analysis does not ensure convergence to the optimality criteria of interest in optimization, such function value or optimal point convergence.
In optimization, the study of discretization can broadly be divided into two categories. One involves applying standard discretization schemes or their variants, and the other provides special rules tailored to the specific dynamics of interest. As previously discussed, the former cases can only guarantee the convergence involving certain errors [24, 64), introduce specific and limited cases they can cover [134, 172, 136, 1 114, 173, 146, 151]. The latter type of works do provide discretization rules with analytic proofs for certain families of ODEs [7, 144, 158, 14, 161, 3, 12, 52, 26], but cannot be applied to general cases. Of course, both approaches have brought significant advances in obtaining new methods from continuous-time dynamics, however, is still true that previous approaches cannot immediately applied the new ODEs that emerge from our framework. To the best of our knowledge, work is the first to propose automate the process of finding discretized method from ODE using computer-assistar tools.
21

---

B Proof of Theorem 2.1
To prove Theorem 2.1, it is sufficient to consider the cases without 0-ohm resistors and furthermore all resistor, inductance, capacitance values are 1. We first state the theorem for such cases, which implies Theorem 2.1.
Theorem B.1. Let f: R + RT be p-strroglyy convex and M -mmoohhh functiiiunttiion and B: R 7 R be a matrix. Suppose (v 1 2, ,00 satisfy
101 ENBB, V
To 2
R(BT), oike 2 -VV((x)).
(10)
Then there is uniquely determined Lipschitz continuous curve (v, y): 10, (0,00) + R satisfies
vu E R(BT), y Vf(x), पर iR. vc dl ce
d
d
ENBB,
Thk.
ic
dl u (11)
V
[
for all t E 00) and the initial condition (v(0), i()), 20), v(0)) = (v", 1 , x² .11) Lemma B.2. Theorem B.I implies Theorem 1.
Proof. (i) KCL, KVL and V-I relations for equivalent dynamics without 0-ohm resistors.
We first consider the equivalent dynamic interconnect without 0-ohm resistors. As 0-ohm resistors are ideal wires, from basic circuit theory we know the nodes connected by O-ohm resistors can be considered as single node. We find the expression for KCL, KVL and V-I relations for the equivalent dynamic interconnect composed with 0f. The equivalent expression for KCL and KVL be considered as consequence of Tellegen's theorem in [50, $10.2.3), however, write the detail here to make it self-contained.
Observe, KCL and KVL can be equivalently written
Im
A
= 0,
We furthermore restrict the values to satisfy Ohm's 's law for 0-ohm resistors, iee. the potential values of two nodes connected to a 0-ohm resistor is identical.
Let's first focus on KCL, the left equation. Suppose node j and are connected with 0-ohm resistor named as R2₁-- Suppose the k'th column of corresponds to R2a- Eliminating R, corresponds to eliminating the k'th column of A and eliminating iR, from i. However, if just directly climinate them, as iR,; may not be zero, the equation will no longer be satisfied. We need to keep the information that currents flowing into node (except for -iR flows to node l. As we do not permit ideal wire loop, without loss of generality we may assume node j is not the ground node.
To preserve the information, when node is not the ground node, we add the j'th row of [ Im to
the l'th row. Then 'tt component of the 1'th row becomes O. thus the equation corresponding to the I'th row will still satisfied after eliminating the k'th column and Ryt. When node the ground node, skip the row addition. Now eliminate the j'th row. Note that column is eliminated only from A.
We now move to KVL. Eliminating a column of A and a component in corresponds to eliminating a row of AT and a component in v. This conserves the validity of the equation. Next, the row operation
Tm
I
_AT
for A
corresponds column operation for 0
Recall we' ve restricted the
T 0
potential values of the nodes connected with 0-ohm resistor to be same, values [x]
corresponding to column j and coincide. Thus when node is not the ground node, adding j 't column to the
I'th column and eliminating j' j'th component in x will not change the values on the left hand side.
When node is the ground node, the same argument holds by skipping the column addition.
Repeat this process until there is no 0-ohm resistors. Name the reduced matrix B and reduced current as i. Then KCL reduces to ß 0 and KVL reduces to BT or equivalently
T
R(BT).
22

---

Now name the reduced diagonal matrices DR. De and De as the reduced matrices that without the entries corresponding to eliminated components. Note DR has no zero diagonal entries. Then KCL, KVL and V-I relations for the equivalent dynamic interconnect composed with o become as follows
ic= De d dt (12)
E (B))
E R(()), y = Vf(r), eR = DRiR, üg = Dc ic.
cc
dt
As an equivalent dynamics, it is enough to prove the curve that satisfies (12) and the initial condition (6(0), (()) v(O) (ō", 70, x², sy)) with condition
j
Too
EN(),
E R((T), x0
o = DRiR. v
(13)
is unique and Lispchitz continuous.
(ii) Sufficient to consider only the cases with DR. Dr and De are identity matrices. For a dynamic interconnect composed with aʃ. consider the equivalent dynamics without 0-ohm resistors. Let B be the matrix in (12) for the dynamics, and let K. be the number of columns of B. Suppose (00, 20, _,,, , satisfy (13). Define the diagonal matrix
P = diag (VDR', DE (Dec.m)
100 p-1
70
[00 0
and define BP. Define 20 and o satisfy
and
P
Then
y0
y
x
(v", 1,, 20 1 satisfies (10) since
70
101
70
B
(BP)
p-1
0,
y
y
10
70
000
60
BT
3:0
PBT = B2
0
=
x0
and
0 R
= DR
DROR
P=170 D
0
R = =ip-
R
Then by Theorem B.1, there is Lipschitz continuous curve (v, i, x, : 10, x)
R 2K that satisfies
(11) for all & (0, oo) and the initial condition (v(0), i(0), (0), v()) (u", 10 x0 y)) Define 7 and
p-1 Then and ō are Lipschitz continuous well, as they are composition of linear operators and Lipschitz continuous curves. Furthermore, we can check (12) and the initial condition (5(0), 7(0), =00) (0)) (6", 70 x y satisfied, with the similar argument above.
and ē to satisfy
Reversing the arguments, the uniqueness can be obtained since invertible and thus (u, + (0, 8) bijective. This concludes the proof.
By Lemma B.2, our goal has reduced to Theorem B. We will establish the well- sell-posedness for de and first, then extended them whole curve. The well-posedness of ug, ig can be obtained by reducing the dynamics to a differential inclusion with a maximal monotone operator. We first restate the theorem in [21] and its immediate implication remark, which we use in the proof.
Theorem B.3. [21, Thm 3.2.1] Let M: R" = R" be maximal monotone operator, consider the differential inclusion
(t) E (t(((t)),
(14)
with initial condition X(0)= = Xo E dom M. Then there is unique solution X: [0, oo) - R that
absolutely continuous and satisfies (14) for almost all f. Moreover, if we denote T (1 E [0, oo)
X is differentiable at t), then then followings true.
23

---

Hw, (i) Let (-)) are the solutions issued from Xo, Yo E dom M respectively. Then (t(()) - Y()il I |Xx Yoll for all t O.
(i)) For all t 0, X (t) limm -0+ Xit+h)-X(() is well-defined and continuous from the right. Note, (() (t) for all t E ET.
(ii) t t ( is nonincreasing.
(iv) (+)+) -)((((((m))) holds for all 2 Here m(K) is the element of K R with minimal norm, that is, m(K) [I (0) argmin ||k|] Therefore X = (m((M(((t))
kek
holds for all t T, and so (14) is satisfied almost everywhere.
Remark. From (iil) we have ||{,(()||
- [x)( |lm[M(X)))] for all 2 0. thus for
t, 2 0 we have
-1/12 (s)ds
(1 |
(I((G) x(())
S
ds
l2
(1)
[lm(M(X6))] ds |t1 (m(()
Therefore the theorem implies that X is Lipschite-contimuuus, in particular with parameter [M))ll
Thus our first goal is to prove the condition
(11) can be equivalently written as
yc E
uc ic
-
dt
ic
for some maximal monotone operator A: R C[++CI reformulation of KCL and KVL.
R
[CH+AI
We first establish an efficient
Lemma B.4. There is skew-symmetric matrix H: R t and corresponding diagonal
matrix J: + + R with entries 0 of 1 that satisfies
EN(),,
E RR(B)
where û and i are defined as
w 1o+m
J]
à 1otm - J]
i
yy
y
Moreover, let Q: Rm + + be a permutation matrix, define w = Qw, a Qù. Then there is skew-symmelric matrix H that satisfies
( R((BT)
(B)),
Hw.
Remark. The diagonal matrix determines whether select voltage or current for each component, to construct w. To clarify, w. u E R +m are the vectors that (wi, u) becomes current and voltage pair of component for 1,2,..... + m. Such partitions of current, voltages values w, and nnew-symmetric matrix H were also considered in [82] with different notation. However, we introduce our method of constructing them here, as we will consider with special property in Corollary B. B.4.1 that plays key role in the proof.
Proof. Define N and B be matrices consisted with basis of (BB) and Row(B) respectively. Then KCL and KVL can be shortly rewritten as
N
0
T
0
0
B
0
y

---

We now show there is diagonal matrix J: Rd R below square matrix invertible
+ R mm with entries 0 or 1, that makes the
N
0
G
=
0
B
E R 2(o+m)x2(o+m)
Ia+m
J
N o
Name No
and Bo =
B
We will attach the standard basis vectors or 0 below, and increase
the index with attached number of rows, We proceed induction on the index, until the index becomes + m.
Suppose, for 0 S k < 1, Ng and Bg satisfy the form
N
0
B
N₂
jie1
j1
(15)
Live
ja es
where ji E {0,1] and e, E R is standard basis (row) vector for S S k. We claim either Cx+1 & Row(Nx) or ck+1 & Row(Bx) is true.
Proof by contradiction. Suppose not. That is, suppose ek+1 E Row(N&) and ex+1 E RRo Then there are n = mm) E Row(N), r (Fom...,Fo+m) E Row(B) ()) and coefficients ag by such that
&
ck+1 = =n n Σ
aiji: = - Σ
bi - b11-jee.
1-1
Taking inner product with Cp, 1sp5 σ + m, we have
if S S ki 1
0
if sk
0
if S < k. Jn =0
bp
i J, - -0 pfp=
pp
Tp
1
pf k 11
1
0
if < p < + m,
0
if m.
Therefore
m+
(n.r) Σ npT' M4419++1 1.
By the way, since Row(N) = N(B), Row(B) R(NT) we have n r and so (n, r) 0. A contradiction, we conclude either ct+1 Row(Nz) Cx+1 & Row(BR) is true.
From the proved claim, we can extend No. Bg to Notm. Batm with keeping the form of (15) by repeating the process below. Recall, the desired form of the matrix was
N
0
G =
0
B
T T
J
with diagonal matrix J E R( ((o+m) with entries 1. By the construction, we see matrix [Ntm Ba+m] satisfies the desired form. Moreover, we know the nonzero rows of No+m and Botm are linearly independent respectively, by their construction. By the form of G we see if 1-th row of No4m is nonzero then 1-th row of Bo+m is zero and vice-versa, conclude the rows of G are linearly independent. Therefore, G is invertible.
Observe
N
0
G
B
I
G-
(16)
i
i
J
J
y
y
25

---

We know above equation holds for arbitrarily chosen (v, x). (i,3) that satisfies KVL and KCL respectively. Observe dom(G) R(BT) (B) and from dimension theorem we know
dim(R(BT) x (B)) dim (R(n(((BT))) dim((N
As G is invertible, we have dim [RG)) = dim (dom
m. Therefore the values of the
components of be arbitrary values in R.
Rearranging the rows of G-1, from (16) we obtain H ((0+m)x2(=+m) that satisfies
i
[
H
H
0
FT
H
à
where the block matrices are in R (a+m))x( ((++)), Now, naming fl ft we get
i ū= A...
Now to show H is skew-symmetric, recall from (v,x) E R(BT) and (i,v) N(B) we have ((v,)), v)) = 0. Thus for all ú R we have
wr Hw) (1i, ú) = ((v,2), (4. = 0.
Therefore i skew-symmetric.
Finally, Q: R R be a permutation matrix. Define H QUQT. Since
H = QQTQTTTT- = Q(- =
Hl is skew-symmetric. And from QTQ Lo+m have
f=
u = Qú = = = Hw,
we conclude the proof.
Corollary B.4.1. Recall à is composed with voltage or current values of each component. Integrate the values of resistors and denote as integrate vc. ic as and integrate ic, Then we may rearrange the elements of in with certain permutation matrix Q, that w Qúi can be decomposed as following order
WeR
=
Wp- Wr
Up
where
Wpp =
[wee]] wie
Wpr =
Wic Wve ,
wr
Tee W
W.
Wli
Wy
Consider rewriting Hw in the decomposed way as
Upp
HP-
HP-
HP-
Up Wp-
Up Mp
HP
HP
HP
(17)
p.
H
H
Wp
Then there is diagonal matrix J satisfies the properties considered in Lemma B.4, that corresponding H satisfies
HT. 0, Hb_ 0, H1a =0. 0.
Proof. Name the indices Ci, Le E (1....,, m) for Be...,,CI:, & E (1,..., LC] that satisfy
ec
uc
ec
icy
First we put ec, and ec,," 's in J as many as possible. That is, determine the values of jc, and jc." to satisfy
fec, je, 1} is linearly independent to Row(N).
26

---

fee, iec, 1 U {ec,} } is linearly dependent to Row(N) for any l' E tic, # 1}.
fee, lic = 0} is linearly independent to Row(B).
(ec, jcc, = 03 U { is linearly dependent to Row(B) for any s' E Lic, #0}.
Next, fill the remaining j's as we' we've done in Lemma B.4.
Since the proof can be applied using the same argument other cases, we will focus on a specific case. Focusing on the last row of (17), can furthermore decompose and write as following
Wec
Wic
U, = H
H P+
H
wpp
Upp
Uir Ue.
0 th H
H ic
H
H
H
H
0
Wez
Wic
Wr
oc
We.
Wi,
Note, since above equations origin from KCL and KVL (which are linear equations only with current values or voltage values), Ha Theorem 6.3].
a current and | is voltage, and vice-versa. Refer [135,
H 0
Observe Hр. above equality we get
here we show H O. Focusing on arbitrary k th row of H from
Wic
Wie
Mirg H
Hig
H
Wie Wi,
0 H
H &
Wie Wi
thir
where the subscript & means the k' row of the block matrix. As this linear equation of current values, it origins from KCL, thus there is vector Row (B) corresponding to this equation, i.e.
Wie
r H
i y
Wic
Wire
Wi,-
On the other hand, as Wig Wie; Wi, are consisted with the components of i, that corresponds to ji = 0, there are coefficient vectors E RI b Rl C R
||| that satisfies
Wic Wie Wi,
[H
H.
H
Wirk
Σ a.ec, + Σ biec, +
E crer, - Er
i
y
sElic, =0}
LE(de==0)
=ELi-,=0}
Note bi's correspond to components of [H::] k Organizing, have
Σ a,ec, +
Σ bicc, +
Σ cgera Cru-
sEfje,=0f
gEfrr,=0f
Observe that from right hand side, we can see r is orthogonal to {ec, jc,, = 1}.
By the way, as {ec, jcz = 11 U (ec, is linearly dependent to Row(N) for all / E (ic, = 0}. we
blec, span (Yee, jcc, 1 Row(N))
=))
so there is some coefficient vector d E R and Row(N) that satisfies
Σ blec. =
Σ dree, + n.
LE (jc, 0)
=1
However, as r E Row(B) and Row (B) Row(N), we have (r, = 0. Moreover, as r is orthogonal {ec, | = 13. we conclude
0= r, Σ drec, + ('E(i,, =1
r,
Σ
blec,
Σ blec
b7 LE LE =0}
IE (cc
=0}
(Jo, =0
27

---

Therefore, as bi corresponds to components of [HT:c] k. we conclude [H] = 0. As k was arbitrary,
we get Hi = O. Similarly we can show Ha O, and thus Hÿ. = O. Repeating the same argument, we can show Hp. 0. Finally, as is skew-symmetrie, we have HPP -HH
0.
We now move on to V-I relations of resistors. To express V-I relations in terms of w and we adopt partial inverse.
Definition. [23, Definition 20.42] Let M: R = R be a set-valued operator and let K be a closed the projection onto K as
linear subspace of R Denote Ilx: R Rd
xx)x
argmin
| k||
KEK
The partial inverse of M with respect to K is the operator Mx: Rd = Rd defined by
gra Mx {[ + g y, Rx xgxx) (x,y) E graM),
i.e.,
E (M)) + y such that y E Mx and (we, u) (ITxx + KT,,,, Ky + -xxx).
We then prove important properties of the function related to V-I relations for resistors.
Lemma B.5. Suppose f is p-strongly convex and M -smoooh functiino Let Qr, H Jp: R R +m +
R ||| be permulation matrix, skew-symmetric matrix, diagonal matrix with entries 1 or 0
respectively and let K = R.)r). Define F; R + R as
F(UR,I) x) = || 11 + f(z).
Then the following holds.
(i) dom(Q H;) R|
(ii) (VF())) - -H;)- is Lipschitz continuous monotone operator.
Proof. Take (wf, u E R | for 1 E {1, such that uf E (Q+(VF) @.). As Qr is permutation matrix, we know (Q,)-1 = (Q.)T, and thus QT E (QT))) Then there are
E R [R such that
) x
R
F
W = k
11 K
II
2
+
II
(18)
By [23, Proposition 20.44, (ii)), we have
(QT - - (n. - x²))
$
Moreover, check
2
2
R
-
2
[.11
II
3
+
I1x=
R
+
+
x
|| ||w. w1 + || u
Define Mmin
{11, 1} and Mmin (M, 13.
Then we can check VF is -tinnstrrngly convex and
we see
(1ik w²) (12. v²) (ot, )² (1% x²))
Mmin [ x21) (122 |12
(lih. v²) (iZe, v²), (ok, (0 x²))
Main (ik. (iZe ((2.,12) 11?
28

---

Thus
(w) wr: u, -2²)
(Q](w, wx), QT xtt)
R
Mmin + Miin
2
+
2
Mmin + .mmin
(1uu²
w
1|
+
- m²?1²)
2
Mmia +
Mmin
w 211
2
check (VF)x is also strongly monotone, by considering the special case Q, = [r|+m- Lastly, since H. skew-symmetin we
see (VFF)) Q is M -srongly monotone. Note
know (H, 2) = 0 for all 2 R [R|+m Therefore for arbitrary (itt ūt)) E R [l with I E {1,2)
such that ir. E (Q.(VP) QT H7) aff. since n = utt + H E (Q.(PP) QT
( w U. - -,?) = ( w u u -H, -
H,,
w())
= 10 W u un/)
Mmin Mmin
W w ?1?
2
thus (Vx(VF)x(] - Hę) also Muin Man strongly monotone.
Now since VF is maximal monotone, (VF) is maximal monotone by [23, Proposition 20.44, (v)]. Since (VF) k is strongly monotone, we have dom dommVF). F))x R | by [23, Proposition 22.11], and thus Qr(VF) Q is maximal monotone by [129, Theorem 12]. Moreover, since both
(V(FF) QT and HH have full domain, Q] H,)) is maximal monotone by [129,
Theorem 10].
Organizing, (Q. (VF)x - HF) is maximal monotone and strongly monotone. Therefore by [23, Proposition 22.11], we conclude (ii). Finally, observe
(Q.(VF) -H)
(A(VF)RQ H.
Mmin
Muin
R|+m + Mmin + Mmin
2
2
M:M
+ Mainn JRR|m-
Puin 3a
Mmin
Since M is monotone, Puin +
M is also monotone, by [23, Corollary 23.9] we know J
M
is I-Lipschitz continuous. Therefore (QF( - (:-)111 is Mmnt-Mar Lippscittz continuous.
Finally it is monotone as it inverse of monotone operator, we conclude (ii).
Finally, we are ready to prove Theorem 2.1.
Proof of Theorem 2.1. By Lemma B.2 it is suffices show Theorem B.I.
(i) pell-posedness and Lipschitz continuity uc, ic. Existence of the whole curve (v, 1, y).
Define an operator A: R|[|+|11 = RlC++|e| as
(
[v) ic
ic Wc)
=
3 (VR, Ne, ve), i = (i,,)e,))) (x.v)
(19)
such that NN)), v
E R(BB), y Vf(z), ix
We prove A is maximal monotone by providing explicit expression of A and apply Theorem B.3.

---

From Corollary B,4.1, we know there is a diagonal matrix J: R + R permutation matrix
Q:
R R and a corresponding skew-symmetric matrix H: Rd - -R** that satisfies
Upp up
H
H
p-
HP-
Up
NDD),
(RBT)
HP
0
0
Wp.
(20)
y
ur
H
0
Hr
Wr
where and are defined in Lemma B.4.
Define F; R k
F(VR, x) 2/2 |1 2 f(x).
Then it straight forward that
y = (z)), uे = iR
iR
UR
y
By the construction of w, u, there diagonal matrix J,: R and permutation matrix Qr R R| + R R||m that satisfies
R
with entries
UR
Q 20 Q 1 ur
[Iwr] Q.ur
[ Jr
T|R|+m Jr
a
=
=
11Rl-m
iR
Define K, = R(J,). Note, we can check II, (2) = J,z and I (2) = (1|))+m J,)z for all R +m
2 E
Recalling (18) in Lemma B.5 we see
iR
Ur (Q2((()) 11
UR x
y
From
(Qr(VF) (.F)).FFF.. Wf = U4 Hp + H Wr.
we get expression for in terms of Wpp
Wp = (Q.(V)) QF -H,) H u.p.pp
(21)
Up. Up
Now focusing the expression for ing wy by applying (21) we see
since H. -HHF T H is skew-symmetric, eliminat-
Up.
Hp-
H
H
Up
Up.
(22)
Up
H
HP-
p-
[H OJ (Q.(VF)) QJ H; [ 0]
Up Wp.
H1
0
H HE
He.
Since H is skew-symmetric, its principal minors
and - H. are skew-symmetric and 0
so maximal monotone. Furthermore, by Lemma B.5 have (Q.(VF) , QT HF) -1 is maximal
monotone and dom((VF) H R |||+ Invoking [129, Theorem 11, 12], we conclude B is maximal monotone.
Organizing, we see
ie
ve
A
E
e(B),
ERBT), y Vf(x), UR iR
ic
y
Up. Up
B
Wp Wp.
where
=
Q 0 J Jo+m 0
Iotm
Ø
Therefore there a diagonal matrix Jp.p=: R
CI+|c|
R
[C|+
with entries and a permutation
matrix Qp.p": R
[C[++
+ R
[C++C)) that satisfies
ic
Up- Upp
Wp Wp.
E
-
=
B
ic
30

---

where
Wp
1/c
Op
0
Wp-
Jp.
1101+101 Jp.p Sp.""
ic
Qp.p-
Up-
1/21-111 Jp.p
ic
Up
Vr.
Therefore, for kpp-- R(pp.p
we have
A = Qp.p p.p Qp.pp
Since B is maximal monotone operator with dom B R 44 we have 2p.p- B Qppr maximal monotone. Finally from [23, Proposition 20.44, (v)), we conclude A maximal monotone.
By applying Theorem B.3 and its remark, we know there is unique Lipschitz continuous curve (ve,éc): o0)
R/4 cl x R that satisfies
(uc(t) mm dt ic(()]
(t) (t((t) it(tt
E -
ic(t)
for almost all t E [0, oo), where mA is the minimum-norm selection of A. Let ic(())
Pc(())
-mA Ec [t(t)] and y that satisfy KCL, KVL and V-I relations. This concludes the existence of the curve.
Moreover, the definition of A implies the existence of accompanying curves UR, iR.
(ii) The whole flow (u, i, y) is well-posed and Lipschitz continuous.
Finally, show other curves besides (vg,ic) defined uniquely and Lipschitz continuous. To do
so, we prove there a Lipschitz continuous function G: R R satisfies
+ R
R
R x R that
G(vc, ic) (v, i, 2, y)-
We prove the claim by finding the explicit expression of the component functions of G. We first show one key equation
Wpp - -HH Tup.
(23)
From (20) have HE. wp. up. And as Hl is skew-symmetric, have 11 (H.:)T. The core information we additionally use here, is the V-I relations at u0 = up. As differentiation is linear operation, get (23) by following
(Hp:)" Up. = Hhuup Hb "D) di
(HB
= dl.
" Wp.
Recall, from (22) have
Up. HP- + H (Q, -I -H H1) wp + Hb: up..
Moving the last term of right hand side to left hand side, multiplying both sides by -HH:: )T and using (23), we have
(I (HB:) HE:) up. = -HE:) H + HE- (V.), H;) H₁) upp
Since + (HB:) Hp: its inverse exists, we conclude
Wp. = + H TH:) (HF:)
H + H (Q.
QT HD) H Wp.
C
Organizing, we have
Wp
0 0
Wpp
0
C
Wp-
Wr 0
0
(Q.(F)) QF -H Hy
From Lemma B.5 we know (Q.(VF)K, QT H;)- is Lipschitz continuous, and clearly linear operators are Lipschitz continuous, C is Lipschitz continuous as it is composition and sum of
31

---

Lipschitz continuous functions. Therefore up + w is Lipschitz continuous. Finally since = H and H indeed Lipschitz continuous as linear operator, mapping wp + also Lipschitz continuous. As (we, u) is rearrangement of (v, 1, and Wre, Wig are component functions of re and éc. we get the desired result.
For (v, i, æ, y) that satisfies (11) with proper initial value, we know (vc, ig) is uniquely defined by previous observation and (u, y) G(vc, i should hold, conclude (v, i, x, y) is uniquely determined since G is single valued. Furthermore, as vt(() and ic(() are Lipschitz continuous with respect to t, we have (v(t). (t)), (+),, y(t)) (te) (()) is also Lipschitz continuous as is composition of Lipschitz continuous functions. This concludes the proof.
32

---

C
Equilibrium condition
Define the of voltages and currents in the equilibrium of the interconnect
{ (1..3) (v. | Ai
DaN -
y
AT I
UR DRİR, vc 0, 00ic=0]
Lemma C.1. Assume the dynamic interconnect is admissible. Then for all (u,i) E Da.y we have
UR iR 0.
Proof. First, note that for all (v, t) in the dynamic interconnect
x:
y - (0, v)-
(c, i) = (e, Ai)
(24)
c
Now suppose (v, i) E Dayy then we have
(u, (UR, -i -xx y).
From the admissibility assumption we have E R(ET) and y WEE). Thus
liRllBe (x, 0,
which concludes the proof.
Theorem C.2. Assume the dynamic interconnect is admissible. If (x",y" ) is primal- -ual solution
pair (with zero duality gap) for the optimization problem, then there exist ve E. RRC and ig R such that
E D
Conversely, if E (f() and
((UR,Ve, Uc, vc), (iR, ic, ic)) E Daay
then UR = iR. and (x, y) is a primal-dual solution pair (with zero-dualiyy) for the optimization problem.
Proof. First, observe the admissibility assumption can be rewritten as
{(z, v) 3(v, such that (v, E DaNt
Now suppose (x*,y") E X* y*. Then by Karush- Cerush-Kuhn-TTe Kuhn-Tucker (KKT) optimality conditions, have (x",y") E (ET)) x (E). Thus there exists (u", i**) such that
(v" (²* ((rR, O, vt), (ite 22, 0)) E Dat.y" Furthermore from Lemma C.1 have oik it 0. Therefore vž, i22 are the vectors that satisfiy the desired statement.
Conversely, suppose
(v. = ((VR, vc, ve), (ix. (tr (c, Dr.y.
From Lemma C.I, have UR = é 0. Moreover, since there exists (u, i) such that (v, Da.w- by admissibility assumption we have (r, y) E R(ET) x NEE).. Finally, given the assumption that y E (z)). by using KKT optimality conditions, we conclude (x, y) X Y
33

---

D Energy dissipation analysis
In this section, provide the proof of Theorem 2.2. The energy function (6) used in the proof is related to the Lyapunov function considered in [159]. However, the dissipativity theory presented in [159, 160] does directly apply to our setup. our setup, we allow cases where vc: i oscillate, for example, circuit with a disconnected L C' loop. The proof is obtained by combining Barbalat's lemma [85, Lemma 8.2] with Theorem 2.1.
Proof of Theorem 2.2. Let (x*,y") ,y") be primal-dual solution pair. Then by Theorem C.2, there is (o",it) E Dz y that satisfies
(v* ((0, 0, vt), (0, 0)).
(25)
In particular, i 0 and vic 0. Define the total energy at time as
{() = - ve velloe + z Ellic - l.
Then the power at time is given by
d
E(t)
(vc - v Detc) + fic cz Dric)
dt
(ve vg, ic - i6) fic 122 Uc - v2)
(URR DRiiR. itte xn,y yr)
(26)
-iRlll (r y
3.0
where used (24) and the monotonicity of 0f. Therefore E(oo) lim E(t) exists. Now, integrating from 0 to oo we have
S [
(a(t) vtt) y- )tt 8(0) E(oo) < co.
From Theorem 2.1 we know the integrand is Lipschitz continuous, by Barbalat's 's lemma get
lim (I(t) xx, yyt) y²) = O.
Since f is p-strongly convex and M-smooth, f and (v -1 are strictly monotone, we conclude
lim xxt) x=, lim y(t) y²,
which is our desired result.
34

---

E
Centralized classical algorithms
E.1 Resistors and Moreau envelope
For R > 0, define the Moreau envelope of f: R - R of parameter R
n f(x)) = inf =ER TM
[(z)
1
1| =112
2R
Then f is 1/ smooth with gradient given by
f(x) = R f(
pr
(27)
In this section we show that composing linear resistors with 0ʃ equivalent taking Moreau envelope of f. See two circuits below.
m
0f
m
R f
By KCL and Ohm's law for the first circuit, we have
R (o=
which is equivalent - prox Rz (z). Using identity for the gradient of the Moreau envelope, we get
fz)(x) = (x prox (x)) = (x 2) =
R
R
Therefore, the V-I relation pins of x: in both circuits is identical.
As consequence, consider f to be 1/R R-smooth. Let f be pre-Moreau envelope of f. i... Rf= Note that / is convex function. Then from the series connection of the resistors (- Rt in series with R is the same as 0-ohm resistor), we get the equivalence of the two circuits below.
= f.
o
V f
Note that for this circuit & = RV (G).
E.2 Gradient flow
Let f: R" + R be convex function. Consider the circuit below.
35

---

Let x be the potentials at pins of f and be the current entering those pins. Applying KCL and the V-I relations the capacitor we get
Dc uc ic -- (3)(x).
dt
c 0. The resulting differential inclusion is Since e is connected to ground, we have
di --E- -
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy at time k as
E - - =laa* xx x=Bl
E.3 Nesterov acceleration
Let f: RD - RR be a RRssmooth convex function. Consider the circuit helow.
R
C
R
0000
L
Observe, by Ohm's law and y fx) we have
x
+
x
Ry = z RV RV
From KCL, KVL, and V-I relations we have
d
ic
=D (vc (vc x+)
d
-D VD())
d cC
Applying KCL and Ohm's law at æ, it follows
vf(x)= = ic + (vc x+),
which implies that
== vc + Ric-
Differentiating the above equality twice and plugging in the V-I relations, get
d²
d
d
dt2 x R(D&De)
RD dt (D - R² R2DE dt
Vf(x).
Reorganizing, we conclude
d di x + RD
d RRDD
di x
x
- -
(DE
R(DcD))
0.
(28)
dt
Under the proper selection of parameters for p-strongly convex and L-smooth function f. (28)
corresponds to the high-resolution ODE for NAG-SC introduced in [136]
d²
Vs d dt dt
T
Vs(x) + (1 V 0.
dia
As an immediate consequence, if we set = resolution ODE of NAG-SC
1 L = 8pyT C₁ = 2/14, we recover the low-
dt2 + 2 d dt
d
vf(x) 0.
For the automatic discretization of the continuous-time dynamics of this eircuit, define the energy at time k as
1 1 x=* 1BB + Ex
1 1 w v'
2
36

---

E,4 Proximal point method Consider the circuit below.
m
0f
Then from the discussion in $E.1, the above circuit is equivalent to the circuit below.
C
According to $E.2, the ODE for the above circuit is
d
vD((()()))
(29)
dt
Since from (27) we have
(x) = x RVR fxx)
this circuit gives continuous model for the proximal point method.
Applying Euler discretization to (29) with a stepsize of C,R for each ith coordinate, we recover proximal point method
RV ((*") = r² - p proxpxxxp RY (1*).
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy at time k as
E l1aa x'.l.e.
E.5 Proximal gradient method
Let f: RD - R be 1/ 1/R-smooth convex function, and g: R - R be convex function. Consider the circuit below.
V
VRg g
m
m
Observe, by the Ohm's law v RV (z:) Using KCL at and KVL at we get
ic -vf(x) - "'((e)
ve
(v)
Applying V-I relation for the capacitor and eliminating gives
d
vx(x)=
(Vfl))+**9(z (((2))))())))))))
r dt dt
2c
37

---

Organizing
d x
= (V" (V))+ (4) R d v
1
dt
We show that R
de fx(x))
M for some M 0, thus
d
1
di -ー- CR ((RV RV /) + (z)) (0)
(30)
Applying Fuler discretization with stepsize C'R we have
k+ r
RVF) + RV (I*) +M(CR)). ((RV" -
CR Multiplying CR on both sides and reorganizing gives
CR
x+1 x² (RVV g RV + RV (I +0(CR))
RVF) (prox 1) (I (-- + +M(CR) = proX - fz*) + O(MC)).
If set C & R, we recover the proximal gradient method.
For the automatic discretization of the continuous- time dynamics of this circuit, we define the energy at time k as
C llee -e- e²112.
E
2
where ex =x-- RV
E.6
Primal decomposition
Let fI...., fN: R R convex functions. Consider the circuit below.
0f
OfN
m
m
C
Let IN, E RD be vectors of potentials pins of afi..... 0fN respectively. From KVL, we have
21 TN vc.
Using KCL at and the V-I relation of nonlinear resistors we get E/= Uj + ic = 0, where Y (zz). Using the V-I relation for capacitor we have
di = 1 Σ Uj
d
-
Discretizing above V-I relations, recover primal decomposition
Ji 015(2/))
For the automatic discretization of the continuous-time time dynamics of this circuit, define the energy at time k: as
C Ex
f|ee x= 11....
2
38

---

E.7 Dual decomposition
Let fi...., fv: R
R convex functions. Consider the circuit below.
0f
QfN
0000
1.
Using KCL. at xy and V-I relation for nonlinear resistors we get
E 0ff = 0ff
Using KCL e yields Σ ΣØ=1 Uj
0. Using KVL and V-I relation for inductors we get
e e- Uj = UC2 L d
di ic,
Summing over j 1, ,,...,N N gives
N Ne
d N
Σ d dt ic;
Σ
x==
Σ yj =0
dt
j=1
j=1
j=1
leading to e (1/N) N
2y. Discretizing above V-I relations, we recover dual decomposition
2 0fj
(12,)
N
k
Σ
k
= N
j=1
h
k+1 2
12
(c
x
L
For the automatic discretization of the continuous-timg time dynamics of this circuit, we define the energy at time & as
Ex
11: 0ブ 12
E.8
Proximal decomposition
Let f1...., fN: R" + R be convex functions. Consider the circuit below.
Qh
θfN
m
m
.11
0000
L
39

---

Let 2i....,, EN E R" be vectors of potentials at pins of . fN respectively. Define e e R be vector of potentials on the bottom the circuit. Observe, by Ohm's law and KCL we have
V/ = ic, + 1 ( xz) E (2z(
R
It implies that prOXæf (e Ric.). The V-I relations for inductors are given by
d a'c ve/L (E x\/L,
where ET (T...., Nmxm
Further, note that by KCL Ey - Ej=1 Mj 0, therefore E E relations for = Ne FEr we get the following ODE
4 Ey O. Using the above V-I
RE ic) RE d ic ELETE-
R
R
T
(31)
dl
We initialize circuit with (0) and E NI gives
1
0 Ey) = (0) + (0) - x<0))/ R)
9
R
Thus the solution to an ODE (31) g 0 and we conclude N Ex. The V-I relations for the circuit are
Ij prox (e+ Ricc,) j= 1=
e Ex
d
di ic
(ETe-z)) L)/L.
Discretizing above V-I relations recover proximal decomposition (e RiiE));
proxes,
I,...,N N
k+ 1
Fat
N
h ((ETettI_2tt 2441).
k+1
1/2
c
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy time &s as
E Σ 12, 2911 + ylle" - x x=1
where y is parameter that is being optimized, see SG.
E.9 Douglas-Rachford splitting
Let f.g: Rd >> R be convex functions. Consider the circuit below.
Og
O
m
m
L
81
0000
40

---

Using KCL at 21 and Ohm's law we get
R (a2 x1) + E 0g(z1),
which implies 21 prox Ry (22 + Rig). Similarly, using KCL at 22 and Ohm's law get
1 R
01 x2) ic E 0
which implies 22 proxRo (I1 Ric). From KVL and V-I relation for inductors we have
d ic
1
L (22 - 21).
dt
Discretizing above V-I relations with Rt = - 1 and stepsize h 1, recover Douglas- splitting
a k+1
prox (2 + -RiE)
2 k+1
(roxns(E Ri
k+1 i/ + h kt1 - (
c
For the automatic discretization of the continuous- time dynamics of this circuit, we define the energy at time k as
L & =
2 21 vi + > - x 2=1
where y is parameter that is being optimized, see $G, and yf 0g(x*).
E.10 Davis Yin splitting
Let f.
h: R" + R be convex functions, with h also being 1/S- S-soohh.h. Consider the circuit below.
0g
h
Of
m
m
m
0000
31
22
Using KCL at e and Ohm's law we have
31 = -2-
Si-s Sig = 32.
Applying KCL at Zzz get
e 32 Vh(rz)-
is
(32)
S
Using KCL 33 and (32) it follows
T1 33
+ ic
T1 T3
I2 -
Vh(x2) E 0g(xa).
R
S
Using KCL 21, we get
T3
0f(z)).
S
41

---

Organizing, and applying V-I relation for inductor
R
R
33 = proX Rg
1
5
11
5
RVh(21))
21 = proXnf
Ø3 +
(e
x1)
5
ic SS
11
Vh(x1)
d
ig
I (2) xz).
dt
Now we eliminate the term ig. Differentiating (32), applying L L 21 33 get
d d
d
(2) 23)
cc
Vh(r1)-
dt dt
dt
In other words,
d S x1)
d
1 s d
di L, (13 (13
Vh(x1).
di
di
Using "alternating update" and Euler discretization of and æ1, we have
((1+
R
R
23
k+1
prox
5
se
RVh(x))
PRoXRt
D/
k+1
R
(c
xt)
5
Sh
Sh d Vh(at).
k+1
k +
k+1
k-1
L
dl
Set R S= and L a² then the above can be rewritten as
23 h+1 prox, (2xf e - a vh(+))
2 b+ = Prox, f (e + 2zz k+1 - =x))
A+ = et + xz xº a d
vh(zt).
dt
When _ Vh(**) is bounded, then a² & (h(=*) O(a?). For small may ignore this term and recover DYS.
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy time & as
& 112 > -
where y is parameter that is being optimized, see $G, and x R(yt + vτ), vt Of(x*). 3/ 0g(x*).
42

---

Decentralized classical algorithms
In decentralized optimization setup, we are given a graph G (V, which defines the communi- cation pattern between agents. This means that each agent is constrained to communicate only to its direct neighbors for the edges of the graph.
We define T as the neighbors of j in graph G. For simplicity. in each example we only illustrate the circuit between components indexed by j and I, where j and are connected through an edge in the graph G.
F.1 Decentralized gradient descent
Let fi...., fN: Rd R be differentiable convex functions. Decentralized gradient descent (DGD) derived as a gradient descent the appropriate penalty formulation a decentralized problem. Similarly, to construct DGD circuit apply the gradient flow circuit of $E.2 to appropriate nonlinear resistors and arrive at the following circuit.
V fi
m
m
R
31
The right side of the circuit contains the graph with resistors Ry connecting vectors of potentials Iy R" and 24 R" for every neighbors and in the given graph G.
Using the KCL at 22 we get
0 Vbb())
Σ eT,
Tj It
icy-
Rii
Applying the V-I relation for the capacitors we get
dt x, dt vc, - 1 [zz(z,)) + Σ (xy -1) Ryy
ter
Euler discretization recovers the DGD
k+1
x +
CR2i xt - (
CR2i
IET
IET,
with gradient stepsize h/C and the mixing matrix
1-
b EiEr,, CRa
if
W j
h CR,,
jf 1, LET,
otherwise.
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy at time k as
E
2 |a - x;.
j=1
43

---

F.2 Diffusion
1/R-smooth convex functions. Decentralized gradient descent is derived as forward-backer backward splitting fixed point iteration of the appropriate penalty formulation of a decentralized problem. Similarly, to construct a diffusion circuit we apply the proximal gradient circuit of $E.5 to appropriate nonlinear resistors and arrive at the following circuit.
Let fi..... R"
fi
Vfj
R
Ry
C
The right side of the circuit is the graph with linear resistors Ry connecting vectors of potentials ey E R and E, R" for every neighbors j and in the given graph G.
By Ohm's 's law we have ve, = Ej = 2j - RV fy (zz). Using the KCL at we get
Σ
Ej el
ic, 0.
EET,
Applying the V-I relation for the capacitors get
d
R d {)}(az)
dt ej = J .
dt
1
V1z(2g)) + Σ
(z, - RV RVf)(z,)) (x) RV (zl))
-
LET;
We can show that R
4 [x,(), < M for some M > O, thus
d - 1 at Vzb(z,)+ +
(x RV)((1,)) - (x) - RVS(()))
+ +O(MO))
TET
Applying Euler discretization with stepsize C'R gives
A+1
1
Σ
R
(2) - RV
R3y
IET
R
(at RVF((Z))+((MM))
R3
Jer
with gradient stepsize R and the mixing matrix
Eier,
ifj=
W
R
if I, LE
R₁
otherwise.
If we set C < R, we recover the diffusion method.
44

---

For the automatic discretization of the continuous-tin time dynamics of this circuit, we define the energy time l as
N C lle c3
E = -
j=1
where ej =z (x) for all = I,...,N. N.
F.3
Decentralized ADMM
Let II....,JN:: RT + R be convex functions. Then the decentralized ADMM circuit is given below.
0fj
Qfi
31
0000
R
Note that this circuit is similar to the one in proximal decomposition in $E.8 with the difference that instead of a single net we now have a net Eg for each edge (j. () in graph G. Denote currents on inductors to be i R and ézı E Rm
Using KCL at 2, we get
Σ
Lics Syt - Iz
(zz)
(33)
LET,
We initialize the circuit such that (c,z(() + (0) = for each edge (j, 1) in graph G. Now consider
KCL at ejt
(est - xz))
(est x1)
ie icij
(34)
R
R
Using V-I relation for inductor we also have
/ ic
_ icss
d
- (2ez1
1
- Ij - x.).
Combining the two equalities above we get an ODE
R (iest + ici))
(ien+ien)
Using initial conditions the solution an ODE is ictt + icij = From (34) we conclude that Cyt (2, + 21).
Using (33), we get the V-I relations for the circuit
xj proX(R/II;DA
(Rich + egi)
[Tg
LeT
egt 2 (x, + x1)
ic 1
(ejt .r,);
45

---

for every = =....... .N' and every edge (j.() in graph G. Discretizing the V-I relations with stepsize L/ R. we recover decentralized ADMM,
x k+1
RRi2 + egi))
[Tyl IET;
k+1
3 2 (ooftt + abttt
1
ic k+1
ieji
+ R (c z 1.
For the automatic discretization of the continuous-time dynamics of this circuit, we define the energy time k as
&
Σ
H -2
- 2 11 121,,12 7 x² 11
L
edge (1d)
where y is parameter that is being optimized, see $G, and 22 is the current through inductor at equilibrium.
E44 PG-EXTRA
Let f1,...,fN fN: Rm R be convex functions, and hi...., hv RD R be convex M-smooth functions. Then the PG-EXTRA circuit is given below. Denote current on inductor going from 23 to
m
Oh
V h4
R
Ljt
Vhy
Ej
Zj
R
to be ic Rm
Recall $E.1 and apply Ohm's law get
J
ej
prox RS, (eg)
(e,))))) = Ij Ej
R
R
- R
This yields zÿ = RV fz(e,) = prox R., (ez). Using KCL at æj we get
= Vhy(a,) + Σ
(ic + 23 --- 2z
(35)
R
IeT
Define the mixing matrix
1-
ΣiEr, R₁i
R
ifj
if IeT,
R2
otherwise.
46

---

Rearranging the terms in (35) we get
cj = 3 RVh)(1z)
Σ
Riggi
Ij 21 Rys R
IEr
N
= 2j
Σ
W5i(2s - -xi) RV))(zz)
Σ
Rigst
1=1
Ier;
N
Σ
W HVh5(o;)
Σ
Rigst
IET,
Using the V-I relation for inductor we also have
1
icn
(2) xz).
dt
Lis
Set Lir = Ryi for every edge (i, 1) in graph G. Define wi = EiET, Rigg, then
d dt
R
w
Σ
(x) x1)
Li
iET;
Σ W W
2j
Combining the above, we get the V-I relations for the circuit
prox Rí,
Σ Warn RVh5(xz) wy
(36)
w/
2j
W W
dt
for every j = I,..., N and every edge (j,() in graph G. Discretizing the above V-I relations with stepsize 1/2, and following the decentralized notation of [129, $11.3], recover PG-EXTRA,
s+1 prox Rs (Wa* RVh(=*) w²)
(37)
1 w + (I W)x*
6+1
We can simplify the circuit by eliminating potentials ej as shown below.
afi
V hu
T,3
0f,
Vh
Z2
For the automatic discretization of the continuous-tim dynamics of this circuit, we define the energy at time k as
L 1 2
Ex
Σ
Σ >aa -xx x11
odge (1)))
where 7 is parameter that is being optimized, see $G. and 22 is the current through inductor at cquilibrium.
47

---

G Automatic discretization
In this paper, we discretize admissible dynamic interconnects corresponding to the following decen- tralizes setup with graph consensus
minimize PIo.eN e RRm/N subject
(1(11 +... (N(
(38)
=- 31, j 1-,,..,,, N, LET,
where I'y contains the neighbors of agent in the communication graph, see ŞF. We assume that the communication graph connected, ensuring that all agents can communicate with each other [129, $11.2). The static interconnect for this problem corresponds to the consensus problem
minimize 21 21 IN c subject
f1 +... SN(EN)
I1
NN:
which is a special case of (1) where ET (I,..., I) E mmxm/N Therefore, have m/N nets each of size N with 2. E R for all 1,...,, N. This setup generalizes the setup of the classical methods discussed in ŞE and SF.
For automatic discretization, we focus on dynamic interconnects that have the same RLC circuit across each net, ie., the dynamic interconnects represented with the multi-wire notation.
Runge-Kutta method. The capacitor and inductor ODEs are of the form
d _ #(t) ((x())).
dt
We discretize ODEs using the two-stage Runge- Kutta method, with coefficients a, B, and stepsize
r k+1/2 x² +hh((") x² + + (1 (/tt/))
k+1
We clarify that simpler one-stage discretization schemes can also be used. We chose two-stage Runge- Kutta to demonstrate that multi-stage discretization schemes compatible with automatic discretization methodology.
Energy descent. Let discrete-time optimization algorithm generate sequence {(v*, , " with v² z² E R" (voltages across and currents through the branches of interconnect) and x², y E RT (potentials at terminals and currents leaving terminals). Let the subscripts R, L, and C denote the components related to resistors, inductors, and capacitors, respectively. Then the energy stored in the circuit is given by
E5 2 line vell.. + +21l/ 12..2.
Lemma G.I. Assume f: R + + (ooo is strictly corvex function and the dynamic interconnect
admissible. Let discrete-time -imee optimization algorithm generate sequence {(v sk x ,yy M there exists 7) > 0 such that for all k = 1,2,... the energy descent
D₁ (Ex+1 + n/ax --= x². x²-""= Ex 50
(39)
holds, then & converges to primal solution.
Proof. Suppose there exists 1) > 0 for which (39) holds. Then we have
0 < EK+1
< EK - m/ x², n - y*)
< Eg
Σn Maak x², x² y²).
k=0
48

---

By monotonicity of subdifferential operator Of, we have
(x x² .y y²) 2 0, df(l")
Thus rearranging the terms we get
0 < Σ (a
x², x², --) S Ev-
k=0
Sending K to infinity, by the summability argument it follows that
- x"'"" - + 0.
(40)
Define the Lagrangian function
Tax, 2, = -y- y=(xx= 2.
Since x* E R(ET), there exists some 2* such that x²' ET Then for fixed 2* and y", function L(x, 2", y²) is strictly convex. Its subgradient is given by (y y") E Oz, ,²,"") for y E 0z(z),
therefore, L(z*, 2², y*). Together with strict convexity this implies that L 2", y*) achieves unique global minimum at x with L(x", ,,,,²") =((²). By the subgradient inequality, we have
(x - - -²) 2 L(x", ,"" ,²,²²*) f(x*) 2
Then the condition (40) implies L( ;"²"") (x*). Therefore, xt - x. which concludes the proof.
By the descent lemma G.1, the discretization is dissipative if there exist value vj 0 such that D3 = (Ex+1 + 17(2** x=, 1 n²)) & S 0
for all h = 1,2,... Since the descent D2 is defined using a one-step transition, without loss of generality, suffices to consider k:
Solver dissipative term. incorporate dissipation from the linear resistors as in the continuous-time energy dissipation (7), ie.. try establish
To provide more flexibility with the Ipopt [155, 9] solver, we also
DR = (Ex+1 + +)/ - - p Ex.
(41)
with 7) > 0 and p 2 O. Also see $D. If there exist values 0 and 2 0 such that Dj S 0 holds, then the discretization is sufficiently dissipative and Lemma G.1 applies.
G.1 Dissipative discretization
In this section, we fix a, B, h, 77, and p and describe a convex optimization problem that checks whether the discretization is dissipative. We focus on problem (38).
Worst-case optimization problem. To verify if the dissipativity condition D₃ S 0 (41) is satisfied for given discretization, we can alternatively solve worst-case problem. Specifically, this entails determining if the optimal value of the following optimization problem is non-positive:
maximize subject to
E₂ E₁ + tt x= y¹ yy> + p
E, = 1 E1 oill. + - 1
s S [1,2}
(v) 1 x! .y is feasible initial point
(42)
(v2 12, x² y²) generated by discrete optimization method from initial point
f FEF.
where f. 2h a 2 wt j x² y² are the decision variables and F is a family of functions (e.g.,
L-smooth convex) that the algorithm is to be applied to.
49

---

Reformulated worst-case optimization problem. Recall that we assume that the RLC circuit across each the same. Thus we can define an operator mat(2) that reshapes vector 2 R into matrix of size o/n, where each row contains information (voltage or current) of the electric components that belong to the same net. Define index sets
1k 11,1,,,,,4
In [I,...,N},
Ik x IN (N,,)llEIN,KEI
and matrices
и = maa) mat(i") [ [ofl E (R
G = H THES E2522//t
F [1t] (x. ERIMIN
where u E 0f((a*) and Sf = fi(x²) for all I E IN. Note that we have
|F = |
G = (20 [k([))
and for [Tx 4 this simplifies to
[F
G = (20
+ / 4N)2.
Recall the circuit ODEs are discretized with the two-stage Runge- Kutta method, leading to the variables mr*) mat((*), at yx that are linear combinations columns in H. The coefficients
of these linear combinations are polynomials in 8, and h. In other words, there exist matrices vk 1 x² yf such that
mat(v*) Hv* mat(i") Hi" == =x of Hyl
for all & E IK, l IN. Similarly, we can find f such that ff =f For fixed parameters a, B, h, n, and p. the problem (42) can be reformulated as maximize hN...N..H
Eg - El + , - -x", -x,,"² 1²) + 1
subject
E, } 1l1 1/ rEll.. + 11 iz Bl s {1,2)
mat (ua) llv*, KE
mat(?") Hit EE
x² = Hx kElK
/ = Hyt, k IK, LE Fm,M (R"),
le IN-
By the interpolation lemma ([149], Theorem 2), fi Fu (R") if and only if
2 fl fi + (of x - x²) + 2M
l6 of l12
||I"" x² 1/ of 1ll.. i,j Ik.
2(1
/
Therefore, we can replace infinite dimensional decision variable fi E Fr,M(R" with xxl -1) inequalities.
Grammian formulation. Now using Grammian formulation, the problem of finding the worst-case energy difference over a given family of functions reduces solving an SDP, similar to [150]. This SDP can be presented compactly as
maximize G,F
FT
Dp
subject to
FT G
voo(G)
i.je Tk
(43)
where is a vector with dummy variables that encode the monomials of a, h, n, and D R (I and S E w (1I some matrices with constant coefficients.
50

---

Dualization. Define variables for the energy descent as
VD [F= vec(G)"
and for interpolating inequality indexed by lij as
(Vs)uj = [FT vec(G)"]Sugp)
Let Z and Aay for all i,j E Tx. = 1,...,N be the dual variables for problem (43). Vertically stack Äny and (Vs)us form vectors À and Vs respectively. The Lagrangian that generates primal problem (43) is
L(G, J, 2) VD VTVs + Tr(GZ),
and the dual problem is given by
minimize
0
2,X
subject to
DFp X Spp = 0
DGP ScP + =0 2=0
(44)
A 0.
Algebraic proof. Using a weak duality we have p* S d' Let Z and X be optimal dual variables with d' = 0, then for all G E S (((0H141//+ and F E R [ix IN it follows that
L(G,F,Z,,') FT (Dpp (X") SFp) + +Tr (D)) Scp Z*)
Therefore, having Z and A gives algebraic proof for the worst-case step energy difference
VD
Tr(GZ") $0,
20
50
where because Gram matrix and (Vs)ui S for all fi Fp
G.2 Optimizing over discretizations
In this section we also optimize over the parameters o, 8, h, 1, and
G.2.1 QCQP formulation
We formulate the dual problem (44) as QCQP following [45].
minimize P.X.P subject to
DFp X' Dep XT STP PPT =
p peQep+ a.' = 0, is lower triangular
1, I..... p
diag( P) 2 X2 0,
where relations for dummy variables are specified using quadratic or bilinear constraints n² Q.P T
a p= 0.
51

---

G.2.2 Lifted nonconvex SDP
Alternatively, we can formulate the dual problem (44) as lifted nonconvex semidefinite problem with respect to variable w (v, E R #I+|i| Specifically, we have
minimize
0
W.Z
subject to
Df(i:))u Tr (S,(.,,:)) = 0, i ==1...., [F
De(i,:)w Tr ( + Z(i.i) = i= 1..,,,,... |G|
Tr (Q.W) () + ,. w=0-0
(45)
W ww.
Z = 0
À 2 0,
0
ST
where Sp
Dr = DF 0.. S. =
Da = De 0 }
SF
Sc
Qe
0
Q.
and a. = (ae, 0). In the above the transpose for the third order tensors Sp and Sg obtained by transposing the first and third dimensions. Note that with the exception of the rank-1 1 constraint W = www" the constraints define convex sets.
-
0
0
G.2.3 SDP relaxation
To find globally optimal solutions to the nonconvex optimization problem, methods like spacial sanch-and-boumg require good initial bounds on the variables. Following [45], an SDP relaxation of (45) is given by
minimize W,
0
subject to
D (1,:)w Tr (p(,,,)) = 0, i= i.,,... FF
Da(i.))w Tr :e(...,))W) + Z(i. =0, i= 1...., |G|
Tr (Q.W) + प. ==
(46)
W w
TT
Z 2 0
A A20.
Problem (46) is now convex optimization problem, since the rank-1 constraint W = wwf has been relaxed to W ww."" This constraint uurn can represented equivalently using the Schur complement.
52

---

H
Package ciropt
In this section, we present simple problem instance demonstrate the step-by-step process of obtaining a discretized algorithm with our methodology.
Optimization problem.
Consider problem
minimize
f(x),
where f is convex function.
Determine the static interconnect. Static interconnect determined from the optimality conditions. The optimality condition for this problem is to find an such that 0 af(z). Thee corresponding static interconnect for this condition provided below.
173
0f
Admissible dynamic interconnect. An admissible dynamic interconnect with RLC components relaxes to the static interconnect in equilibrium. The following provides example of such dynamic interconnect.
Ra
m
0f
fb
The V-I relations for the circuit (left column) and convergent discretized method found by our method (right) are displayed below.
2 prox (R/2)S (2)
* prox( (2*)
2
8¹ 2 (2 -x²)
y
(2 x)
R
d
h
22
Ry 302)
c A+1 c
Ry 3c
dt
2CR
2CR
h
(5Ry + 382)
k+1 *
(5Ry* + 3e
dt
4C'
4CR
Automatic discretization. Now we find a discretization parameters for this dynamic interconnect that guarantee algorithm convergence using ciropt package.
Step 1.
Define a problem.
import ciropt as co problem circuitttt ()
Step 2. M oc.
Define function class, in this example is convex and nondifferentiable, i.e., μ 0 and
def fo.defffunction function (problem, mu=0, M=np. inf)
53

---

Step 3.
Define the optimal points.
x_star, y_star, f_star f sttationary_point ( return_gradient, ler.fffccionvvauleeeeeeee
Step 4. Define values for the RLC components and discretization parameters, here for simplicity we take a = 0 and 1.
R, = 1, 10 h, eta problem.h, h, problem. eta
Step 5.
Define the one step transition in the discretized V-I relations.
2_1 = proloa.set_innttaalpoonn
e2_1 problem. problem.set (ottlentss__mmtiialpooottt
x_1 = co. ww.proxmal_sttp(21111
f, R/2) [0]
y-1 (2 R) (z_1 x_1)
e1_1 = (e2_1 R * y_1) /
V_CI_1 e2_1 / z_1
V_C2_1 e2_1
e2_2 e2_1
h / (2 * R C) (R * y-1 + 3 e2_1)
z_2 z_1
h (4 R C) (5 R y-1 * e2_1)
x_2 = proximal_stepp2222
f, R/2) [0]
y_2 (2 R)
(z_2 x_2)
v_C1_2 e2_2 / 2 z_2
v_c2_ e2_2
Step 6. Define the dissipative term
& El + n/xx - x²,y² -²).
Solve the final problem.
E_1 (C/2) (v_Ci_1 x_star) (C/2) * (v_C2_1)****
E_2 (C/2)
(v_C1_2 x_star)**2 **2 (C/2) (v_C2_2) **2
Delta_1 eta (x_1 x_star) (y_1 y_star)
problem. set wwwppeeewwneeeeerriiieeiee
(E_1 Delta_1) 1))
params = problem. solve() [:1]
This gives the disretization parameters
b = 6.66,
= 6.66.
The resulting provably convergent algorithm is
zk prox (12)(1/2))(2")
y 2(2 x²
w w 0.33(1² + 3)
A+1 =² #=-0.16(5) * + 3w
New algorithm.
Solve your problem using new algorithm. Consider Huber penalty function
à R R R
2
x 1
((x)
2x
|x|
1.
54

---

We consider the primal problem
minimize subject to Ar=
f(x) E, p ci)
where
Rd Rux b R and C E R", and solve the dual problem
maximize
gly) - bTy.
We apply our algorithm to solve the dual problem. Note that the proximal operator prox ag (0) is equivalent
argmin (ʃ(x) + (a/2)]lAr b1 + oT b)), y = デ at b).
Since f is CCP and 2-smooth (as Huber loss), f is 1/2-strongly convex. We take m = 30. 100 and sample entries of A, c and b from i..d. Gaussian distribution. Finally we rescale the entries of A by Amin (AAT) to have that is 1/2 stronly convex. The following Figure 10 presents the results of the algorithm applied a random problem instance.
10
10-2
If(x] //
10
10
10
15
25
Figure 10: Relative error across iterations when applying the new algorithm.
55

---

I Numerical experiments
I.1 Decentralized ADMM+C
Consider a decentralized optimization problem
minimize R
Σ f((x),
where fi...., fN are CCP. Suppose furthermore we know some of the functions are strongly convex, that is, suppose there a subset S C. (I. such that fy are strongly convex for E S. We wish to find an efficient algorithm that fully exploits the additional information for fj's.
To solve the problem in decentralized manner, define primal variable 2; E Rd for each agent function fi- To leverage the strong convexity of f for each j E S, we could consider implementing a specialized update rule for zy that is more effective for strongly convex functions.
We consider a modification the DADMM circuit in $F.3. Recall from $3.1, a circuit with capacitor and inductor corresponds to method with momentum. is known [124] that momentum accelerates the convergence of methods for strongly convex functions. Therefore, we propose to attach capacitors to the circuit in $F.3, on the nets that directly related to z 's in j E S. We anticipate that the method derived by discretization of a new circuit (using our automatic discretization methodology) will outperform the DADMM.
Consider a modified decentralized geometric median problem from [138]. Suppose each agent i E [I....,N] N holds vector b; E R" and consider the minimization problem
minimize z TM
Eies (II== bill2 + || byll2) Eigs ||
by 112-
(47)
The minimization subproblem has an explicit solution, i.e., b, -
prox (z) = b4
(l|b, øl12 - +)++
|b; E||2
where
i $ S E S
i $ S
1+2p (= + 2pb:)
P 142p
i
S.
We set 100, N = 6, S 54, and sample vectors b; E R 1100 from the uniform distribution
over | 100, 100] 100 We use graph G provided in Figure 9. We initialize iterates to x = b, for all i.
We use a modified DADMM circuit $F.3 for the graph in Figure 9, This modified version includes an extra capacitor connected at e,s, to which we refer as DADMM+C.
0f4
0fs
m
33
44
i445
A1254
0800
0000
L
0000
645
C
56

---

Note when N = 1, the DADMM+C circuit corresponds to the Nesterov acceleration circuit $3. 1.
Using KCL. 645, we have
CA4 + ic31 (e45 x4)
(E45
135 C 645.
d
R
R
dt
Thus for (i.1} + (4,5) the update rule egr is given by (34), while for 645 we get
a 645 - -
d 1 (icas + +ics
1
(2e45
34 225)
dt
R
Other V-I relations remain unchanged as in $F3. The resulting algorithm becomes
a/t1 PFOX(R/IE,DS
1
Σ
(Ri
25 + exi))
[T5]
TET,
k+1 ces A (R(12as + :l(sa) + 2045 [1 axtll
=1/11 25 +
(i.1) (4.5) otherwise
en
h (c -x 21
k+1 = igii + L E
We consider the circuit with R = 0.8, I. = 2 and C = 15. To discretize the circuit, we take advantage of the fact that the strong convexity of fi is for (47). Specifically, we apply our automatic for fi with i & S and μ 2 for fi
discretization methodology convex functions, setting 100. The sufficiently dissipative parameters we find are
with E S, and using smoothness
3.70, h 3.52, 0, a 0, 8=1,
4.48.
We compare DADMM+C with DADMM and P-EXTRA. Based on grid search, we DADMM in $F.3, and R = and h1 = = hN = 0 for PG-EXTRA in $F.4 to get P-EXTRA. Note that the parameters of the proximal operators for DADMM are scaled by 1/[1i) in contrast to P-EXTRA, where [Ty is generally not equal to 1. We use Metropolis mixing matrix for P-EXTRA,
0.6 for
if i E D
Wia
jer, Wú
otherwise.
The numerical results are illustrated in Figure 11. The relative error for DADMM+C decreases to 10-10 10 in 66 iterations, for DADMM in 87 iterations and for P-EXTRA 294 iterations.
EXTRA DADMM
Claeuit DADMM+C
10
2
// (---)-1
10
1
6
10
10
10
20
40
60
80
100
Iteration
Figure 11: (Left) Underlying graph G. (Right) Relative error
[f(x*) f 1f vs. k.
57

---

L111 Convergence proof of decentralized ADMM+C
We first review the meaning of the numerical values in the previous section. Suppose (x". y²) be primal-dual solution pair. Then by Theorem C.2, there is (e", ,",) E Dr that satisfies (v*, (0,,)) ) = ((0, 0, (0, 20, 0)). The numerical values imply, for the energy function
Ex = Σ 12
22
Σ
15
|le)) - x51l 3.52
Σ s4Dddes
1 - -
2
UDEE
following inequality is true up certain numerical precision
(Ex+1 + 3.7 - x², y - y²)) - & 0.
This inequality guarantees the convergence the method we've used in the experiment. Inspired form the numerical results, we could obtain analytic proof for generalized cases well. To clarify, is the set of edges introduced in $F, and each edge counted twice in the sum ΣG,ne
Lemma L11 Let f;: Rd RU (co} are CCP functions for j E {1,.... .......N) NJ and S C (1. N). Consider the generalized DADMM+C
k+1 2j
(r/X(/
(Rit E,t + egi))
[T's
IET
Je/i- - on (Blikg) fa + :l21z) 20ti 2n k+ - 2f 2f+1)
(j. s otherwise
k+1 j1
[b(()t) 2ttt)
k+1 icil
icst + 1. (077
h+1 1
with initilzation 622,, i2,, for all edge (i,t) in G. Let (x*,1") be a primal-dual solution pair and
(u*,i*) E D2- y. Define the energy function as
EN Σ
22,
Σ
C
-
2111+
Σ
h
|1e
2R
(1.)EA
KLUACS
sellines
Then for all R, L, C, h.h > 0 that satisfy
max
{1
(1,
|
2h
S 52
hR L
following inequality is true
El+1+ +
2
hR
Σ (AD)A
k+1
2
+ h(x k+1 x,, x", v3)
E6 S 0.
2R
L
Proof. For notation simplicity, define
5 J+l 2/ + R (cts -55-) 22t1).
Note, from the first line of the algorithm we have N+1 + 1t 11 12 =11; Eier, (Rie, + tzt).. and therefore
A+1
2z +
(e -
1 22t1)
Σ 2デ
JEr
LEr
& 1 - -12 2
(i) Difference of Eiinen
Name
A =
Σ 1
:2,1
||
Σ
i2 - -2,1 ||
2
(AE)A
GDDEA
58

---

Observe
AL h
= h
C2
f2 +
I [
h k+1
- n2t11
- Σ
12,
-
22,1
1
2
2
(WDEA
(i,)EA
Σ GHEE
k+1
/241/ )
+
Σ
h
m 111
2L
(),))A
Σ UNEE
A+1 31
k+1
1
(c)
$2.00 ) + Σ
h
k-1 1
2r 2241
R
2L
31
(1D)A
k+1
k+1
+ Σ
R+1 k+1
12,z)
31
-
R
(iIEE
(11)).
Σ
h
k+1
25
2L
(
1
h
Σ
k+1
k+1
(ettt)
k+l
2//t11 ,egx- -cp1"
e )) :2,))
R
2L
R
(DEE
(JDEA
Σ
k+1
k+1
'2,1)
k+1
-. V5l
k+1
GDEA
(
On the other hand, from Theorem C.2 we know i/p2 = 0, by KCL at I. we have 33 = Eier, "2,,1 Therefore
N 13.1ÿi 1-1 $2,1)
N
Σ A-
u k+1 1221
Σ
(an - 23 V3 h- m5)
j=1 LET,
j=1
Moreover, 42,,, = - "c,y, Eg1 = =eip Therefore we see
k+1
k+1 holds by their definition, and u3 = xt as x² is the solution.
k+1 JJj (c,))
E
1+1 - 22, + +z22)) =0. O.
GAEA
jeLUNDE
Lastly, following equality is true for 00)
2 ||
x+1
-
k+1
5
31
411
=
T
T
g1
k+1
-
+ (c -
-
91
x+1
-2
k+1
o
x+1 2
1
k
c 1
2
51
27
Finally, applying above observations we have
A = -
1
[
h
72
Σ
k+1
25
1
2L
2R
(iT)EA
c 1
Σ
k+1
Σ
T(ch+1 -22-2) + (c))
-c 91
2R
S1
31
2R
(1))A
(JH)EA
Σ (a k+1 - -z3 k+1 - v2) +
Σ
k+l - x3. b+1
Eil
/=1
(HEE
(ii) Difference of E Ejet(Ancs & | =
Name
Do= =
Σ
k+l
Σ
1 - x7
2
5t
2
59

---

Plugging the definition of the method, we have
Ac
C
51
k+l
23
||
2
1
Σ
C
2
k+l
- zj
(ct -)))
(
C
Σ
A+1
k k+1
-x})
C
k+1
eti ||
2h
Ejt
4h
51
(11)ss
=
2
Σ
+ +11
1+1 k+1
.991 :egt"
- -x3)
4h
Σ
- 1
(ANss
(81)s
Σ UWCS
k+t k+1 -25) -2)
C
Σ
|+t1
-
1|2
91'
4h
UNCS
||0/ mz11²
(iii) Difference of Ejeh(indes 28
Name
h
h
4, =
Σ
h+l 31
Σ
|l xz
2R
2R
For (i.1) g.S. from the initialization we can check
22
b',,,
and from ejt
k+1 1 (1gtt + xx x2)t)), inductively
2
A++1 = */2,, + L (ett -2)+) -,, L E,
(cut))
(9l
|+l - xt =x(t) - - ktt1
-1%1)-
Therefore 121 = -,,,, for all k. And from the definition of ffj o we have
k-1 - 2/x R (e) - - +) +
2 R
c2tt))
k+1
2
C/ - c
Vig
R
And thus
R
k+1
Vig
+ yig
Now proceeding the similar calculation and argument for Ac, we have
A
Σ
k+1
25)
Σ
-
k+1
h
=
2R
GagEs
Finally, summing the calculations in (i), (ii). (iii), we have
1 (Ex+1 Ex) +
Σ
N
(1
k+1
23. 3/
+
1
h
72
Σ
k+1
25
2211
R
2L
2R
j=1
UrEE
To
1 (AL + + Ary + Σ (1 23 2
k+1
リイ) +
2R
2
hR
L
72
Σ
-
k+1
-
5=1
UDDEA
1
Σ
( k+1
1 + -
(c - + ||
|
R
(AA)A
1
CR
1
Σ
x+l et
1|²
1
c3
6+1
e//l²
2R
2h
72
2R
72
[s
Therefore, for all R, L, C, h,
0 that satisfy
2 hR
CR
2
0,
20,
1-
20
2h
72
or equivalently,
max (1,
2h
hR
<² <
CR
L
we conclude the desired inequality.
60

---

1.2 PG-EXTRA + Parallel C
In this section, we introduce an additional pipeline designing new optimization algorithm via circuit. The previous automatized discretization pipeline has the advantage of guaranteeing convergence; however, it may provide a conservative step size since it considers worst-case scenarios. As result, it may eliminate the possibility of finding efficient step size that works for certain optimization problem in practice.
Our circuit-based approach has the advantage of designing a variant of the prior method quickly, that likely converge and possibly works better based on physical intuition. Furthermore, the variant method provides greater freedom in selecting parameters to tune. We provide an example of new optimization method obtained with exploiting these advantages, that outperforms PG-EXTRA for the problem considered in the paper introduced PG-EXTRA [138].
We use modified PG- PG-EXTRA circuit $F.4, that includes extra capacitors connected parallel to inductors.
m
I
f
VW
WW
V h4
R
L
R
Cyt
0f,
/
WW
V h2
6j
Ij
R
R
Recalling (6), we know the energy for this circuit is defined as below
Cjt
La
12 ||
E(t)
Σ
UC,, (4) V
Σ
ic,
2
2
jELGNDA
JELÚ,DEA
Note, compared to the energy of PG-EXTRA, we have additional energy terms for capacitors. Observe = zt) - 21)1) (2) - xx) x1(() (t).
Previously, the energy dissipation by the resistors only reduced the values of (1) (1)-ii))) 222,, 11 but now it also reduces the values of ||z, (1) for (j,1) E A. Intuitively, we may hope that this dissipation accelerates the convergence lim (zr (1)) 0, thus eventually speed up the convergence to the optimal. This observation provides informal motivation for the method.
C Following the arguments of $F4, and additionally defining u, Eier, Ric, and setting Cj Ry for (j.() 1) E A with some constant
> O, we derive the following method
A+1 = prox (Wx* RVh(x*) w -²
w A+1 w s(1 (\'*
(48)
A+1 = C - W(a
u
We now consider the decentralized quadratic programming from [138]. Suppose each agent j E (I...., NN holds symmetric positive semidefinite matrix Q, E m vectors aj,Pj E R and scalars by E R. Consider the minimization problem
minimize z TM
$ EN (ITQ,I pJ.z).
subject
a7x < byt j I,...,, N.
Set [5(x) = ((Hle]=5a, (x) and hy(x) = x =Qr + 1..r. where
0 if if < by
{
fo otherwise
61

---

is the indicator function.
Then the given optimization problem recasts to
minimize
N/4 +
z
Since the minimization subproblem has an explicit solution
if fo S by otherwise,
proX (2)
by 4=a +
1 0j
this problem can be solved by PG-EXTRA.
We follow the same setting of [138]. We set m 50. Each Qj is generated by taking the product of 2; and its transpose, where Q3 E Rm is matrix with elements that follow an ii.d. Gaussian distribution. Each Py is generated to follow an i.i.d. Gaussian distribution. Vectors dj and by are also randomly generated, however, we conducted the experiment for the case that the solution of the constrained problem differs from that of the unconstrained problem. We use Metropolis mixing matrix as in $1.I.
The numerical results are illustrated in Figure 12. We compare PG-EXTRA and the variant method (48) obtained from the modified circuit with additional parallel capacitors. We use R = 0.05, R 0.07 for PG-EXTRA and R 0.07,
0.3 and s 0.8 for (48). The parameters for PG- EXTRA were obtained through a grid search. The parameters for (48) are cand-optimized starting from C 0 and 0.5, the parameter selection that makes (48) to coincide with PG-EXTRA when
w0 = 0. The relative error for (48) decreases to 10-S in 147 iterations, while for PG-EXTRA with R 0.05 in 214 iterations.
10a
PG-EXTRA, R-0.06
PG EXTRA, R 0.07
Cueutt PG-EXTRA Paralle
[/(x") (0-))
10-9
10-11
10-11
10-18
200
400
800
800 1000
Iteration count
Figure 12: (Left) Underlying graph G. (Right) Relative error ((x*)-ff) f vs. k.
62

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide the methodology to design an appropriate electric circuit whose continuous-time dynamies converge to the solution of the optimization problem in $2, $3, and introduce the automated, computer-assisted discretization methodology in $4, $5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: This work proposes new methodology for optimization algorithm design. The theoretical nature makes the discussion of such limitations not strongly relevant.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
63

---

Answer: [Yes]
Justification: Our paper provides the full set of assumptions and complete proofs for all theoretical results, with theorems and lemmas properly numbered and cross-referenced.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the code and thoroughly describe the details to ensure reproducibil- ity of the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
64

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide codes and the instructions for using them in the README md file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce
conolicyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpps.ccpppliiiii/mmm/tao./nttc wwtppccppcc////ccccccccccccccclt htplllic/giieeee http//uudieeeeeeeeeee https//ooSSSuuiiseeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the necessary details and code understand and reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our work is theoretical and includes non-statistical simple experiments with synthetic data. Therefore, the notion of statistical significance not applicable our work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
65

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We use minimal CPU computation for toy experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /ttparr////////////eee hta.bliic/hhicrcccceeeeeees
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and our paper conforms to it in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We conduct theoretical research convex optimization and do not anticipate any negative social impacts from our results.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
66

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our theoretical research on convex optimization does not involve releasing data models, hence safeguards needed.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We explicitly mention the solvers and the packages we are referring to in the paper and the code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
67

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new datasets or assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
68

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
69


Reviews:
[{"review_id": "Bl2N1cxeE6", "reviewer": "Reviewer_a4Xt", "summary": "This paper presents a novel framework for designing optimization algorithms with electric RLC circuits. It contains two stages:\n1. design an appropriate circuit whose equilibrium is the solution to the optimization problem.\n2. discretize the continuous-time dynamics of the circuit to form a discrete-time algorithm.\n\nTheoretical guarantees are given on the convergence of the continuous-time dynamics.", "questions": "1. How to determine whether a circuit is admissible from construction instead of checking the equation on lines 98-99?\n\n2. In line 125, under what \"appropriate\" conditions?\n\n3. Although modifications on the RLC circuits of existing algorithms can lead to new algorithms, how to ensure these modifications of the RLC circuits still can reach equilibrium? Is there a general recipe? I would like to see more discussion on this.", "limitations": "There are no separate sections in the main paper. However, the authors state the assumptions for their results.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The idea of the paper is novel. Though prior works have explored the relationship between ODE and optimization algorithms, using RLC circuits to explain existing algorithms and design new ones seems a novel framework.\n\n2. The authors demonstrate the proposed framework covers a lot of existing algorithms and can be extended to new ones with convergence guarantees, which is practically useful.\n\n3. The paper is comprehensive and overall well-written.", "weaknesses": "1. Some parts lack clarity. See *Questions*.\n\n2. The theoretical results in this paper focus on the strongly-convex settings. It is unclear how can this be extended to convex or nonconvex settings which are more common in real-world problems. \n\n3. It would be better if there was more discussion on the benefit of using this approach to design algorithms compared to the standard approaches.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to hear that the reviewer found our proposed framework \"novel\" and \"practically useful\". \n\n\n**W1.**\n\nThis is further addressed below.\n\n**W2.**\n\nThe assumption of strong convexity is made to prove the well-posedness of the circuit ODE. We clarify that this assumption is not necessary for showing convergence of the discretized methods (Lemma 4.1). In an extension to non-convex setups, we expect the technical well-posedness of the circuit ODE to be somewhat challenging (especially for non-differentiable non-convex functions), but the convergence analysis should not be difficult, at least not more so than how non-convex optimization is usually difficult.\n\n**W3.**\n\nExisting optimization methods are designed either with the worst-case convergence analysis or to have fast empirical\nperformance on some problems. This means that either the methods are too pessimistic and slow in practice or they do not have convergence guarantees. We present a new framework that allows to quickly design and explore provably convergent algorithms that are well suited to a problem at hand. \n\n**Q1.**\n\nAs line 97 states, a dynamic interconnect is admissible if, at equilibrium, it reduces to the static interconnect. In the language of circuit theory, this can be stated as follows. First, at equilibrium, the dynamic components relax, i.e., capacitors become disconnects ($i_C=0$), and inductors become wires ($v_L=0$). Second, the circuit relations hold, which is expressed with KCL, KVL, and resistor relations. Third, at terminals $1, \\ldots, m$ the V-I relation of the relaxed circuit is the same as that of the static interconnect, i.e., $x \\in \\mathcal{R}(E^T)$ and $y \\in \\mathcal{N}(E)$. The admissibility condition (lines 98-99) is a mathematical formalization of this.\n\n**Q2.**\n\nThe conditions are concretely stated in the statement of Theorem 2.1 on line 128.\n\n**Q3.**\n\nIn continuous-time, the intuition comes from the observation that the convergence of electric circuits to equilibrium hinges on incremental passivity, i.e., no component can generate energy, and the fact that resistors dissipate energy.     Since convexity of $f$ leads to incremental passivity of $\\nabla f$ (so $f$ also does not generate energy), the circuit will relax to equilibrium.\n\nWhen we discretize the dynamics, however, there is a possibility that the discretized process is no longer dissipative. Therefore, we obtain a formal convergence guarantee of the discretized dynamics through the use of the computer-assisted proof framework called the performance estimation problem (PEP). Using the PEP, we certify that the discretized process is also dissipative and, therefore, will reach equilibrium. This is a very general recipe.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1NvmwyOP77", "reviewer": "Reviewer_bgKe", "summary": "This paper proposes the use of RLC circuits to design optimization algorithms. The authors prove that circuit dynamics in continuous time converge to the solution of the optimization problem. By specifically designing the RLC components, this approach recovers many existing algorithms. The authors also introduce a PEP-based method to discretize continuous-time circuit dynamics and prove its convergence. Experiments demonstrate the effectiveness of their methods.", "questions": "Significant issues\n1. Could you please provide more applications and examples for Problem (1) in Line 25 ?\n2. In Line 104, could you please explain in detail about $\\partial f$ electric device and why $\\partial f$ enforces $y\\in\\partial f(x)$? \n3. In Line 139, the authors use the energy definition in (6) instead of the total energy of the circuit, i.e., the sum of the energy of all components in the circuit. Could you please futher explain the reason for this choice?\n4. Can the convergence rate of the proposed algorithm be analyzed?\n5. When solving Problem (9) in Line 217, is it necessary to know $v^\\star$ and $i^\\star$ in advance?\n6. When designing an algorithm, how should the parameters of the RLC components be chosen? For example, in the gradient descent method, how should $D_{\\mathcal{C}}$ be selected?\n\nMinor issues\n1. In Line 79, should nodes $1,...,m$ be $1,...,\\tau-1$?\n2. In Line 1222, should it be $y^k \\in \\partial f(x^k)$?", "limitations": "N.A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors use RLC circuits to design new optimization algorithms, offering a novel and interesting perspective on algorithm design.\n2. The authors provide the convergence of circuit dynamics in continuous time and the convergence of the algorithm in discrete time.\n3. The authors provide an automatic discretization package, and experimental results show that the proposed method achieves fast convergence.", "weaknesses": "1. Compared to classical optimization algorithms, discretization requires solving the performance estimation problem, which needs extra computation.\n2. The convergence rate of the RLC-based algorithm is not discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments. We are pleased that you found our framework to be \"a novel and interesting perspective on algorithm design.\" Additionally, we're glad that you recognized our automatic discretization package as a strength of our work. \n\n\n\n**W1.**\n\nTo clarify, the role of the Performance Estimation Problem (PEP) in our framework automates the calculations and analysis for obtaining discretizations. So, it does not produce extra computation (it does not make the algorithm more expensive), but rather, it eliminates the need for humans to carry out the convergence proof of the discretized algorithm.\n\nAs mentioned in line 628 of the prior works section, continuous-time-based optimization design is a powerful approach for designing new algorithms, but a shortcoming of this prior work has been that there was no principled way of performing discretization. Our PEP-based automated discretization overcomes this shortcoming. We believe that our PEP-based automated discretization is not a weakness but rather a substantive contribution that completes the methodology of continuous-time optimization algorithm design.\n\n**W2.**\n\nWe agree with the reviewer that obtaining fast/efficient algorithms (rather than merely convergent algorithms) is the ultimate goal of optimization algorithm design. Since this present work represents the very first steps in this framework, we focus on laying the basic foundations and introducing the computer-assisted methodology. Utilizing and extending this machinery to design fast/efficient algorithms is the very next step of our planned agenda.\n\nHowever, we would like to point out that it is possible to extract an $O(1/k)$ convergence rate from the analytic convergence proof Lemma I.1 in line 1423 of the appendix, and a similar argument can be made more generally. We further elaborate on this point in our response to the reviewer's Question 4.\n\n\n\n### **Questions: Significant issues**\n\n**Q1.**\n\nThis form includes many problems that arise in distributed and \ndecentralized optimization. For example, Sections E and F of the appendix discuss how we recover many classical centralized and decentralized optimization methods for their respective problems. For more details on the setup for each of these classical methods, see, e.g., Chapters 2, 3, and 11 of [1], and paper [2]. These optimization problems and their solution methods have a wide range of applications, for example, \nwireless sensory networks [3], federated learning [4], power grids, and many more [5].\n\nWe thank the reviewer for raising this point. We agree that it is important to at least briefly discuss the motivating applications of Problem (1), so we will include this discussion in the updated version of the paper.\n\n[1] Ryu, E. K., and Yin, W. *Large-scale Convex Optimization: Algorithms & Analyses via Monotone Operators.* Cambridge University Press, 2022.\n\n[2] Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. Distributed optimization and statistical learning via the alternating direction method of multipliers. *Foundations and Trends® in Machine Learning*, 3(1):1–122, 2011.\n\n[3] Mota, J. F., Xavier, J. M., Aguiar, P. M., and Püschel, M. D-ADMM: A communication-efficient distributed algorithm for separable optimization. *IEEE Transactions on Signal Processing*, 61(10):2718–2723, 2013.\n\n[4] Zhou, S., and Li, G. Y. Federated learning via inexact ADMM. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 45(8):9699–9708, 2023.\n\n[5] Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., ..., and Johansson, K. H. A survey of distributed optimization. *Annual Reviews in Control*, 47:278–305, 2019.\n\n\n**Q2.**\n\nTo start with the simplest example, consider the case $m=1$ and $f(x) = \\frac{1}{2R} x^2$ with some $R>0$. \nSince $f$ is differentiable $\\partial f=\\nabla f$, and the V-I relation becomes $y=\\nabla f(x)=\\frac{1}{R}x$, i.e., $x=Ry$. Recalling $x$ is potential, and $y$ is current, the electric device $\\partial f$ becomes the usual linear resistor with resistance $R$. \n\nAs another example, an ideal diode is a device that blocks current flow if the voltage is less than $0$ (reverse biased) and allows current flow with no voltage drop otherwise (forward biased). Such an ideal diode can be modeled with a convex function\n$$\nf(x) = \\begin{cases}\n0 & \\text{if } x \\leq 0 \\\\\\\\\n\\infty & \\text{otherwise}.\n\\end{cases}\n$$\n\nSo the V-I relation given by $\\partial f$ has a vertical line at $x=0$, i.e.,\n$$\n\\partial f(x) = \n\\begin{cases}\n0 & \\text{if } x < 0 \\\\\\\\\n[0, \\infty] & \\text{if } x = 0 \\\\\\\\\n\\emptyset & \\text{if } x > 0.\n\\end{cases}\n$$\nThus the electric device $\\partial f$ becomes the ideal diode, as no current flows through the device when $x<0$, and current flows with zero resistance (infinite slope) otherwise. \nIt does not result in $x>0$ because there is no voltage drop in forward bias. \n\nUsing set-valued functions to describe V-I curves of circuit elements is a standard approach in circuit theory. So please think of $\\partial f$ as something like a non-linear resistor generalizing resistors and diodes.\n\n\n**Q3.**\n\nWe clarify that the energy in (6) is indeed the total energy in the circuit since resistors and $\\partial f$ do not store energy.\n\nOne slightly non-standard aspect is that the energy in the capacitors and inductors is computed after translating by $v\\_C^\\star$ and $i\\_L^\\star$. This is necessary because $\\partial f$ is a non-linear resistor that is incrementally passive (instead of being simply passive). Therefore, shifting by the equilibrium values $v\\_C^\\star$ and $i\\_L^\\star$ leads to a dissipative energy. (If $\\partial f$ is simply passive, then the circuit's equilibrium is at $x=y=0$, but the incrementally passive $\\partial f$ allows the circuit to relax to the (non-zero) solution to the optimization problem.)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ybxxpj75sG", "reviewer": "Reviewer_iKJ3", "summary": "This paper presents a methodology of designing an electric circuit whose continuous-time dynamics converge to the solution to its corresponding optimization problem (Theorem 2.2).  Furthermore, the paper presents the discretization scheme of the continuous-time dynamics, generating convergent optimization algorithms.", "questions": "1) The authors use the RLC circuit as an intermediate product to derive the optimization solver. As an alternative use, it might be possible to use the real-world RLC circuit directly as an optimization solver.  Do the authors have any comments or perspectives on such a development?\n\n2) As stated in Lemma 4.1, the convergence of the optimization algorithm is shown by performing a proper discretization that ensures dissipativity.  Would it be possible to provide specific examples of such \"proper\" discretization in the main body of the paper?", "limitations": "This paper focuses on the theoretical analysis and interpretation of optimization problems, and it does not present its negative social impacts.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper presents a unified framework of implementing various optimization problems into an electric circuit with static and dynamic interconnections.  The paper also presents the scheme of generating new optimization algorithms by discretizing the analog circuit equation.", "weaknesses": "1) The paper claims two novelties, one of which is interpreting the optimization problem as an RLC circuit. However, the reviewer disagrees with this novelty. The idea of implementing an optimization problem in an RLC analog circuit is classical and has been studied for a long time.  More surveys and comparisons with other works are necessary.  \n\nChua, Leon, and Gui-Nian Lin. \"Nonlinear programming without computation.\" IEEE Transactions on Circuits and Systems 31.2 (1984): 182-188.\nWilson, G. \"Quadratic programming analogs.\" IEEE transactions on circuits and systems 33.9 (1986): 907-911.\nVichik, Sergey, and Francesco Borrelli. \"Solving linear and quadratic programs with an analog circuit.\" Computers & Chemical Engineering 70 (2014): 160-171.\n\n2) Theorem 2.2, the main theorem of this paper, seems to be a special version of the Willems stability condition.  Although the authors refer to related works like [75], they should make more surveys and clarify the connection between the theorem presented in this paper and the original works on dissipativity theory by J. C. Willems.  \n\nWillems, Jan C. \"Dissipative dynamical systems part I: General theory.\" Archive for rational mechanics and analysis 45.5 (1972): 321-351.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive and constructive feedback. We are glad that the reviewer found our \"unified framework of implementing various optimization problems into an electric circuit\" as a strength of the paper. \n\n\n**W1.**\n\nThank you for bringing these references to our attention. We will include them\nand other related work we find from reading these references in the revised paper. Indeed, the reviewer is correct in that the relation between \nthe optimization problem and V-I relations has been studied for many decades. We discuss this in more detail in section A of the appendix, lines 670–679.\n\nHowever, our intention was to claim novelty in using this correspondence to design optimization *algorithms* (as opposed to physical circuits), and, in our view, our approach is made complete with the PEP-based automated discretization. However, we now see that this distinction was not made sufficiently clear, so in the revised manuscript, we will rewrite the claims of novelty to make clear that the connection between optimization algorithms and electric circuits has been studied previously.\n\n(Also, we doubly thank the reviewer for sharing the Vichik–Borrelli 2014 reference. We just found that this paper also uses the notion of negative resistors. Since we also use negative resistors, we are happy to find a prior reference to this notion. We will include this discussion in the revised paper as well.)\n\n**W2.**\n\nThank you for directing us to this reference. In the revised paper, we will adequately reference prior work on dissipative dynamical systems.\n\nFrom our reading of the reference you provide and the work [1], it seems like our analysis is indeed quite related to the Willems stability condition, but there were some minor differences. While the setups are related to ours, the fact that $v_C, i_L$ and $i_C, v_L$ may not converge in our setup makes the prior results by Willems not immediately applicable. In our setup, we allow cases where $v_C, i_L$ oscillate (for example, a circuit with a disconnected $L-C$ loop). \n\nNevertheless, it seems that the energy functions and the analyses presented by Willems are closely related to our result, so we will adequately discuss this connection in the revised paper.\n\n[1] Willems, J. C. The generation of Lyapunov functions for input-output stable systems. *SIAM Journal on Control*, 9(1):105–134, 1971. \n\n\n**Q1.**\n\nWe thank the reviewer for this suggestion. This is indeed an interesting direction with some challenges one should overcome. One crucial challenge would be implementing the nonlinear resistor $\\partial f$ (for any \nconvex $f\\colon \\mathbf{R}^m \\to \\mathbf{R} \\cup \\\\{ \\infty \\\\}$) in a real-world circuit.\nIn [1], the authors explicitly model the constraints and objective\nfunctions of an LP and QP using analog circuits, but doing so for general convex problems will likely be more challenging.\nAnother issue is that given the extreme efficiency of modern digital circuits (CPUs and GPUs), which implement standard optimization algorithms, making (analog) RLC circuits have some sort of advantage would likely be a significant challenge. Nevertheless, we do think this is an interesting direction worth pursuing.\n\n[1] Vichik, S., and Borrelli, F. Solving linear and quadratic programs with an analog circuit. *Computers & Chemical Engineering*, 70:160–171, 2014.\n\n\n**Q2.**\n\nYes, we can. The **Example** on line 232 is an example of a \"proper\" discretization. Also, the algorithm DADMM+C (fully presented in line 1404 of the appendix) in the Experiments section is another example. We also provide a proof that this discretization is indeed proper, as Lemma I.1 in line 1423. We will include this discussion in the main body of the revised paper.\n\nHowever, we point out that our framework provides an automatic tool to find proper discretizations. Specifically, our PEP-based framework circuit finds an appropriate stepsize that makes the discretization proper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "upaSZPw2XQ", "reviewer": "Reviewer_UMkv", "summary": "This paper addresses the design of new optimization algorithms (centralized and distributed) which lend themselves better to theoretical analysis than existing optimization algorithms, which are tailored more towards establishing fast worst-case convergence guarantees. The novel part is that the authors borrow analogies from electric circuits, specifically RLC circuits (which have components consisting of resistors, inductors, and capacitors).", "questions": "Do the equations for voltage across the inductor and current through the capacitor (page 3, line 93) have initial conditions as well? (e.g. initial charge across the inductor or current through the capacitor). If so, what are the analagous values for this in the optimization formation?\n\nI don't quite understand how the subdifferential operator enforces all of the considered V-I relationships. For example, if the x variables are analogous to voltage and the y variables are analogous to currents, wouldn't there also be relationships where x \\in df(y)?\n\nWhy is the 'equilibrium state' also indicative of the voltage across/current through a resistor being zero? Is this definition different than steady state?\n\nIn Section 3.1, a negative resistor is used. Do all of the circuit laws (Ohm's, KCL, KVL) also hold for negative resistance?", "limitations": "There does not seem to be any potential negative societal impacts.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Noticing that iterations of a (small iteration, or \"continuous-time\") optimization algorithm tend to mimic the behavior of RLC circuits with nonlinear resistor components is interesting. The authors also provide a methodology for converting convergent continuous-time dynamics into discrete-time. \n\nRLC circuits have a rich history and body of literature and these findings can thus be extended to the realm of optimization algorithm design with provable convergence, which, outside of it just being interesting to apply RLC concepts, is also quite useful for convergence analysis of optimization algorithms.", "weaknesses": "The authors should specify in the abstract and introduction that the optimization algorithm design in question seems to only work for convex optimization problems, which doesn't seem to be clear until the official definition of (1). This is a significant drawback considering there are significantly more convergence guarantees for convex problems in general versus nonconvex/mixed-integer etc. \n\nThe provable convergence is definitely of value, but is the speed/rate of convergence an improvement upon standard optimization algorithms? In practice, even if convergence isn't provable, for many practical problems most of the consideration would be towards optimization speed (and convergence would be achieved in practice but maybe not in theory).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and thoughtful questions. \nWe are glad that the reviewer found our framework to be \"quite useful for convergence analysis of optimization algorithms\".\n\n\n**W1.**\n\nWe thank the reviewer for this precise point. In the revised paper, we will clarify (in the abstract and introduction) that our framework currently focuses on developing convergent algorithms for convex problems. Extending the framework to cover more general nonconvex problems, including mixed-integer optimization problems, is a long-term goal for this project.\n\n**W2.**\n\nWe agree with the reviewer that obtaining fast/efficient algorithms (rather than merely convergent algorithms) is the ultimate goal of optimization algorithm design. Since this present work represents the very first steps in this framework, we focus on laying the basic foundations and introducing the computer-assisted methodology. Utilizing and extending this machinery to design fast/efficient algorithms is the very next step of our planned agenda.\n\n\n**Q1.**\n\nYes, they do. The initial conditions, stated in line 128, require that $ v_L^0 $ and $ i_C^0 $ should be compatible with the other voltage and current values of the resistors and $\\partial f$. Here, 'compatible' means that they should satisfy KCL and KVL. \n\nIn terms of optimization formulation, this means the initial values should be compatible with the optimization algorithm. \nHowever, $v_L$ and $i_C$ are often eliminated from the optimization algorithm, so the issue doesn't arise in most implements of the algorithm.\n\nLet us clarify this with an example. Consider the gradient flow in section E.2 of the appendix. \nFor the sake of simplicity, assume $f$ is differentiable and $D_C=I$. \nIf we write out KCL, KVL, V-I relations, we have \n$$\n\\begin{align*}\n    y &= \\nabla f(x) \\\\\\\\\n    i_C &= y \\\\\\\\\n    v_C &= -x \\\\\\\\\n    \\frac{d}{dt} v_C &= i_C.\n\\end{align*}\n$$\nThe initial condition of $i_C$ means that the value should be compatible with the first 3 lines. \nThat is, for the initial value $x^0$, the value $i_C^0$ should satisfy $i_C^0=\\nabla f(x^0)$. \nNow let's think of the discrete counterpart. \nThe last line corresponds to the update rule of the algorithm\n$$  v_C^{k+1} = v_C^{k} + h i_C^k $$\nwhere $h>0$ is step size. Here, we obtain the algorithm by eliminating $v_C, i_C, y$, by solving the system of equations from the first 3 lines. Substituting $v_C^k = -x^k$, $i_C^k = y^k = \\nabla f(x^k)$ we get\n$$  x^{k+1} = x^{k} - h \\nabla f(x^k) .$$\nThus, $i_C$ has been eliminated, and the constraint $i_C^0=\\nabla f(x^0)$ does not explicitly manifest in the discrete-time algorithm.\n\n\n**Q2.**\n\nThe subdifferential operator enforces the V-I relationship specified by $\\partial f$. The specific case mentioned by the reviewer can be enforced by considering the conjugate function $f^*$. Recall that if $f$ is closed convex proper, then Fenchel's identity tells us $(\\partial f)^{-1} = \\partial f^*$, thus\n$$ x \\in \\partial f(y) \\iff y \\in (\\partial f)^{-1}(x) \\iff y \\in \\partial f^*(x). $$\n\n\n**Q3.**\n\nWe believe the reviewer's notion of 'steady state' is the same as our 'equilibrium state'. \nWe define the 'equilibrium state' as the condition where all the circuit states are constant. This happens when $v_L=0$ and $i_C=0$, as discussed line 968 in the appendix. In equilibrium for admissible dynamic\ninterconnect, the current through the resistor must be zero, as otherwise the resistors will dissipate energy, and a circuit with strictly decreasing energy cannot be in equilibrium.\n\n**Q4.**\n\nYes, all circuit laws also hold for negative resistance. The only unusual aspect of negative resistors is that they *generate*, rather than dissipate, energy. However, this is not a problem since, in the equivalent circuit shown on the right side of the figure in Section 3.1, the negative resistor cancels out with the positive resistor and energy dissipation $\\frac{d}{dt} \\mathcal{E}(t)\\le0$ is still guaranteed. (So, the negative resistor is merely a conceptual tool.)\nWe will further clarify this point in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Common Response

We thank the reviewers for their thoughtful comments and suggestions. We are pleased that the reviewers generally find our framework novel and valuable. We address the reviewers' specific questions in the individual responses.

Meta-review: This paper presents a novel idea of designing optimization algorithms with electric RLC circuits. The first step is to design an appropriate circuit whose equilibrium is the solution to the optimization problem, and the second step is to discretize the continuous-time dynamics of the circuit to form a discrete-time algorithm. Overall, this is an interesting paper and has publication merits. The strengths outweigh the weaknesses.
Decision: Accept (spotlight)