凸优化笔记

作者: 太捉急 | 来源:发表于2019-06-03 17:55 被阅读0次

凸优化笔记2-主要内容
凸优化笔记
凸优化笔记(1) 引言
机器学习（6）——凸优化理论(一)
Convex Optimization Note 1 | Int
凸优化有什么用
凸优化&非凸优化
凸优化相关概念学习笔记
《凸优化理论》笔记：前言
通俗易懂地理解机器学习理论中的凸优化

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

第二章

2.1 这部分是在用数学分析和集合论的语言定义一些 $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.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.

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

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.

理解起来很简单。 $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{align} 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{align}$
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$ .

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

由此再引出以下：

$Ax < b$ 无可行解

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

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

（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$ .

也就是，以下两个只有一个能成立：

$Ax < b$ 有可行解

$\lambda \neq 0, \lambda \geq 0, A'\lambda = 0, \lambda'b \leq 0$

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

第四、五章

优化问题的标准形式
$\begin{align} \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{align}$
对于 $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$
用拉格朗日乘数，解法很简单，设:
$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)$

这里，对于 $\lambda_i \geq 0$ ，标准形式的解 $p^* \geq g(\lambda, \nu)$ ，这个很容易证明。
求解的话，对 $L(x)$ 求梯度，令其等于零，求得 $x$ 代入 $L(x)$ 即可求得 $g(\lambda, \nu)$ ，这里利用了 $L(x)$ 是concave的性质。
那么对于LP的标准形式，
$\begin{align} \text{minimize } \quad & c'x\\ \text{subject to} \quad &x\geq 0 \\ &Ax=b \end{align}$
易得
$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}$

因为 $p^* \geq g(\lambda, \nu)$ ，LP的标准形式对偶形式为：
$\begin{align} \text{maximize} \quad & -b'\nu \\ \text{subject to} \quad & A'\nu + c \geq 0 \end{align}$
我们称其解为 $d^*$ .

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

对于形如
$\begin{align} \text{minimize } \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \qquad i = 1, \dots, m\\ & A(x) = b, \end{align}$

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

对于形如
$\begin{align} \text{minimize } \quad & c'x \\ \text{subject to} \quad & Ax \geq b \\ \end{align}$

的LP，其对偶形式为：
$\begin{align} \text{maximize} \quad & b'\lambda \end{align}$
我们来其分析其对偶性。 $S = \{x| Ax\geq b, x \in R^m \}$ 这里无非有这么几种情况：

$S=\emptyset$ ，即问题无可行域。
如果不用几何性质，证明就简单多了。
$S = \emptyset, \{A'\lambda = c\} \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$ 。
因为 $\{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无可行域的情况下，其对偶形式要么无可行域，要么是无界的。
存在 $x \in S$ 使得 $||x|| \rightarrow \infty$ ，即 $S$ 是无界的。此时，如果原LP无最优解，那么 $c'$ 不可用 $A$ 的列向量正线性组合来表示，这意味着对偶形式无可行域。如果原LP是有界的，那么肯定有最优解，其对偶形式有可行域，且有解。
$S$ 是有界的。这种情况下原LP肯定有解，且对偶形式也有解。

如果理解了正交补，证明以上就变得很简单。维基百科的正交补定义:
对于 $V$ 的子空间 $W$ ， $W$ 的正交补为 $W^\bot$ 定义为：
$W^\bot = \{x \in V | \forall y \in W, x'y = 0\}$
对于 $m \times n$ 的矩阵 $A$ 来说，记 $R(A), C(A), N(A)$ 为其行，列，零空间，则
$R(A)^\bot = N(A)$
$C(A)^\bot = N(A')$
对应LP的及其对偶问题，
$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)$

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

凸优化笔记2-主要内容
笔记主要内容凸集、凸函数、凸优化凸优化理论若干算法
凸优化笔记
Convex Optimization 这本书非常有意思，它是线性代数，几何学，集合论，数学分析的综合。第二章 ...
凸优化笔记(1) 引言
凸优化笔记(1) 引言 1. 引言 1.1 数学优化优化问题可以写成如下形式向量称之为优化向量，是目标函数，...
机器学习（6）——凸优化理论(一)
概述凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化...
Convex Optimization Note 1 | Int
凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义...
凸优化有什么用
本文结构：凸优化有什么用？什么是凸优化？凸优化有什么用？鉴于本文中公式比较多，先把凸优化的意义写出来吧，就...
凸优化&非凸优化
凸优化指的是，如果得到了局部最优，那么这个局部最优就是全局最优。讲凸优化就涉及到凸函数和凸集合集合C内任意两点间...
凸优化相关概念学习笔记
前言由于凸优化具有一些很好的性质，比如：凸问题中的局部最优解就是全局最优解凸优化理论中的拉格朗日对偶为凸优化...
《凸优化理论》笔记：前言
简介凸优化理论是非线性规划研究领域的核心成果，也是研究一般非线性规划问题的理论基础。本文...介绍凸优化的一个完...
通俗易懂地理解机器学习理论中的凸优化
写在前头凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化...