非线性最优化基础

第1章 最优化问题简介

  最优化问题记为

$$\begin{align} min\ & f(x)\\ s.t.\ & g_i(x) \leqslant 0,\ i = 1, \cdots, m\\ & h_i(x) = 0,\ j = 1, \cdots, m \end{align}$$

  满足约束条件的向量$x$称为可行解(feasible solution)，全体可行解构成的集合称为可行域(feasible region). 此外，函数$g_i\ (i = 1, \dots, m)$与$h_j\ (j = 1, \dots, l)$称为约束函数(constraint function)，而可行域中使得目标函数值为最小的向量$x$称为问题的最优解(optimal solution).

第2章 凸分析

2.1 向量与矩阵

  $R^n$为全体$n$维实向量构成的集合(即$n$维欧氏空间).$R^1$代表全体实数的集合.

  内积(inner product) $\langle x, y\rangle = x^Ty$.

  范数(norm) $\Vert x\Vert = \sqrt{\langle x, x\rangle}$.

  空间$R^n$中两点$x$与$y$之间的距离为$\Vert x - y\Vert$.

  对任意向量$x, y \in R^n$均有如下Cauchy-Schwarz不等式(Cauchy-Schwarz inequality)成立:

$$-\Vert x\Vert\ \Vert y\Vert \leqslant \langle x, y\rangle \leqslant \Vert x\Vert\ \Vert y\Vert$$

  另外，两个非零向量$x$与$y$的夹角$\theta$可由下式定义:

$$cos\theta = \frac{\langle x, y\rangle}{\Vert x\Vert\ \Vert y\Vert}$$

  二维空间中的任意直线以及三维空间中的任意平面或直线虽大都不是线性子空间，但这些集合都包含由其中任意两点所确定的直线，将这样的集合称为仿射集(affine set). 仿射集可以看成是某个线性子空间的平移，故必存在向量$x^0, x^1, \cdots, x^k \in R^n$，使得仿射集可表示为

$$\{x \in R^n | x = x^0 + \alpha_1x^1 + \cdots + \alpha_kx^k, \alpha_1 \in R, \cdots, \alpha_k \in R\}$$

  给定向量$a \in R^n(a \neq 0)$及常数$\alpha \in R$，考虑集合

$$H = \{x \in R^n | \langle a, x\rangle = \alpha \}$$

这是由与向量$a$正交的向量全体构成的$n - 1$维线性子空间$\{x \in R^n | \langle a, x\rangle = \alpha \}$经适当平移而得到的仿射集，称之为$R^n$的超平面(hyperplane). 二维空间中的任意直线和三维空间中的任意平面均为超平面. 超平面$H$具有将空间$R^n$一分为二的重要性质.

  给定集合$S \subseteq R^n$与$T \subseteq R^n$，二者的合集定义为

$$S + T = \{z \in R^n | z = x + y, x \in S, y \in T\}$$

注意不要与并集$S \cup T$混淆. 对$\alpha \in R$，集合$S \subseteq R^n$的数乘$\alpha S$定义为

$$\alpha S = \{z \in R^n | z = \alpha x, x \in S\}$$

此外，对给定的集合$X \subseteq R^m$与$Y \subseteq R^n$，集合

$$X \times Y = \{(x, y) \in R^{m + n} | x \in X, y \in Y\}$$

称为$X$与$Y$的笛卡尔积(Cartesian product).

---

  矩阵$A \in R^{m \times n}$与向量$x \in R^n$的积$Ax$是$m$维向量，并且对任意$x, y \in R^n$及实数$\alpha, \beta \in R$均有$A(\alpha x + \beta y) = \alpha Ax + \beta Ay$成立，因此，矩阵$A$也可看成由空间$R^n$到空间$R^m$的线性映射(linear mapping). 给定集合$S \subseteq R^n$，映射$A: R^n \rightarrow R^m$的像(image)定义为

$$AS = \{z \in R^m | z = Ax, x \in S\} \subseteq R^m$$

特别地，若$S$为线性子空间，则$AS$也是线性子空间.

  单位矩阵(unit matrix) $I$.

  给定$n$阶方阵$A$，若存在$n$解方阵$B$满足$AB = BA = I$，则成$A$非奇异(nonsingular). 上述矩阵$B$(如果存在)必定唯一，称为$A$的逆矩阵(inverse matrix)，记为$A^{-1}$.

  将正整数集合$\{1, 2, \cdots, n\}$重新排列成$\{i_1, i_2, \cdots, i_n\}$的运算称为置换(permutation)，记为

$$\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ i_1 & i_2 & \cdots & i_n \end{pmatrix}$$

对集合$\{1, 2, \cdots, n\}$的置换总数为$n!$. 特别地，在集合$\{1, 2, \cdots, n\}$中只互换两个元素的置换称为对换(transposition). 每个置换均可通过若干次对换来实现，其中能够经过偶数次对换实现的置换称为偶置换; 反之，则称为奇置换. 规定置换$\sigma$的符号$sgn(\sigma)$如下: 当$\sigma$是偶置换时，其值为1; 当$\sigma$是奇置换时，其值为-1.

  $A$的行列式(determinant) $|A|$.

  $det\ AB = det\ A\ det\ B$.

  $det\ I = 1$，故$det\ A\ det\ A^{-1} = det\ AA^{-1} = 1$. 易知$n$阶方阵$A$非奇异的充要条件时$det\ A \neq 0$.

  给定$n$阶方阵$A$，以$tr\ A$表示其对角线元素之和$a_{11} + a_{22} + \cdots + a_{nn}$，称为$A$的迹(trace). 对任意给定的矩阵$B \in R^{m \times n}$及$C \in R^{m \times n}$有$tr\ BC = tr\ CB$成立.

  当系数矩阵$A \in R^{n \times n}$非奇异时，线性方程组$Ax = b$的解为$x = A^{-1}b$，并且其分量可表示为$x_i = det\ [A|b|i] / det\ A\ (i = 1, \cdots, n)$，其中$[A|b|i]$表示$A$的第$i$列用向量$b$替换后所得的矩阵. 这个结果称为Cramer法则(Cramer’s rule).

  引理 2.1 给定方阵$A, B \in R^{n \times n}$，并设$A$非奇异，则有下式成立:

$$tr[A^{-1}B] = \sum\limits_{i = 1}^{n}\frac{det\ [A|B^{[i]}|i]}{det\ A}$$

其中$B^{[i]}$表示$B$的第$i$个列向量.

  证明 由Cramer法则知，$det\ [A|B^{[i]}|i] / det\ A$表示向量$A^{-1}B^{[i]}$的第$i$个坐标，而这正是矩阵$A^{-1}B$的第$(i, i)$个元素.

  给定$n$阶方阵$A$，使得

$$Ax = \lambda x$$

存在非零解$x$的数$\lambda$称为$A$的特征值(eigenvalue)，并称其非零解$x$为对应该特征值的特征向量(eigenvector). 矩阵$A$的特征值是如下特征方程(characteristic equation)的根:

$$det(\lambda I - A) = 0$$

由于该方程的左侧是关于$\lambda$的$n$次多项式，故特征方程的根，即矩阵$A$的特征值，共有$n$个(重根按其重数计算). 若将这些根分别记为$\lambda_1, \cdots, \lambda_n$，则根据特征方程的根与系数关系有

$$\lambda_1 + \lambda_2 + \cdots + \lambda_n = tr\ A, \quad \lambda_1\lambda_2\cdots\lambda_n = det\ A$$

  $n \times n$阶矩阵$Q$为正交矩阵(orthogonal matrix)，$QQ^T = Q^TQ = I$.

  若$n$阶(实)对称矩阵$A \in S^n$满足

$$\langle x, Ax\rangle \geqslant 0, x \in R^n$$

则称$A$半正定(positive semidefinite)，记为$A \succeq O$. 进一步，若

$$\langle x, Ax\rangle \gt 0, x \in R^n, x \neq 0$$

则称$A$正定(positive definite)，记为$A \succ O$. $A \in S^n$为半正定(正定)的充要条件是$A$的所有特征值均为非负(正)，故半正定(正定)矩阵的迹与行列式均为非负(正).

2.2 开集、闭集与极限

  开集(open set)可理解为一个不包含边界的球，球内每一个点都有一个以该点为中心的邻域(neighborhood)包含于球内，球内的点与边界的并集是闭集(closed set).

  内点(interior point).

  内部(interior).

  包含$S$的最小闭集称为$S$的闭包(closure).

  属于$cl\ S$但不属于$int\ S$的点的全体构成的集合称为$S$的边界(boundary)，记为$bd\ S$.

  包含$S$的最小的仿射集称为仿射包(affine hull)，记为$aff\ S$.

  设$x \in S$，若存在$x$的某邻域$U$，使得$U \cap aff\ S \subseteq S$，则称$x$为$S$的相对内点(relatively interior point)，$S$的所有相对内点的集合称为$S$的相对内部(relative interior)，记为$ri\ S$.

  若$aff\ S = R^n$，则有$ri\ S = int\ S$.

  若集合$S \subseteq R^n$内的任意点列$\{x^k\}$的聚点均属于$S$，则$S$是闭集，$S$中所有收敛点列的极限构成的集合即为$S$的闭包.

  称有界闭集为紧集(compact set).

2.3 凸集

  若集合$S \subseteq R^n$中任意两点的连线仍包含于$S$，即成立

$$x \in S, y \in S, \alpha \in [0, 1] \Rightarrow (1 - \alpha)x + \alpha y \in S$$

则称$S$为凸集(convex set).

  任意两个(闭)凸集的交集仍是(闭)凸集.

  对任意集合$S \subseteq R^n$，包含$S$的最小凸集称为$S$的凸包(convex hull)，记为$co\ S$.

  凸组合(convex combination). 引理 2.2 p11.

  定理 2.2 任意集合$S \subseteq R^n$的凸包$co\ S$等同于由$S$中至多$n + 1$个点的凸组合的全体构成的集合(Carathéodory‘s theorem).

  连通集(connect set).

  定理 2.3 有界闭集$S \subseteq R^n$的凸包$co\ S$是闭集.

  引理 2.3 对任意凸集$S \subseteq R^n$均有

$$x \in ri\ S, y \in cl\ S, \lambda \in [0, 1) \Rightarrow (1 - \lambda)x - \lambda y \in ri\ S$$

  引理 2.4 设$S \subseteq R^n$为非空凸集，则$z \in ri\ S$的充要条件是对任意$x \in S$，均存在$\mu > 1$，使得$(1 - \mu)x + \mu z \in S$.

  定理 2.4 对任意凸集$S \subseteq R^n$均有$cl\ ri\ S = cl\ S$及$ri\ cl\ S = ri\ S$成立. 此外，给定两个凸集$S, T \subseteq R^n$，则$cl\ S = cl\ T$当且仅当$ri\ S = ri\ T$.

  定理 2.5 对任意凸集$S \subseteq R^n$与线性映射$A : R^n \rightarrow R^m$，$AS$必为凸集，并且总有$cl\ AS \supseteq Acl\ S$及$ri\ AS = Ari\ S$成立. 进一步，给定两个凸集$S, T \subseteq R^n$，则有$cl\ (S + T) \supseteq cl\ S + cl\ T$与$ri\ (S + T) = ri\ S + ri\ T$成立.

  凸多面体(convex polytope).

  凸多面体$S$中的$m$个向量$x^1 - x^0, \cdots, x^m - x^0$是线性无关的，则称$S$为m维单纯形(m-simplex)，对应的$m + 1$个点$x^0, x^1, \cdots, x^m$称为$S$的顶点(vertex).

  凸多面集(polyhedral convex set).

2.4 分离定理

2.5 锥与极锥

2.6 函数的连续性与可微性