代数方程与最优化问题的计算机求解

第6章

代数方程与最优化问题的计算机求解高等应用数学问题的MATLAB求解清华大学出版社2008CAI课件开发：薛定宇、刘莹莹、董雯彬2/1/2023第6章代数方程与最优

化问题的计算机求解代数方程的求解无约束最优化问题求解有约束最优化问题的计算机求解混合整数规划问题的计算机求解线性矩阵不等式问题求解多目标优化问题求解动态规划及其在路径规划中的应用2/1/20236.1代数方程的求解代数方程的图解法多项式型方程的准解析解法一般非线性方程数值解非线性矩阵方程求解2/1/20236.1.1代数方程的图解法一元方程的图解法二元方程的图解法2/1/2023

一元方程的图解法用ezplot()函数可以绘制出给定的隐函数

曲线，所以可以用图解法从给出的曲线和

线的交点上读出所有的实数解。2/1/2023例6.1用图解法求解方程：MATLAB求解命令证明：2/1/2023

二元方程的图解法使用ezplot()函数将所有的方程都画出来，得出曲线后就可以通过读取交点坐标的方式得出联立方程的根2/1/2023例6.2用图解法求解联立方程：画第一个函数：画第二个函数：2/1/20236.1.2多项式型方程的准解析解法特殊的高阶方程如多项式型方程，可以被求解出Abel-Ruffini定理证明5阶以上的多项式型方程没有解析解一般的数值算法得出的解不精确得出高精度解的方法存在很多方程可以转换成多项式方程2/1/2023例6.3试用图解方法求解二元方程MATLAB求解命令：2/1/2023求解多项式型方程的函数调用格式最简调用方式直接得出根指定变量2/1/2023例6.4使用solve()函数求解MATLAB求解命令：证明：2/1/2023例6.5试求解MATLAB求解命令：证明：2/1/2023最后一个式子改写成MATLAB求解命令：2/1/2023例6.6试求解MATLAB求解命令：2/1/2023证明：2/1/2023例6.7试求解带有参数的方程MATLAB求解命令：2/1/20236.1.3一般非线性方程数值解求出已知多元方程的一个实数根的函数调用格式最简求解语句一般求解语句2/1/2023选择方法和修改控制精度的函数调用格式获得默认的常用变量设置控制参数或2/1/2023求解数值代数方程组的步骤设置变量，使等式变成如下所示按如下方式描述等式M-函数匿名函数Inline函数，不推荐使用求解方程组检验阶的正确性2/1/2023例6.8Lambert函数，是变量，

是方程的解，对不同的，求解

然后绘制

求解策略和过程使用for循环使用匿名函数描述生成w向量绘制函数曲线MATLAB求解语句：2/1/2023MATLAB表述直接求解，使用lambertw函数2/1/2023例6.9数值方法求解选择变量把原始常微分方程组(ODEs)变为变成矩阵形式2/1/2023描述方程的方法M-函数匿名函数Inline函数2/1/2023当初值选为当使用另一个搜索初始点注意：选择不同的初值可以得出不同的结果2/1/2023例6.10数值方法解使用solve()函数：使用图解法求初始值：2/1/2023重新设置相关精度的控制变量所期望的精度可能无法达到然而，在算精度制下的最好结果可以得到2/1/20236.1.4非线性矩阵方程求解Riccati

方程（第4章）更多的非线性矩阵方程，例如，广义Riccati方程类Riccati方程还有很多很多的矩阵方程2/1/2023函数fsolve()只能求解出，而不是，其中，是向量不是矩阵将矩阵方程转换成向量方程向量转换成矩阵

数学表述

MATLAB表述矩阵转换成向量数学表述MATLAB表述Riccati方程求解2/1/2023以向量的形式描述Riccati方程的残差求解Riccati方程的新函数2/1/2023例6.11求解下列Riccati方程组：

其中2/1/2023are()

函数可能会得出一个解重新使用MATLAB命令：另一个解：2/1/2023例6.12给定其中求出并检验全部的根2/1/2023对于类Riccati方程另一个M-函数另一个矩阵方程求解函数2/1/2023重新使用MATLAB命令注意：有些解可能很难得到，需要反复调用多次上述函数2/1/2023已通过检验的可能解

2/1/20236.2无约束最优化问题求解解析解法和图解法基于MATLAB的数值解法全局最优解与局部最优解利用梯度求解最优化问题带有变量边界约束的最优化问题求解2/1/2023无约束最小化问题的数学描述目标函数是一个标量函数向量决定变量，或优化变量物理意义：求取一组

向量，使得最优化目标函数

为最小最大化问题数学描述2/1/20236.2.1解析解法和图解法无约束最优化问题的必要条件：其中，是最优点方程的求解可能会更难，有时可能需要二阶导数运算2/1/2023例6.13研究下式的最优性绘制函数的一阶导数2/1/2023求一阶导数为零的点，并验证二阶导数为正2/1/20236.2.2基于MATLAB的数值解法得出数值解的函数调用格式最简求解语句或一般求解格式或2/1/2023描述目标函数M-函数匿名函数Inline函数（不推荐使用）在匿名函数或inline函数中无法使用中间变量2/1/2023例6.14给定

，求其最小值

使用函数fminsearch()：使用函数fminunc()：2/1/2023绘制出搜索过程中间点的轨线：2/1/2023结果：2/1/20236.2.3全局最优解与局部最优解最小值存在的必要条件是使用搜索方法，从初始值出发，可能找到唯一的一个这样的点，它是全局最小值2/1/2023例6.15给定观察不同的初值得出的最小值构造目标函数初值是2/1/2023初值是在

内的曲线：在

内的曲线2/1/20236.2.4利用梯度求解最优化问题有时，仅利用目标函数提供的信息，很难得到最优解。这是由于求解最优化问题收敛速度一般较慢，尤其是变量较多的最优化问题可以利用梯度信息解决上述问题2/1/2023例6.16求Rosenbrock

函数的无约束最优化问题绘制三维等高线图：2/1/2023无梯度信息求梯度矩阵：2/1/2023编写目标函数：求解最优化问题2/1/20236.2.5带有变量边界约

束的最优化问题求解带有变量边界约束的最优化问题的数学描述

其中，符号s.t.表示subjecttoJohnD'Errico,woodchips@fminsearchbnd()函数在随书光盘中给出2/1/2023带有变量边界约束的最优化问题求解的语句调用格式最简求解语句

一般求解格式2/1/2023例6.17求解Rosenbrock问题其中，和

MATLAB求解语句2/1/20236.3有约束最优化

问题的计算机求解约束条件与可行解区域线性规划问题的计算机求解二次型规划的求解一般非线性规划问题的求解2/1/20236.3.1约束条件与可行解区域有约束非线性最优化问题的一般描述为其中，所有的

满足约束条件该范围称为可行解区域2/1/2023例6.18图解方法求解：目标函数描述可行解区域描述2/1/2023可行区域图解说明2/1/20236.3.2线性规划问题的计算机求解线性规划(LP)问题的一般数学描述为所有都是线性的注意，约束的标准形式2/1/2023求解LP问题的函数调用格式2/1/2023例6.19试求解下面的线性规划问题2/1/2023MATLAB求解语句：2/1/2023例6.20求解下列LP问题：先将原问题转换为最小值问题2/1/2023MATLAB求解命令2/1/2023例6.21是求解下列LP问题双下标描述2/1/2023将原问题转换成单下标自变量原问题改写成2/1/2023MATLAB求解命令2/1/20236.3.3二次型规划的求解一般二次型规划问题的数学表示为首先建立矩阵表述2/1/2023求解二次型规划问题的函数调用格式2/1/2023例6.22试求解下面的四元二次型规划问题首先求出相关矩阵形式2/1/2023展开目标函数得写成矩阵形式2/1/2023MATLAB求解语句其中，忽略了常数302/1/20236.3.4一般非线性规划问题的求解一般非线性规划问题其中，物理解释：在给出的约束条件下，找出向量，使目标函数达到最小值2/1/2023简化描述求解出非线性规划问题2/1/2023例6.23试求解下面非线性规划问题为目标函数和约束函数编辑M-函数，后者返回两个变量2/1/2023编辑非线性约束函数编辑目标函数2/1/2023使用函数fmincon()求解2/1/2023简化非线性约束条件函数：求出结果：2/1/2023例6.24利用梯度信息求解如下问题，并比较结果

2/1/2023推导Jacobian矩阵编写目标函数2/1/2023使用函数fmincon()得出结果2/1/20236.4混合整数规划

问题的计算机求解整数线性规划问题的求解一般非线性整数规划问题与求解0-1规划问题求解2/1/20236.4.1整数线性规划问题的求解整数线性规划的一般数学描述其中，

为变量

的子集2/1/2023求解整数线性规划问题的函数调用格式该免费工具箱，可以由MathWorks公司网站下载，也可以由本书光盘得出当前版本的ipslv_mex()函数不能用于低于MATLAB7.*的版本2/1/2023求解下列线性整数规划问题，其中，各个变量全为整数例6.252/1/2023MATLAB求解命令2/1/2023采用穷举算法，假定

的各个元素均为202/1/2023得出次最优解混合整数规划问题，要求

为整数，其他两个变量为任意数2/1/20236.4.2一般非线性整

数规划问题与求解分枝定界算法是一种最常用的处理非线性整数规划或混合规划问题的算法免费工具箱由

Mr.Keort

Kuipers提供

koertkuipers@该工具箱也附在由随书光盘上在MATLABR2008a中，薛定宇老师对其进行了简单的修改2/1/2023函数调用格式向量表示变量必须是整数，当表示变量可以是实数fun变量要是一个被引用的文件名，而不能是@...的形式如果err返回空，则求解成功2/1/2023补丁语句调用前调用后，截断多余的数字2/1/2023例6.26假定,使用函数bnb20()求解线性整数规划问题(ILP)编辑目标函数（不要编辑非匿名函数）2/1/2023求解出ILPerrmsg是空，求解成功2/1/2023如果要求

为整数，其他两个变量为任意数，则2/1/2023穷举法小结优点保证得出全局最优值除了最优值，还可以得出次最优值对于小规模问题，求解简便缺点带来很重的计算负担和极大的内存使用不可能求解大型甚至中型问题2/1/2023例6.27求出修改的Rosenbrock问题其中，并且是整数目标函数2/1/2023MATLAB求解语句：2/1/2023选择区间给定区间，使用穷举法2/1/20236.4.30-1规划问题求解0-1线性规划问题MATLAB求解函数0-1非线性规划问题，使用函数bnb20()将下界定义一个全为0的向量将上界定义一个全为1的向量直接使用函数bnb20()2/1/2023例6.28求解0-1线性规划问题MATLAB求解语句：2/1/2023枚举方法2/1/2023例6.29运用函数bnb20()求解下列问题构造目标函数：2/1/2023MATLAB求解语句：2/1/20236.5线性矩阵不等式问题求解线性矩阵不等式的一般描述Lyapunov不等式线性矩阵不等式问题分类线性矩阵不等式问题的MATLAB求解基于YALMIP工具箱的最优化求解方法2/1/20236.5.1线性矩阵不等式的一般描述线性矩阵不等式(LMI)的数学描述其中，为多项式系数向量，又称为决策向量，为实对称矩阵或复Hermit矩阵2/1/2023如果LMI矩阵是负定矩阵，那么解是凸集其中，多个线性矩阵不等式可以合并成单一的线性矩阵不等式2/1/20236.5.2Lyapunov不等式Lyapunov不等式的数学描述

其中，

是对称矩阵2/1/2023构造MATLAB函数求取2/1/2023接上页函数调用格式：2/1/2023例6.30给定试求出其线性矩阵不等式表示。对于矩阵，写出相应的线性矩阵不等式MATLAB求解语句：2/1/2023对于X矩阵线性矩阵不等式形式的数学描述2/1/2023对于的符号矩阵结果：2/1/2023给定分块矩阵其中，

是方阵，那么，下述三种况等价Schur补性质2/1/2023数学描述其中，原非线性不等式可以等价地变换成下述线性矩阵不等式代数Riccati不等式2/1/20236.5.3线性矩阵不等式问题分类可行解问题可行解问题实际上就是求下述的解其中要找到最小值如果找到的

，则得出的解是原问题的可行解，否则会提示无法找到可行解。2/1/2023线性目标函数最优化问题给定这样的问题可以用普通的线性规划方法求解2/1/2023广义特征值最优化问题广义特征值问题可以视为线性矩阵不等式问题的最一般的问题.表达式由该式演化可以得到更一般的不等式其中，是矩阵的广义特征值归纳出下面的最优化问题2/1/20236.5.4线性矩阵不等式

问题的MATLAB求解用MATLAB描述线性矩阵不等式创建LMI模型定义需要求解的变量其中，是未知矩阵类型的标记2/1/2023描述分块形式给出线性矩阵不等式

其中通常，该项是APB如果,那么k=-k如果flag==‘s’,该项是如果该项是常数，那么P=0，并且忽略B完成LMI模型描述2/1/2023求解LMI问题可行解问题线性目标函数问题广义特征值问题2/1/2023例6.31给定对于Riccati不等式试求出该不等式的一个正定可行解2/1/2023MATLAB求解语句：2/1/20236.5.5基于YALMIP工

具箱的最优化求解方法YALMIP(yetanotherLMIpackage)由瑞典Linköping

大学电子工程专业的JohanLöfberg博士开发,

johanl@isy.liu.se现在，它以成为最优化问题建模和求解的一种简便求解方法接近数学形式本书的随书光盘附带最新的版本2/1/2023决策变量的声明对称矩阵长方形矩阵整数变量二项形式其它形式，例如Hankel矩阵，hankel()2/1/2023约束可以通过[]来声明最优化问题求解求解可行解问题求解目标函数的最优化问题2/1/2023允许设定选项，如算法选择提取得出的解矩阵2/1/2023例6.32给定使用YALMIP工具箱求解Riccati不等式2/1/2023MATLAB求解命令比使用鲁棒控制工具箱(RCT)更方便2/1/2023例6.33求解线性规划问题MATLAB求解语句2/1/2023假设决策变量是整数2/1/2023例6.34对于线性系统其中2/1/2023采用LMI方法也可以求解系统的范数，其数学描述为

求解线性系统模型的范数2/1/2023MATLAB求解命令：2/1/20236.6多目标优化问题求解多目标优化模型无约束多目标函数的最小二乘求解多目标问题转换为单目标问题求解多目标优化问题的Pareto解集极小极大问题求解目标规划问题求解2/1/20236.6.1多目标优化模型多目标最优化问题的一般表示为其中，2/1/2023例6.35

三种糖果，单价每公斤4，2.8和2.4元，买糖果不超过20元，总量不得少于6公斤，

和

不得少于3公斤，设计方案设

购买量为

公斤，则2/1/20236.6.2无约束多目标

函数的最小二乘求解设目标函数将其转换成单目标问题MATLAB函数调用格式2/1/2023例6.36求解下面无约束非线性多目标规划问题的最小二乘解2/1/2023MATLAB求解语句使用函数fmincon()2/1/20236.6.3多目标问题转

换为单目标问题求解线性加权变换及求解线性规划问题的最佳妥协解线性规划问题的最小二乘解2/1/2023

线性加权变换及求解单目标优化算法不能直接由于求解多目标优化问题，需要将其变换成单目标优化问题线性加权变换的数学描述其中，且2/1/2023例6.37重新考虑例6.35，求解如下最优化问题2/1/2023不同加权系数下的方案2/1/2023不同加权系数下的最优方案2/1/2023

线性规划

问题的最佳妥协解特殊的线性规划数学描述目标函数不是一个向量，而是一个矩阵每一个目标函数2/1/2023最佳妥协解的求解步骤如下单独求解每个单目标函数的最优化问题，得出最优解通过规范化构造单独的目标函数最佳妥协解变换成单目标线性规划2/1/2023最佳妥协解（最大值）的求解程序2/1/2023例6.38重新考虑例6.35，求解如下最优化问题2/1/2023MATLAB求解语句：2/1/2023例6.39求解如下最优化问题2/1/2023MATLAB求解语句：2/1/2023

线性规划

问题的最小二乘解多目标线性规划问题的最小二乘表示则最小二乘解可以由函数直接得出2/1/2023例6.40给定如下最优化问题，试求其最小二乘解2/1/2023MATLAB求解语句：2/1/20236.6.4多目标优化

问题的Pareto解集对于双目标函数的问题，将可行解的离散点在二维平面上显示出来从得出的可行解离散点提取出区域左下角的一条曲线，这个曲线上的点都是原问题的解，称为Pareto解集2/1/2023YiCao

在Gianluca

Dorini

贡献的Pareto解集提取程序的基础上，开发了改进的快速提取程序函数调用格式其中，

为可行解、离散点构成的列向量，向量为标志向量，指示可行解离散点是否为Pareto解集中的点2/1/2023例6.41采用上述的离散点分析方法重新研究下述的多目标优化问题2/1/2023对原始问题中花费的钱数取一系列离散点原始问题可以改写成单目标的线性规划问题2/1/2023MATLAB求解语句：2/1/2023例6.42重新考虑例6.35，试提取其Pareto解集2/1/2023MATLAB求解语句：2/1/20236.6.5极小极大问题求解极小极大问题的数学描述极小极大问题是在最不利的条件下寻找最有利决策方案的一种方法2/1/2023直接求解极小极大问题的函数调用格式其中，目标函数为向量形式描述，用匿名函数、inline()函数和M-函数均可以表示新目标函数2/1/2023例6.43试求解下面的极小极大问题2/1/2023选择随机数为初值2/1/2023有了fminimax()函数，还可以求解相关的变形问题极小极小问题极小极大问题2/1/20236.6.6目标规划问题求解最优化问题求解过程中，发现找不到可行解时，要放松约束条件。如，不等式约束条件

改写成将偏差对

引入目标函数使得严格的不等式约束尽可能小地被突破，相应的最优化问题称为目标规划问题。2/1/2023数学描述形式其中，

为原始的多目标向量，

为各个目标函数的加权系数，

为用户人为引入的目标2/1/2023MATLAB函数调用格式2/1/2023例6.44试用目标规划方法求解下式2/1/2023两个目标函数可以接受的目标分别是20和6，将其权重设置80%和20%2/1/20236.7动态规划及其

在路径规划中的应用图的矩阵表示方法有向图的路径寻优无向图的路径最优搜索2/1/20236.7.1图的矩阵表示方法图是由节点和边构成的。边是连接两个节点的直接路径。如果边是有向的，则图称为有向图，否则称为无向图在计算机中，图用矩阵表示，即关联矩阵MATLAB语言还支持关联矩阵的稀疏矩阵表示方法2/1/2023构造关联矩阵的稀疏矩阵函数调用格式其中，为起始节点向量，为终止节点向量，为边权值向量，这里各个向量最后的一个值使得关联矩阵为方阵2/1/2023稀疏矩阵可以由full()函数变换成常规矩阵，而常规矩阵可以由sparse()函数转换成稀疏矩阵注意：在若第i和j节点间不存在边，则可令，当然，也有的算法要求2/1/20236.7.2有向图的路径寻优有向图最短路径问题的手工求解有向图搜索及图示Dijkstra最短路径算法及实现2/1/2023

有向图最短

路径问题的手工求解有向图与最优路径搜索是很多领域都能遇到的常见问题应用动态规划理论，通常需要由终点反推回起点，搜索最优路径2/1/2023例6.45有向图路径如下，数字为从该路径所花费的时间，试求出从节点①到节点⑨的最优路径。最短路径为：2/1/2023

有向图搜索及图示函数调用格式建立有向图对象求解最短路径问题函数view()可以显示有向图2/1/2023例6.46试求出从节点①到节点⑨的最优路径。2/1/2023建立关联矩阵并显示图2/1/2023求出最短路径2/1/2023

Dijkstra最

短路径算法及实现编辑MATLAB程序实现Dijkstra算法2/1/2023接上页2/1/2023函数的调用格式其中，W为关联矩阵