Convex Optimization 这本书非常有意思，它是线性代数，几何学，集合论，数学分析的综合。

### 第二章

#### 2.1.2 定义仿射集合

Every affine set can be expressed as the solution set of a system of linear equation

If a set $S$ is affine, then it can be expressed as $\{x| Ax = b\}$

#### 2.1.4, 2.1.5, 2.2.1, 2.2.2, 2.2.3, 2.2.4 介绍了凸体(Convex Set)，椎体(Cone)，超平面(hyperplane)，半空间(halfspace)，球体(ball)，椭圆体(ellipsoids)，多面体(polyhedra) 等等。

If $x_1, x_2 \in S$, let $x_3 = \theta x_1 + (1 - \theta) x_2$, for any $\theta \in [0, 1]$, $x_3 \in S$, then $S$ is convex.
Any line segments constructed from any two points in the set are within the set, then the set is convex.

#### 2.3 介绍了一些保持Convex Set的convexity的operation。主要有：交集运算，仿射（translation, scaling and projection)，linear-factional.

If $S_1, S_2$ are convex sets, then $S_3 = S_1 \cap S_2$ is convex.
If $S$ is convex set, then $\{y | y = Ax + b, x \in S \}$ is convex
If $S$ is convex set, then $\{y | y = Ax + b / (c'x + d), c'x + d > 0, x \in S \}$ is convex.

Let $x_1, x_2 \in S$, then $x_3 = \theta x_1 + (1 - \theta) x_2 \in S$ for any $\theta \in [0, 1]$.
After transformation $f(x) = (Ax+b)/(c'x + d)$, $x_4 = f(x_1), x_5 = f(x_2)$, we want to show that $x_6 = f(x_3) = ux_4 + (1-u)x_5$ and $u \in [0, 1]$
Expanding above equations:

\begin{aligned} x_6 &= f(x_3) = f(\theta x_1 + (1 - \theta)x_2) \\ &= (A(\theta x_1 + (1 - \theta)x_2)+b ) /(c'(\theta x_1 + (1-\theta)x_2) + d) \\ &= (\theta(Ax_1+b) + (1-\theta)(Ax_2+b)) / (\theta(c'x_1 + d) + (1-\theta)(c'x_2+d)) \\ \\ x_6 &= ux_4 + (1-u)x_5 \\ &= u(Ax_1 + b) /(cx_1 + d) + (1-u)(Ax_2 + b)/(cx_2+d) \end{aligned}

By comparison, we get

$u = \theta(c'x_1 + d)/(\theta(c'x_1 + d) + (1-\theta)(c'x_2+d))$

And indeed we can show $u \in [0, 1]$ since $c'x_1 + d > 0$, $c'x_2 + d > 0$ and $\theta \in [0,1]$

#### 2.5 超平面分割定理

If $C, D$ are convex sets, and $C \cap D = \emptyset$, then there exists a hyperplane $a'x = b$ such that $a'x \geq b$ for any $x \in C$ and $a'x \leq b$ for any $x \in D$.

$C \subset R^n$ is convex and $D = \{Fu + g| u \in R^m, F \in R^{n \times m}\}$ is affine. If $C \cap D = \emptyset$, then there exists $a \neq 0$ such that $F'a = 0$ and $a'x \leq a'g$ for all $x \in C$.

1. $Ax < b$ 无可行解
2. For $C = \{b - Ax | x \in R^n\}$ and $D = R_{++}^m = \{y\in R^m|y > 0\}$, $C \cap D = \emptyset$
(1) 和 (2) 是等价的

（2）不就是前面证明的仿射体和凸体的分割么，他们无交集的话，那不就可以根据平面分割定理引出一些东西？

For $C = \{b - Ax | x \in R^n\}$ and $D = R_{++}^m = \{y\in R^m|y > 0\}$, if $C \cap D = \emptyset$, then there exists $\lambda'y \leq \mu$ for any $y \in C$ and $\lambda' y \geq \mu$ for any $y \in D$.
The first inequality shows that $\lambda'(b - Ax) \leq \mu \implies \lambda'b - \mu \leq \lambda'Ax$ for all $x$, which implies $\lambda'A = 0$, $\lambda'b - \mu \leq 0$.
The second inequality shows $\lambda'y \geq \mu$ for all $y > 0$ implies $u \leq 0$ and $\lambda \geq 0$ and $\lambda \neq 0$.
From $\lambda'b - \mu \leq 0$ and $u \leq 0$ we can show $\lambda' b \leq 0$.

1. $Ax < b$ 有可行解
2. $\lambda \neq 0, \lambda \geq 0, A'\lambda = 0, \lambda'b \leq 0$

### 第四、五章

\begin{aligned} \text{minimize } \quad & f_0(x)\\ \text{subject to} \quad & f_i(x) \leq 0, \qquad i = 1, \dots, m\\ &h_i(x) = 0, \qquad i = 1, \dots, p \end{aligned}

$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{i=1}^{n}\nu_ih_i(x)$

$g(\lambda, \nu) = \inf_{x\in D} L(x, \lambda, \nu)$

\begin{aligned} \text{minimize } \quad & c'x\\ \text{subject to} \quad &x\geq 0 \\ &Ax=b \end{aligned}

$L(x,\lambda, \nu) = -b'\nu + (c + A'\nu - \lambda)'x$

$g(\lambda, \nu) = \inf_x L(x, \lambda, \nu) = -b'\nu + \inf_x(c + A'\nu - \lambda)'x$

$g(\lambda, \nu) = \begin{cases} -b'\nu, & A'\nu-\lambda + c= 0 \\ -\infty, & \text{otherwise } \end{cases}$

\begin{aligned} \text{maximize} \quad & -b'\nu \\ \text{subject to} \quad & A'\nu + c \geq 0 \end{aligned}

$d^* \leq q^*$，我们称其为弱对偶。
$d^* = q^*$, 我们称其为强对偶。

\begin{aligned} \text{minimize } \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \qquad i = 1, \dots, m\\ & A(x) = b, \end{aligned}

\begin{aligned} \text{minimize } \quad & c'x \\ \text{subject to} \quad & Ax \geq b \\ \end{aligned}

\begin{aligned} \text{maximize} \quad & b'\lambda \\ \text{subject to} \quad & A'\lambda = c\\ & \lambda \geq 0 \end{aligned}

1. $S=\emptyset$，即问题无可行域。
如果不用几何性质，证明就简单多了。

$S = \emptyset, \{\lambda| A'\lambda = c, \lambda \geq 0\} \neq \emptyset \implies !\exists x: Ax \geq b$

$!\exists: x'A'\lambda \geq b'\lambda \implies \forall x: b'\lambda > x'A'\lambda \implies b'\lambda > 0$

1. 存在$x \in S$ 使得 $||x|| \rightarrow \infty$，即$S$是无界的。此时，如果原LP无最优解，那么$c'$不可用$A$的列向量正线性组合来表示，这意味着对偶形式无可行域。如果原LP是有界的，那么肯定有最优解，其对偶形式有可行域，且有解。

2. $S$是有界的。这种情况下原LP肯定有解，且对偶形式也有解。

$W^\bot = \{x \in V | \forall y \in W, x'y = 0\}$

$R(A)^\bot = N(A)$

$C(A)^\bot = N(A')$

$A'\lambda = c，A'(\lambda - c_0) = 0 \implies c \in R(A), \lambda - c_0 \in N(A')$

$Ax = b, A(x - b_0) = 0 \implies b \in C(A), x - x_0 \in N(A)$