Optimization: principles and algorithms, by Michel Bierlaire
Errata

Errors

  1. Page 16: Equation (1.31) is ambiguous. It should be

    \[ \argmin{_{x \in X \subseteq \R^n}} f(x) = \argmin{_{x \in X \subseteq \R^n}} h(x), \]

    where $h(x)=g(f(x))$.
  2. Page 86. Theorem 3.40. The correct statement is 'Let $\mathcal{P}= \{ x \in \mathbb{R}^n | Ax = b, x \geq 0 \}$ be a polyhedron such that each feasible basic solution is non degenerate. The point $x^* \in \mathcal{P}$ is a vertex of $\mathcal{P}$ if and only if it is a feasible basic solution.'
  3. Page 86. Proof of Theorem 3.40. Replace 'Consider $ m $ linearly independent columns of $A$, chosen arbitrarily, which form an invertible matrix $B$,...' by 'As $ x^*$ is not a feasible basic solution, there are strictly more than $m$ non zero components in $x^*$. Consider $m$ linearly independent columns of $A$, corresponding to non zero components of $x^*$, which form an invertible matrix $B$,...
  4. Page 99. After Eq. (4.15). 'Therefore, we can eliminate $\mu_1$ and $\mu_2$ so that $ X_q = \{ \lambda | \lambda \leq 1 \}, $ and the dual function becomes $ q(\lambda) = \lambda. $ The dual problem is written as $ \max \lambda $ subject to $ \lambda \leq 1 $'
  5. Page 388: 'The algorithm may detect an unbounded problem at step 15, or produce an optimal solution $x^*,x_a^*$. Consequently, one of the following three possibilities occurs:'. It should be 'The algorithm cannot detect an unbounded problem at step 15, as the objective function of $(\mathcal{A}$) is bounded below by 0. It always produces an optimal solution $x^*,x_a^*$. Consequently, one of the following two possibilities occurs:'
  6. Page 388: 'In summary, if the original problem is bounded, solving the auxiliary problem....' should be 'In summary, solving the auxiliary problem....'
  7. Page 546: Example 22.14: 'The best deal is obtained by selling .... for a total of 32,000.01 kEuros' should be 'The best deal is obtained by selling the Botticelli to Harry, the Bruegel to Giny, the Kandinsky to Ron and the last one to Hermione, for a total of 34,000.01 kEuros.'

Typos

Page 20Section 1.3'Korte and Vygen, 2007'should be'Korte and Vygen (2007)'
Page 51Definition 3.1'this concept is sometimes called afeasible solution'should be'this concept is sometimes called a feasible solution'
Page 82proof of Theorem 3.37'for any $i \in \mathcal{A}(x^*)$'should be'for any $i \in \mathcal{A}(x_0)$'
Page 83Definition 3.38'If, moreover, $x=B^{-1}b \geq 0$'should be'If, moreover, $x_B=B^{-1}b \geq 0$'
Page 166After Eq. (6.160)' $b\in \R^n$'should be' $b\in \R^m$'
Page 159Example 6.23' $x_1^2+ 4x_1 +3 = 0 $'should be' $x_1^2+ 4x_1 -x_2+3 = 0 $'
Page 263Introduction to Section 11.3'a one-dimensional optimization problems'should be'a one-dimensional optimization problem'
Page 265Last paragraph'the improvement of objective function'should be'the improvement of the objective function'
Page 371Algorithm 16.2, step 22' $\alpha_q = \min_i \lambda_i $'should be' $\alpha_q = \min_i \alpha_i $'
Page 494Definition 21.4'where $\mathcal{M} \subseteq \mathcal{N}$'should be'where $\mathcal{M} \subset \mathcal{N}$'
Page 501biography of Leonhard Euler'..., and became friends with his two sons'should be '..., and became friend with his two sons'
Page 506Theorem 21.14'a subset of nodes $\mathcal{M} \subseteq \mathcal{N}$'should be'a subset of nodes $\mathcal{M} \subset \mathcal{N}$'.
Page 535Section 22.2'The Karush-Kuhn-Tucker conditions (see Theorem 6.13) significantly simplify the transhipment problem'should be'The Karush-Kuhn-Tucker conditions (see Theorem 6.13) are significantly simpler for the transhipment problem'
Copyright 2015-2016 Michel Bierlaire