最优化理论-最优化1
3. 非线性规划
3.1 非线性规划的数学模型
定义 3.1.1:极值点的定义
设 ( f(x) ) 是定义在开集 ( S \subseteq \mathbb{R}^n ) 上的可微函数。若在点 ( x^* ) 处:
[
f(x^) \leq f(x), \quad \forall x \in N(x^)
]
其中 ( N(x^) ) 是点 ( x^ ) 的某个邻域,则称 ( x^* ) 为 ( f(x) ) 的局部极小值点。若满足:
[
f(x^) \geq f(x), \quad \forall x \in N(x^)
]
则称 ( x^* ) 为局部极大值点。
解释与几何意义:
极值点的定义指出,在该点附近的所有位置,函数值都不比该点的函数值更优(即更小或更大)。几何上,这对应于曲线的谷底(极小值)或山顶(极大值)。
定义 3.1.2:一阶必要条件
设 ( f(x) ) 是定义在开集 ( S \subseteq \mathbb{R}^n ) 上的可微函数。若 ( x^* ) 是 ( f(x) ) 的局部极小值或局部极大值点,则有:
[
\nabla f(x^*) = 0
]
即,局部极值点的梯度必须为零。
解释与几何意义:
该定义描述了在极值点,函数的变化率为零。几何上,极值点处的切线是水平的,意味着函数没有朝任何方向增大或减小的趋势。
证明:
假设 ( \nabla f(x^*) \neq 0 ),则沿梯度的负方向,函数值会下降(或上升),这与极值点的性质矛盾,因此梯度必须为零。
定理 3.1.1:二阶必要条件
设 ( f(x) ) 是定义在开集 ( S \subseteq \mathbb{R}^n ) 上的二阶可微函数。若 ( x^* ) 是 ( f(x) ) 的局部极小值点或局部极大值点,则必须满足:
- ( \nabla f(x^*) = 0 );
- ( \nabla^2 f(x^*) ) 为半正定矩阵(对于局部极小值)或半负定矩阵(对于局部极大值)。
解释与几何意义:
这个定理进一步说明了极值点的性质,不仅要求梯度为零,还要求该点的二阶导数矩阵(黑塞矩阵)必须具备相应的正定或负定特性,以确保曲率的方向与极值点相符。几何上,这意味着极小值点处的曲率向上,而极大值点处的曲率向下。
证明:
利用二阶泰勒展开式,在 ( x^* ) 附近的函数值近似为:
[
f(x) = f(x^) + \nabla f(x*)T (x - x^) + \frac{1}{2} (x - x*)T \nabla^2 f(x^) (x - x^)
]
由于 ( \nabla f(x^) = 0 ),若黑塞矩阵 ( \nabla^2 f(x^) ) 为半正定或半负定,则二阶项主导函数的变化,使得函数在该点为极值点。
定义 3.1.3:黑塞矩阵
设 ( f(x) ) 是一个二阶可微函数,则 ( f(x) ) 的黑塞矩阵 ( \nabla^2 f(x) ) 是一个由函数的二阶偏导数组成的对称矩阵。对于函数 ( f(x_1, x_2, \dots, x_n) ),黑塞矩阵的形式为:
[
\nabla^2 f(x) = \begin{bmatrix}
\frac{\partial^2 f}{\partial x_1^2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \
\vdots & \ddots & \vdots \
\frac{\partial^2 f}{\partial x_n \partial x_1} & \cdots & \frac{\partial^2 f}{\partial x_n^2}
\end{bmatrix}
]
解释与几何意义:
黑塞矩阵描述了函数在各个方向上的二阶变化。几何上,黑塞矩阵的正定性表示函数在该点的所有方向上都是向上弯曲的(极小值),而负定性则表示函数在该点的所有方向上都是向下弯曲的(极大值)。
定理 3.1.2:局部极值的判定准则
设 ( f(x) ) 是二次可微函数,若 ( \nabla f(x^) = 0 ),则可以通过黑塞矩阵 ( \nabla^2 f(x^) ) 来判定 ( x^* ) 的性质:
- 若 ( \nabla^2 f(x^) ) 为正定矩阵,则 ( x^ ) 是局部极小值点;
- 若 ( \nabla^2 f(x^) ) 为负定矩阵,则 ( x^ ) 是局部极大值点;
- 若 ( \nabla^2 f(x^) ) 既不正定也不负定,则 ( x^ \
) 是鞍点。
解释与几何意义:
这个定理给出了通过黑塞矩阵来判定极值点性质的标准。几何上,正定矩阵对应于谷底(极小值),负定矩阵对应于山顶(极大值),而不定矩阵对应于马鞍形状(鞍点)。
证明:
利用泰勒展开式,在 ( \nabla f(x^*) = 0 ) 时,函数 ( f(x) ) 的变化由二阶项主导。如果黑塞矩阵正定,则二阶项总为正,表示极小值;如果负定,则二阶项总为负,表示极大值;如果既不正定也不负定,则函数在某些方向上升,在某些方向下降,表示鞍点。
定理 3.1.3:严格局部极小值的条件
若 ( f(x) ) 是二次可微函数,且在点 ( x^* ) 处梯度为零,且黑塞矩阵 ( \nabla^2 f(x^) ) 是正定的,则 ( x^ ) 是一个严格局部极小值点。
解释与几何意义:
该定理进一步加强了局部极小值的判定标准,要求黑塞矩阵必须是正定的,以确保该点是严格的局部极小值。几何上,正定的黑塞矩阵意味着函数的谷底是“尖锐的”,而不是平坦的。
证明:
同样利用泰勒展开式,若梯度为零且黑塞矩阵是正定的,则函数在 ( x^* ) 附近的所有方向上都是上升的,因此 ( x^* ) 是严格的局部极小值点。
3.2 无约束问题的最优化条件
定义 3.2.1:必要条件
设 ( f(x) ) 是定义在开集 ( S \subseteq \mathbb{R}^n ) 上的二次可微函数。如果 ( x^* ) 是 ( f(x) ) 的局部极小值点或局部极大值点,则该点必须满足:
[
\nabla f(x^*) = 0
]
即,梯度在极值点处为零。
解释与几何意义:
这是无约束优化问题中的一阶必要条件,表明极值点的梯度必须为零。几何上,这意味着函数在极值点处没有方向上的变化趋势,曲线或曲面的切线是水平的。
证明:
假设 ( \nabla f(x^*) \neq 0 ),则沿着梯度下降的方向,函数值会继续减小,这与局部极值的定义矛盾。因此,梯度必须为零。
定理 3.2.1:二阶必要条件
设 ( f(x) ) 是二次可微函数,若 ( x^* ) 是 ( f(x) ) 的局部极小值点或局部极大值点,则 ( \nabla f(x^) = 0 ),且黑塞矩阵 ( \nabla^2 f(x^) ) 为半正定(极小值点)或半负定(极大值点)。
解释与几何意义:
这是局部极值点的二阶必要条件,指出极值点的黑塞矩阵必须为半正定或半负定。几何上,半正定表示曲率方向上函数是向上弯曲的,而半负定表示曲率方向上函数是向下弯曲的。
证明:
在极值点 ( x^* ) 附近,利用二阶泰勒展开式:
[
f(x) = f(x^) + \frac{1}{2}(x - x*)T \nabla^2 f(x^) (x - x^)
]
如果黑塞矩阵为半正定,则 ( f(x) \geq f(x^) ),保证了 ( x^* ) 为极小值;如果黑塞矩阵为半负定,则 ( f(x) \leq f(x^) ),保证了 ( x^ ) 为极大值。
定理 3.2.2:局部极小值的充分条件
若 ( f(x) ) 是二次可微的实值函数,且在点 ( x^* ) 处满足:
- ( \nabla f(x^*) = 0 );
- 黑塞矩阵 ( \nabla^2 f(x^*) ) 是正定矩阵。
则 ( x^* ) 是 ( f(x) ) 的局部极小值点。
解释与几何意义:
这是局部极小值的充分条件,要求梯度为零且黑塞矩阵为正定。正定的黑塞矩阵意味着函数在 ( x^* ) 点附近的所有方向上都是向上弯曲的,因此 ( x^* ) 是局部极小值点。几何上,这对应于一个谷底。
证明:
利用泰勒展开式,若 ( \nabla f(x^) = 0 ) 且 ( \nabla^2 f(x^) ) 为正定,则函数 ( f(x) ) 在 ( x^* ) 附近可以近似为:
[
f(x) = f(x^) + \frac{1}{2}(x - x*)T \nabla^2 f(x^) (x - x^)
]
由于 ( \nabla^2 f(x^) ) 是正定的,二阶项总是正的,因此 ( f(x) \geq f(x^) ),故 ( x^ ) 是局部极小值点。
定理 3.2.3:局部极大值的充分条件
若 ( f(x) ) 是二次可微的实值函数,且在点 ( x^* ) 处满足:
- ( \nabla f(x^*) = 0 );
- 黑塞矩阵 ( \nabla^2 f(x^*) ) 是负定矩阵。
则 ( x^* ) 是 ( f(x) ) 的局部极大值点。
解释与几何意义:
这是局部极大值的充分条件,要求梯度为零且黑塞矩阵为负定。负定的黑塞矩阵意味着函数在 ( x^* ) 点附近的所有方向上都是向下弯曲的,因此 ( x^* ) 是局部极大值点。几何上,这对应于一个山顶。
证明:
与极小值的证明类似,利用泰勒展开式,在 ( \nabla f(x^) = 0 ) 且 ( \nabla^2 f(x^) ) 为负定的条件下,函数 ( f(x) ) 在 ( x^* ) 附近可以表示为:
[
f(x) = f(x^) + \frac{1}{2}(x - x*)T \nabla^2 f(x^) (x - x^)
]
由于 ( \nabla^2 f(x^) ) 是负定的,二阶项总是负的,因此 ( f(x) \leq f(x^) ),故 ( x^ ) 是局部极大值点。
定理 3.2.4:鞍点判定条件
若 ( f(x) ) 是二次可微函数,且在点 ( x^* ) 处满足:
- ( \nabla f(x^*) = 0 );
- 黑塞矩阵 ( \nabla^2 f(x^*) ) 既不正定也不负定。
则 ( x^* ) 是 ( f(x) ) 的鞍点。
解释与几何意义:
这是鞍点的判定条件,指出当黑塞矩阵既不正定也不负定时,函数在 ( x^* ) 点附近的一些方向上表现为极小值,而在其他方向上表现为极大值。几何上,这类似于马鞍的形状。
证明:
利用二阶泰勒展开式,如果黑塞矩阵既不正定也不负定,说明函数在某些方向上的二阶导数为正(上升),而在其他方向上的二阶导数为负(下降),因此 ( x^* ) 是鞍点。
定理 3.2.5:正定二次函数的唯一极小值
若 ( f(x) = \frac{1}{2}x^T A x + b^T x + c ) 为二次型函数,其中 ( A ) 是正定矩阵,则 ( f(x) ) 在点 ( x^* = -A^{-1} b ) 处达到唯一的极小值。
解释与几何意义:
这是关于二次型函数的极小值问题。正定的二次型函数具有唯一的极小值点,且可以通过求解线性方程 ( A x + b = 0 ) 来找到该极小值点。几何上,正定矩阵对应于一个开口向上的抛物面,极小值点位于谷底。
证明:
对函数 ( f(x) = \frac{1}{2}x^T A x + b^T x + c ) 求梯度,得到:
[
\nabla f(x) = A x + b
]
令 ( \nabla f(x^) = 0 ),解得 ( x^ = -A^{-1} b )。由于 ( A ) 是正定矩阵,保证了 ( x^* ) 是唯一的极小值点。
定理 3.2.6:局部极小值的充分条件
设 ( f(x) ) 为二次可微函数,如果 ( \nabla f(x^) = 0 ),且黑塞矩阵 ( \nabla^2 f(x^) ) 为正定矩阵,则 ( x^* ) 是局部极小值点。
解释与几何意义:
这个定理是局部极小值的充分条件,类似于之前的二阶充分条件,要求梯度为零且黑塞矩阵为正定。正定的黑塞矩阵保证了函数在该点的所有方向上都是向上
弯曲的,因此 ( x^* ) 是局部极小值点。
证明:
利用二阶泰勒展开式,如果 ( \nabla f(x^) = 0 ) 且 ( \nabla^2 f(x^) ) 为正定,则函数 ( f(x) ) 在 ( x^* ) 附近的变化为:
[
f(x) = f(x^) + \frac{1}{2}(x - x*)T \nabla^2 f(x^) (x - x^)
]
由于二阶项为正,因此 ( f(x) \geq f(x^) ),即 ( x^* ) 是局部极小值点。
定义 3.2.7:黑塞矩阵的半正定性
设 ( f(x) ) 是二次可微函数,如果在点 ( x^* ) 处的黑塞矩阵 ( \nabla^2 f(x^) ) 是半正定的,则 ( x^ ) 可能是局部极小值点。
解释与几何意义:
黑塞矩阵的半正定性意味着在某些方向上函数没有二阶变化,但在其他方向上是向上弯曲的。几何上,半正定的黑塞矩阵可能对应于函数的某些方向上是平的,但其他方向上是谷底。
证明:
利用二阶泰勒展开式,如果黑塞矩阵为半正定,则函数在某些方向上保持不变或上升,因此 ( x^* ) 可能是局部极小值点。
3.3 凸函数与凸规划
定义 3.3.1:凸函数
设 ( f(x) ) 是定义在凸集 ( S \subseteq \mathbb{R}^n ) 上的函数。如果对于任意 ( x^{(1)}, x^{(2)} \in S ) 和 ( \alpha \in [0, 1] ),有:
[
f(\alpha x^{(1)} + (1-\alpha)x^{(2)}) \leq \alpha f(x^{(1)}) + (1-\alpha)f(x^{(2)})
]
则称 ( f(x) ) 为定义在 ( S ) 上的凸函数。
解释与几何意义:
凸函数的定义表明,函数在两个点之间的值不会超过这两个点的加权平均值。几何上,凸函数的图像在任何两点之间的连线都位于函数图像的上方,表示函数是向上凹的,类似于碗的形状。
定理 3.3.1:凸函数的一阶条件
设 ( f(x) ) 是定义在凸集 ( S ) 上的可微函数。则 ( f(x) ) 是凸函数的充要条件是,对于任意 ( x^{(1)}, x^{(2)} \in S ):
[
f(x^{(2)}) \geq f(x^{(1)}) + \nabla f(x{(1)})T (x^{(2)} - x^{(1)})
]
即,函数在任意一点的线性近似是一个下界。
解释与几何意义:
这个定理通过一阶导数条件描述了凸函数的特性:在凸函数的任意一点,切线或切平面始终是函数图像的下界。几何上,这意味着函数图像不会在切线以下发生变化。
证明:
从凸函数定义出发,结合泰勒展开式可以推导出函数的线性近似为其下界。该定理的证明直接依赖于凸函数定义。
定理 3.3.2:凸函数的二阶条件
若 ( f(x) ) 是定义在凸集 ( S ) 上的二阶可微函数,则 ( f(x) ) 是凸函数的充要条件是,黑塞矩阵 ( \nabla^2 f(x) ) 在 ( S ) 内是半正定的,即:
[
\nabla^2 f(x) \geq 0, \quad \forall x \in S
]
解释与几何意义:
该定理通过二阶导数描述了凸函数的性质。黑塞矩阵的半正定性意味着函数在每一点的曲率都是向上的,几何上,这对应于函数在所有方向上的二阶变化均不会使得函数值减小,从而保持了函数的凸性。
证明:
通过泰勒展开式,可以证明函数的二阶导数决定了函数的曲率性质,黑塞矩阵为半正定是函数凸性的充要条件。
性质 1:凸函数的加权平均性质
设 ( f(x) ) 是定义在凸集 ( S ) 上的凸函数,则对于任意非负实数 ( \alpha ),函数 ( \alpha f(x) ) 也是定义在 ( S ) 上的凸函数。
解释:
凸函数的凸性在数乘下仍然保持。几何上,这意味着将凸函数拉伸或缩放(乘以非负数)后,其形状仍然保持向上凹的特性。
性质 2:凸函数的加法封闭性
设 ( f_1(x) ) 和 ( f_2(x) ) 都是定义在凸集 ( S ) 上的凸函数,则 ( f(x) = f_1(x) + f_2(x) ) 也是定义在 ( S ) 上的凸函数。
解释:
凸函数的和仍然是凸函数。几何上,两个“向上凹”的函数相加,结果仍然是向上凹的。
性质 3:凸函数的水平集
设 ( f(x) ) 是定义在凸集 ( S ) 上的凸函数,则对于任意实数 ( \beta ),其水平集
[
H_S(f, \beta) = {x \in S \mid f(x) \leq \beta}
]
是凸集。
解释:
凸函数的水平集是一个凸集,表示低于某个函数值的所有点形成的集合是凸的。几何上,水平集就像是从凸函数图像中选取某个高度以下的部分,这个部分保持了凸性。
定理 3.3.3:凸函数的极小点是全局极小值点
设 ( f(x) ) 是定义在凸集 ( S ) 上的凸函数,若 ( x^* ) 是 ( f(x) ) 的局部极小值点,则 ( x^* ) 是 ( f(x) ) 的全局极小值点。
解释与几何意义:
凸函数的局部极小值点也是全局极小值点,这是凸优化问题的核心特性。几何上,凸函数不会有多个局部极小值,所有的局部极小值点都是全局极小值点。
证明:
利用凸函数的定义,对于任意 ( x^{(1)}, x^{(2)} \in S ),有:
[
f(\alpha x^{(1)} + (1-\alpha) x^{(2)}) \leq \alpha f(x^{(1)}) + (1-\alpha) f(x^{(2)})
]
由此可得,当 ( x^* ) 是局部极小值点时,任意其他点的函数值均不小于 ( f(x^) ),因此 ( x^ ) 是全局极小值点。
定理 3.3.4:平稳点的全局最优性
设 ( f(x) ) 是定义在凸集 ( S ) 上的可微凸函数,若 ( x^* ) 是 ( f(x) ) 的平稳点(即 ( \nabla f(x^) = 0 )),则 ( x^ ) 是 ( f(x) ) 的全局极小值点。
解释与几何意义:
凸函数的平稳点必然是全局极小值点。几何上,平稳点是函数在该点的变化率为零的点,对于凸函数,这样的点必然是函数的最低点。
证明:
由于 ( f(x) ) 是凸函数,结合一阶导数条件,可以推导出对于任意 ( x \in S ),有:
[
f(x) \geq f(x^)
]
因此,平稳点 ( x^ ) 是全局极小值点。
定理 3.3.5:拉格朗日乘数法
设凸规划问题为:
[
\min f(x)
]
subject to
[
g_i(x) \leq 0, \quad i = 1, 2, \dots, m,
]
[
h_j(x) = 0, \quad j = 1, 2, \dots, l,
]
其中 ( f(x) ) 和 ( g_i(x) ) 为凸函数,( h_j(x) ) 为线性函数。则最优解满足拉格朗日条件,即存在拉格朗日乘子 ( \lambda_i \geq 0 ) 和 ( \mu_j ) 使得:
[
\nabla f(x^) + \sum_{i=1}^m \lambda_i \nabla g_i(x^) + \sum_{j=1}^l \mu_j \nabla h_j(x^) = 0
]
且
[
\lambda_i g_i(x^) = 0, \quad \forall i
]
解释与几何意义:
拉格朗日乘数法是一种求解带约束的凸规划问题的有效方法。几何上,拉格朗日乘数表示目标函数和约束条件之间的平衡,在最优解处,梯度的线性组合为零,且乘子确保不活跃的约束不会影响解。
证明:
利用拉格朗日函数 ( L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^l
\mu_j h_j(x) ),通过对 ( L ) 求导,并结合KKT条件,得出上述结果。
定义 3.3.6:凸规划问题
凸规划问题是指目标函数和约束条件均为凸函数的最优化问题。其标准形式为:
[
\min f(x)
]
subject to
[
g_i(x) \leq 0, \quad i = 1, 2, \dots, m,
]
[
h_j(x) = 0, \quad j = 1, 2, \dots, l,
]
其中,( f(x) ) 和 ( g_i(x) ) 为凸函数,( h_j(x) ) 为线性函数。
解释与几何意义:
凸规划问题是一类特殊的优化问题,因其目标函数和约束条件的凸性,保证了如果问题有解,则解为全局最优解。几何上,凸规划问题可以被看作在一个凸集上寻找使得目标函数最小的点。
附录
1. 凸集
定义
设 ( S \subseteq \mathbb{R}^n ) 是一个集合。如果对于任意的 ( x^{(1)}, x^{(2)} \in S ) 和 ( \alpha \in [0, 1] ),都有:
[
\alpha x^{(1)} + (1-\alpha)x^{(2)} \in S
]
则称集合 ( S ) 为凸集。
解释与几何意义
凸集的定义表明,集合内任意两点的连线上的所有点也都属于该集合。几何上,凸集的形状不包含“凹陷”或“洞”,即连接任意两点的线段完全在集合内。
2. 二次型
定义
设 ( A ) 是一个 ( n \times n ) 的对称矩阵,( x \in \mathbb{R}^n ) 是一个向量,则二次型函数的形式为:
[
f(x) = x^T A x
]
这里,( x^T ) 是向量 ( x ) 的转置,( A ) 是一个对称矩阵。
详细说明
在二次型函数中,矩阵 ( A ) 描述了函数的二阶特性,而向量 ( x ) 是自变量。二次型是描述曲面或更高维曲面的基本工具。对于 ( x \in \mathbb{R}^2 ),二次型的形式为:
[
f(x) = a_{11}x_1^2 + 2a_{12}x_1x_2 + a_{22}x_2^2
]
其中,( A = \begin{pmatrix} a_{11} & a_{12} \ a_{12} & a_{22} \end{pmatrix} ),这代表着二次函数中关于各个变量 ( x_1 ) 和 ( x_2 ) 的二次项和混合项。
几何意义
几何上,二次型函数的图像通常为抛物面或椭圆状曲面。矩阵 ( A ) 的正定性、负定性或非定性(即是否存在正负的特征值)决定了函数的形状:正定表示开口向上的碗形,负定表示开口向下的碗形,非定则表示马鞍形。
3. 多元函数的微分与偏导数
微分
设 ( f(x_1, x_2, \dots, x_n) ) 是定义在 ( \mathbb{R}^n ) 上的多元函数。该函数在点 ( x^* = (x_1^, x_2^, \dots, x_n^*) ) 处的全微分定义为:
[
df = \frac{\partial f}{\partial x_1} dx_1 + \frac{\partial f}{\partial x_2} dx_2 + \dots + \frac{\partial f}{\partial x_n} dx_n
]
其中,( \frac{\partial f}{\partial x_i} ) 表示函数对第 ( i ) 个变量的偏导数。
解释: 全微分描述了函数值的一个近似增量,由各个自变量的微小变化 ( dx_1, dx_2, \dots, dx_n ) 及其偏导数加权和组成。
导数与偏导数
-
导数(单变量):
对于单变量函数 ( f(x) ),导数定义为:
[
f’(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}
]
这表示函数在 ( x ) 处的变化率。 -
偏导数(多变量):
对于多元函数 ( f(x_1, x_2, \dots, x_n) ),其对某个变量 ( x_i ) 的偏导数表示为:
[
\frac{\partial f}{\partial x_i} = \lim_{h \to 0} \frac{f(x_1, \dots, x_i+h, \dots, x_n) - f(x_1, \dots, x_i, \dots, x_n)}{h}
]
这描述了函数在固定其他变量时,随 ( x_i ) 的变化率。
示例
假设 ( f(x_1, x_2) = 3x_1^2 + 2x_1x_2 + x_2^2 ),我们计算其偏导数:
- ( \frac{\partial f}{\partial x_1} = 6x_1 + 2x_2 )
- ( \frac{\partial f}{\partial x_2} = 2x_1 + 2x_2 )
几何意义: 偏导数描述了函数在某一方向的变化趋势,全微分则描述了函数在各个方向上的综合变化。
4. 矩阵的正定、负定、半正定和半负定
定义
设 ( A ) 是一个 ( n \times n ) 的对称矩阵,对于任意非零向量 ( x \in \mathbb{R}^n ),我们可以根据二次型 ( x^T A x ) 的符号来分类矩阵 ( A ) 的性质:
- 正定矩阵:若对于任意 ( x \neq 0 ),有 ( x^T A x > 0 ),则称 ( A ) 是正定矩阵。
- 负定矩阵:若对于任意 ( x \neq 0 ),有 ( x^T A x < 0 ),则称 ( A ) 是负定矩阵。
- 半正定矩阵:若对于任意 ( x \neq 0 ),有 ( x^T A x \geq 0 ),则称 ( A ) 是半正定矩阵。
- 半负定矩阵:若对于任意 ( x \neq 0 ),有 ( x^T A x \leq 0 ),则称 ( A ) 是半负定矩阵。
- 不定矩阵:若 ( x^T A x ) 在某些 ( x ) 上为正,在其他 ( x ) 上为负,则 ( A ) 是不定矩阵。
判定矩阵正定性/负定性的方法
方法一:通过特征值判断
矩阵的特征值可以告诉我们关于其正定性或负定性的重要信息:
- 正定矩阵:如果矩阵 ( A ) 的所有特征值 ( \lambda_i ) 都为正,则 ( A ) 是正定矩阵。
- 负定矩阵:如果矩阵 ( A ) 的所有特征值 ( \lambda_i ) 都为负,则 ( A ) 是负定矩阵。
- 半正定矩阵:如果矩阵 ( A ) 的所有特征值 ( \lambda_i ) 都是非负的(即 ( \lambda_i \geq 0 )),但至少有一个特征值为零,则 ( A ) 是半正定矩阵。
- 半负定矩阵:如果矩阵 ( A ) 的所有特征值 ( \lambda_i ) 都是非正的(即 ( \lambda_i \leq 0 )),但至少有一个特征值为零,则 ( A ) 是半负定矩阵。
- 不定矩阵:如果矩阵 ( A ) 的特征值有正有负,则 ( A ) 是不定矩阵。
步骤:
- 写出矩阵 ( A )。
- 求解特征值:
- 计算特征值方程 ( \det(A - \lambda I) = 0 ),其中 ( I ) 是单位矩阵,解出所有特征值 ( \lambda )。
- 判定性质:根据特征值的符号,判断矩阵的正定、负定、半正定或不定性质。
示例:
设矩阵 ( A = \begin{pmatrix} 4 & 1 \ 1 & 3 \end{pmatrix} ),我们通过特征值法判断其正定性。
- 写出矩阵 ( A )。
- 计算特征值:
[
\det(A - \lambda I) = \det \begin{pmatrix} 4 - \lambda & 1 \ 1 & 3 - \lambda \end{pmatrix} = (4 - \lambda)(3 - \lambda) - 1 = 0
]
展开并解方程:
[
\lambda^2 - 7\lambda + 11 = 0
]
解得特征值为 ( \lambda_1 = 5 ),( \lambda_2 = 2 )。 - 由于所有特征值均为正,因此矩阵 ( A ) 是正定矩阵。
方法二:通过主子式法判断
主子式法是通过检查矩阵的顺序主子式的符号来判断矩阵的正定性或负定性。
- 正定矩阵:如果矩阵的所有顺序主子式(即从左上角开始的 ( k \times k ) 子矩阵的行列式)均为正,则矩阵是正定的。
- 负定矩阵:如果矩阵的所有顺序主子式的行列式交替为负和正(即第一个主子式负,第二个主子式正,依次类推),则矩阵是负定的。
- 半正定矩阵:如果所有主子式的行列式为非负,但至少有一个为零,则矩阵是半正定的。
- 半负定矩阵:如果所有主子式的行列式为非正,但至少有一个为零,则矩阵是半负定的。
- 不定矩阵:如果主子式中存在正值和负值,则矩阵是不定的。
步骤:
- 写出矩阵 ( A )。
- 计算顺序主子式:
- ( k = 1 ) 时,计算矩阵的第一个主子式(左上角的 ( 1 \times 1 ) 子矩阵)。
- ( k = 2 ) 时,计算矩阵的第二个主子式(左上角的 ( 2 \times 2 ) 子矩阵)。
- 依次类推,直到 ( k = n )。
- 判定性质:根据主子式的符号,判断矩阵的正定性、负定性、半正定性或不定性。
示例:
设矩阵 ( A = \begin{pmatrix} 2 & -1 \ -1 & 2 \end{pmatrix} ),我们通过主子式法判断其正定性。
- 写出矩阵 ( A )。
- 计算顺序主子式:
- 第一个主子式(左上角的 ( 1 \times 1 ) 矩阵)为 ( 2 ),正。
- 第二个主子式(整个 ( 2 \times 2 ) 矩阵)为:
[
\det \begin{pmatrix} 2 & -1 \ -1 & 2 \end{pmatrix} = 2 \times 2 - (-1) \times (-1) = 4 - 1 = 3
]
也是正。
- 由于所有顺序主子式均为正,因此矩阵 ( A ) 是正定矩阵。
总结
- 矩阵的正定、负定、半正定、半负定、不定 可以通过特征值法和主子式法进行判定。
- 特征值法:通过计算矩阵的特征值,依据特征值的符号判断矩阵的性质。
- 主子式法:通过计算矩阵的顺序主子式(从左上角的子矩阵),依据子式的符号变化判断矩阵的性质。
5. 求特征值和特征向量的方法
定义
设 ( A ) 是一个 ( n \times n ) 的矩阵。向量 ( v \in \mathbb{R}^n ) 称为 ( A ) 的特征向量,若存在标量 ( \lambda \in \mathbb{R} ),使得:
[
A v = \lambda v
]
此时 ( \lambda ) 称为 ( A ) 的特征值。
求特征值与特征向量的步骤
-
特征值的求解:
解特征方程 ( \det(A - \lambda I) = 0 ),求出特征值 ( \lambda ),其中 ( I ) 是单位矩阵,( \det ) 表示行列式。 -
特征向量的求解:
对于每个特征值 ( \lambda ),解齐次线性方程 ( (A - \lambda I) v = 0 ),求出对应的特征向量 ( v )。
示例
设 ( A = \begin{pmatrix} 4 & 1 \ 2 & 3 \end{pmatrix} ),我们求解其特征值和特征向量。
-
特征值:
特征方程为:
[
\det(A - \lambda I) = \det\begin{pmatrix} 4-\lambda & 1 \ 2 & 3-\lambda \end{pmatrix} = (4-\lambda)(3-\lambda) - 2 = 0
]
解得 ( \lambda_1 = 5 ),( \lambda_2 = 2 )。 -
特征向量:
对于 ( \lambda_1 = 5 ),解 ( (A - 5I)v = 0 ),得特征向量 ( v_1 = \begin{pmatrix} 1 \ 2 \end{pmatrix} )。
对于 ( \lambda_2 = 2 ),解 ( (A - 2I)v = 0 ),得特征向量 ( v_2 = \begin{pmatrix} -1 \ 1 \end{pmatrix} )。
6. 求多元函数极值的方法
步骤
-
寻找驻点:
对多元函数 ( f(x_1, x_2, \dots, x_n) ) 求偏导数,求解 ( \nabla f(x) = 0 ),即求解方程:
[
\frac{\partial f}{\partial x_1} = 0
, \frac{\partial f}{\partial x_2} = 0, \dots, \frac{\partial f}{\partial x_n} = 0
]
解出所有驻点 ( x^* )。 -
判断极值点:
计算黑塞矩阵 ( \nabla^2 f(x) ),并利用其正定性或负定性判断驻点性质:- 若 ( \nabla^2 f(x^) ) 为正定矩阵,则 ( x^ ) 是局部极小值点;
- 若 ( \nabla^2 f(x^) ) 为负定矩阵,则 ( x^ ) 是局部极大值点;
- 若 ( \nabla^2 f(x^) ) 既不正定也不负定,则 ( x^ ) 是鞍点。
示例
设 ( f(x_1, x_2) = 2x_1^2 + 3x_2^2 + 2x_1x_2 ),求该函数的极值。
-
寻找驻点:
计算偏导数:
[
\frac{\partial f}{\partial x_1} = 4x_1 + 2x_2 = 0, \quad \frac{\partial f}{\partial x_2} = 6x_2 + 2x_1 = 0
]
解得 ( x_1 = 0 ),( x_2 = 0 ),所以驻点为 ( (0, 0) )。 -
判断极值点:
计算黑塞矩阵:
[
\nabla^2 f(x) = \begin{pmatrix} 4 & 2 \ 2 & 6 \end{pmatrix}
]
计算其特征值,得到特征值为 ( \lambda_1 = 3.24 ),( \lambda_2 = 6.76 )。由于黑塞矩阵是正定的,因此 ( (0, 0) ) 是局部极小值点。
3.1 和 3.2 中的泰勒展开
泰勒展开的定义
对于在某点 ( x_0 ) 处具有足够阶数导数的函数 ( f(x) ),我们可以使用泰勒展开对函数在该点附近进行近似。函数 ( f(x) ) 在点 ( x_0 ) 处的泰勒展开式为:
[
f(x) = f(x_0) + f’(x_0)(x - x_0) + \frac{f’'(x_0)}{2!}(x - x_0)^2 + \dots + \frac{f^{(n)}(x_0)}{n!}(x - x_0)^n + R_n(x)
]
其中,( R_n(x) ) 是高阶剩余项。
对于多元函数 ( f(x_1, x_2, \dots, x_n) ),泰勒展开式类似,但包含偏导数项。
一元函数的泰勒展开
设 ( f(x) ) 是一元函数,在点 ( x_0 ) 处,( f(x) ) 的二阶泰勒展开式为:
[
f(x) \approx f(x_0) + f’(x_0)(x - x_0) + \frac{f’'(x_0)}{2!}(x - x_0)^2
]
- 几何意义:
该展开式将函数近似为 ( x_0 ) 附近的一个二次多项式,其中一次项描述了函数在该点的斜率,二次项描述了曲率(凹凸性)。
多元函数的泰勒展开
对于多元函数 ( f(x_1, x_2, \dots, x_n) ),在点 ( x_0 = (x_1^0, x_2^0, \dots, x_n^0) ) 处的二阶泰勒展开式为:
[
f(x) \approx f(x_0) + \nabla f(x_0)^T (x - x_0) + \frac{1}{2}(x - x_0)^T \nabla^2 f(x_0)(x - x_0)
]
其中:
- ( \nabla f(x_0) ) 是在 ( x_0 ) 处的梯度向量;
- ( \nabla^2 f(x_0) ) 是在 ( x_0 ) 处的黑塞矩阵。
几何意义:
- 一次项 ( \nabla f(x_0)^T (x - x_0) ) 表示函数在 ( x_0 ) 处的线性近似(即切平面)。
- 二次项 ( \frac{1}{2}(x - x_0)^T \nabla^2 f(x_0)(x - x_0) ) 描述了函数的曲率,即在该点附近的二次变化。
泰勒展开在 3.1 和 3.2 中的应用
在 3.1 无约束问题的最优化条件 和 3.2 无约束问题的最优化条件 中,泰勒展开用于分析多元函数在驻点附近的行为。通过泰勒展开,我们可以通过函数的梯度和黑塞矩阵来判定驻点是局部极值点还是鞍点。
-
一阶条件:
( \nabla f(x^) = 0 ) 表示函数在点 ( x^ ) 处的变化率为零,这是极值点的必要条件。 -
二阶条件:
( \nabla^2 f(x^) ) 是函数在点 ( x^ ) 处的黑塞矩阵。利用泰勒展开的二次项,我们可以判定 ( x^* ) 的性质:- 如果黑塞矩阵正定,说明函数在该点附近是上凸的,因而 ( x^* ) 是局部极小值点;
- 如果黑塞矩阵负定,说明函数在该点附近是下凸的,因而 ( x^* ) 是局部极大值点;
- 如果黑塞矩阵既不正定也不负定,则该点是鞍点。
示例:多元函数的泰勒展开
设 ( f(x_1, x_2) = x_1^2 + 2x_1x_2 + 3x_2^2 ),我们在点 ( (0, 0) ) 处展开其二阶泰勒展开式:
-
函数在 ( (0, 0) ) 处的值:
( f(0, 0) = 0 )。 -
梯度向量 ( \nabla f(0, 0) ):
计算偏导数:
[
\frac{\partial f}{\partial x_1} = 2x_1 + 2x_2, \quad \frac{\partial f}{\partial x_2} = 2x_1 + 6x_2
]
在 ( (0, 0) ) 处,梯度 ( \nabla f(0, 0) = (0, 0) )。 -
黑塞矩阵 ( \nabla^2 f(0, 0) ):
计算二阶导数:
[
\nabla^2 f = \begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} \end{pmatrix} = \begin{pmatrix} 2 & 2 \ 2 & 6 \end{pmatrix}
]
黑塞矩阵为 ( \begin{pmatrix} 2 & 2 \ 2 & 6 \end{pmatrix} )。 -
二阶泰勒展开式:
根据泰勒展开公式:
[
f(x_1, x_2) \approx f(0, 0) + \nabla f(0, 0)^T (x - 0) + \frac{1}{2}(x - 0)^T \nabla^2 f(0, 0) (x - 0)
]
化简得:
[
f(x_1, x_2) \approx \frac{1}{2} \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 2 & 2 \ 2 & 6 \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \end{pmatrix} = x_1^2 + 2x_1x_2 + 3x_2^2
]
这个结果与原函数形式一致。
几何意义:
通过泰勒展开,我们可以看出函数 ( f(x_1, x_2) ) 在 ( (0, 0) ) 点附近的行为,具体表现在曲率特性上。通过黑塞矩阵可以进一步分析该点是否为极值点或鞍点。
总结
- 泰勒展开 是用于近似多元函数在某点附近行为的重要工具。
- 在 3.1 和 3.2 部分,通过泰勒展开,可以使用梯度和黑塞矩阵来判定驻点的性质。
- 一阶项表示函数的线性近似,二阶项则通过黑塞矩阵描述曲率的特性。
- 正定的黑塞矩阵 意味着该点是局部极小值,负定的黑塞矩阵 表示该点是局部极大值,不定黑塞矩阵 则对应鞍点。