Thank you for your positive review and thoughtful questions. We are glad that the reviewer found our framework to be "quite useful for convergence analysis of optimization algorithms".

W1.

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

W2.

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

Q1.

Yes, 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.

In terms of optimization formulation, this means the initial values should be compatible with the optimization algorithm. However, $v_L$ and $i_C$ are often eliminated from the optimization algorithm, so the issue doesn't arise in most implements of the algorithm.

Let us clarify this with an example. Consider the gradient flow in section E.2 of the appendix. For the sake of simplicity, assume $f$ is differentiable and $D_C=I$. If we write out KCL, KVL, V-I relations, we have

$ y &= \nabla f(x) \\\\ i_C &= y \\\\ v_C &= -x \\\\ \frac{d}{dt} v_C &= i_C. $

The initial condition of $i_C$ means that the value should be compatible with the first 3 lines. That is, for the initial value $x^0$, the value $i_C^0$ should satisfy $i_C^0=\nabla f(x^0)$. Now let's think of the discrete counterpart. The last line corresponds to the update rule of the algorithm $v_C^{k+1} = v_C^{k} + h i_C^k$ where $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 $x^{k+1} = x^{k} - h \nabla f(x^k) .$ Thus, $i_C$ has been eliminated, and the constraint $i_C^0=\nabla f(x^0)$ does not explicitly manifest in the discrete-time algorithm.

Q2.

The 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 $x \in \partial f(y) \iff y \in (\partial f)^{-1}(x) \iff y \in \partial f^*(x).$

Q3.

We believe the reviewer's notion of 'steady state' is the same as our 'equilibrium state'. We 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 interconnect, 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.

Q4.

Yes, 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.) We will further clarify this point in the revised paper.

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.

W1.

Thank you for bringing these references to our attention. We will include them and other related work we find from reading these references in the revised paper. Indeed, the reviewer is correct in that the relation between the 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.

However, 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.

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

W2.

Thank you for directing us to this reference. In the revised paper, we will adequately reference prior work on dissipative dynamical systems.

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

Nevertheless, 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.

[1] Willems, J. C. The generation of Lyapunov functions for input-output stable systems. SIAM Journal on Control, 9(1):105–134, 1971.

Q1.

We 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 convex $f\colon \mathbf{R}^m \to \mathbf{R} \cup \\{ \infty \\}$) in a real-world circuit. In [1], the authors explicitly model the constraints and objective functions of an LP and QP using analog circuits, but doing so for general convex problems will likely be more challenging. Another 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.

[1] Vichik, S., and Borrelli, F. Solving linear and quadratic programs with an analog circuit. Computers & Chemical Engineering, 70:160–171, 2014.

Q2.

Yes, 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.

However, 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.

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.

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.

W1.

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

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

W2.

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

However, 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.

Questions: Significant issues

Q1.

This form includes many problems that arise in distributed and decentralized 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, wireless sensory networks [3], federated learning [4], power grids, and many more [5].

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

[1] Ryu, E. K., and Yin, W. Large-scale Convex Optimization: Algorithms & Analyses via Monotone Operators. Cambridge University Press, 2022.

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

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

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

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

Q2.

To start with the simplest example, consider the case $m=1$ and $f(x) = \frac{1}{2R} x^2$ with some $R>0$. Since $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$.

As 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

$$f(x) = \begin{cases} 0 & \text{if } x \leq 0 \\\\ \infty & \text{otherwise}. \end{cases}$$

So the V-I relation given by $\partial f$ has a vertical line at $x=0$, i.e.,

$$\partial f(x) = \begin{cases} 0 & \text{if } x < 0 \\\\ [0, \infty] & \text{if } x = 0 \\\\ \emptyset & \text{if } x > 0. \end{cases}$$

Thus 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. It does not result in $x>0$ because there is no voltage drop in forward bias.

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

Q3.

We clarify that the energy in (6) is indeed the total energy in the circuit since resistors and $\partial f$ do not store energy.

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

We are happy to hear that the reviewer found our proposed framework "novel" and "practically useful".

W1.

This is further addressed below.

W2.

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

W3.

Existing optimization methods are designed either with the worst-case convergence analysis or to have fast empirical performance 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.

Q1.

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

Q2.

The conditions are concretely stated in the statement of Theorem 2.1 on line 128.

Q3.

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

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