二次规划专题.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,“,”,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,“,”,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,线性规划与非线性规划,线性规划,(Linear Programming),在,一组线性约束定义的区域上，对一个线性函数进行极小化（或者极大化）的问题，其数学模型可以表示为,满足约束条件的点称可行点，可行点集合构成可行域,线性规划与非线性规划,非线性规划,(Nonlinear Programming),非线性规划的,数学模型可以表示为,在目标函数或者约束函数中至少有一个函数是非线性的,当非线性规划问题的可行域为整个实数域时，称为无约束优化问题，,否则称为约束优化问题,凸集、凸函数与凸优化,凸集：如果,某个集合中任意两点连起来的直线都属于该集 合，则称其为凸集，否则为非凸集,非凸集 凸集,凸集、凸函数与凸优化,凸集的数学定义：,是凸集当且仅当,成立,凸集、凸函数与凸优化,线性约束的可行集是凸集,证明：,凸集、凸函数与凸优化,凸函数,凸规划,目标函数为凸函数，可行集为凸集,的规划问题,Karush-Kuhn-Tucker,条件,对于非线性规划问题,引入,Lagrange,函数：,其关于,x,的梯度为：,Karush-Kuhn-Tucker,条件,KKT,条件可以表述为,这三行分别表示可行性条件、目标函数梯度的线性表示条件以及互补松弛条件,对于线性不等式约束的非线性规划问题，,KKT,条件是局部,极小值点的必要条件,对于凸规划问题，,KKT,条件是全局最优解的充要条件,二次规划,二次规划是非线性规划的一种特殊形式，其数学模型为：,约束条件为线性约束，故其可行集为凸集,目标函数为非线性函数，当,Hesse,矩阵,Q,是非负定矩阵时，,目标函数为凸函数，此时优化问题为凸二次规划问题,二次规划,二次规划的,KKT,条件为,：,凸二次规划的,KKT,解就是全局最优解,非凸二次规划的,KKT,解为局部极小值点,求解凸优化问题转化成求解,KKT,解的问题,二次规划,简单,的,KKT,条件,可以直接求解，复杂的可以采用投影梯度法求解,MATLAB,程序,线性规划,二次规划,MATLAB,程序,二次线性规划,二次规划,输出可调整为,为自变量,为目标函数值,迭代收敛到,超出设定的迭代次数,优化问题无界或者不可行,优化算法类型,算法的迭代次数,不等式约束的乘子,等式约束的乘子,变量下界和上界,案例分析,假设有四种投资,1,2,3,4,，第,i,种投资的收益率 的预期收益均值为 ，,方差 表示投资的风险大小，即收益率关于均值的偏离程度,令 为第,i,个项目的投资额占总投资的比例，向量 表示一个投资组合，则其对应的收益率为,记第,i,和,j,种项目投资收益率的相关系数,投资组合收益率,R,的方差为,案例分析,令收益率的协方差矩阵为 ，则上式可记为,令预期收益满足,在满足收益率条件下最小化风险模型：,案例分析,预期收益不小于,8.5,Q,社保债券,技术交易中心,管理咨询中心,游乐中心,社保债券,2,0.4,0.1,0,技术交易中心,0.4,4,3,-1,管理咨询中心,0.1,3,6,1,游乐中心,0,-1,1,10,预期收益,7,8,10,14,案例分析,各项投资比例为：,0.5418,0.2510,0.0503,0.1569,风险最小值,0.6137*2=1.2274,结语,规划问题属于运筹学（,Operations Research,）范畴，其计算使用,LINGO,、,MATLAB,、,Mathematica,等软件分分钟搞定,故而运筹学的核心不在于具体计算而在于,建模,！,Thank You,！,