# Traverse discrete approximations to a continuous system

I have a system of equations looking like

$$\frac{2.8 R_{6}}{R_{4} + R_{6}} = \frac{5.2}{\left(\frac{1}{R_{2}} + \frac{1}{R_{1}}\right) \left(R_{7} + \frac{1}{\frac{1}{R_{2}} + \frac{1}{R_{1}}}\right)}$$

$$\frac{Vpn_{lo} - 1.2}{R_{4}} = \frac{Vo_{lo} - Vpn_{lo}}{R_{6}}$$

$$\frac{Vp_{pk} - 3.92}{R_{4}} = \frac{Vo_{pk} - Vp_{pk}}{R_{6}}$$

$$\frac{Vo_{lo} - Vpn_{lo}}{R_{2}} = - \frac{Vo_{lo} - Vpn_{lo}}{R_{6}}$$

$$\frac{- Vn_{pk} + Vo_{pk}}{R_{2}} = - \frac{Vo_{pk} - Vp_{pk}}{R_{6}}$$

$$\frac{Vo_{lo} - Vpn_{lo}}{R_{2}} = - \frac{5.2 - Vpn_{lo}}{R_{7}}$$

$$\frac{- Vn_{pk} + Vo_{pk}}{R_{2}} = - \frac{5.2 - Vn_{pk}}{R_{7}}$$

$$0.5 Vn_{pk} + 0.5 Vp_{pk} \leq 3.2$$

This system is continuous in the first session, every variable is doubly bounded, every equation is differentiable, and the system is fairly under-determined.

In scipy using minimize() in auto-differentiation mode, I've run it with two styles:

• A null cost function, and constraints from the equations above
• A cost function that's least-squares over the error from the equations above

They both work but the former is more accurate, with example output

{'R1': 3852.6461161901593,
'R2': 52181.65309869594,
'R3': 5478.114258581004,
'R4': 23053.763182191393,
'R6': 57687.03740102816,
'R7': 5737.979499744396,
'Vn_pk': 2.2060323247749043,
'Vo_lo': 4.70000786771414,
'Vo_pk': 4.857957862651767,
'Vp_pk': 4.187813277600707,
'Vpn_lo': 2.1993504143658305,


The trouble comes in the second session, when I want to discretise the R variables, since it turns into a MINLP problem. Every R variable must take a value in the series

$$R \approx 10^{i/24}$$

which you'll recognize as an approximation to the E series of preferred electronic numbers. The approximations to R are numerous but finite. Since every R has roughly four decades of range and there are six R variables, that means that the entire solution space has a size upper bound of

$$(24 * 4)^6 \approx 7.8 \times 10^{11}$$

The problem goes from having an infinite number of solutions to having no exact solutions. I want to traverse and rank a subset of the solution space by approximation error. I tried using scipy's differential_evolution, which is theoretically a MINLP solver, but it doesn't at all work for this problem; it's derivative-free when I think I actually want to keep my autoderivatives. So my questions are:

• What are some numerical strategies to branching away from a known good solution to achieve somewhat comprehensive coverage of a large but finite solution space?
• What are some numerical strategies to choosing solution space traversal vectors that preserve equation validity and don't violate inequalities?
• Are there any straightforward ways to reveal secondary equations (such as fixed ratios between some R) that must remain true for the solution to be satisfied?
• Whereas I've given up on differential_evolution, is the Gekko APOPT MINLP support suited to this problem?

It seems unlikely that this is going to get an answer, and in the intervening time I've found a working solution on my own, so I'll answer it myself:

Scipy's differential_evolution is an implementation of a stochastic, derivative-free population method from Storn, R and Price, K, Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 1997, 11, 341 - 359 and Qiang, J., Mitchell, C., A Unified Differential Evolution Algorithm for Global Optimization, 2014.

The implementation does support doubly-bounded integer variables (my resistances) and both linear and non-linear constraints. I've found that when the constraints are not satisfied, DE represents them as an infinite cost, and the solver never converges - this in contrast to Kraft's SLSQP algorithm that is able to simultaneously converge on difficult constraints while still approaching a local minimum. In this context the constraints are:

• two KCL systems to solve for unspecified voltages in the case where $$V_o$$ floats
• an upper bound to the common-mode input voltage (the last equation shown in the question)
• a lower bound to the output voltage during input-low, $$Vo_{lo}$$

The latter two are easy enough to satisfy as they're inequalities but the first is difficult to satisfy as it's an equality and DE does not do well when fed it directly. For this reason I've moved to a nested optimisation strategy where, in the outer DE layer, only the integral resistances are degrees of freedom and the voltages are unspecified. In an inner layer that uses MINPACK's hybrid Powell method for root finding on a continuous vector-valued domain, the voltages are re-calculated whenever the cost or constraints are evaluated. This is somewhat slow but works well enough.

The implementation is on Github. I might tune it later to try some of the alternative Qiang-Mitchell DE strategies, but for now it's good enough.