IEEE Circuits and Systems Magazine - Q1 2018 - 35

subproblems involving the solution of linear equations,
which lend themselves to the use of memristors for efficient computation.
A. Linear Optimization With Memristors
The standard form of LP is expressed as follows,
minimize
dT x
x
subject to Gx = h,

(10)
n

where x ! R is the optimization variable, d ! R , G !
R l # n and h ! R l are given parameters, and the last inequality constraint represents the elementwise inequalities x i $ 0 for i = 1, 2, f, n. In this paper, we assume
that G is of full row rank.
We begin by reformulating problem (10) as the canonical form (4) that is amenable to the use of ADMM
algorithm,
d T x + p (x) + g (y)

minimize
x,y

(11)

subject to x = y,

where y ! R n is a newly introduced optimization variable, and similar to (5), p and g are indicator functions,
with respect to constraint sets {x|Gx = h} and {y | y $ 0},
respectively. If we set f (x) = d T x + p (x), A = I, B =-I
and c = 0 , then problem (11) is the same as problem (4).
Based on (11), the ADMM steps (6)-(9) become
x k +1 = arg min $ d T x + p (x) + (n k) T (x - y k)
x

+

t

2

2
x - yk 2 .

(12)

y k +1 = arg min $ g (y) + (n k ) T (x k +1 - y)
y

+

t

2

2
x k +1 - y 2 .

(13)

n k +1 = n k + t (x k +1 - y k +1) .

(14)

As we show next, the primary advantage of employing
ADMM here is that problem (12) can be readily solved
using memristor crossbars, and problem (13) yields a
closed-form solution that only involves elementary vector operations.
Problem (12) is equivalent to
t

||x - a||22
2
subject to Gx = h,
minimize
x

(15)

where a := y k - (1/t) (n k + d) . The solution of problem
(15) is determined by its Karush-Kuhn-Tucker (KKT)
conditions [37], t (x - a) + G T m = 0, and Gx = h, where
m ! R l is the Lagrangian multiplier. The KKT conditions
imply a system of linear equations
ta
x
C ; E = ; E,
h
m
first quarter 2018

tI G T

C =;

G

0

E.

t

||y - b||22
2
subject to y $ 0,
minimize
y

x $ 0,

n

Based on (2), the linear system (16) can be efficiently
mapped to memristor crossbars by configuring their
memristance values according to the matrix C.
On the other hand, problem (13) is equivalent to

(16)

(17)

where b := x k +1 + (1/t) n k . The solution of problem (17)
is determined by the projection of b onto the nonnegative orthant,
y k +1 = (b) + .

(18)

Note that the positive part operator ($) + in (18) can be
readily implemented using elementary logical or digital operations.
We summarize the memristor-based LP solver in Fig. 4.
Although LP is a relatively simple optimization problem,
the LP solver illustrates our general idea and paves the
way for numerous memristor-based applications in optimization problems. Our solution framework offers two
major advantages. First, in the linear system (16), the coefficient matrix C is independent of the ADMM iteration
so that memristors need to be configured only once. This
feature makes it more attractive than gradient-type and
interior-point algorithms, where memristors have to be
reconfigured at each iteration [27]. Second, ADMM splits
a complex problem into subproblems, each of which is
easier to solve and implement in hardware.
B. Quadratic Optimization With Memristors
QP is an optimization problem whose objective and constraint functions involve quadratic and/or linear terms.
There exist many variants of QP, such as a second-order
cone program (SOCP) and a quadratically constrained
quadratic program (QCQP) [37]. In this section, we focus on the design of a memristor-based solver for SOCP,

Iterate Until Convergence

Solve Linear
System in (15)
Using M

Updated x k+1
M: Memristor Crossbars
with Mapped C

Project Onto
Positive Orthant
in (17) Using a
Analog/Digital
Technology

Updated µk+1

Updated y k+1
Summing
Amplifier

Figure 4. memristor crossbar based solution framework in
linear programming.

ieee circuits and systems magazine

35



Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2018

Contents
IEEE Circuits and Systems Magazine - Q1 2018 - Cover1
IEEE Circuits and Systems Magazine - Q1 2018 - Cover2
IEEE Circuits and Systems Magazine - Q1 2018 - Contents
IEEE Circuits and Systems Magazine - Q1 2018 - 2
IEEE Circuits and Systems Magazine - Q1 2018 - 3
IEEE Circuits and Systems Magazine - Q1 2018 - 4
IEEE Circuits and Systems Magazine - Q1 2018 - 5
IEEE Circuits and Systems Magazine - Q1 2018 - 6
IEEE Circuits and Systems Magazine - Q1 2018 - 7
IEEE Circuits and Systems Magazine - Q1 2018 - 8
IEEE Circuits and Systems Magazine - Q1 2018 - 9
IEEE Circuits and Systems Magazine - Q1 2018 - 10
IEEE Circuits and Systems Magazine - Q1 2018 - 11
IEEE Circuits and Systems Magazine - Q1 2018 - 12
IEEE Circuits and Systems Magazine - Q1 2018 - 13
IEEE Circuits and Systems Magazine - Q1 2018 - 14
IEEE Circuits and Systems Magazine - Q1 2018 - 15
IEEE Circuits and Systems Magazine - Q1 2018 - 16
IEEE Circuits and Systems Magazine - Q1 2018 - 17
IEEE Circuits and Systems Magazine - Q1 2018 - 18
IEEE Circuits and Systems Magazine - Q1 2018 - 19
IEEE Circuits and Systems Magazine - Q1 2018 - 20
IEEE Circuits and Systems Magazine - Q1 2018 - 21
IEEE Circuits and Systems Magazine - Q1 2018 - 22
IEEE Circuits and Systems Magazine - Q1 2018 - 23
IEEE Circuits and Systems Magazine - Q1 2018 - 24
IEEE Circuits and Systems Magazine - Q1 2018 - 25
IEEE Circuits and Systems Magazine - Q1 2018 - 26
IEEE Circuits and Systems Magazine - Q1 2018 - 27
IEEE Circuits and Systems Magazine - Q1 2018 - 28
IEEE Circuits and Systems Magazine - Q1 2018 - 29
IEEE Circuits and Systems Magazine - Q1 2018 - 30
IEEE Circuits and Systems Magazine - Q1 2018 - 31
IEEE Circuits and Systems Magazine - Q1 2018 - 32
IEEE Circuits and Systems Magazine - Q1 2018 - 33
IEEE Circuits and Systems Magazine - Q1 2018 - 34
IEEE Circuits and Systems Magazine - Q1 2018 - 35
IEEE Circuits and Systems Magazine - Q1 2018 - 36
IEEE Circuits and Systems Magazine - Q1 2018 - 37
IEEE Circuits and Systems Magazine - Q1 2018 - 38
IEEE Circuits and Systems Magazine - Q1 2018 - 39
IEEE Circuits and Systems Magazine - Q1 2018 - 40
IEEE Circuits and Systems Magazine - Q1 2018 - 41
IEEE Circuits and Systems Magazine - Q1 2018 - 42
IEEE Circuits and Systems Magazine - Q1 2018 - 43
IEEE Circuits and Systems Magazine - Q1 2018 - 44
IEEE Circuits and Systems Magazine - Q1 2018 - Cover3
IEEE Circuits and Systems Magazine - Q1 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q1
https://www.nxtbookmedia.com