lec3:

二阶条件

范数

极大值函数（无法用二阶条件分析）

$$f(x) = \max \{ x_1, \dots, x_n \}$$ $$\forall x, y \in R^n, \forall \theta \in [0, 1] \\ f(\theta x + (1 - \theta)y) = \max\{ \theta x_1 + (1 - \theta)y_1, \dots, \theta x_n + (1 - \theta)y_n\} \\ \le \theta \max\{ x_i\} + (1 - \theta)\max\{y_i\}\\ \theta f(x) + (1 - \theta)f(y) = \theta \max\{x_i\} + (1 - \theta)\max\{y_i\}$$

解析近似：构造函数，无穷阶可微

logsumexp

$$f(x) = \log (e^{x_1} + \dots + e^{x_n})$$ $$\max\{x_i\} \longleftrightarrow \log(\sum e^{x_i}) \\ e^{\max \{x_i\}} \le \sum e^{x_i} \le ne^{\max\{x_i\}} \\ \max \{x_i\} \le \log(\sum e^{x_i}) \le \log n + \max\{x_i\}$$

证明凸性：

$$\frac{\partial f}{\partial x_i} = \frac{1}{\sum e^{x_i}}e^{x_i} \\ \frac{\partial ^ 2 f}{\partial x_i\partial y_i} = -(\sum e^{x_i})^{-2}e^{x_j}e^{x_i} \quad (i\neq j) \\ \frac{\partial^2 f}{\partial x_i\partial x_i} = -(\sum e^{x_i})^{-2}e^{x_i}e^{x_i} + (\sum e^{x_i})^{-1}e^{x_i}\\ =(\sum e^{x_i})^{-2}[-e^{x_ix_i} + (\sum e^{x_i})e^{x_i}] \\ = (\sum e^{x_i})^{-2} \begin{pmatrix} -e^{x_1}e^(x_1) + (\sum e^{x_i})e^{x_1}, \dots, -e^{x_1}e^{x_n}\\ -e^{x_1}e^{x_n}m, \dots, -e^{x_n}e^{x_n} + (\sum e^{x_i})e^{x_n} \end{pmatrix} \\ H = (1^T z){\rm Diag} z - zz^T \\ \forall v \in R^n, v^THv = (1^tz)v^T{\rm Diag}(z) v - v^T zz^Tv \\ = (\sum z_i)(\sum z_iv_i^2) - (\sum z_iv_i)^2\\ a_i = \sqrt z_i v_i, b_i = \sqrt z_i \\ v^THv = (b^Tb)(a^Ta) - (a^Tb)^2 \ge 0$$