【学习笔记

您所在的位置：网站首页 › 极值点检验例题 › 【学习笔记

【学习笔记

2024-06-13 20:46| 来源: 网络整理| 查看: 265

学习目的：应对博士申请考核中《最优化理论与算法》的考试。

学习材料：《运筹学》第4版清华大学出版社&《最优化理论与算法》第2版清华大学出版社&《线性代数》国立交通大学出版社

主要内容：

一、无约束非线性规划问题

二、等式约束非线性规划问题

三、不等式约束非线性规划问题

四、12个例子

一、无约束非线性规划问题

1.1 函数存在极值的一阶/二阶必要条件

a) 一阶必要条件：函数 $f(x)$ 在 $\bar{x}$ 点可微，若 $\bar{x}$ 是局部极小点，则梯度 $\nabla_{}f(\bar{x})=0$

b) 二阶必要条件：函数 $f(x)$ 在 $\bar{x}$ 点二次可微，若 $\bar{x}$ 是局部极小点，则梯度 $\nabla_{}f(\bar{x})=0$ ，并且Hesse矩阵 $\nabla^{\boldsymbol{2}}_{}f(\bar{x})$ 半正定。

1.2 备注

a) “可微”、“Hesse矩阵 ”、“半正定”这三个概念在无约束非线性规划问题中的判断较为重要，可直接点击链接进行学习，在此不在赘述。

b) 对应后续例题1。

二、等式约束非线性规划问题

2.1 学习目的

为学习不等式约束非线性规划问题做铺垫。

2.2 等式约束

假设，约束优化问题（1）型为

这里f 与g 都是连续可导的函数，定义Lagrangian函数型为：

其中 $\lambda$ 为Lagrange 乘数。上述Lagrangian函数将问题（1）中的约束条件吸收至目标函数中，将有约束的优化问题转化为无约束优化问题，即形如:

对于上式的最优解的必要条件是：

联立上述方程（第一个方程是Lagrange函数的定常方程），可得 $x^{*}$ 以及 $\lambda$ 的值，求得最优解。

三、KKT条件——求解不等式约束优化问题

3.1 不等式约束问题

假设，约束问题（2）形如：

$g(x)$ 划定了上述目标函数的可行域(feasible region) $\kappa$ ，当最优解 $x^{^{*}}$ 位于可行域 $\kappa$ 的位置意味着约束条件的有效性，将 $x^{^{*}}$ 的位置情况分为两类：

1、内部解：最优解 $x^{^{*}}$ 位于可行域 $\kappa$ 内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；

2、边界解：最优解 $x^{^{*}}$ 位于可行域 $\kappa$ 边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

因此，两种情况的必要条件也是不同。对应上述两种情况，可分别转化为两种结果：

1、最优解 $x^{^{*}}$ 位于可行域 $\kappa$ 内部时，约束条件无效，因此约束优化问题退化为无约束优化问题，易于求解；

2、最优解 $x^{^{*}}$ 位于可行域 $\kappa$ 边界时，约束条件由不等式变为等式 $g(x)=0$ 可转化为上述Lagrange 乘数法的情形。

3.2 KKT条件的形式

整合上述两种情况，最优解 $x^{^{*}}$ 的必要条件是：1）Lagrangian函数的定常方程 2）原始约束条件 3）对偶可行性 4）互补松弛性（之后的学习中会详细介绍对偶可行性和互补松弛性），形如：

四、 12个例子

备注: 例子来源于《最优化理论与算法》第2版清华大学出版社。

1、求函数 $f(x)=\frac{x_{1}+x_{2}}{3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2}}$ 的极小点。

解：

（1）求驻点（2）求Hesse矩阵（3）判断矩阵性质（正定/半正定）

求解过程：

$\frac{\partial f}{\partial x_{1}}=\frac{3-x_{1}^{2}-2x_{1}x_{2}}{{(3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2})}^{2}}$ ， $\frac{\partial f}{\partial x_{2}}=\frac{3-x_{2}^{2}-2x_{1}x_{2}}{{(3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2})}^{2}}$

令上述两个式子等于0，求得驻点 $x^{(1)}=(1,1),x^{(2)}=(-1,-1)$

对 $f(x)$ 分别对 $x_{1}$ 和 $x_{2}$ 求二阶偏导有：

$\frac{\partial^{2} f}{\partial x_{1}^{2}}=\frac{-18x_{1}-12x_{2}+2x_{1}^{3}-2x_{2}^{3}+6x_{1}^{2}x_{2}}{{(3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2})}^{3}}$

$\frac{\partial^{2} f}{\partial x_{2}^{2}}=\frac{-12x_{1}-18x_{2}-2x_{1}^{3}+2x_{2}^{3}+6x_{1}x_{2}^{2}}{{(3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2})}^{3}}$ $\frac{\partial^{2} f}{\partial x_{1}x_{2}}=\frac{-12x_{1}-12x_{2}+6x_{1}x_{2}^{2}+6x_{1}^{2}x_{2}}{{(3+x_{1}^{2}+x_{2}^{2}+x_{1}x_{2})}^{3}}$

得到Hesse矩阵后，将上述两个驻点代入Hesse矩阵有：

$\nabla^{2}_{}f(x^{(1)})=\left [ \begin{matrix} -1/9 & -1/18 \\ -1/18 & -1/9 \\ \end{matrix} \right ]$

$\nabla^{2}_{}f(x^{(2)})=\left [ \begin{matrix} 1/9 & 1/18 \\ 1/18 & 1/9 \\ \end{matrix} \right ]$

由上， $\nabla^{2}_{}f(x^{(1)})$ 是负定矩阵， $\nabla^{2}_{}f(x^{(2)})$ 是正定矩阵。

因此， $f(x)$ 的极小点是 $x^{(2)}$

2、考虑非线性规划问题

$min(x_{1}-3)^2+(x_{2}-2)^2$

$s.t.$ $\\ x_{1}^{2}+x_{2}^{2}\leqslant 5\\ x_{1}+2x_{2}= 4\\ x_{1}, x_{2}\geqslant 0$

检验 $\bar{x}=(2,1)^{^{T}}$ ，是否为KT点。

解：

（1）改写非线性规划形式（2）求目标函数和约束条件的梯度（3）判断是否满足Fritz-John条件

求解过程：

上述约束问题可改写为：

$min(x_{1}-3)^2+(x_{2}-2)^2$

$s.t.$ $\\ -x_{1}^{2}-x_{2}^{2}\geqslant 5\\ x_{1}+2x_{2}= 4\\ x_{1}, x_{2}\geqslant 0$

将 $\bar{x}=(2,1)^{^{T}}$ 代入上述约束条件，发现 $\bar{x}$ 正好在前两个约束条件的边界上，因此前两个约束是起作用约束。

分别对目标函数和前两个约束条件求一阶偏导，再代入 $\bar{x}$ 得：

在点 $\bar{x}$ 目标函数的梯度为 $\left [ \begin{matrix} -2 \\ -2\\ \end{matrix} \right ]$ ，两个约束条件的梯度分别是 $\left [ \begin{matrix} -4 \\ -2\\ \end{matrix} \right ]$ 和 $\left [ \begin{matrix} 1 \\ 2\\ \end{matrix} \right ]$ 。

(未完，csdn的编辑器太难用了)

【本文地址】

公司简介

联系我们