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

第二章

这部分是在用数学分析和集合论的语言定义一些$N$维空间的几何体

2.1.1 定义线和线段

2.1.2 定义仿射集合

仿射集合有如下性质：

连接仿射集合中的任意两点成一条直线，那么直线上任意一点也在该仿射集合内

对应的几何体是：点，直线，超平面(hyperplane)，有offset的线性子空间(subspace)

最后得出的结论很有意思:

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.3 仿射体的维度

其实就是线性子空间的维度。

2.1.4-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]\Rightarrow 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.

介绍多面体的时候提到了Simplex，对应的是一维的线段，二维的三角形，三维的四面体等等。它其实是由k个affinely independent的点组成的凸包，亦即，从这k个点中任取三个点组成一个超平面，那么其他所有点不能在这个超平面内。

2.3 凸运算 Convex 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.

理解起来很简单。$f(x) = Ax+b$ 相当于线性变换。对$A$做奇异值分解，得到$f(x) = U\Sigma V x + b$, 其中 $U, V$ 为旋转操作, $\Sigma$为缩放操作，$+b$为平移操作。几何体经过旋转，缩放，旋转再平移之后，它的convexity不变。

再看 $f(x) = (Ax + b) / (c'x + d)$，需理解$x / (c'x + d)$ 这个操作。$c'x + d = 0$ 代表一个超平面，$f(x) = c'x + d$ 得到的绝对值代表离超平面的远近，正负号代表在超平面哪一侧 。那么 $f(x) = x/(c'x + d), c'x + d > 0$ 这个操作的意思是，离平面越远的点我会让它离原点越近，离平面越近的点我会让它离原点越远。这里保证了定义域在平面的正侧。

证明的方法很简单，根据定义即可。简单证明下linear-factional function reserves convexity.

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) \\ &=\frac{A(\theta x_1 + (1 - \theta)x_2)+b}{c'(\theta x_1 + (1-\theta)x_2) + d} \\ &= \frac{\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 \\ &= \frac{u(Ax_1 + b)}{cx_1 + d}+\frac{(1-u)(Ax_2+ b)}{cx_2+d} \end{aligned}$$

By comparison, we get

$$u = \frac{\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$.

证明见 Example 2.19. 文中用了一个直观的事实：

If $c'x \geq d$，where $c', d$ are constant vector and constant scalar，then $c'=0, d \leq 0$.

由此再引出以下:

Below two statements are equivalent:

1. $Ax=b$ has no feasible solutions
2. If $C = \{b - Ax | x \in R^n\}$ and $D = R_{++}^m = \{y\in R^m|y > 0\}$, then $C \cap D = \{\emptyset \}$

很直观的理解，$Ax < b \implies b - Ax > 0$，$C$ 代表不等式左边的空间，$D$代表不等式右边的空间，他们不可能有交集的，否则交集中的点可令不等式成立。上面第二条不就是前面证明的仿射体和凸体的分割么，他们无交集的话，那不就可以根据平面分割定理引出一些东西？

For $C = \{b - Ax | x \in R^n\},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$, which 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$.

也就是说

Below two statements must be one True and one False:

1. $Ax<b$ has feasible solutions.
2. If $\lambda \neq 0, \lambda \geq 0$ and $A'\lambda = 0$, then $\lambda'b \leq 0$

这里是不是有对偶的感觉了？

第四、五章

优化问题的标准形式

对于$f_i(x) \leq 0, h_i(x) =0$组成的交集，如果其不为空，则这个问题是可行的。

对于非标准形式，比如$l_i \leq x \leq u_i$其可转为为标准形式 $l_i - x \leq 0, x - u_i \leq 0$  用拉格朗日乘数，解法很简单，设:

标准形式的对偶函数即为：

这里，对于$\lambda_i \geq 0$， 标准形式的解$p^* \geq g(\lambda, \nu)$，这个很容易证明。 求解的话，对$L(x)$求梯度，令其等于零，求得$x$代入$L(x)$即可求得$g(\lambda, \nu)$，这里利用了$L(x)$是concave的性质。 那么对于LP的标准形式

易得

那么

因为$p^* \geq g(\lambda, \nu)$，LP的标准形式对偶形式为：

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

对于形如

的问题，如果$f_i(x)$ 是convex 的，那么强对偶一般都成立。

对于形如

的LP，其对偶形式为：

我们来其分析其对偶性。$S = \{x| Ax\geq b, x \in R^m\}$这里无非有这么几种情况：

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

因为$\{y|y=Ax\}$对应的是线性子空间，$\{y|y=Ax -b\}$是对线性子空间朝$-b$方向平移，那么$S = \{y|y=Ax -b\}\cap\{y|y\geq 0\}=\emptyset$意味着平移之后与$R^n_+$无交集，$rank(A) < m$。所以到底是如何平移的呢？想象把$x + y + z = 0$平移到$x+y+z = -1$，平移方向有垂直于子空间的分量，且存在子空间的某个法向量，使得这部分分量与这个法向量的方向相反，即存在$A'$的某一列$A_j$($A$的某一行)，使得$(-b)'A_j < 0$， 或者$b'A_j > 0$。如果对偶形式有可行域，则意味着$\lambda$在$A'$的零空间内，且方向为正，而显然$b$在$A'$的零空间内有正向的分量，这就使得$b'\lambda > 0$，所以$\max_\lambda b'\lambda = \infty$。因此，在LP无可行域的情况下，其对偶形式要么无可行域，要么是无界的。

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

如果理解了正交补，证明以上就变得很简单。维基百科的正交补定义: 对于$V$的子空间$W$，$W$的正交补为$W^\bot$定义为：

对于$m \times n$的矩阵$A$来说，记$R(A), C(A), N(A)$为其行，列，零空间，则

对应LP的及其对偶问题，

读者可以用以上性质自证$S = \emptyset$的情况。

Convex Optimisation 下载地址

bv_cvxbook.pdf