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

第二章

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

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 SS is affine, then it can be expressed as {xAx=b}\{x| Ax = b\}

2.1.3 介绍了仿射体的维度,其实就是线性子空间的维度。

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 x1,x2Sx_1, x_2 \in S, let x3=θx1+(1θ)x2x_3 = \theta x_1 + (1 - \theta) x_2, for any θ[0,1]\theta \in [0, 1], x3Sx_3 \in S, then SS 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 Set的convexity的operation。主要有:交集运算,仿射(translation, scaling and projection),linear-factional.

If S1,S2S_1, S_2 are convex sets, then S3=S1S2S_3 = S_1 \cap S_2 is convex.
If SS is convex set, then {yy=Ax+b,xS}\{y | y = Ax + b, x \in S \} is convex
If SS is convex set, then {yy=Ax+b/(cx+d),cx+d>0,xS}\{y | y = Ax + b / (c'x + d), c'x + d > 0, x \in S \} is convex.

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

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

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

Let x1,x2Sx_1, x_2 \in S, then x3=θx1+(1θ)x2Sx_3 = \theta x_1 + (1 - \theta) x_2 \in S for any θ[0,1]\theta \in [0, 1].
After transformation f(x)=(Ax+b)/(cx+d)f(x) = (Ax+b)/(c'x + d), x4=f(x1),x5=f(x2)x_4 = f(x_1), x_5 = f(x_2), we want to show that x6=f(x3)=ux4+(1u)x5x_6 = f(x_3) = ux_4 + (1-u)x_5 and u[0,1]u \in [0, 1]
Expanding above equations:

x6=f(x3)=f(θx1+(1θ)x2)=(A(θx1+(1θ)x2)+b)/(c(θx1+(1θ)x2)+d)=(θ(Ax1+b)+(1θ)(Ax2+b))/(θ(cx1+d)+(1θ)(cx2+d))x6=ux4+(1u)x5=u(Ax1+b)/(cx1+d)+(1u)(Ax2+b)/(cx2+d)\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=θ(cx1+d)/(θ(cx1+d)+(1θ)(cx2+d))u = \theta(c'x_1 + d)/(\theta(c'x_1 + d) + (1-\theta)(c'x_2+d))

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

2.5 超平面分割定理

If C,DC, D are convex sets, and CD=C \cap D = \emptyset, then there exists a hyperplane ax=ba'x = b such that axba'x \geq b for any xCx \in C and axba'x \leq b for any xDx \in D.

证明书上有。
由此引出仿射体和凸体的分割:

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

证明见 Example 2.19. 文中用了一个直观的事实:即如果 cxdc'x \geq d,这里c,dc', d是constant vector and constant scalar,那么c=0,d0c'=0, d \leq 0.

由此再引出以下:

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

很直观的理解,Ax<b    bAx>0Ax < b \implies b - Ax > 0CC 代表不等式左边的空间,D代表不等式右边的空间,他们不可能有交集的,否则交集中的点可令不等式成立。

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

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

也就是,以下两个只有一个能成立:

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

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

第四、五章

优化问题的标准形式

minimize f0(x)subject tofi(x)0,i=1,,mhi(x)=0,i=1,,p\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}

对于fi(x)0f_i(x) \leq 0hi(x)=0h_i(x) =0组成的交集,如果其不为空,则这个问题是可行的。
对于非标准形式,比如lixuil_i \leq x \leq u_i其可转为为标准形式 lix0,xui0l_i - x \leq 0, x - u_i \leq 0
用拉格朗日乘数,解法很简单,设:

L(x,λ,ν)=f0(x)+i=1mλifi(x)+i=1nνihi(x)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(λ,ν)=infxDL(x,λ,ν)g(\lambda, \nu) = \inf_{x\in D} L(x, \lambda, \nu)

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

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

易得

L(x,λ,ν)=bν+(c+Aνλ)xL(x,\lambda, \nu) = -b'\nu + (c + A'\nu - \lambda)'x

g(λ,ν)=infxL(x,λ,ν)=bν+infx(c+Aνλ)xg(\lambda, \nu) = \inf_x L(x, \lambda, \nu) = -b'\nu + \inf_x(c + A'\nu - \lambda)'x

那么

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

因为pg(λ,ν)p^* \geq g(\lambda, \nu),LP的标准形式对偶形式为:

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

我们称其解为dd^*.

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

对于形如

minimize f0(x)subject tofi(x)0,i=1,,mA(x)=b,\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}

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

对于形如

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

的LP,其对偶形式为:

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

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

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

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

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

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

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

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

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

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

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

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

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

对应LP的及其对偶问题,

Aλ=cA(λc0)=0    cR(A),λc0N(A)A'\lambda = c,A'(\lambda - c_0) = 0 \implies c \in R(A), \lambda - c_0 \in N(A')

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

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