前面两篇介绍了关于线性规划和混合整数线性规划的相关知识,相信各位对于线性规划这一部分已经有了一些基本的了解了,如果有兴趣进一步去了解有关线性规划的知识的话,可以去参照线性规划教材,欢迎大家一起交流。
General nonlinear programming(NLP)一般非线性规划
定义
前面已经介绍了线性规划的一些简单定义,即目标函数和约束条件都是线性函数一类约束规划。非线性规划,顾名思义,其实就是非线性类的规划,所谓的非线性指的是目标函数或者约束条件至少有一个是非线性函数。
模型
模型非线性规划的一般标准形式如下所示:
分类
非线性规划主要分为以下几类:
1.凸规划
关于凸规划,首先需要了解什么叫凸函数。关于凸函数的概念,我们可以通过如下不等式来进行定义:
符合上述不等式的我们称f(x)为S上的凸函数。
为了帮助大家理解这一函数,我们假设参数α=1/2,那么可以等式可以转化为
那么通过如一简图如下所示:
从上图可以明显看到曲线y=f(x)的特征,当函数形状为向下凸出时,我们可以称之为凸函数。而凸规划则是指,约束条件中不等式g(x)为凸函数,h(x)为线性函数,目标函数f(x)为凸函数的规划。
2. 二次规划
关于二次规划,由于在系列介绍OPTMODEL中下一篇会讲到,因此本篇略过不讲。
3.几何规划
几何规划为非线性规划的一个分支,它的目标函数和约束条件均由广义多项式构成,这是一类特殊的非线性规划,利用其对偶原理,可以把高度非线性问题的求解转化为具有线性约束的优化问题求解,使计算大为简化。所谓的广义多项式是指优化变量的乘幂的连乘积的代数和形式,或其等价形式。其函数一般形式如下所示:
上述函数可以拆分为两个阶段来理解:第一阶段为后面的优化变量的乘幂的连乘积;第二阶段则为第一阶段得到的结果的代数和。
算法
算法非线性规划求解算法种类较多,由于非线性模型的非线性性质,我们通常求解得到的可行解都是局部最优解,即我们不能保证在变量满足的所有可行域里此可行解是最优的(凸规划例外,具体有兴趣的话可以自行进一步研究),但是可以保证在此可行解对应的可行域附近是最优的,因此针对不同类型的非线性规划问题,对应不同的算法求解。由于本系列主要侧重于对OPTMODEL的分享,因此不再一一介绍对应的算法,后面将通过案例来介绍如何通过OPTMODEL来求解NLP问题。
案例
接下来将为大家介绍一个案例:Rosenbrock 问题。Rosenbrock问题是在数学约束规划理论中非常经典的一个问题,它对应的函数我们称之为Rosenbrock函数,Rosenbrock函数有一个很有趣的特征,它的每个等高线是一个窄长弯曲的山谷,形状像香蕉,俗称香蕉函数,是经典算例之一,也是公认的能用来有效的评价算法的性能。
Rosenbrock问题对应目标函数如下所示:
SAS代码如下所示:
运行程序之后,我们可以得到如下结果:
运行时间在log中如下所示:
NOTE: “PROCEDURE OPTMODEL”所用时间(总处理时间):
实际时间 4.28 秒
CPU 时间 3.62 秒
从模型结果来看,模型问题为非线性规划(NLP)问题,模型采用的算法为内点法(Interior Point),并达到最优化(Optimal),且最终得到最优结果为0。
关于算法内点法,是求解非线性规划的一个性能不错的一个算法,它的原理是通过构造一个惩罚函数来遍历内部可行域搜索最优解,关于这个算法的具体详细介绍,如果有兴趣的可以参照下面这位博主的博客:【http://blog.csdn.net/dymodi/article/details/46441783】
非线性规划除了OPTMODEL这一过程步可以进行求解外,SAS中还有NLP过程也可以进行相应的求解,如果有兴趣可以自行去了解一下。
微信公众号:mingfeng07数据搬运工
个人微信:xiaopengpeng07
欢迎加我微信一起来愉快地玩耍啦!