Method and apparatus for solving an optimization problem using an analog circuit

Abstract

An analog circuit design is described that solves Linear Programming (LP) or Quadratic Programming (QP) problems.

Claims

1. A method of solving an optimization problem with an analog circuit, the method comprising: (a) providing an optimization lattice comprising: (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) connecting one or more cost functions to corresponding cost function rows of the optimization lattice; (c) connecting zero or more equality constraints to the optimization lattice; (d) connecting zero or more inequality constraints to the optimization lattice; (e) providing voltage sources to each cost function, equality constraint, and inequality constraint; and (f) reading voltages from the columns of common voltage conductors of the optimization lattice after the optimization lattice has reached steady state; (g) wherein the voltages of the optimization lattice columns of common voltage conductors form a solution vector to the optimization problem; and (h) wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice; (i) wherein each equality constraint is a voltage supplied to a corresponding row in the rows of common voltage conductors of the optimization lattice through a negative resistance; and (j) wherein the negative resistance is implemented through an operational amplifier.

2. The method of claim 1: wherein each inequality constraint is a voltage supplied to a corresponding row in the rows of common voltage conductors of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode.

3. The method of claim 2, wherein the negative resistance is implemented through an operational amplifier.

4. The method of claim 2, wherein the perfect diode is implemented through an operational amplifier.

5. The of claim 1, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; (a) wherein element G.sub.ij is the i, j element of G; (b) wherein i(0, . . . , m); (c) wherein j(1, . . . , n); and (d) $G_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};$ (e) wherein m is a sum of a number of equality constraints plus a number of inequality constraints.

6. The method of claim 1, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Quadratic Programming (QP) problems.

7. The method of claim 1, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

8. The method of claim 1, wherein each constraint negative resistance for a particular row is calculated as $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$ where R.sub.k=1/G.sub.k.

9. The method of claim 1, wherein each constraint voltage source for a particular row is calculated as $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$ where R.sub.k =1/G.sub.k and b.sub. is a corresponding constraint value for row .

10. The method of claim 1, further comprising: changing one or more of the voltage sources to the cost functions, the equality constraints, or the inequality constraints without otherwise changing the optimization lattice; and then re-reading voltages from the optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state.

11. The method of claim 1: (a) wherein the optimization problem is of the form: $\underset{V={\left[V_1,\mathrm{.Math.},V_n\right]}^T}{\min }\left(c^{T}V\right)$ $s.t.A_{\mathrm{eq}}V=b_{\mathrm{eq}}$ $A_{\mathrm{ineq}}V{b}_{\mathrm{ineq}};$ (b) wherein a recasting of the optimization problem is performed so that A.sub.ineq, A.sub.eq, and C have non-negative entries; and (c) modeling the recast optimization problem in into the optimization lattice; and (d) wherein V=[V.sub.1, . . . , V.sub.n].sup.T are generated as solution voltages.

12. An analog circuit for solving an optimization problem, comprising: (a) an optimization lattice comprising: (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) one or more cost functions connected to corresponding cost function rows of the optimization lattice; (c) zero or more equality constraints connected to the optimization lattice; (d) zero or more inequality constraints connected to the optimization lattice; (e) voltage sources connected to the cost functions, the equality constraints, the inequality constraints; (f) output voltages of optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state; (g) wherein the output voltages of the optimization lattice columns of common voltage conductors form a solution vector to an optimization problem:, (h) wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice; (i) wherein each equality constraint is a voltage supplied to a corresponding row of common voltage conductors of the optimization lattice through a negative resistance; (j) wherein each inequality constraint is a voltage supplied to a corresponding row of common voltage conductors of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode; and (k) wherein the negative resistance is implemented through an operational amplifier.

13. The analog circuit of claim 12, wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice.

14. The analog circuit of claim 12, wherein the perfect diode is implemented through one or more devices selected from a group of devices consisting of: an operational amplifier, a comparator, a switch, and a Field Effect Transistor (FET).

15. The analog circuit of claim 12, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; (a) wherein element G.sub.ij is the i, j element of G; (b) wherein i(0, . . . , m); (c) wherein j(1, . . . , n); and (d) $G_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};$ (e) wherein m is a sum of a number of equality constraints plus a number of inequality constraints.

16. The analog circuit of claim 12, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Model Predictive Control (MPC) problems.

17. The analog circuit of claim 12, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

18. The analog circuit of claim 12, wherein each constraint negative resistance for a particular row has a value of $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$ where R.sub.k=1/G.sub.k.

19. The analog circuit of claim 12, wherein each constraint voltage source for a particular row has a value of $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$ where R.sub.k=1/G.sub.k and b.sub. is a corresponding constraint value for row .

20. The analog circuit of claim 12, wherein one or more of the voltage sources supplied to corresponding cost functions, equality constraints, or inequality constraints may be changed without otherwise changing the optimization lattice.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

(1) The invention will be more fully understood by reference to the following drawings which are for illustrative purposes only:

(2) FIG. 1 is a schematic of an equality enforcing circuit comprising 11 resistors (R.sub.1, . . . , R.sub.n), a negative resistance that has a value of

(3) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
and a voltage source with a value of

(4) $\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}.$

(5) FIG. 2 is a schematic of a circuit illustrating Kirchhoff's Current Law (KCL), where 11 branches feed current I.sub.k (i1, . . . , k, . . . , n) into a common node that has a corresponding potential of U.

(6) FIG. 3 is a schematic of an inequality enforcing circuit comprising 11 resistors (R.sub.1, . . . , R.sub.n), a diode, a negative resistance that has a value of

(7) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
and a voltage source with a value of

(8) $\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}.$

(9) FIG. 4 is a schematic of a cost circuit that is connected to a cost voltage source.

(10) FIG. 5 is a schematic of an optimization lattice circuit designed for solving an optimization problem, where: 1) vertical conductors are variable nodes with potentials V.sub.1 . . . V.sub.n; 2) horizontal conductors are cost or constraint nodes; 3) black dots represent resistances connecting vertical and horizontal conductors; 4) the topmost horizontal conductor is one cost circuit that is connected to a cost voltage source; and 5) quadratic cost resistors have been added to the bottom of the optimization lattice to allow for Quadratic Programming (QP) problem solution.

(11) FIG. 6A is a schematic of one of the resistors R represented by a dot previously shown in FIG. 5.

(12) FIG. 6B is schematic of dot resistor R of FIG. 6A, where the compact representation of the resistor R.sub.ij is shown as a resistance of magnitude R interconnecting a horizontal i.sup.th row conductor, and a vertical j.sup.th column conductor.

(13) FIG. 7 is a schematic of one prior art approximate implementation of a negative resistor, where an operational amplifier is used to provide feedback to approximate a negative resistor.

(14) FIG. 8A is a schematic of one prior art approximate implementation of a perfect diode, where an operational amplifier uses feedback and a comparator controlled switch to eliminate the band gap normally present in single component diodes, thereby approximating an ideal diode.

(15) FIG. 8B is a prior art graph of the output voltage versus the input voltage of the prior art approximate implementation of a perfect diode of FIG. 8A.

(16) FIG. 9A is a graph of the solution to the QPCBLEND problem over a time scale of 0-1 s, where the solutions are voltages corresponding to the problem unknowns.

(17) FIG. 9B is a graph of the solution to the QPCBLEND problem over a time scale of 1-30 s, where the solutions are voltages corresponding to the problem unknowns.

(18) FIG. 9C is a graph of the error between the circuit cost and the optimal solution, and the norm of the solution error as a function of time, to the QPCBLEND problem over a time scale of 0-1 s, with results shown for nominal and high gain bandwidth (GBW) operational amplifiers (denoted here as HG).

(19) FIG. 9D is a graph of the error between the circuit cost and the optimal solution, and the norm of the solution error as a function of time, to the QPCBLEND problem over a time scale of 1-30 s, with results shown for nominal and high gain bandwidth (GBW) operational amplifiers (denoted here as HG).

(20) FIG. 10 is a graph of a Model Predictive Control (MPC) analog circuit implementation of a Linear Programming (LP) problem solution voltages, where solid lines represent the nominal controller, and dashed lines represent the controller implemented with 1% Gaussian random error analog devices.

DETAILED DESCRIPTION OF THE INVENTION

(21) Introduction

(22) The present invention teaches a design methodology of an analog optimization lattice electric circuit that has an equilibrium point that is the solution of a particular problem. Generally, the problem is an optimization problem. However, it may instead comprise a zero cost optimization, which is a solution of algebraic equality or inequality equations.

(23) The problem solution is available after the settling time of the circuit. The settling time is usually much faster than corresponding digital computation time, and can be as low as a few nanoseconds. The method is potentially faster, and believed to be simpler, than any other presently known method.

(24) The circuit may be used in any application where fast solutions of a series of similar problems are required and somewhat lower solution accuracy is tolerable. Examples include, but are not limited to:

(25) (a) Model Predictive Control (MPC) for fast mechanical and electric systems, electric drives, microelectromechanical systems (MEMS);

(26) (b) Building blocks for solvers of integer optimization problems;

(27) (c) Optimal filters (such as Kalman Filters) that are embedded in sensor circuitry;

(28) (d) Fast analog decoding or encoding circuits;

(29) (e) Linear Programming (LP) problems;

(30) (f) Quadratic Programming (QP) problems; and

(31) (g) Image processing prior to analog to digital sampling.

(32) The Optimizing Analog Circuit

(33) Consider the optimization problem:

(34) $\begin{array}{cc}\underset{V={\left[V_1,\mathrm{.Math.},V_n\right]}^T}{\min }\left(\frac{1}{2}{V}^T\mathrm{QV}+c^{T}V\right)& \left(1\right)\\ s.t.A_{\mathrm{eq}}V=b_{\mathrm{eq}}& \left(2\right)\\ A_{\mathrm{ineq}}V{b}_{\mathrm{ineq}}& \left(3\right)\end{array}$
where [V.sub.1, . . . , V.sub.n] are the optimization variables, Q, A.sub.ineq, and A.sub.eq are matrices, and c, b.sub.eg and b.sub.ineq are column vectors. The equality and inequality operators are element-wise operators. It should be parenthetically noted that Q is positive semidefinite. If Q is a zero matrix, then the optimization problem is a Linear Programming (LP) problem, otherwise it is a Quadratic Programming (QP) problem.

(35) Without loss of generality, it is assumed that A.sub.ineg, A.sub.eq, and c have non-negative entries. Any LP described by Equations (1) through (3) can be transformed into this form by introducing an auxiliary vector V as follows:

(36) $\begin{array}{cc}\underset{\stackrel{\_}{V},V}{\min }\left(\frac{1}{2}{V}^T\mathrm{QV}+c^{T}V\right)& \left(4\right)\\ s.t.A_{\mathrm{eq}}^{+}V+A_{\mathrm{eq}}^{-}\stackrel{\_}{V}=b_{\mathrm{eq}}& \left(5\right)\\ A_{\mathrm{ineq}}^{+}V+A_{\mathrm{ineq}}^{-}\stackrel{\_}{V}{b}_{\mathrm{ineq}}& \left(6\right)\\ V+\stackrel{\_}{V}=0& \left(7\right)\end{array}$
where A.sub.ineq, A.sub.eq, and c are split into positive and negative parts (A.sub.ineq=A.sub.ineq.sup.+A.sub.ineq.sup., A.sub.eq=A.sub.eq.sup.+A.sub.eq.sup. and c=c.sup.+c.sup.).

(37) Next in this section, the basic circuit building blocks are described that will be later used to create a circuit that solves a particular problem via an implementation of an optimization lattice. The first basic block enforces equality constraints of the form of Equation (5). The second building block enforces inequality constraints of the form of Equation (6). The penultimate basic block implements the cost function (here it is linear), and finally, the ultimate basic block implements Quadratic cost functions.

(38) The Equality Constraint

(39) Refer now to the circuit 100 of FIG. 1. V.sub.k is the potential of node k 102, and R.sub.k 104 is the resistance between node k 102 and the common node 106 with potential U. The value

(40) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}108$
is a negative resistance, and

(41) $\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}110$
is a voltage source.

(42) For simplicity, just the single variable b has been used. However, b may also be known as b.sub., or the constraint corresponding to the common node 106. Similarly, the voltage source U may also be known as U.sub., or the constraint voltage for the common node 106.

(43) Proposition 1 (Equality Constraint Circuit)

(44) The circuit in FIG. 1 enforces the equality constraint:

(45) $\begin{array}{cc}\left[\frac{1}{R_1}\mathrm{.Math.}\frac{1}{R_n}\right]\left[\begin{array}{c}{V}_1\\ \mathrm{.Math.}\\ V_n\end{array}\right]=b.& \left(8\right)\end{array}$

(46) Refer now to the circuit 200 depicted in FIG. 2. In this circuit, 11 conductors are connected to a common node 202, which has a corresponding potential U. The current that exits node 202 is termed I 204. Kirchhoff's current law (KCL) implies:

(47) 0$\begin{array}{cc}\underset{k=1}{\overset{n}{.Math.}}{I}_k=\underset{k=1}{\overset{n}{.Math.}}\frac{V_k-U}{R_k}=I& \left(9\right)\end{array}$
where I.sub.k 206 is the current through branch k 208, and R.sub.k 210 is the resistance between node k 212 and common node 202. Equation (9) can be written as an equality constraint on potentials V.sub.k:

(48) $\begin{array}{cc}\underset{k=1}{\overset{n}{.Math.}}\frac{V_k}{R_k}=I+U\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}.& \left(10\right)\end{array}$

(49) If the right hand side (rhs) of Equation (10) is set to any desired value b, then Equation (10) enforces an equality constraint on a linear combination of V.sub.k. The voltage U is set to:

(50) $\begin{array}{cc}U=-\frac{I}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}+\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}& \left(11\right)\end{array}$

(51) The rhs in Equation (11) may be implemented by a negative resistance of

(52) $\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}$
(thereby forming the IR, or

(53) $-\frac{I}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}$
term of Equation (11) and a constant voltage source of magnitude

(54) $\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}.$

(55) Equation (11) taken together with Equation (10) yields the desired Equation (8). Therefore, the circuit shown in FIG. 1 successfully enforces the equality constraint of Equation (8).

(56) The Inequality Constraint

(57) Refer now to the circuit 300 of FIG. 3 for enforcing a set of inequality conditions. Similar to the equality constraint circuit previously described above in FIG. 1, n conductors are connected to a common node 302. Common node 's potential is U and the current exiting this common node 302 is I. An ideal diode 304 connects node to node . The potential of node is taken to be U. The ideal diode 304 enforces the requirement that potential UU.

(58) Finally, the common node 302 output current I passes through the forward biased ideal diode 304, through a negative resistance of

(59) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}306,$
and then to a constant voltage source of

(60) $\frac{b}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}308.$

(61) As previously described in the section for equality constraints, for simplicity just the single variableb has been used. However, b may also be known as b.sub., or the constraint value for the common node 302. Similarly, the voltage source U may also be known as U.sub., or the constraint voltage source 308 for the common node 302.

(62) Proposition 2 (Inequality Constraint Circuit)

(63) The circuit in FIG. 3 enforces the inequality constraint:

(64) $\begin{array}{cc}\left[\frac{1}{R_1}\mathrm{.Math.}\frac{1}{R_n}\right]\left[\begin{array}{c}{V}_1\\ \mathrm{.Math.}\\ V_n\end{array}\right]b& \left(12\right)\end{array}$

(65) Proof.

(66) Kirchhoff's current law (KCL) implies Equation (9) as in the previous case. The ideal diode enforces U U. In FIG. 3, the voltage U at node can be calculated as follows

(67) $\begin{array}{cc}{U}^{}=\frac{b-I}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}}U.& \left(13\right)\end{array}$
Equation (9) and the condition that UU yield:

(68) 0$\begin{array}{cc}\underset{k=1}{\overset{n}{.Math.}}\frac{V_k}{R_k}=I+U\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}I+U^{}\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}=b& \left(14\right)\end{array}$
which can be compactly rewritten as Equation (12). Therefore, the circuit shown in FIG. 3 enforces the inequality constraint of Equation (12).

(69) It should be noted that the ideal diode 304 in FIG. 3 enforces:
I0(15)
I(UU)=0(16)
By using Equation (15) and rearranging its terms, Equation (16) can be rewritten as

(70) $\begin{array}{cc}I\left(\left(\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}\right)U-b+I\right)=0& \left(17\right)\end{array}$
This Equation (17) is useful for characterizing the analog optimization lattice electrical circuit in other contexts not described here.

(71) The Linear Cost Function

(72) Refer now to the circuit 400 in FIG. 4. In this circuit 400 the potential of common node 402 is equal to U.sub.cost and the current that exits common node 402 is I.sub.cost 404. From Equation (10), one obtains:

(73) $\begin{array}{cc}{c}^{T}V=I_{\mathrm{cost}}+U_{\mathrm{cost}}\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}J& \left(18\right)\end{array}$
where c=[1/R.sub.1 . . . 1/R.sub.n].sup.T, V=[V.sub.1 . . . V.sub.n].sup.T and J is the cost function. This part of the circuit implements the minimization of the cost function.

(74) A thorough explanation of the cost circuit requires the equations of the entire LP circuit, is presented outside of this patent application. Here, a brief intuitive interpretation is presented.

(75) It can be shown that the LP circuit is passive. This implies that when U.sub.cost is set to a low value, the voltages V.sub.k are driven in a direction that minimizes the current I.sub.cost. Consequently, the cost, J is decreased by decreasing U.sub.cost.

(76) The Quadratic Cost Function

(77) Refer now back to the circuit 300 of FIG. 3 for enforcing a set of inequality conditions. The quadratic cost function is a special case of an inequality enforcing circuit. If the inequality is redundant, meaning that the voltage 308 is very high, the diode 304 is always in a non-conducting state. Therefore, the circuit 300 is equivalent to each quadratic cost resistor R.sub.1 . . . R.sub.k . . . R.sub.n connected to the common node 302.

(78) Unlike the equality and inequality constraints, the quadratic cost function requires neither a voltage source nor a negative resistor. Unlike the inequality constraints, the quadratic cost resistor network also has the ideal diode removed. Therefore, in actual implementation, these additional components are not needed, and only the resistors are necessary.

(79) However, for ease of description and limiting the complexity of the description in this invention, the quadratic cost functions may be more readily described as inequality constraints having a large positive voltage source.

(80) A thorough explanation of the quadratic cost circuit requires the equations of the entire LP circuit, which will be presented outside of this patent application.

(81) In short, where a quadratic cost is being used, the circuit 300 remains the same, except that: 1) the perfect diode 304, 2) negative resistor 306, and 3) constant voltage source 308 are all omitted.

(82) The dissipation of energy from a resistor is proportional to a square of current through the resistor E.sub.dissipated=I.sup.2R. The current through a resistor is proportional to difference of voltages between the attached columns of common voltage conductors. The distribution of voltages minimizes power dissipation from resistors, according to the physics of current distribution. Therefore, the circuit dynamically settles into a minimum power dissipation state that corresponds by design to the required quadratic cost matrix Q.

(83) Connecting the Basic Circuits

(84) This section presents how to construct the electrical circuit that solves a general LP or QP problem. A conductance matrix G.sup.(m+1)n is constructed as:

(85) $\begin{array}{cc}G\left[\begin{array}{c}{c}^T\\ A\end{array}\right]=\left[\begin{array}{c}{c}^T\\ A_{\mathrm{eq}}\\ A_{\mathrm{ineq}}\end{array}\right]& \left(19\right)\end{array}$
and denotes G.sub.ij as the i, j element of G. For a given LP or QP problem, previously described by Equations (1) through (3), the R.sub.ij resistor is defined as:

(86) $\begin{array}{cc}{R}_{\mathrm{ij}}\frac{1}{G_{\mathrm{ij}}},i=0,\mathrm{.Math.},m,J=1,\mathrm{.Math.},n& \left(20\right)\end{array}$
where the first row of G (corresponding to c.sup.T or the cost function) is indexed by i=0. Additional cost functions may be added to the optmization lattice by indexing negatively on i, such as [1, 2, 3, . . . ].

(87) Refer now to the optimization lattice circuit 500 shown in FIG. 5. The circuit is shown using a compact notation where each resistor R.sub.ij is represented by a dot 502. Vertical conductors 504 represent variable nodes with potentials V.sub.1 . . . V.sub.n, and horizontal conductors 506 represent constraint nodes. These conductors may be wires, with generally small resitances, or may be conductors in an LSI or VLSI integrated circuit, which may be implemented by metal or other similarly highly conductive material.

(88) The circuit 500 of FIG. 5 may be most generally thought of as an optimization lattice that implements an optimization problem. As previously discussed, the horizontal conductors 506 represent constraints, and the vertical conductors 504 represent variables in the solution of the optimization problem.

(89) Although provision is made for each horizontal conductor 506 to intersect with each vertical conductor 504 via a resistor, a resistor at each intersection is not necessary when the constraint or cost function is independent of particular variables. In such instances, the resistance is effectively infinite, with a corresponding conductance of zero: i.e. the resistance is omitted.

(90) The optimization lattice is most generally presented as an implementation of a complete (m+1,n) array of conductances corresponding to the conductance matrix G previously discussed in Equation (19). However, it is understood that the optimization lattice may be populated with a number of zero conductance elements. Therefore, the lattice is taken as merely a generalization of the optimization problem, and not strictly limited to the population of each and every element with non-zero conductances.

(91) The constraint nodes are illustrated here by equality constraints 508 and inequality constraints 510. There may be as many equality or inequality constraints as necessary to describe the particular LP problem. There may also be zero equality or inequality constraints for particular problems.

(92) There is a cost function 512 that implements the LP problem cost (here indicated as a single row cost function), and quadratic cost resistors that implement the QP problem cost 514. The quadratic cost resistors are implemented in the optimization lattice with each row corresponding to one quadratic cost.

(93) There may be zero to QR numbers of quadratic costs in a particular QP problem. In the case of a non-zero number of QR quadratic costs, the optimization lattice increases in size to accommodate a quadratic resistor subarray of:

(94) $\begin{array}{cc}\begin{array}{ccc}{R}_{m+1,1}& \mathrm{.Math.}& R_{m+1,n}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ R_{m+\mathrm{QR},1}& \mathrm{.Math.}& R_{m+\mathrm{QR},n}\end{array}& \left(21\right)\end{array}$
with corresponding conductances of:

(95) $\begin{array}{cc}\begin{array}{ccc}{G}_{m+1,1}& \mathrm{.Math.}& G_{m+1,n}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ G_{m+\mathrm{QR},1}& \mathrm{.Math.}& G_{m+\mathrm{QR},n}\end{array}& \left(22\right)\end{array}$

(96) As previously discussed, the quadratic cost functions may also be implemented by simply setting an inequality constraint to have a large positive value voltage source. In this case, the subarrays would instead become part of the inequality constraints in the treatment above.

(97) FIG. 6A depicts one of the resistor nodes 600 R.sub.ij=R.sub.i,j 602 represented by a dot .circle-solid. previously shown in FIG. 5. The compact representation of a resistor 604 through a dot .circle-solid. symbol is clarified in FIG. 6B, where a resistance of magnitude R.sub.ij 606 interconnects a horizontal 608 i.sup.th row and vertical 610 j.sup.th column conductor. If G.sub.ij=0, then no resistor (zero conductance) is needed to be present at the corresponding dot .circle-solid., thereby corresponding to an infinite resistance.

(98) Referring back to FIG. 5, the LP circuit is constructed by connecting the nodes associated with the variables V.sub.1 . . . V.sub.n to all three types of the basic circuits: equality 508, inequality 510, and cost 512. Such nodes will be referred to as variable nodes. Each row of the circuit in FIG. 5 is one of the basic circuits presented above as equality constraints, inequality constraints, and a cost function. If U.sub.cost is small enough, then the values of the potentials V.sub.1 . . . V.sub.n in this circuit are a solution of the Linear Programming problem described by Equation (1) throughEquation (3).

(99) Note that one can easily change the rhs of equality constraints of Equation (8) or inequality constrains of Equation (12) to a different value b by simply using a voltage source equal to

(100) $\stackrel{\_}{b}\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}.$
This allows one to solve parametric problems by simply changing the value of the external voltage sources.

(101) The circuit as shown in FIG. 5 contains no time-varying dynamic elements such as capacitors or inductors. Therefore, the time required to reach steady-state is governed by the parasitic effects (e.g. conductor inductances and capacitances) and by the properties of the elements used to realize negative resistance (usually an operational amplifier) and perfect diode implementation. Hence, a good electronic design can achieve solution times on the order of these parasitic effects. Indeed, initial results of ongoing work on Very Large Scale Integration (VLSI) implementations indicate that time constants can be as low as a few nanoseconds.

(102) Negative Resistance Implementation

(103) Recall that in FIG. 5, each of the R.sub.j, where j(1, . . . , m) are negative resistors. One must generally implement such negative resistances by using operational amplifiers in a feedback configuration.

(104) Refer now to FIG. 7, which is a schematic 700 of one approximate implementation of a negative resistor. The negative resistance circuit shown in FIG. 7 is an operational amplifier implementation of a negative impedance converter. The two resistors R1 and the operational amplifier constitute a negative feedback non-inverting amplifier having a gain of A=2. The input resistance (for an ideal operational amplifier) is given by:

(105) $\begin{array}{cc}{R}_{\mathrm{in}}\frac{V}{i}=-R& \left(23\right)\end{array}$

(106) Further analysis of the circuit is possible to account for limited gain bandwidth (GBW) products, as well as non-infinite operational amplifier input impedances.

(107) In this implementation, the input port of the circuit can be connected into another network as if it were a negative resistance component.

(108) Approximate Perfect Diode Implementation

(109) Recall that in FIG. 5, for each of the inequality constraints 510, an ideal diode was required. One must generally implement such approximate ideal diodes by using operational amplifiers in a feedback configuration.

(110) Refer now to FIG. 8A, which is a schematic 800 of one approximate implementation of a perfect diode. The near perfect diode circuit shown in FIG. 8A is an operational amplifier implementation of an ideal diode that uses negative feedback, a comparator, and a switch to approximate the behavior of the ideal diode.

(111) Refer now to FIG. 8B, which shows the input-output relationship of the approximate ideal diode of FIG. 8A.

(112) Simulations and Experiments

(113) This section presents three examples where the approach proposed in this invention has been successfully applied. In the first example, a Quadratic Programming (QP) problem is solved by the disclosed modeling electrical circuit and simulated by the SPICE [Nagel and Pederson (1973)] simulator. In the second example, an analog Linear Programming (LP) problem is used to control a linear system by using Model Predictive Control (MPC). In the third and final example, an experiment is conducted by realizing the circuit for a small LP with standard electronic components.

(114) Quadratic Programming (QP) Example QPCBLEND

(115) Here, the method disclosed herein is demonstrated and its limits explored by solving the problem QPCBLEND from the Maros and Meszaros QP problem set [Maros and Meszaros (1999)]. The original problem has 83 variables, 43 equality constraints, and 114 inequality constraints. After translation to the all-positive form and the addition of constant variables (see above) the recast problem has 169 variables, 126 equality constraints, and 114 inequality constraints. The circuit that solves this problem was constructed with non-ideal components, including parasitic capacitances that roughly correspond to typical Very Large Scale Integration (VLSI) Complementary Metal Oxide Silicon (CMOS) analog design, and an operational amplifier with gain-bandwidth product (GBW) of 10 GHz.

(116) Refer now to FIG. 9A through FIG. 9D, which detail the convergence of the electric circuit to the problem solution. The circuit converges to a solution that is slightly different from the optimum because non-ideal elements have been used. As can be seen in FIG. 9C and FIG. 9D, the steady-state error between the circuit cost and the optimal one J.sub.optJ is of the order 10.sup.3. Similarly the steady-state norm of the solution error X.sub.optX is of the order 10.sup.3. There is a small constraint violation AXb.sup.2=9.310.sup.4 since the operational amplifiers have finite gain and require non-zero violation to generate voltage. As expected, if higher gain (HG) operational amplifiers are used (with GBW products of 100 GHz), the infeasibility and the optimal cost errors decrease.

(117) The circuit transient can be partitioned into two phases. During the first 1000 ns (or first 100 ns for the high gain circuit), rapid convergence to a solution close to optimal can be observed. Afterwards, the circuit continues to improve the solution with a smaller change in the cost value. This behavior suggests that there are two main circuit modesfast modes are associated with components that move in the direction of the cost gradient, and slow modes are associated with voltages quasi-orthogonal to the cost gradient. The fast modes converge rapidly and provide a solution close to the optimum while the slow modes gradually improve the solution over a longer time period.

(118) Model Predictive Controller (MPC) Example

(119) This example demonstrates the implementation of a Model Predictive Controller (MPC) with an Linear Programming (LP) analog circuit model. For this example, the dynamical system

(120) $\frac{\mathrm{dx}}{\mathrm{dt}}=-x+u$
is used, where x is the system state and u is the input. It is desired that x follows a given reference trajectory while satisfying input constraints. The finite time optimal control problem at time t is formulated as:

(121) 0$\begin{array}{cc}\underset{u_0\mathrm{.Math.}{u}_{n-1}}{\min }\underset{i=1}{\overset{N}{.Math.}}.Math.x\left(i\right)-x_{\mathrm{ref}}\left(i\right).Math.& \left(24\right)\\ x_{i+1}=x_i+\left(u_i-x_i\right),i=0,\mathrm{.Math.},N& \left(25\right)\\ -1.5u_{i}1.5,i=0,\mathrm{.Math.},N& \left(26\right)\\ x_0=x\left(t\right)& \left(27\right)\end{array}$
where N is the prediction horizon, x.sub.ref(i) is the reference trajectory at step i, is the sampling time, and x(t) is the initial state at time t. Only the first input, u.sub.0, is applied at each time step t.

(122) With N=16, the LP in Equations (24) through Equations (27) has 96 variables, 63 equality constraints, and 49 inequality constraints. Both an electric circuit that implements the system dynamics together with the circuit that implements the MPC controller were constructed and simulated using Simulation Program with Integrated Circuit Emphasis (SPICE). The voltage value representing the system state was measured and enforced on the x.sub.0 node of the LP. The optimal input value u.sub.0 was injected as input to the simulated system dynamics. Note that in this setup there is no sample and hold. Rather, the two circuits continuously interact with each other.

(123) Refer now to FIG. 10, which is a graph 1000 that shows the closed loop SPICE simulations results. Note the predicted behavior of the closed loop control input and the satisfaction of the system constraints. Here, solid lines represent the nominal controller.

(124) In order to demonstrate system performance for imperfect analog devices, another simulation result with 1% random Gaussian errors in the values of the resistors is presented on the same FIG. 10 via dashed lines. There appears to be no significant change in system behavior with the 1% random Gaussian errors.

(125) Linear Programming (LP) Hardware Implementation Example

(126) A small Linear Programming (LP) problem was implemented using standard electronics components. The same problem was realized by Hopfield [Tank and Hopfield (1986)] and Chua [Kennedy and Chua (1988)]. The LP problem is defined as follows:

(127) $\begin{array}{cc}\underset{x_1,x_2}{\min }{c^T\left[x_1{x}_2\right]}^T& \left(28\right)\\ s.t.\frac{5}{12}{x}_1-x_2\frac{35}{12},\frac{5}{2}{x}_1+x_2\frac{35}{2}& \left(29\right)\\ -x_{1}5,x_{2}5& \left(30\right)\end{array}$
where c is a cost vector that is varied to get different solution points. The circuit was realized using resistors of 1% accuracy, operational amplifiers (OP27) for the negative resistance, and a comparator (LM311) with a switch (DG201) for implementing functionality of an ideal diode.

(128) Various values for the cost function c and test results are summarized in Table 1. Table 1 shows that the experimental results are accurate up to 0.5%. The circuit reaches an equilibrium 6 s after the cost voltage was applied. The convergence time is governed by a slew rate of the OP27 that is limited to 2.8 v/s.

(129) From the description herein, it will be appreciated that the invention can be embodied in various ways which include but are not limited to the following:

(130) 1. A method of solving an optimization problem with an analog circuit, the method comprising: (a) providing an optimization lattice comprising: (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) connecting one or more cost functions to corresponding cost function rows of the optimization lattice; (c) connecting zero or more equality constraints to the optimization lattice; (d) connecting zero or more inequality constraints to the optimization lattice; (e) providing voltage sources to each cost function, equality constraint, and inequality constraint; and (f) reading the voltages of the optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state; (g) wherein the voltages of the optimization lattice columns of common voltage conductors form a solution vector to the optimization problem.

(131) 2. The method of any of the previous embodiments, wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice.

(132) 3. The method of any of the previous embodiments, wherein each equality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance.

(133) 4. The method of any of the previous embodiments: wherein each inequality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode.

(134) 5. The method of any of the previous embodiments, wherein the negative resistance is implemented through an operational amplifier.

(135) 6. The method of any of the previous embodiments, wherein the negative resistance is implemented through an operational amplifier.

(136) 7. The method of any of the previous embodiments, wherein the perfect diode is implemented through an operational amplifier.

(137) 8. The method of any of the previous embodiments, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; wherein element G.sub.ij is the i, j element of G; wherein i(0, . . . , m); wherein j(1, . . . , n); and

(138) $G_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};$
wherein m is the sum of the number of equality constraints plus the number of inequality constraints.

(139) 9. The method of any of the previous embodiments, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Quadratic Programming (QP) problems.

(140) 10. The method of any of the previous embodiments, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

(141) 11. The method of any of the previous embodiments, wherein each constraint negative resistance for a particular row is calculated as

(142) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k.

(143) 12. The method of any of the previous embodiments, wherein each constraint voltage source for a particular row is calculated as

(144) $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k and b.sub. is the corresponding constraint value for row .

(145) 13. The method of any of the previous embodiments, further comprising: changing one or more of the voltage sources to the cost functions, the equality constraints, or the inequality constraints without otherwise changing the optimization lattice; and then re-reading the voltages of the optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state.

(146) 14. A method of solving an optimization problem with an analog circuit, the method comprising: (a) providing an optimization problem of the form:

(147) $\begin{array}{cc}\underset{V={\left[V_1,\mathrm{.Math.},V_n\right]}^T}{\min }\left(c^{T}V\right)s.t.A_{\mathrm{eq}}V=b_{\mathrm{eq}},A_{\mathrm{ineq}}V{b}_{\mathrm{ineq}}& \left(b\right)\end{array}$
recasting the optimization problem so that A.sub.ineq, A.sub.eq, and c have non-negative entries; and (c) modeling the recast optimization problem in an optimization lattice; and (d) wherein V=[V.sub.1, . . . , V.sub.n].sup.T are solution voltages.

(148) 15. An analog circuit for solving an optimization problem, comprising: (a) an optimization lattice comprising (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) one or more cost functions connected to corresponding cost function rows of the optimization lattice; (c) zero or more equality constraints connected to the optimization lattice; (d) zero or more inequality constraints connected to the optimization lattice; (e) voltage sources connected to the cost functions, the equality constraints, the inequality constraints; and (f) output voltages of optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state; (g) wherein the output voltages of the optimization lattice columns of common voltage conductors form a solution vector to an optimization problem.

(149) 16. The analog circuit of any of the previous embodiments, wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice.

(150) 17. The analog circuit of any of the previous embodiments, wherein each equality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance.

(151) 18. The analog circuit of any of the previous embodiments, wherein each inequality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode.

(152) 19. The analog circuit of any of the previous embodiments, wherein the negative resistance is implemented through an operational amplifier.

(153) 20. The analog circuit of any of the previous embodiments, wherein the negative resistance is implemented through an operational amplifier.

(154) 21. The analog circuit of any of the previous embodiments, wherein the perfect diode is implemented through one or more devices selected from a group of devices consisting of: an operational amplifier, a comparator, a switch, and a Field Effect Transistor (FET).

(155) 22. The analog circuit of any of the previous embodiments, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; (a) wherein element G.sub.ij is the i, j element of G; (b) wherein i(0, . . . , m); (c) wherein j(1, . . . , n); and (d)

(156) $\begin{array}{cc}{G}_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};& \left(e\right)\end{array}$
wherein m is the sum of the number of equality constraints plus the number of inequality constraints.

(157) 23. The analog circuit of any of the previous embodiments, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Model Predictive Control (MPC) problems.

(158) 24. The analog circuit of any of the previous embodiments, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

(159) 25. The analog circuit of any of the previous embodiments, wherein each constraint negative resistance for a particular row has a value of

(160) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k.

(161) 26. The analog circuit of any of the previous embodiments, wherein each constraint voltage source for a particular row has a value of

(162) $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k and b.sub. is the corresponding constraint value for row .

(163) 27. The analog circuit of any of the previous embodiments, wherein one or more of the voltage sources supplied to corresponding cost functions, equality constraints, or inequality constraints may be changed without otherwise changing the optimization lattice.

(164) 28. A method of solving an optimization problem with an analog circuit, the method comprising: (a) providing an optimization lattice comprising: (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) connecting zero or more cost functions to corresponding cost function rows of the optimization lattice; (c) connecting zero or more equality constraints to the optimization lattice; (d) connecting zero or more inequality constraints to the optimization lattice; (e) providing voltage sources to each cost function, equality constraint, and inequality constraint; and (f) reading the voltages of the optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state; (g) wherein the voltages of the optimization lattice columns of common voltage conductors form a solution vector to the optimization problem.

(165) 29. The method of solving the optimization problem with the analog circuit of embodiment 28, further comprising: (a) connecting one or more quadratic cost functions to the optimization lattice; (b) wherein each quadratic cost function comprises one or more quadratic cost resistors connected from (i) a corresponding quadratic cost function row to (ii) one of the columns of common voltage conductors of the optimization lattice.

(166) 30. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 29, wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice.

(167) 31. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 30, wherein each equality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance.

(168) 32. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 31, wherein each inequality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode.

(169) 33. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 32, wherein the negative resistance is implemented through an operational amplifier.

(170) 34. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 33, wherein the perfect diode is implemented through an operational amplifier.

(171) 35. The method of solving the optimization problem with the analog circuit of embodiments 28 through 34, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; wherein element G.sub.ij is the i, j element of G; wherein i(0, . . . , m); wherein j(1, . . . , n); wherein

(172) $G_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};$
and wherein m is the sum of the number of equality constraints plus the number of inequality constraints.

(173) 36. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 35, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Quadratic Programming (QP) problems.

(174) 37. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 36, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

(175) 38. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 37, wherein each constraint negative resistance for a particular row is calculated as

(176) 0$-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k.

(177) 39. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 38, wherein each constraint voltage source for a particular row is calculated as

(178) $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k and b.sub. is the corresponding constraint value for row .

(179) 40. The method of solving the optimization problem with the analog circuit of any of embodiments 28 through 39, further comprising: changing one or more of the voltage sources to the cost functions, the equality constraints, or the inequality constraints without otherwise changing the optimization lattice; and then re-reading the voltages of the optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state.

(180) 41. A method of solving an optimization problem with an analog circuit, the method comprising: (a) providing an optimization problem of the form

(181) $\underset{V={\left[V_1,\mathrm{.Math.},V_n\right]}^T}{\min }\left(\frac{1}{2}{V}^T\mathrm{QV}+c^{T}V\right)$$s.t.A_{\mathrm{eq}}V=b_{\mathrm{eq}}$$A_{\mathrm{ineq}}V{b}_{\mathrm{ineq}};$
(b) recasting the optimization problem so that A.sub.ineq, A.sub.eq, and c have non-negative entries; and (c) modeling the recast optimization problem in an optimization lattice; (d) wherein V=[V.sub.1, . . . , V.sub.n].sup.T are solution voltages; (e) wherein Q is a matrix where each non-zero entry represents a quadratic cost resistor that forms one or more quadratic cost functions to the optimization lattice; and (f) wherein each quadratic cost function comprises one or more of the quadratic cost resistors connected from a corresponding quadratic cost function row to one of the columns of common voltage conductors of the optimization lattice.

(182) 42. An analog circuit for solving an optimization problem, comprising: (a) an optimization lattice comprising: (i) rows of common voltage conductors; (ii) columns of common voltage conductors; and (iii) a resistance R.sub.ij connected between row i and column j of the optimization lattice; (b) zero or more cost functions connected to corresponding cost function rows of the optimization lattice; (c) zero or more equality constraints connected to the optimization lattice; (d) zero or more inequality constraints connected to the optimization lattice; (e) voltage sources connected to the cost functions, the equality constraints, the inequality constraints; and (f) output voltages of optimization lattice columns of common voltage conductors after the optimization lattice has reached steady state; (g) wherein the output voltages of the optimization lattice columns of common voltage conductors form a solution vector to an optimization problem.

(183) 43. The analog circuit of embodiment 42, further comprising: (a) one or more quadratic cost functions connected to the optimization lattice; (b) wherein each quadratic cost function comprises one or more quadratic cost resistors connected from a corresponding quadratic cost function row to one of the columns of common voltage conductors of the optimization lattice.

(184) 44. The analog circuit of any of embodiments 42 through 43, wherein each cost function comprises a voltage supplied to a corresponding cost function row of the optimization lattice.

(185) 45. The analog circuit of any of embodiments 42 through 44, wherein each equality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance.

(186) 46. The analog circuit of any of embodiments 42 through 45, wherein each inequality constraint is a voltage supplied to one of the corresponding rows of the optimization lattice through a negative resistance, and then through an implementation of a perfect diode.

(187) 47. The analog circuit of any of embodiments 42 through 46, wherein the negative resistance is implemented through an operational amplifier.

(188) 48. The analog circuit of any of embodiments 42 through 47, wherein the perfect diode is implemented through one or more devices selected from a group of devices consisting of: an operational amplifier, a comparator, a switch, and a Field Effect Transistor (FET).

(189) 49. The analog circuit of any of embodiments 42 through 48, wherein the resistances R.sub.ij connected between row i and column j of the optimization lattice, when inverted, form elements of a conductance matrix G; wherein element G.sub.ij is the i, j element of G; wherein i(0, . . . , m); wherein j(1, . . . , n); wherein

(190) $G_{\mathrm{ij}}=\frac{1}{R_{\mathrm{ij}}};$
and wherein m is the sum of the number of equality constraints plus the number of inequality constraints.

(191) 50. The analog circuit of any of embodiments 42 through 49, wherein the optimization problem is selected from a group of optimization problems consisting of: Linear Programming (LP) problems, and Quadratic Programming (QP) problems.

(192) 51. The analog circuit of any of embodiments 42 through 50, wherein absent all resistances R.sub.ij connected between row i and column j of the optimization lattice, each row and column of common voltage conductors in the optimization lattice are electrically isolated.

(193) 52. The analog circuit of any of embodiments 42 through 51, wherein each constraint negative resistance for a particular row has a value of

(194) $-\frac{1}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k.

(195) 53. The analog circuit of any of embodiments 42 through 52, wherein each constraint voltage source for a particular row has a value of

(196) $\frac{b_{}}{\underset{k=1}{\overset{n}{.Math.}}\frac{1}{R_k}},$
where R.sub.k=1/G.sub.k and b.sub. is the corresponding constraint value for row .

(197) 54. The analog circuit of any of embodiments 42 through 53, wherein one or more of the voltage sources supplied to corresponding cost functions, equality constraints, or inequality constraints may be changed without otherwise changing the optimization lattice.

(198) Embodiments of the present invention may be described with reference to flowchart illustrations of methods and systems according to embodiments of the invention, and/or algorithms, formulae, or other computational depictions, which may also be implemented as computer program products. In this regard, each block or step of a flowchart, and combinations of blocks (and/or steps) in a flowchart, algorithm, formula, or computational depiction can be implemented by various means, such as hardware, firmware, and/or software including one or more computer program instructions embodied in computer-readable program code logic. As will be appreciated, any such computer program instructions may be loaded onto a computer, including without limitation a general purpose computer or special purpose computer, or other programmable processing apparatus to produce a machine, such that the computer program instructions which execute on the computer or other programmable processing apparatus create means for implementing the functions specified in the block(s) of the flowchart(s).

(199) Accordingly, blocks of the flowcharts, algorithms, formulae, or computational depictions support combinations of means for performing the specified functions, combinations of steps for performing the specified functions, and computer program instructions, such as embodied in computer-readable program code logic means, for performing the specified functions. It will also be understood that each block of the flowchart illustrations, algorithms, formulae, or computational depictions and combinations thereof described herein, can be implemented by special purpose hardware-based computer systems which perform the specified functions or steps, or combinations of special purpose hardware and computer-readable program code logic means.

(200) Furthermore, these computer program instructions, such as embodied in computer-readable program code logic, may also be stored in a computer-readable memory that can direct a computer or other programmable processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the block(s) of the flowchart(s). The computer program instructions may also be loaded onto a computer or other programmable processing apparatus to cause a series of operational steps to be performed on the computer or other programmable processing apparatus to produce a computer-implemented process such that the instructions which execute on the computer or other programmable processing apparatus provide steps for implementing the functions specified in the block(s) of the flowchart(s), algorithm(s), formula(e), or computational depiction(s).

(201) Although the description above contains many details, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention. Therefore, it will be appreciated that the scope of the present invention fully encompasses other embodiments which may become obvious to those skilled in the art, and that the scope of the present invention is accordingly to be limited by nothing other than the appended claims, in which reference to an element in the singular is not intended to mean one and only one unless explicitly so stated, but rather one or more. All structural, chemical, and functional equivalents to the elements of the above-described preferred embodiment that are known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the present claims. Moreover, it is not necessary for a device or method to address each and every problem sought to be solved by the present invention, for it to be encompassed by the present claims. Furthermore, no element, component, or method step in the present disclosure is intended to be dedicated to the public regardless of whether the element, component, or method step is explicitly recited in the claims. No claim element herein is to be construed as a means plus function element unless the element is expressly recited using the phrase means for. No claim element herein is to be construed as a step plus function element unless the element is expressly recited using the phrase step for.

(202) TABLE-US-00001 TABLE 1 Experimental and theoretical results for an LP solution. cost x1 x2 direction simulated x1 exact simulated x2 exact 1 4.996 5.000 4.990 5.000 1 1 7.002 7.000 5.005 5.000 2 7.012 7.000 4.980 5.000 0 6.976 7.000 0.005 0.000