# Errata for Algorithms for Convex Optimization

### Nisheeth K. Vishnoi

This errata refers to the printed edition of the book, available here and here. The author would like to thank the contributors to this errata. Further corrections, feedback, and comments are welcome and should be emailed to the author.

List of contributors to errata: Sergio Cabello, Anay Mehrotra

## First print (2021)

• Definition 2.7 (Page 20)
Old text: \sum_{k\geq 3}\nabla^kf(a)[x-a,\ldots,x-a]
New text: \sum_{k\geq 3}\frac{1}{k!}\nabla^kf(a)[x-a,\ldots,x-a]
• Page 20:
Old text: {\alpha_0 + \sum_{i=1}^k alpha_i v_i : \alpha_0,\alpha_1,\ldots,\alpha_k\in \mathbb{R} }
New text: {v_0 + \sum_{i=1}^k alpha_i v_i : v_0\in \mathbb{R}^n,\ \ \alpha_1,\ldots,\alpha_k\in \mathbb{R} }
• Exercise 2.1 (a) (Page 29)
Old text: a_1,\ldots,a_m\in\mathbb{Q}^m
New text: a_1,\ldots,a_m\in\mathbb{Q}^n
• Exercise 2.1 (c) (Page 29)
Old text: A is a symmetric n\times n matrix and X runs over symmetric matrices
New text: A is a real-symmetric n\times n matrix and X runs over real-symmetric matrices
• Theorem 3.6 (Page 39)
Old text: f: K\to R
New text: f: K\to \mathbb{R}
• Exercise 3.10 (Page 47)
Old text: a convex function is
New text: a convex function, whose domain is an open set, is
• Section 4.1.1 (Page 50)
Old text: b \in \mathbb{R}^n
New text: b \in \mathbb{R}^m
• Exercise 4.9 (c) (Page 66)
Old text: vertex of P
New text: vertex of K
• Exercise 4.11 (c) (Page 67)
Old text: polynomial time
New text: polynomial time algorithm
• Theorem 5.5 (Page 72)
Old text: Suppose that the functions f,f_1,f_2,\ldots,f_m and ...
New text: Suppose that the functions f,f_1,f_2,\ldots,f_m are convex and ...
• Exercise 5.11 (Page 80)
Old text: consider the primal problem where
New text: consider the primal problem from Equation (5.2) where
• Exercise 5.11 (Page 80)
Old text: Prove that the dual is
New text: Prove that the objective of the dual is
• Exercise 5.12 (Page 80)
Old text: primal convex optimization problem over
New text: primal convex optimization problem from Equation (5.2) over
• Exercise 5.12 (Page 80) (Page 81)
Old text: a^\top X a \leq 0
New text: a^\top X a \leq 1
• Exercise 5.14 (c) (Page 81)
Old text: positive orthant
New text: non-negative orthant
• Page 91
• Last equation on Page 92
Old text: R_t \leq
New text: R_t =
• Exercise 6.5 (Page 102)
Old text: which satisfies for every x\in \mathbb{R}^n, one has mI\preceq \nabla^2 f(x)\preceq MI
New text: which satisfies for every x\in \mathbb{R}^n, mI\preceq \nabla^2 f(x)\preceq MI
• Page 112
Old text: we can ignore terms that depend only on x
New text: we can ignore terms that depend only on x^t
• Page 112
Old text: f(x^t) may be more than f(x^{t+1})
New text: f(x^{t+1}) may be more than f(x^{t})
• Lemma 7.4 (Page 115)
In item 2, drop “for all i=1,2,…,n“ at the end
• Page 129
In the last two inequalities replace x_e by x_e^t
• Page 130
Old text: \alpha_e:= \sum_{e\in N(v)} w_v^t
New text: \alpha_e:= \sum_{v:\ e \in N(v)} w_v^t
• Page 131
In the first two inequalities replace x_e by x_e^t
• Page 131
Old text: \frac{1}{T}\cdot \frac{1}{n}\left(\sum_{e:\ v\in e} x_e^t -1\right)\leq \frac{1}{T}\cdot T\cdot 0 + \delta
New text: \frac{1}{T}\cdot \sum_{t=0}^{T-1}\frac{1}{n}\left(\sum_{e:\ v\in e} x_e^t -1\right)\leq \frac{1}{T}\cdot T\cdot 0 + \delta
• Page 134
Old text: x:= \frac{1}{T}\sum_{t=0}^{T-1}x^i
New text: x:= \frac{1}{T}\sum_{t=0}^{T-1}x^t
• Exercise 7.11 (Page 134)
Old text: Assume that ||\nabla f(x)||_2 \leq G
New text: Assume that \mathbb{E}[||g(x)||_2^2] \leq G^2
• Exercise 7.17 (Page 139)
Old text: oracle satisfy ||g^t||\leq 1.
New text: oracle satisfy 0\leq g_i^t \leq 1 for all i\in [n]
• Exercise 7.17 (d) (Page 139)
Old text: the following always holds: $$-\varepsilon \sum_{t=0}^{T-1} \hat{g}_i^t - \ln{n} \leq -\frac{\varepsilon}{1-n\varepsilon} \sum_{t=0}^{T-1} \langle p^t, \hat{g}^t\rangle + \frac{2\varepsilon^2}{1-n\varepsilon}nT$$
New text: the following holds for any fixed i: $$-\varepsilon \sum_{t=0}^{T-1} g_i^t - \ln{n} \leq -\frac{\varepsilon}{1-n\varepsilon} \sum_{t=0}^{T-1} \langle p^t, g^t\rangle + \frac{2\varepsilon^2}{1-n\varepsilon}nT$$
• Equation 8.15 (Page 147)
In this equation, also define \lambda_t:= (1-\gamma_t)\lambda_{t-1}
• Exercise 8.3 (Page 157)
Old text: f(x) := \min_{x\in \mathbb{R}^n} \frac{1}{2}(x-x^\star)^\top A (x-x^\star)
New text: \min_{x\in \mathbb{R}^n} \frac{1}{2}(x-x^\star)^\top A (x-x^\star)
• Exercise 8.3 (Page 157)
Set x_0=x_1.
• Exercise 8.3 (b) (Page 158)
Old text: \theta := \max{ |1-\sqrt{\eta\lambda_1}|, |1-\sqrt{\eta\lambda_n}|}
New text: \theta := \max{ |1-\sqrt{\eta\lambda_1}|, |1-\sqrt{\eta\lambda_n}|}^2
• Figure 9.1 (Page 161)
Replace f by g and f(x_0) by g(x_0)
• Page 168
Old text: D^{(3)}
New text: D^3
• Theorem 9.4 (Page 167)
Old text: Let x_0 be an arbitrary starting point
New text: Let x_0 be the starting point specified in the NE condition
• Proof of 9.4 (Page 167)
Old text: We can take M = \frac{L||H(x_0)^{-1}||}{2}\leq \frac{L}{2h}
New text: Since f and x_0 satisfy the NE condition, we can take M = \frac{L||H(x_0)^{-1}||}{2}\leq \frac{L}{2h}
• Theorem 10.2 (Page 186)
Old text: or terminates stating that the polyhedron is infeasible. The algorithm runs in poly\left(L,\log\frac{1}{\varepsilon}\right) time.
New text: The algorithm runs in poly\left(L,\log\frac{1}{\varepsilon}\right) time.
• Lemma 10.9 (Page 194)
Let x_T and \eta_T be the variables defined in Algorithm 8
• Theorem 10.10 (Page 194)
Old text: outputs a point \hat{x}\in P that satisfies
New text: outputs a point \hat{x}\inint(P) that satisfies
• Proof of Lemma 10.7 (Page 196)
Old text: n_{\eta'}(x)=H(x)^{-1}\nabla f_{\eta'}(x)
New text: -n_{\eta'}(x)=H(x)^{-1}\nabla f_{\eta'}(x)
• Lemma 10.15 (Page 203)
Old text: For any \eta>0 denote
New text: For any \eta>0 and x\in \mathbb{R}^n denote
• Equation 11.3 (Page 218)
Old text: $$\begin{bmatrix}B & 0\\I & I\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}b\\u\end{bmatrix}$$
New text: $$\begin{bmatrix}B & 0\\I & I\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}b\\\rho\end{bmatrix}$$
• Section 11.2.1 (Page 221)
Old text: \tilde{n}(x) := \tilde{H}(x)^{-1}\tilde{g}(x)
New text: \tilde{n}(x) := -\tilde{H}(x)^{-1}\tilde{g}(x)
• Section 11.2.2 (Page 221)
First equation in Section 11.2.2 should have “=” instead of “:=”
• Section 11.2.2 (Page 222)
Old text: (where E=... such that
New text: (where E=...) such that
• Page 225
Old text: g(x)=X^{-1}1
New text: g(x)=-X^{-1}1
• Equation 11.8 (Page 225)
Old text: \tilde{n}_{\eta}(x):=X^2(A^\top (AX^{-2}A^\top)^{-1} AX^2 -I)(\eta c+X^{-1}1)
New text: \tilde{n}_{\eta}(x):=X^2(A^\top (AX^{2}A^\top)^{-1} AX^2 -I)(\eta c-X^{-1}1)
• Lemma 11.10 (Page 228)
Old text: s,t\in G
New text: s,t\in V
• Page 229
Old text: \frac{F}{2}\leq x_{\hat{i}}\leq F=u_{\hat{i}}-F
New text: \frac{F}{2}\leq x_{\hat{i}}\leq F=\rho_{\hat{i}}-F
• Page 229
Old text: \min{\frac{1}{2},\frac{F}{2}} \leq y_i
New text: \min{\frac{1}{2},F} \leq y_i
• Page 231
Old text: ||H(x)^{-1}g(x)||_x=g(x)^\top H(x)^{-1} g(x)
New text: ||H(x)^{-1}g(x)||_x^2=g(x)^\top H(x)^{-1} g(x)
• Page 231
Old text: ||H(x)^{-1}g(x)||_x=1^\top \Pi 1=||\Pi 1||_2^2\leq ||1||_2^2=m
New text: ||H(x)^{-1}g(x)||_x^2=1^\top \Pi 1=||\Pi 1||_2^2\leq ||1||_2^2=m
• Exercise 11.10 (Page 244)
Old text: self-concordance implies that for all x\in K
New text: self-concordance implies that for all x\inint(K)
• Exercise 11.15 (Page 247)
Part (d) of this exercise should be its own exercise 11.16
• Algorithm 9 (Page 253)
Old text: A number u such that u\leq y^\star+\varepsilon
New text: A number u such that y^\star \leq u\leq y^\star+\varepsilon
• Algorithm 10 (Page 255)
Before Line 1 add “Initialize t=0” and after Line 9 add “Set t:=t+1”
• Proof of Theorem 12.7 (Page 256)
Replace all occurences of n by m
• Section 12.2.2 (Page 257)
Old text: the method developed we present in
New text: the method developed in
• Section 12.4 (Page 262)
Old text: The proof of Lemma 12.12 is has two parts
New text: The proof of Lemma 12.12 has two parts
• Proof of Lemma 12.18 (Page 272)
Old text: \geq \langle c, x^\star \rangle + (1-\alpha)
New text: = \langle c, x^\star \rangle + (1-\alpha)
• Section 12.5.5 (Page 273)
Old text: but still manageable The idea
New text: but still manageable. The idea
• Exercise 12.3 (Page 274)
Replace all occurences of n by m
• Part (c), Exercise 12.3 (Page 274)
Old text: a polynomial time linear optimization oracle
New text: a polynomial time separation oracle
• Exercise 12.6 (Page 276)
Old text: larger than the lower bound derived above
New text: larger than the upper bound derived above
• Section 13.2.2 (Page 287)
Lovász misspelt as Lovás.
• Theorem 13.12 (Page 287)
Old text: l_0\leq u_0\in R
New text: l_0\leq u_0
• Section 13.3 (below Definition 13.14) (Page 289)
Old text: \Delta_\omega is convex
New text: \Delta_\Omega is convex
• Definition of f^{-}(x) in Exercise 13.10 (Page 305)
Old text: \sum_{S\subseteq [n]} \alpha_S f(S)
New text: \sum_{S\subseteq [n]} \alpha_S F(S)