凸优化作业-2

凸优化作业-2

问题 1

(a) 证明 $K^\circ$ 是一个闭合的凸锥

证明：

1. 闭合性：设 $\{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$ 是闭合的。

2. 凸性：设 $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$ 是凸的。

3. 锥性：对于任意 $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) 证明条件等价性

证明：

1. 假设 $z^* = \Pi_K(x)$。根据投影的性质，$z^* \in K$，且 $x - z^* \in K^\circ$，并且 $(x - z^*)^T z^* = 0$，因为投影是最小化距离的，且在锥内。

2. 反之，假设 $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)$

证明：

1. 设 $z^* = \Pi_K(x)$，根据 (b) 的条件，我们有 $x - z^* \in K^\circ$。

2. 由于 $x - z^* \in K^\circ$，我们可以定义 $w^* = \Pi_{K^\circ}(x)$，则有 $x - z^* = w^*$。

3. 因此，结合上述结果，我们得到：

   $$x = z^* + w^* = \Pi_K(x) + \Pi_{K^\circ}(x).$$

综上所述， $x = \Pi_K(x) + \Pi_{K^\circ}(x)$。

---

问题 2

需要证明以下三个陈述是等价的：

1. 函数 $f$ 是 $\rho-convex$的，对于某个 $\rho \in \mathbb{R}$。

2. 函数 $( x \mapsto f(x) + c\|x\|^2 )$ 是凸的。

3. 对于任意 $( 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]$。

1. 左侧不等式：

   • 由$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$ 的位置，得到左侧不等式。

2. 右侧不等式：

   • 由 $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)$。

1. 左侧不等式：

   由 $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}.$$

2. 右侧不等式：

   由 $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}$

解答：

1. 一阶导数：

$$f'(x) = e^x$$

1. 二阶导数：

   由于 $f''(x) = e^x > 0$ 对所有 $x \in \mathbb{R}$ 恒成立，因此该函数是 凸的*。

(b) $f(x_1, x_2) = x_1 x_2$ on $\mathbb{R}_{++}^2$

解答：

1. 一阶偏导数：

   $$f_{x_1} = x_2, \quad f_{x_2} = x_1$$

2. 二阶偏导数：

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

解答：

1. 一阶偏导数：

   $$f_{x_1} = -\frac{1}{x_1^2 x_2}, \quad f_{x_2} = -\frac{1}{x_1 x_2^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$

解答：

计算一阶和二阶偏导数：

1. 一阶偏导数：

   $$f_{x_1} = \frac{1}{x_2}, \quad f_{x_2} = -\frac{x_1}{x_2^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}_{++}$

解答：

我们计算一阶和二阶偏导数：

1. 一阶偏导数：

   $$f_{x_1} = \frac{2x_1}{x_2}, \quad f_{x_2} = -\frac{x_1^2}{x_2^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}$$

满足凹性定义，其次可加性确保其是一个凹函数。