凸优化作业-2
问题 1
(a) 证明 $K^\circ$ 是一个闭合的凸锥
证明：
闭合性：设 ${w_k} \subseteq K^\circ$ 是一个收敛序列，且 $w_k \to w$。我们需要证明 $w \in K^\circ$。对于任意 $x \in K$，有：
$$
w_k^T x \leq 0 \quad \text{对于所有 } k.\由于内积是连续的，取极限得：
\w^T x = \lim_{k \to \infty} w_k^T x \leq 0.
$$
因此，$w \in K^\circ$，所以 $K^\circ$ 是闭合的。凸性：设 $w_1, w_2 \in K^\circ$，对于任意 $\lambda \in [0, 1]$，考虑 $w = \lambda w_1 + (1 - \lambda) w_2$。对于任意 $x \in K$，有：
$$
w^T x = \lambda w_1^T x + (1 - \lambda) w_2^T x \leq \lambda \cdot 0 + (1 - \lambda) \cdot 0 = 0.
$$
因此，$w \in K^\circ$，所以 $K^\circ$ 是凸的。锥性：对于任意 $w \in K^\circ$ 和 $\alpha \geq 0$，有：
$$
(\alpha w)^T x = \alpha (w^T x) \leq 0,
$$
因此 $\alpha w \in K^\circ$。
综上所述，$K^\circ$ 是一个闭合的凸锥。
(b) 证明条件等价性
证明：
假设 $z^* = \Pi_K(x)$。根据投影的性质，$z^* \in K$，且 $x - z^* \in K^\circ$，并且 $(x - z^)^T z^ = 0$，因为投影是最小化距离的，且在锥内。
反之，假设 $z^* \in K$，$x - z^* \in K^\circ$，且 $(x - z^)^T z^ = 0$。根据 $x - z^* \in K^\circ$，对于任意 $x \in K$，有：
$$
(x - z^)^T z^ \leq 0.
$$
由于 $(x - z^)^T z^ = 0$，这意味着 $z^*$ 是 $x$ 在 $K$ 上的投影。
因此，$z^* = \Pi_K(x)$ 当且仅当满足上述条件。
(c) 证明 $x = \Pi_K(x) + \Pi_{K^\circ}(x)$
证明：
设 $z^* = \Pi_K(x)$，根据 (b) 的条件，我们有 $x - z^* \in K^\circ$。
由于 $x - z^* \in K^\circ$，我们可以定义 $w^* = \Pi_{K^\circ}(x)$，则有 $x - z^* = w^*$。
因此，结合上述结果，我们得到：
$$
x = z^* + w^* = \Pi_K(x) + \Pi_{K^\circ}(x).
$$
综上所述， $x = \Pi_K(x) + \Pi_{K^\circ}(x)$。
问题 2
需要证明以下三个陈述是等价的：
函数 $f$ 是 $\rho-convex$的，对于某个 $ \rho \in \mathbb{R} $。
函数 $( x \mapsto f(x) + c|x|^2 )$ 是凸的。
对于任意 $( x, y \in \mathbb{R}^n )$，有
$$
f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle - \frac{1}{2}|y-x|^2.
$$
证明：
(1)$\Rightarrow$ (2)：
假设 $f$ 是 $\rho-convex$的。我们考虑函数$g(x) = f(x) + c|x|^2 $，我们需要证明 $g(x)$ 是凸的。
对于任意 $ x, y \in \mathbb{R}^n $ 和 $ \alpha \in (0, 1) $，根据 $\rho - convex$性质，有：
$$
f(\alpha x + (1-\alpha)y) \leq \alpha f(x) + (1-\alpha)f(y) + p\left(\frac{1}{2}\right)|\alpha x + (1-\alpha)y - y|^2.
$$
同时，考虑$ |x - y|^2$的性质，可以得到：
$$
|\alpha x + (1-\alpha)y - y|^2 = |\alpha(x - y)|^2 = \alpha^2 |x - y|^2.
$$
因此：
$$
f(\alpha x + (1-\alpha)y) \leq \alpha f(x) + (1-\alpha)f(y) + \frac{p}{2} \alpha^2 |x - y|^2.
$$
再加上$c|\alpha x + (1-\alpha)y|^2$的项，结合后可以得到 $ g$是凸的。
(2)$\Rightarrow$ (3)：
假设$ g(x) = f(x) + c|x|^2$是凸的。根据凸性的定义，对于任意$x, y \in \mathbb{R}^n$和$alpha \in (0, 1)$，我们有：
$$
g(y) \geq g(x) + \langle \nabla g(x), y - x \rangle.
$$
展开 $ g $ 的定义，得到：
$$
f(y) + c|y|^2 \geq f(x) + c|x|^2 + \langle \nabla f(x) + 2c x, y - x \rangle.
$$
通过适当的变换，可以得到所需的不等式。
(3)$\Rightarrow$ (1)：
假设 (3) 成立。我们需要证明$ f$是 $\rho-convex$的。根据 (3) 的不等式，我们可以得到：
$$
f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle - \frac{1}{2} |y-x|^2.
$$
这正是$\rho-convex$性的定义，因此$f$是的$\rho-convex$。
综上所述，所有三个陈述是等价的。
问题 3
(a) 证明不等式
我们需要证明：
$$
\frac{b-x}{f(a)-f(b)} \leq \frac{f(x)-f(a)}{b-a} \leq \frac{b-x}{b-a}
$$
对于所有$x \in [a, b] $。
左侧不等式：
- 由$ f $的凸性，对于 $ x \in [a, b] $，有：
$$
f(x) \geq f(a) + \frac{f(b) - f(a)}{b-a}(x - a).
$$- 变形得到：
$$
\frac{f(x) - f(a)}{x - a} \geq \frac{f(b) - f(a)}{b - a}.
$$- 结合 $ x $ 的位置，得到左侧不等式。
右侧不等式：
- 由 $ f $ 的凸性，对于 $ x \in [a, b] $，有：
$$
f(x) \leq f(b) + \frac{f(a) - f(b)}{a - b}(x - b).
$$- 变形得到：
$$
\frac{f(x) - f(b)}{x - b} \leq \frac{f(a) - f(b)}{a - b}.
$$- 结合 $ x $ 的位置，得到右侧不等式。
因此，两个不等式都成立。
(b) 证明不等式
我们需要证明：
$$
\frac{f(x)-f(a)}{f(b)-f(a)} \leq \frac{b-x}{b-a} \leq \frac{f(b)-f(x)}{f(b)-f(a)}
$$
对于所有 $ x \in (a, b) $。
左侧不等式：
由 $ f $ 的凸性，对于 $ x \in (a, b) $，有：
$$
f(x) \geq f(a) + \frac{f(b) - f(a)}{b-a}(x - a).
$$
变形得到：
$$
\frac{f(x) - f(a)}{f(b) - f(a)} \leq \frac{x - a}{b - a}.
$$右侧不等式：
由 $ f $ 的凸性，对于 $ x \in (a, b) $，有：
$$
f(x) \leq f(b) + \frac{f(a) - f(b)}{a - b}(x - b).
$$
变形得到：
$$
\frac{f(b) - f(x)}{f(b) - f(a)} \geq \frac{b - x}{b - a}.
$$
因此，两个不等式都成立。
问题 4
假设 $ f: \mathbb{R}^n \rightarrow \mathbb{R} $ 是一个凸函数，且在 $ \mathbb{R}^n $ 上有界上界。我们需要证明 $ f $ 是常数。
证明：
由于 $ f $ 是凸的，任意两个点 $ x, y \in \mathbb{R}^n $ 有：
$$
f(\alpha x + (1 - \alpha)y) \leq \alpha f(x) + (1 - \alpha)f(y) \quad \text{对于所有 } \alpha \in [0, 1].
$$
假设 $ f $ 有上界 $ M $，即 $ f(x) \leq M $ 对于所有 $ x \in \mathbb{R}^n $。
选择任意 $ x_0 \in \mathbb{R}^n $，并取 $ y $ 趋近于 $ x_0 $，由于 $ f $ 的连续性，得到：
$$
f(y) \to f(x_0) \quad \text{当 } y \to x_0.
$$
由于 $ f $ 是凸的，且有界，假设 $ f(x_0) < M $，则存在 $ \epsilon > 0 $ 使得在某个邻域内 $ f(y) $ 也小于 $ M $。
通过选择不同的 $ x $ 和 $ y $，可以得到 $ f $ 在整个域内的值都在 $ [f(x_0), M] $ 之间。
由于 $ f $ 是凸的，且在整个域内有界，最终得到 $ f $ 必须是常数。
因此，得出结论：如果 $ f $ 是凸的并且在 $ \mathbb{R}^n $ 上有界，那么 $ f $ 是常数。
问题5:
判断每个函数是否是凸的。
(a) $f(x) = e^x - 1 \ on\ \mathbb{R} $
解答：
- 一阶导数：
$$
f’(x) = e^x
$$
二阶导数：
由于 $ f’’(x) = e^x > 0 $ 对所有 $ x \in \mathbb{R} $ 恒成立，因此该函数是 凸的*。
(b) $ f(x_1, x_2) = x_1 x_2 $ on $ \mathbb{R}_{++}^2 $
解答：
一阶偏导数：
$$
f_{x_1} = x_2, \quad f_{x_2} = x_1
$$二阶偏导数：
$$
f_{x_1 x_1} = 0, \quad f_{x_1 x_2} = 1, \quad f_{x_2 x_1} = 1, \quad f_{x_2 x_2} = 0
$$
Hessian 矩阵为：
$$
H(f) = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}
$$
由于 Hessian 矩阵的特征值为 $\pm 1$，它并不是半正定的，因此该函数 不是凸的。
(c) $ f(x_1, x_2) = \frac{1}{x_1 x_2} $ on $ \mathbb{R}_{++}^2 $
解答：
一阶偏导数：
$$
f_{x_1} = -\frac{1}{x_1^2 x_2}, \quad f_{x_2} = -\frac{1}{x_1 x_2^2}
$$二阶偏导数：
$$
f_{x_1 x_1} = \frac{2}{x_1^3 x_2}, \quad f_{x_1 x_2} = \frac{1}{x_1^2 x_2^2}, \quad f_{x_2 x_1} = \frac{1}{x_1^2 x_2^2}, \quad f_{x_2 x_2} = \frac{2}{x_1 x_2^3}
$$
Hessian 矩阵为：
$$
H(f) = \begin{pmatrix}
\frac{2}{x_1^3 x_2} & \frac{1}{x_1^2 x_2^2} \
\frac{1}{x_1^2 x_2^2} & \frac{2}{x_1 x_2^3}
\end{pmatrix}
$$
检查 Hessian 矩阵的正定性，经过计算可得该矩阵是正定的，因此函数 $ f(x_1, x_2) = \frac{1}{x_1 x_2} $ 是凸的。
(d) $ f(x_1, x_2) = \frac{x_1}{x_2} $ on $ \mathbb{R}_{++}^2 $
解答：
计算一阶和二阶偏导数：
一阶偏导数：
$$
f_{x_1} = \frac{1}{x_2}, \quad f_{x_2} = -\frac{x_1}{x_2^2}
$$二阶偏导数：
$$
f_{x_1 x_1} = 0, \quad f_{x_1 x_2} = 0, \quad f_{x_2 x_1} = 0, \quad f_{x_2 x_2} = \frac{2x_1}{x_2^3}
$$
Hessian 矩阵为：
$$
H(f) = \begin{pmatrix} 0 & 0 \ 0 & \frac{2x_1}{x_2^3} \end{pmatrix}
$$
Hessian 矩阵的特征值为 $ 0 $ 和 $ \frac{2x_1}{x_2^3} $。对于 $ x_1, x_2 > 0 $，第二个特征值大于零，因此该函数是凸的。
(e) $ f(x_1, x_2) = \frac{x_1^2}{x_2} $ on $ \mathbb{R} \times \mathbb{R}_{++} $
解答：
我们计算一阶和二阶偏导数：
一阶偏导数：
$$
f_{x_1} = \frac{2x_1}{x_2}, \quad f_{x_2} = -\frac{x_1^2}{x_2^2}
$$二阶偏导数：
$$
f_{x_1 x_1} = \frac{2}{x_2}, \quad f_{x_1 x_2} = -\frac{2x_1}{x_2^2}, \quad f_{x_2 x_1} = -\frac{2x_1}{x_2^2}, \quad f_{x_2 x_2} = \frac{2x_1^2}{x_2^3}
$$
Hessian 矩阵为：
$$
H(f) = \begin{pmatrix}
\frac{2}{x_2} & -\frac{2x_1}{x_2^2} \
-\frac{2x_1}{x_2^2} & \frac{2x_1^2}{x_2^3}
\end{pmatrix}
$$
Hessian 矩阵的特征值不完全为正，因此该函数不是凸的。
(f) $ f(x_1, x_2) = x_1^\alpha x_2^{1-\alpha} $ where $ 0 \leq \alpha \leq 1 $ on $ \mathbb{R}_{++}^2 $
解答：
这是一个均匀函数，它是凸函数。
题目6：
要证明函数
$$
f(x) = \left( \sum_{i=1}^{n} x_i^p \right)^{1/p}, \quad \text{定义域为 } \mathbb{R}^+
$$
解答：
a. 齐次性
函数 $$ f(x) $$ 是正齐次函数，即 $$ f(k\mathbf{x}) = kf(\mathbf{x}) $$ 对任意 $$ k > 0 $$ 成立。
b. Minkowski 不等式
对于 $$ p < 1 $$，Minkowski 不等式表明 $$ p $$-范数是凹函数。具体来说，对于任意 $$ \mathbf{x}, \mathbf{y} \in \mathbb{R}^+ $$，有：
$$
\left( \sum_{i=1}^{n} (\lambda x_i + (1-\lambda) y_i)^p \right)^{1/p} \geq \lambda \left( \sum_{i=1}^{n} x_i^p \right)^{1/p} + (1-\lambda) \left( \sum_{i=1}^{n} y_i^p \right)^{1/p}.
$$
该不等式成立是因为 $$ p < 1 $$ 导致函数具有次可加性。
c. 二阶导数验证（可选）
虽然对于该多元函数，直接计算二阶导数较为复杂，但通过上述不等式分析已可证明凹性。
由于 $$ p < 1 $$，函数
$$
f(x) = \left( \sum_{i=1}^{n} x_i^p \right)^{1/p}
$$
满足凹性定义，其次可加性确保其是一个凹函数。