IEEE Circuits and Systems Magazine - Q1 2018 - 34

both time and space. However, it requires more memristors and higher communication overhead. In addition to
circuit-level techniques [19], [27], [28], [51], we will show
that the non-ideal effects caused by hardware variations can also be mitigated by optimizing the algorithm
prior to mapping to memristor crossbars.
III. Convex Optimization and ADMM
Although memristor-based AI applications are different
such as sparse learning and dictionary learning [24]-
[30], the principle of designing memristor-based computation accelerators is the same, namely, recognizing
the optimization problem underlying the learning task
and mapping the corresponding optimization algorithm
onto a memristor network. In what follows, we provide
some background on mathematical programming and
focus on a solver called alternating direction method of
multipliers (ADMM).
A. Preliminaries on Convex Optimization and ADMM
In general, an optimization problem can be cast as
minimize
f (x),
x
subject to x ! X,

(3)

where x ! R n is the optimization variable, f ($) denotes
the cost function to be minimized, and X denotes a constraint set. In this paper, we focus on the convex version
of problem (3), where f ($) is a convex function and X is
a convex set [37]. In convex programming, a local minimum given by a stationary point of (3) implies the global
optimality. Convex optimization forms the foundation of
many AI applications [35].
There exist many algorithms to solve convex optimization problems, such as gradient-type first-order methods [52], and primal-dual interior-point (second-order)
methods [37]. Compared to the conventional optimization methods, ADMM has drawn great attention in the
last ten years [41], [53]. The main advantage of ADMM
is that it allows us to split the optimization problem into
subproblems, each of which can be solved efficiently
and, in some cases, analytically.
A standard problem that is suitable for the application of ADMM is given by
minimize
x,y

f (x) + g (y)

subject to Ax + By + c = 0,

(4)

where x ! R n and y ! R m are optimization variables, f ($)
and g ($) are convex functions, and A ! R l # n, B ! R l # m,
and c ! R l are appropriate coefficients associated
with a system of l linear equality constraints. Problem
(4) reduces to problem (3) when A = I n, B =-I m, c = 0 l,
34

ieee circuits and systems magazine

and g ($) is an indicator function on the convex set
X, namely,
g (y) = '

0 if y ! X
3 otherwise.

(5)

Here I n denotes the n # n identity matrix, and 0 n is the
n # 1 vector of all zeros. In what follows, while referring
to identity matrices and vectors of all ones (or zeros),
their dimensions are omitted for simplicity but can be inferred from the context. ADMM is an iterative algorithm,
and its kth iteration is given by [41]
x k +1 = arg min $ f (x) + (n k) T (Ax + By k + c)
x

+

t

2

2
Ax + By k + c 2 .

(6)

y k +1 = arg min $ g (y) + (n k) T (Ax k +1 + By + c)
y

(7)

2
Ax k +1 + By + c 2 .

(8)

n k +1 = n k + t (Ax k +1 + By k +1 + c),

(9)

+

t

2

where n is the Lagrangian multiplier (also known as the
dual variable), t is a positive weight to penalize the augmented term associated with the equality constraint of
(4), and $ 2 denotes the , 2 norm. The ADMM algorithm
terminates when an e -accuracy is achieved, namely,
||x k - y k||2 # e, and ||x k - x k -1||2 # e. ADMM has a convergence rate O (1/K) for general convex optimization problems [54], where K is the number of iterations. In other
words, given the stopping tolerance e, ADMM requires
O (1/e) iterations to converge. We remark that ADMM
has a faster convergence rate than many gradient-type
first-order algorithms, which often have the convergence rate of O (1/ K ) . In the next section, we will show
that ADMM provides a suitable framework for mapping
to a memristor network.
IV. Memristor-Based Linear
and Quadratic Optimization Solvers
In this section, we employ memristor crossbars to solve
linear and quadratic programs. Linear programs (LPs)
and quadratic programs (QPs) are the most common
optimization problems that are encountered in many
applications such as resource scheduling, intelligent
transportation, portfolio optimization, smart grid and
signal processing [55]-[58]. The interior-point algorithm is a standard method to solve LPs as well as QPs
[37], with O ^n 3 ~n 3.5 h time complexity [59], where n is
the number of optimization variables. The conventional
interior-point algorithm running on CPUs/GPUs has low
degree of parallelism. By contrast, as we next demonstrate, ADMM breaks up optimization problems into
first quarter 2018



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