凸优化习题一

令 $C_1, C_2$ 为包含原点的两个凸锥集合，证明：
$C_1 + C_2 = \operatorname{conv}(C_1 \cup C_2).$

注释： $\operatorname{conv}(C)$ 表示集合 $C$ 的凸包 $(convex\ hull)$

证明：可以通过双包含关系来证明：

对于 $\forall x\in C_1+C_2$ , $x=x_1+x_2$ 其中 $x_1\in C_1,x_2 \in C_2$ 稍作变换 $x=x_1+x_2=\frac{1}{2}（2x_1）+\frac{1}{2}(2x_2)$ 由于 $C_1$ 和 $C_2$ 是包含原点的两个凸锥集合，所以 $2x_1\in C_1,2x_2\in C_2$
这样就把 $x$ 写成了 $C_1$ 和 $C_2$ 中元素凸组合的形式，所以 $C_1+C_2 \subset \operatorname{conv}(C_1\cup C_2)$
对于 $\forall x \in\operatorname{conv}(C_1\cup C_2)$ ，根据凸包的性质， $x$ 一定可以写成
$x = \alpha x_1+(1-\alpha)x_2,x_1\in C_1,x_2 \in C_2$ 又因为 $C_1$ 和 $C_2$ 都是凸锥，所以 $\alpha x_1 \in C_1,(1-\alpha)x_2\in C_2$
从而 $x\in C_1 + C_2$ , $\operatorname{conv}(C_1\cup C_2) \subset C_1+C_2$

令 $C$ 为非空凸集，且 $\operatorname{conv}(C)$ 包含原点，证明：
$\operatorname{aff}(\operatorname{cone}(C)) = \operatorname{aff}(\operatorname{conv}(C)).$

注释:如果C是一个凸集，显然有 $\operatorname{conv}(C)=C$
根据注释，问题等价于 $\operatorname{aff}(\operatorname{cone}(C)) = \operatorname{aff}(C).$
显然 $C\subset \operatorname{cone}(C)$ 于是 $\operatorname{aff}(C) \subset \operatorname{aff}(\operatorname{cone}(C))$
接下来证明另一侧的包含关系
对于 $\forall y\in\operatorname{cone}(C)$ ,我们可以把 $y$ 写成 $y=\Sigma_{i=1}^n\lambda_i x_i,\lambda_i>0,x_i\in C$ 记 $\lambda = \Sigma_i^n\lambda_i$ , $y=\lambda\Sigma_{i=1}^n\frac{\lambda_i}{\lambda} x_i$ 而 $x=\Sigma_{i=1}^n\frac{\lambda_i}{\lambda} x_i$ 是 $C$ 中元素的一个凸组合。
对于包含原点的凸集 $C$ , $x\in C$ ，有 $\lambda x =\lambda x + (1-\lambda)0\in \operatorname{aff}(C)$
综上可知命题成立。

令 $C$ 为非空凸集，证明：
$\operatorname{cone}(C) = \operatorname{aff}(C) \text{ 当且仅当 } 0 \in \operatorname{ri}(C).$

注释：设集合 $C \in R^n$ 是非空凸集合，则相对内部定义
若 $x\in C$ 且存在一个以 $x$ 为球心的开球 $B(x,\epsilon)$ 满足 $B\cap \operatorname{aff}(C) \subset C$ ,则称 $x$ 为 $C$ 的相对内部点， $C$ 中相对内部点的全体称为相对内部。
当 $0 \in \operatorname{ri}(C)$ ,我们来证明 $\operatorname{cone}(C) = \operatorname{aff}(C)$
任取 $x\in \operatorname{cone}(C)$
$x=\Sigma_{i=1}^n\lambda_i x_i=\lambda \Sigma_{i=1}^n\frac{\lambda_i}{\lambda} x_i,\text{其中} \lambda = \Sigma_{i=1}^n \lambda_i$ 因为 $0\in \operatorname{ri}(C)$ ,和第二题有相似的结论，我们得到 $x \in \operatorname{aff}(C)$ .
另一面，任取 $y\in \operatorname{aff}(C)$ ,必有 $kx\in C$ ,所以 $x\in C \subset cone(C)$
反过来讲，我们假设 $\operatorname{cone}(C) = \operatorname{aff}(C)$
那么对于 $C$ 中所有元素的线性组合 $x=\Sigma_i^nk_ix_i$ ,我们记 $k = \Sigma_{i=1}^nk_i$ 在 $k\neq 0$ 的情况下， $x = k \Sigma_i^n\frac{k_i}{k}x_i$
其中 $\Sigma_i^n\frac{k_i}{k}x_i\in \operatorname{aff}(C)=\operatorname{cone}(C)$
所以 $x=k\Sigma_i^n\frac{k_i}{k}x_i\in \operatorname{aff}(C)=\operatorname{cone}(C)$
所以 $-x\in \operatorname{aff}(C)$ $0\in \operatorname{aff}(C)$

令 $C_1, C_2$ 为 $\mathbb{R}^n$ 中两个非空凸子集且 $C_2$ 为锥集合，若存在一个超平面将 $C_1$ 与 $C_2$ 正常分离，则存在经过原点的超平面正常分离 $C_1$ 与 $C_2$ 。

假设存在超平面 $H= \{ x| a^Tx=b\}$ ，
满足 $a^Tx_1 \geq b\geq a^Tx_2$ 对任意 $x_1\in C_1,x_2\in C_2$ 恒成立
我们在上面的式子中令 $x_2$ 趋于 $0$ ，(因为 $C_2$ 是一个锥集合，所以这一点总是可以做到的),可以得到 $b\geq 0$ 。
我们知道， $C_2$ 是一个锥集合，因此 $\lambda x_2 \in C_2,\lambda >0$
所以 $a^Tx_2 < b \Rightarrow a^T\lambda x_2<b\Rightarrow a^T x_2 <\frac{b}{\lambda}$ 在上式中令 $\lambda$ 趋于正无穷，可以得到 $a^Tx_2\leq 0$ 进而 $a^Tx_2\leq 0<b<a^Tx_1$
这样就找到了一个经过原点的超平面分离了两个凸集。

令 $f : R \to R$ 为凸函数，若 $x_1 < x_2 < x_3$ ，证明：
$\frac{f(x_2) - f(x_1)}{x_2 - x_1} \leq \frac{f(x_3) - f(x_2)}{x_3 - x_2}.$

注意：该题目不可以构造函数求导，因为题目中并没有说明 $f(x)$ 的可微性。
因为 $x_2 = \frac{x_3-x_2}{x_3-x_1}x_1 +\frac{x_2-x_1}{x_3-x_1}x_3$ 根据凸函数的性质
$f(x_2)\leq \frac{x_3-x_2}{x_3-x_1}f(x_1) +\frac{x_2-x_1}{x_3-x_1}f(x_3)$ 简单运算即可知道上面的式子和题目中是等价的。
当然这里只是我们的做法，实际中的思路是分析法：要证，只需证这样的办法得到的。

令 $f : R \to R$ 为可微函数，证明 $f$ 在非空凸集 $C$ 上为凸的当且仅当：
$(\nabla f(x) - \nabla f(y))^T (x - y) \geq 0.$

必要性：如果 $f$ 在 $C$ 上为凸的，则 $(\nabla f(x) - \nabla f(y))^T (x - y) \geq 0$
定义：假设 $f$ 在非空凸集 $C$ 上为凸的，则对于任意 $x, y \in C$ 和 $\lambda \in [0, 1]$ ，有：
$f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y).$
选择点：选择 $\lambda = t$ 其中 $t \in (0, 1)$ ，定义：
$z_t = t x + (1 - t) y.$
应用泰勒展开：利用可微性，对 $f(z_t)$ 进行一阶泰勒展开：
$f(z_t) = f(y) + \nabla f(y)^T (z_t - y) + o(\|z_t - y\|).$
计算 $z_t - y$ ：
$z_t - y = t (x - y).$
因此：
$f(z_t) = f(y) + t \nabla f(y)^T (x - y) + o(t \|x - y\|).$
代入凸性条件：
由于 $f$ 的凸性，我们有：
$f(z_t) \leq t f(x) + (1 - t) f(y).$
结合不等式：
代入得到：
$f(y) + t \nabla f(y)^T (x - y) + o(t \|x - y\|) \leq t f(x) + (1 - t) f(y).$ 化简后得到：
$t \nabla f(y)^T (x - y) + o(t \|x - y\|) \leq t (f(x) - f(y)).$
取极限：
当 $t \to 0$ 时， $o(t \|x - y\|) \to 0$ ，我们得到：
$\nabla f(y)^T (x - y) \leq f(x) - f(y).$
交换 $x$ 和 $y$ ：
同理，对于 $y, x$ 可得：
$\nabla f(x)^T (y - x) \leq f(y) - f(x).$ 结合这两式，我们有：
$(\nabla f(x) - \nabla f(y))^T (x - y) \geq 0.$
充分性：如果 $(\nabla f(x) - \nabla f(y))^T (x - y) \geq 0$ ，则 $f$ 在 $C$ 上为凸的
假设 $(\nabla f(x) - \nabla f(y))^T (x - y) \geq 0$ 对于所有 $x, y \in C$ 。
考虑任意 $x, y \in C$ 和 $\lambda \in [0, 1]$ ，定义：
$z_t = \lambda x + (1 - \lambda) y.$
利用一阶泰勒展开：对于 $z_t$ ，进行一阶泰勒展开：
$f(z_t) = f(y) + \nabla f(y)^T (z_t - y) + o(\|z_t - y\|).$
计算 $z_t - y$ ：
$z_t - y = \lambda (x - y).$ 所以：
$f(z_t) = f(y) + \lambda \nabla f(y)^T (x - y) + o(\lambda \|x - y\|).$
结合不等式：
根据假设：
$\nabla f(y)^T (x - y) \leq f(x) - f(y).$ 所以有：
$f(z_t) \leq f(y) + \lambda (f(x) - f(y)) + o(\lambda \|x - y\|).$
化简：
$f(z_t) \leq (1 - \lambda) f(y) + \lambda f(x).$
得出结论：因此， $f$ 满足：
$f(z_t) \leq \lambda f(x) + (1 - \lambda) f(y),$ 这表明 $f$ 在 $C$ 上为凸的。

利用凸函数二阶条件证明：
$f(x) = \ln(\exp x_1 + \exp x_2 + \cdots + \exp x_n)$ 为凸函数。

注释：凸函数的二阶条件通常涉及到函数的二阶导数（或 Hessian 矩阵），用于判断函数的凸性。以下是一些常见的二阶条件：
一维情况
对于一个一维函数 $f: \mathbb{R} \to \mathbb{R}$ ，如果 $f$ 在某个区间内二次可导，则 $f$ 是凸的当且仅当 $f''(x) \geq 0$ 对于该区间内的所有 $x$ 成立。
多维情况
对于一个多维函数 $f: \mathbb{R}^n \to \mathbb{R}$ ，如果 ( f ) 是二次可导的，则： $f$ 是凸的当且仅当其 $Hessian$ 矩阵 $H(x) = \nabla^2 f(x)$ 在该区间内对所有 $x$ 是半正定的（即对于任意的非零向量 $v \in \mathbb{R}^n$ ，有 $v^T H(x) v \geq 0$ ）。
为了证明函数
$f(x) = \ln(\exp x_1 + \exp x_2 + \cdots + \exp x_n)$ 是凸函数，我们将使用二阶条件，即计算其 Hessian 矩阵并检查其是否为半正定。
首先，计算函数的梯度：
$\nabla f(x) = \frac{1}{g(x)} \nabla g(x),$ 其中 $g(x) = \exp x_1 + \exp x_2 + \cdots + \exp x_n$ ，并且
$\nabla g(x) = \begin{pmatrix} \exp x_1 \\ \exp x_2 \\ \vdots \\ \exp x_n \end{pmatrix}.$ 因此， $\nabla f(x) = \frac{1}{\exp x_1 + \exp x_2 + \cdots + \exp x_n} \begin{pmatrix} \exp x_1 \\ \exp x_2 \\ \vdots \\ \exp x_n \end{pmatrix}.$
计算二阶导数（ $Hessian$ 矩阵）

我们现在计算 $Hessian$ 矩阵 $H(x) = \nabla^2 f(x)$ 。

根据公式， $Hessian$ 矩阵的元素为：
$H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}.$

利用链式法则，对 $\nabla f(x)$ 求导：
$H_{ij} = \frac{\partial}{\partial x_j} \left( \frac{\exp x_i}{g(x)} \right).$

使用商法则，得到：
$H_{ij} = \frac{g(x) \cdot \frac{\partial}{\partial x_j}(\exp x_i) - \exp x_i \cdot \frac{\partial}{\partial x_j}(g(x))}{g(x)^2}.$

$\frac{\partial}{\partial x_j}(g(x)) = \exp x_j.$

在计算二阶偏导数的时候，我们需要考虑 $i=j$ 和 $i \neq j$ 两种情况：

当 $i = j$ ：
$H_{ii} = \frac{g(x) \cdot \exp x_i - \exp x_i \cdot \exp x_i}{g(x)^2} = \frac{\exp x_i (g(x) - \exp x_i)}{g(x)^2}.$
当 $i \neq j$ ：
$H_{ij} = \frac{g(x) \cdot 0 - \exp x_i \cdot \exp x_j}{g(x)^2} = -\frac{\exp x_i \exp x_j}{g(x)^2}.$

最终 $Hessian$ 矩阵 $H(x)$ 可以写成：
$H(x) = \frac{1}{g(x)^2} \left( \text{diag}(g(x) - \exp x_1, g(x) - \exp x_2, \ldots, g(x) - \exp x_n) - \begin{pmatrix} \exp x_1 & \cdots & \exp x_1 \\ \vdots & \ddots & \vdots \\ \exp x_n & \cdots & \exp x_n \end{pmatrix} \right).$
检查 Hessian 矩阵的半正定性

对角元素 $H_{ii}$ ：
$H_{ii} = \frac{\exp x_i (g(x) - \exp x_i)}{g(x)^2}.$ 因为 $g(x) = \exp x_1 + \exp x_2 + \cdots + \exp x_n > \exp x_i$ ，所以 $g(x) - \exp x_i > 0$ ，因此 $H_{ii} > 0$ 。
非对角元素 $H_{ij}$ （当 $i \neq j$ ）：
$H_{ij} = -\frac{\exp x_i \exp x_j}{g(x)^2} < 0.$

由于 $Hessian$ 矩阵的对角线元素都是正的，且其非对角线元素是负的，结合我们对 $Hessian$ 矩阵的结构，可以证明 $Hessian$ 矩阵是半正定的，因此函数 $f(x)$ 是一个凸函数。

令 $C$ 为 $\mathbb{R}^n$ 中的非空锥集合，证明： $L_{C_*} = (\operatorname{aff}(C))^\perp$ 。
我们先解释题目中用到的符号和背景，接下来用双包含关系来证明集合的等价性

锥集合 $C$ ：设 $C \subset \mathbb{R}^n$ 是一个非空的锥集合，这意味着对于任意 $x \in C$ 和任意 $\lambda \geq 0$ ，都有 $\lambda x \in C$ 。
对偶锥 $C_*$ ：对 $C$ 的对偶锥 $C_*$ 定义为
$C_* = \{ y \in \mathbb{R}^n \mid \langle x, y \rangle \geq 0, \forall x \in C \}.$
由此可以看到，一些锥集合比如 $R^3$ 中的 $R^2$ 平面，它作为一个锥，但是它的对偶锥集合仅含有原点。甚至有可能有的锥的对偶锥集合为空集。
仿射包 $\operatorname{aff}(C)$ ：集合 $C$ 的仿射包是所有形式为 $x_0 + \text{span}(C)$ 的点，其中 $x_0 \in C$ 。
正交补 $(\operatorname{aff}(C))^\perp$ ：表示与 $\operatorname{aff}(C)$ 中的每个向量都正交的向量组成的集合。

方向一: 证明 $L_{C_*} \subseteq (\operatorname{aff}(C))^\perp$

假设 $y \in L_{C_*}$ ，则由定义， $y \in L_{C_*}$ 意味着
$\langle x, y \rangle \geq 0, \quad \forall x \in C.$
我们需要证明 $y \in (\operatorname{aff}(C))^\perp$ ，即对于任意 $z \in \operatorname{aff}(C)$ ，有
$\langle z, y \rangle = 0.$

任取 $z \in \operatorname{aff}(C)$ ，则 $z$ 可以表示为 $z = x_0 + \lambda_1 v_1 + \lambda_2 v_2 + \cdots + \lambda_k v_k$ ，其中 $x_0 \in C$ 且 $v_1, v_2, \dots, v_k$ 属于 $\text{span}(C)$ 。
由于 $y \in L_{C_*}$ ，并且对于所有 $x \in C$ ，有 $\langle x, y \rangle \geq 0$ ，可以推导出对于所有 $z \in \operatorname{aff}(C)$ ，
$\langle z, y \rangle = \langle x_0 + \sum_{i=1}^k \lambda_i v_i, y \rangle = \langle x_0, y \rangle + \sum_{i=1}^k \lambda_i \langle v_i, y \rangle.$
由于 $v_1, v_2, \dots, v_k \in \text{span}(C)$ 且 $\langle v_i, y \rangle = 0$ ，我们可以得出
$\langle z, y \rangle = \langle x_0, y \rangle.$
由于 $x_0 \in C$ 并且 $y \in L_{C_*}$ ，有 $\langle x_0, y \rangle \geq 0$ 。再考虑 $\operatorname{aff}(C)$ 中的任意点，它实际上包含了所有的 $x_0 + \lambda_1 v_1 + \lambda_2 v_2 + \cdots$ ，从而得出 $\langle z, y \rangle = 0$ 。

因此， $y \in (\operatorname{aff}(C))^\perp$ ，并且 $L_{C_*} \subseteq (\operatorname{aff}(C))^\perp$ 。

方向二: 证明 $(\operatorname{aff}(C))^\perp \subseteq L_{C_*}$

现在假设 $y \in (\operatorname{aff}(C))^\perp$ ，则由定义，对于所有 $z \in \operatorname{aff}(C)$ ，都有
$\langle z, y \rangle = 0.$
我们需要证明 $y \in L_{C_*}$ ，即对于所有 $x \in C$ ，有
$\langle x, y \rangle \geq 0.$

任取 $x \in C$ ，由于 $y \in (\operatorname{aff}(C))^\perp$ ，意味着 $y$ 与 $\operatorname{aff}(C)$ 中的所有向量都正交。
注意到 $C \subseteq \operatorname{aff}(C)$ ，所以对于任意 $x \in C$ ，有 $\langle x, y \rangle = 0$ 。

因此， $y \in L_{C_*}$ ，从而 $(\operatorname{aff}(C))^\perp \subseteq L_{C_*}$ 。

凸优化习题一

凸优化习题一

相关阅读更多精彩内容

友情链接更多精彩内容