运筹学 第2版 课件 第6章 非线性规划1

JournalonComputing第6章

非线性规划CONTENTS01非线性规划问题的基本概念03凸函数与凸规划局部极值与全局极值0204无约束非线性规划问题05约束非线性规划问题PART01非线性规划问题的基本概念引例1：某证券公司投资组合预期收益与风险决策问题小赵是某证券公司的职业经理人，负责证券投资的管理工作，在他进行投资决策时不仅会关注该项目所能带来的预期回报，还会兼顾投资风险，通过给不同的项目分配不同比例的资金来尽可能达到收益与风险的最佳平衡。现公司准备投入一笔资金来购买市场上的三支股票A，B，C，投资部门对股票历史收益数据进行了调研与评估获得了这三支股票的预期收益投资风险（标准差）以及每两支股票投资组合的交叉风险（协方差）。非线性规划问题的基本概念已知股票A的预期收益为21%，投资风险为25%，股票B的预期收益为30%，投资风险为45%，股票C的预期收益为8%，投资风险为5%，当投资组合为A与C时，交叉风险为-0.005；当投资组合为A与B时，其交叉风险为0.040；当投资组合为B与C时，交叉风险为0.010。非线性规划问题的基本概念

非线性规划问题的基本概念

非线性函数

非线性非线性规划问题的基本概念

解：设投资决策变量为非线性规划问题的基本概念

非线性规划问题的基本概念另外，最佳的投资方案应满足投资额最小而总收益最大的方案，所以最佳投资决策问题可以归结于在总资金以及决策变量（取0或1）的限制条件下，最大化总收益与总投资之比。因此该问题的数学模型可以表示为：

非线性函数

非线性规划问题的基本概念工地位置123456812610812非线性规划问题的基本概念

非线性规划问题的基本概念因此该数学模型可以表达为以下形式：

非线性函数非线性规划问题的基本概念目标函数或约束条件不同：线性规划的目标函数和约束条件都是其决策变量的线性函数（一次式）；非线性规划的目标函数或约束条件是其决策变量的非线性函数（含有非线性成分）。最优解范围不同：如果最优解存在，线性规划只能存在可行域的边界上找到；非线性规划的最优解可能存在于可行域的任意一点。非线性规划与线性规划问题相比，区别主要在以下两个方面：非线性规划问题的基本概念非线性规划数学模型一般形式

所以我们也经常将非线性规划的数学模型写做无等式形式（即约束条件中不出现等式）：

非线性规划问题的基本概念当非线性规划问题只有一个或者两个自变量时，可以利用图解法进行求解。非线性规划的图解法就是用几何作图的方法分析并求出最优解的过程，其大致思路如线性规划图解法相类似，下面用一个例子来讨论图解法的求解过程。

如左图所示，该非线性规划的可行域为一条垂直于水平轴的直线，圆形弧线为目标函数等值线，当目标函数等值线与直线相切时，可以得到相切点非线性规划问题的基本概念

PART02局部极值与全局极值局部极值与全局极值

局部极小值与严格局部极小值：

局部极值与全局极值

全局极小值与严格全局极小值：

局部极值与全局极值

局部极小点全局极小点局部极值与全局极值PART03凸函数与凸规划凸函数与凸规划在对学习凸函数之前，需要了解以下基础知识

凸函数与凸规划

凸函数与凸规划凸函数的定义

凸函数与凸规划

几何意义：凸函数图形上的任意两点的连线都在这个图形的上方，就是向下凸的。凹函数则相反。凸函数与凸规划例6.4

请判定以下函数是否为凸函数。

根据凸函数的定义需要判断以下表达式的正负：

整理上式可得

凸函数与凸规划凸函数的性质

凸函数与凸规划现对定理6.2进行证明：

将以上两式相加得：

凸函数与凸规划

凸函数与凸规划凸函数的判定在判定一个函数是否为凸函数时，可以根据其定义进行判断，这种方法较为直观且适用于各种类型的函数，但对于较为复杂的函数使用这种方法往往需要深入的数学分析，判定过程较为繁琐。如果某一函数是可导函数时，则可以利用函数的导数信息进行判断。凸函数与凸规划泰勒公式（TaylorFormula）

其中

凸函数与凸规划(1)一阶条件

凸函数与凸规划证明：首先证明其必要性：

将上式变形为

由泰勒公式可知：

将其代入上式得：

凸函数与凸规划其次证明其充分性：

凸函数与凸规划

凸函数的定义式实质上是说明凸函数上两点之间的线性插值不低于两点之间函数的值，而该定理说明函数上某点导数的线性近似不高于这个点的函数值。凸函数与凸规划凸函数的判定二阶条件

凸函数与凸规划

凸函数与凸规划

凸函数的根本重要性就在于定理6.6的这个基本性质。凸函数与凸规划例6.5：请判断以下二次函数的凹凸性解：本题可利用凸函数的二阶条件进行判定。首先求得该函数的海赛矩阵如下：

凸函数与凸规划凸规划对于非线性规划式：定义6.7若某一非线性规划的目标函数为凸函数，可行域为凸集，则称该非线性规划为凸规划，即

凸函数与凸规划

凸函数与凸规划凸规划的性质可行解集为凸集。最优解集为凸集（假定最优解存在）。任何局部最优解也是其全局最优解。若目标函数为严格凸函数，且最优解存在，则其最优解必唯一。凸规划是一类比较简单且具有重要意义的非线性规划，如果某个问题是凸规划问题或能将其描述为凸规划问题将会大有裨益。凸函数与凸规划例6.6：请判定以下非线性规划问题是否是凸规划问