IEEE Circuits and Systems Magazine - Q1 2018 - 36
Multiplier
....
β1
βn-1
Multiplier
Summing
Amplifier
Sqrt
Divider
βn
βn /β1:(n)2
Figure 5. schematic illustration of the hardware system for
calculating y k +1 in (22).
since it is possible to convert a QCQP into a SOCP, e.g.,
homogeneous QCQP that excludes linear terms [7].
SOCP is a convex program for minimizing a linear
cost function subject to linear and second-order cone
constraints,
minimize
dT x
x
subject to Gx = h,
||x 1:(n -1)||2 # x n,
(19)
where x ! R n is the optimization variable, G and h are
given parameters, x 1:(n -1) denotes a vector that consists
of the first n - 1 entries of x, and x n is the nth entry
of x. The last constraint in (19) is known as the secondorder cone constraint.
Similar to (11), we can rewrite problem (19) in the canonical form (4) that is amenable to the ADMM algorithm
minimize
x,y
d T x + p (x) + g (y)
subject to x = y,
(20)
n
where y ! R is the newly introduced optimization variable, and p and g are indicator functions with respect
to constraint sets {x |Gx = h} and {y | ||y 1:(n -1)||2 # y n},
respectively.
Following (6)-(9), the ADMM algorithm for solving
problem (20) includes subproblem (15) with respect to
the variable x, step (14) for updating dual variables n,
and a specific y -minimization problem (8),
t
||y - b||22
2
subject to ||y 1:(n -1) ||2 # y n,
minimize
y
(21)
where recall from (17) that b = x k +1 + (1/t) n k . The solution of problem (21) is given by projecting b onto a
second-order cone [53],
0 ||b 1:(n -1)||2 # -b n
y k +1 = * b ||b 1:(n -1)||2 # b n
bu ||b 1:(n -1)||2 $ |b n|,
(22)
bn
T
m 6b 1T:(n -1), ||b 1:(n -1)||2@ . Simiwhere bu = 12 c 1 +
||b 1:(n -1)||2
lar to the memristor-based LP solver, the ADMM step
(6) reduces to the solution of a system of linear equations that can be mapped onto memristor crossbars.
In the ADMM step (21), we can use peripheral circuits
including analog multipliers and summing amplifiers to
36
ieee circuits and systems magazine
evaluate the vector norm in (22) [60], [61]; see schematic
illustration in Fig 5.
To summa rize, one may exploit the a lternating
structure of ADMM to design memristor-based optimization solvers. The crucial property to enable this
is that ADMM helps in extracting parallel operations of
matrix/vector multiplication/addition which can be implemented using memristor crossbars and elementary
hardware elements.
C. Performance Evaluation
In what follows, we present empirical results that show
the effectiveness of the proposed memristor-based optimization framework to solve LPs and QPs. Since the presence of hardware variations leads to a reduced configuration accuracy on memristor crossbars, the matrix C in
(16) is actually modified to Cu = C + R, where R denotes
a random matrix whose elements are i.i.d. zero-mean
Gaussian random variables. The quantity ||R||F /||C||F
then provides the level of hardware variations, where
||·||F denotes the Frobenius norm of a matrix. In the
presence of hardware variations, we compare the solution x above to the optimal solution x * obtained from
the off-the-shelf interior-point solver CVX [62], that
excludes the effect of hardware variation. We adopt
||x - x *||2 /||x *||2 (averaged over 50 random trials) to measure the error between x and x * . In ADMM, the augmented parameter and the stopping tolerance are set to
be t ! {0.1, 1, 10, 100} and e = 10 -3 .
In Fig. 6, we present the difference between the memristor-based solution and the variation-free interior-point
solution as a function of the level of hardware variations for
problems with dimension n ! {100, 600, 1000}. When the
hardware variation is excluded, the memristor-based solution yields the same accuracy as the interior-point solution.
As the problem size or the hardware variation increases,
the difference from the interior-point solution increases.
However, the induced error is always below 5%. In Fig. 7, we
further show the convergence of the memristor-based solution framework as a function of the choice of the ADMM
parameter t. For each value of t, 50 random trials were
performed, each of which involved 10% hardware variation. We find that the convergence of the memristor-based
approach (to achieve e -accuracy solution) is robust to
hardware variations and the choice of ADMM parameter t.
Compared to LP, QP requires more iterations to converge
due to its higher complexity. Moreover, a moderate choice
of t, e.g., t = 1 in this example, improves the convergence
of the memristor-based approach.
V. Memristor-Based Sparse Learning
Sparse learning is concerned with the problem of finding
intrinsic sparse patterns of variables to be optimized.
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