凸优化习题一

令 $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_*}$ 。

最后编辑于：2024.12.18 18:55:12

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,402评论 6赞 499
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,377评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,483评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,165评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,176评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,146评论 1赞 297
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,032评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,896评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,311评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,536评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,696评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,413评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,008评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,659评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,815评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,698评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,592评论 2赞 353

凸优化习题一

推荐阅读更多精彩内容