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

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