Analog Optimization

Overview

The goal of this research is to develop a methodology to solve in real-time linear and quadratic programming (LP and QP) problems with an analog circuit. 

Simple and straight forward computation tasks can be done quickly with digital hardware, but as the complexity builds up, certain tasks demand long computing time (particularly optimization problems).  Some of these tasks can be solved significantly faster using analog computer. Indeed, we have shown that a quadratic optimization task can be solved with an analog circuit many orders of magnitude faster than with a CPU. Using analog technology, a solution to real-time optimization problems can be obtained in a few microseconds and ongoing work aims to reduce it to a few nanoseconds, which is lower than any current method known to us. 

Digital computers are based on a sequential computation paradigm, which assumes that every computation is a sequence of operations. The sequential computation paradigm leads to iterative algorithms, which are major contributors to high latency. Analog computers do not necessarily follow the sequential computation paradigm. For example, the optimization circuit reaches an equilibrium using a simultaneous multi-way interaction between all parts of the problem and the solution is obtained in a single “iteration”, unlike digital computers that require multiple iterations. The proposed method expresses an optimization problem as an equivalent electric circuit whose steady state voltages are solution of the optimization problem. 

Everything that requires repeated low-latency solution of similar problems is a potential application for analog optimization technology. Possible applications of the new technology are fast and power-efficient analog signal processing (e.g. Kalman filter), image processing (e.g. optical flow, mathematical morphology), advanced control (e.g. model predictive control), error correcting decoders (LDPC) and more.

Theory

The theoretical foundation and the connection to the optimization theory was published in the special MPC issue of "Computers & Chemical Engineering" and can be found here or here.  

We solve the following quadratic or linear problem 

where the right hand side vector b is a parameter and can be changed to yield different solution. 

The solver can be integrated as shown on the next image, where the environment, which can be a digital co-processor, controlled system etc., supplies updated parameters and the solver produces a new solution after a very short latency.  

Fast optimal controller prototype

An optimal predictive controller was implemented on a PCB using programmable potentiometers and switches. 

The board is configured as a high-speed online solver of a constrained finite time optimal control  problem for a buck DC-DC converter. 

Analog VLSI prototype

Radically low latency can be achieved when the circuit is made in a nanoscale, using standard VLSI technologies.  This project, done in cooperation with prof. Elad Alon and Kristel Deems from the EECS department, is to build a chip that solves a QP problem with speed typical for analog VLSI - hundreds of MHz up to a few GHz.

Our initial detailed design using a 65 nm process yields nanosecond range latency.

Publications:

Ph.D. thesis Quadratic and linear optimization with analog circuits 

Fast Solution of Linear and Quadratic Programs with an Analog Circuit

Solving linear and quadratic programs with an analog circuit 

Stability of an analog optimization circuit for quadratic programming