Optimization Algorithm Design via Electric Circuits

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.

Paper

Similar papers

Peer review

Reviewer UMkv6/10 · confidence 2/52024-07-08

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).

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. RLC 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. The 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).

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? I 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)? Why is the 'equilibrium state' also indicative of the voltage across/current through a resistor being zero? Is this definition different than steady state? In Section 3.1, a negative resistor is used. Do all of the circuit laws (Ohm's, KCL, KVL) also hold for negative resistance?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

There does not seem to be any potential negative societal impacts.

Reviewer iKJ36/10 · confidence 4/52024-07-09

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.

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. Chua, Leon, and Gui-Nian Lin. "Nonlinear programming without computation." IEEE Transactions on Circuits and Systems 31.2 (1984): 182-188. Wilson, G. "Quadratic programming analogs." IEEE transactions on circuits and systems 33.9 (1986): 907-911. Vichik, Sergey, and Francesco Borrelli. "Solving linear and quadratic programs with an analog circuit." Computers & Chemical Engineering 70 (2014): 160-171. 2) 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. Willems, Jan C. "Dissipative dynamical systems part I: General theory." Archive for rational mechanics and analysis 45.5 (1972): 321-351.

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? 2) 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?

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

This paper focuses on the theoretical analysis and interpretation of optimization problems, and it does not present its negative social impacts.

Reviewer bgKe6/10 · confidence 2/52024-07-12

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.

Strengths

1. The authors use RLC circuits to design new optimization algorithms, offering a novel and interesting perspective on algorithm design. 2. The authors provide the convergence of circuit dynamics in continuous time and the convergence of the algorithm in discrete time. 3. 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. 2. The convergence rate of the RLC-based algorithm is not discussed in the paper.

Questions

Significant issues 1. Could you please provide more applications and examples for Problem (1) in Line 25 ? 2. In Line 104, could you please explain in detail about $\partial f$ electric device and why $\partial f$ enforces $y\in\partial f(x)$? 3. 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? 4. Can the convergence rate of the proposed algorithm be analyzed? 5. When solving Problem (9) in Line 217, is it necessary to know $v^\star$ and $i^\star$ in advance? 6. 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? Minor issues 1. In Line 79, should nodes $1,...,m$ be $1,...,\tau-1$? 2. In Line 1222, should it be $y^k \in \partial f(x^k)$?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

N.A.

Authorsrebuttal2024-08-07

**Q4.** Yes, we can extract an $O(1/k)$ convergence rate from our proven inequalities. We state and prove a more generalized statement here. The assumption is the same as Lemma G.1 (which covers the assumption of Lemma 4.1), and we restate it here for convenience. **Theorem.** Assume $f\colon \mathbf{R}^m \to \mathbf{R} \cup \\{ \infty \\}$ is a strictly convex function and the dynamic interconnect is admissible. Let a discrete-time optimization algorithm generate a sequence $\\{(v^k, i^k, x^k, y^k)\\}^{\infty}\_{k=0}$. Suppose there exists $\eta > 0$ such that for all $k=0, 1, \ldots$ the energy descent $$ \mathcal{E}\_{k+1} + \eta \langle x^k - x^\star, y^k - y^\star \rangle - \mathcal{E}\_k \leq 0 $$ holds. Then, for the Lagrangian defined as $L(x, z, y) = f(x) - y^T(x - E^\intercal z)$, we have $$ \min\_{k \in \\{0, 1, \dots, K\\}} \left( L(x^k, z^\star, y^\star) - f(x^\star) \right) \leq \frac{1}{(K+1)\eta} \mathcal{E}\_0 = O\left(\frac{1}{K}\right) $$ for $K=0,1,\dots$. *Proof outline.* Since we are considering the same assumption as in Lemma G.1, all arguments used in its proof are applicable. From line 1223 we have $$ 0 \leq \sum\_{k=0}^K \eta \langle x^k - x^\star, y^k - y^\star \rangle \leq \mathcal{E}\_0, $$ and from line 1229 we have $$ \langle x^k-x^\star, y^k-y^\star\rangle \geq L(x^k, z^\star, y^\star) - f(x^\star) \geq 0. $$ Combining two inequalities and dividing both sides by $K+1$, we get the desired conclusion. $\blacksquare$ All algorithms obtained by our framework, including DADMM+C, achieve this convergence rate. As mentioned in an earlier part of this response, doing a more refined analysis of convergence rates (establishing, say, linear rates of convergence in an automated fashion) is a follow-up direction of work that we are pursuing. **Q5.** Explicit knowledge of $v^\star$ and $i^\star$ is not needed. We can find the numerical values of $(\alpha,\beta,h)$ without explicit knowledge of the optimal values. For example, consider finding dissipative discretization for gradient descent. Let $f$ be $L$-smooth. The iterates are given by $x^{k+1} = x^k- h\nabla f(x^k)$. The energy is $\mathcal{E}\_k = \frac{1}{2}\\|x^k-x^\star\\|^2\_2$, where $x^\star$ is such that $y^\star = \nabla f(x^\star) = 0$. Then we want to find step size $h>0$ and $\eta>0$ such that $$\mathcal{E}\_{k+1}+\eta\langle x^k - x^\star, y^k - y^\star\rangle-\mathcal{E}\_k \leq 0.$$ Using the inequality arises from $L$-smoothness of $f$, $$ \langle x^k - x^\star, y^k - y^\star\rangle \geq \frac{1}{L} \\|y^k \\|^2\_2, $$ we can check that the discretization is dissipative for all $\eta < \frac{1}{2L}$ and $h \in [\frac{1}{L} \pm \frac{1}{L}\sqrt{1-2\eta L}]$. Thus, we can find proper $\eta$ and $h$ without explicitly specifying $x^\star$, by just representing it as a point satisfying the optimality conditions. Further details on this line of reasoning are available in the PEP papers [1, 2]. [1] Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: A novel approach. *Mathematical Programming*, 145(1):451–482, 2014. [2] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. *Mathematical Programming*, 161(1):307–345, 2017. **Q6.** One approach is to let the solver find the RLC values along with the discretization. (We recently implemented this functionality in ciropt.) Another approach is to try a few variations for the values for resistance, inductance and capacitance, and see for which of them the solver finds a discretization. ### **Questions: Minor issues** **Q1.** We clarify that this is not a mistake. For the circuit in Figure 2, for example, there are $\tau=8$ nodes, but only $m=5$ of the nodes (node $1, 2, \dots 5$) are connected to the terminals. Likewise, there are nodes that are connected to neither the terminal nor the ground. The potential of those nodes is denoted by $e$. **Q2.** Thank you for pointing out to us this typo; we will correct it. We appreciate the reviewer’s thoughtful questions. We hope we have adequately addressed the reviewer's concern regarding the extra computation related to the performance estimation problem and the possibility of obtaining convergence rates from our approach. If so, we kindly ask the reviewer to consider raising the score.

Reviewer a4Xt7/10 · confidence 2/52024-07-17

Summary

This paper presents a novel framework for designing optimization algorithms with electric RLC circuits. It contains two stages: 1. design an appropriate circuit whose equilibrium is the solution to the optimization problem. 2. discretize the continuous-time dynamics of the circuit to form a discrete-time algorithm. Theoretical guarantees are given on the convergence of the continuous-time dynamics.

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. 2. 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. 3. The paper is comprehensive and overall well-written.

Weaknesses

1. Some parts lack clarity. See *Questions*. 2. 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. 3. It would be better if there was more discussion on the benefit of using this approach to design algorithms compared to the standard approaches.

Questions

1. How to determine whether a circuit is admissible from construction instead of checking the equation on lines 98-99? 2. In line 125, under what "appropriate" conditions? 3. 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.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

4

Limitations

There are no separate sections in the main paper. However, the authors state the assumptions for their results.

Reviewer bgKe2024-08-11

I thank the authors for addressing all my concerns in detail. The additional theorem on the convergence rate of the discrete algorithm looks solid to me. The theoretical proof for the faster convergence rate of the discrete algorithm is an interesting direction. I am willing to raise the rating to 6.

Reviewer UMkv2024-08-12

Response to rebuttal

I appreciate the authors' responses to my questions and comments and the examples provided to illustrate that the circuit laws still apply in the cases I mentioned. I do agree that this provides a good step towards speeding up optimization convergence, and is in general, an interesting finding that should be shared with the community. The paper should definitely be published somewhere, I just think for NeurIPS it's a bit borderline in terms of impact. Thus, I keep my 6/Weak Accept score.

Reviewer iKJ32024-08-13

Thank you for your response. The reviewer's concerns have been addressed and appropriately reflected in the revised manuscript.

Reviewer a4Xt2024-08-13

Thanks for the response. It addressed all my concerns. I would like to keep my current rating.

Program Chairsdecision2024-09-25

Decision

Accept (spotlight)

© 2026 NYSGPT2525 LLC