第四讲: 多变量优化模型,-水鹏朗 雷达信号处理国防科技重点实验室,数学建模基础,4.1 多变量优化建模举例,一家彩色电视制造商计划推出19-英寸和21英寸两款LCD平板电视机, 制造商建议零售价格(MSRP)分别是$339/台和$399/台. 制造商给销售公司的价格是每台$195和$225,附加$400,000的固定费用(代理费).市场环境对销售影响(1) 对于每款电视机，每多买一台该款电视机平均销售价格降1美分;(2) 21寸的每买一台,19寸的平均售价减小0.3美分;(3) 19寸的每买一台,21寸的平均售价减小0.4美分; 问题: 制造商两款电视机应该各生产多少台？,19英寸LCD电视机,21英寸LCD电视机,销售商获利最大,4.1 多变量优化建模举例,符号化(变量),基本假设(变量间相互关系),s-19寸TV售出台数 t-21寸TV售出台数 p-19寸售出价格 q-21寸售出价格 C-获得这些电视机的成本 R-销售这些电视机的总收入 P-销售这些电视机的总利润,黑色变量-决策/优化变量 蓝色变量-中间变量 红色变量-优化变量,4.1 多变量优化建模举例,优化模型,目标函数的图像,目标函数的等高线,4.2 多元函数极值点的判断准则,设 是一个至少二阶可微分的n元函数 (充分条件:所有的二阶偏导数存在且连续),f(x)的梯度向量和Hessian矩阵定义为:,4.2 多元函数极值点的判断准则,二阶泰勒展开,对于一个对称的nn的方阵A, 如果对于任何的非零向量x, 矩阵称作正定的, 矩阵称作非负定的 , 矩阵称作负定的,矩阵称作非正定的,满足的点称作函数f(x)驻点. 按照二阶泰勒展开,在 驻点的附件,函数值满 足:,4.2 多元函数极值点判断,极大值点与极小值点条件,4.2 多元函数极值点判断,模型求解,求解线性方程组,最优的生产方案是:19寸生产4735台,21寸 生产7043台, 最大利润为 553641(美元),这种求多变量优化问题的解析方法(解线性方程组)仅在目标函数是优化变量的二次函数时有效. 对于复杂函数必须采用专门的优化算法求解 问题.,4.3 无约束优化问题的求解方法,f(x)是可微分的n-元函数,目标函数是二次函数的情况,n=1情况,(1) a0, 抛物线开口向上,(2) a0, 抛物线开口向下,n1情况,函数存在唯一的驻点,对称矩阵,(1) A是正定矩阵,(2) A是负定矩阵,(3) A既有正特征值,也有负特征值 , x*是一个鞍点, 函数没有最大值点,也没有 最小值点.,4.3 无约束优化问题的求解方法,最速下降法,基本思想: 从一个初始点出发, 沿着函数值下降最快的负梯度方向搜达到该方向上的最小值点, 从这点出发 重复迭代搜索直到满终止条件. 单步搜索过程描述,最速下降方向, 搜索方向,迭代格式, 步长待定,步长的单变量函数,确定最优搜索步长,更新搜索起点,4.3 无约束优化问题的求解方法,函数图像,极小值点,注1: 最速下降方法总是收敛到一个驻点,收敛到哪一个驻点于 初始点 的位置有关.,4.3 无约束优化问题的求解方法,等高线图,注2: 最速下降法在接近极小值点是会出现震荡现象,收敛速度很慢. 注3: 在每个极小值附近,函数的性态可以用抛物面近似,等值线近似于同心椭圆,椭圆的中心是极值点. 等值线椭圆偏心率越大,最速下降法收敛越慢.,迭代过程示意图,4.3 无约束优化问题的求解方法,牛顿迭代法,基本思想: 在每个迭代点上,把函数在这点进行二阶泰勒展开,用展开的二次函数的极小值点进行更新. 在 点计算函数的梯度和Hessian矩阵, 函数在 附近用二次函数近似,4.3 无约束优化问题的求解方法,其它解无约束非线性规划的方法,共轭梯度方法,各种修正的Newton法,4.3 无约束优化问题的求解方法,优化向量的范围限制,4.4 等式约束的多变量优化问题,问题描述的一般形式,约束条件,目标函数,优化向量, 决策向量,可行解集合,一般情况下等式约束的数目要小于优化向量的维数,否则可行解集合可能是空集,优化问题无解.,n+m个方程，n+m个未知数，适定方程组,4.4 等式约束的多变量优化问题,拉格朗日乘子法,驻点,拉格朗日方程组,Edwards, 1973 在 是线性独立向量的情况下， 是目标函数 在S上的极值点，那么它必然是Largrange方程组的解。,求函数 在椭圆 上的最大值,4.4 等式约束的多变量优化问题,拉格朗日乘子法算例,辅助函数,拉格朗日方程组,最小值点,最大值点,两颗行星围绕恒星在各自的椭圆轨道上运行，轨道位于同一平面，各自的运行周期(一年的时间）分别为 和 ， 和 是不可约的，求两颗行星之间的最短和最常距离。,4.4 等式约束的多变量优化问题,行星最近距离的优化建模与求解,在行星轨道平面上建立直角坐标系，椭圆中心为坐标原点，中心与恒星的连线为x轴XOY；伴随地建立极坐标系(O, ).,基本假设与建模准备,轨道方程,T1和T2不可约是指不存在非负的正整数对(m,n),使得,4.4 等式约束的多变量优化问题,基本假设与建模准备(续）,1(t)和2(t)是满足：,的连续函数。,模型1：无约束建模,t的高度非线性函数,4.4 等式约束的多变量优化问题,这样一个优化问题虽然形式上是无约束优化，但存在太多的局部极值点，发现最大值和最小值异常困难。例如参数满足：目标函数随时间变化的曲线如下：,4.4 等式约束的多变量优化问题,对于行星1轨道上的任意一点A ,行星经过这点的时刻是：,模型2：约束优化模型,在这些时刻行星2在轨道上的位置是:,由于两个周期是不可约的，上述集合在行星2的轨道上是稠密的，因此行星1在轨道上A点，到行星2的最短距离是：,4.4 等式约束的多变量优化问题,行星1到行星2的最小距离为,带两个等式约束的优化问题，优化 变量是四维的。,4.4 等式约束的多变量优化问题,拉格朗日乘子法,拉格朗日方程,求 解 非 线 性 方 程 组,参数化方法,无约束优化问题,4.4 等式约束的多变量优化问题,4.5 不等式约束的多变量优化问题,一家彩色电视制造商计划推出19-英寸和21英寸两款LCD平板电视机, 制造商建议零售价格(MSRP)分别是$339/台和$399/台. 制造商给销售公司的价格是每台$195和$225,附加$400,000的固定费用(代理费).市场环境对销售影响(1) 对于每款电视机，每多买一台该款电视机平均销售价格降1美分;(2) 21寸的每买一台,19寸的平均售价减小0.3美分;(3) 19寸的每买一台,21寸的平均售价减小0.4美分;生产商生产能力限制由于产品更新换代,生产能力有限,19寸年产不超过5000台，21寸年产不超过8000台，19寸和21寸年产总量不超过10000台。 问题: 制造商两款电视机应该各生产多少台？,4.5 不等式约束的多变量优化问题,优化模型,目标函数是双变量二次函数，约束条件由5个线性 不等式约束构成 -约束二次规划,4.5 不等式约束的多变量优化问题,不等式约束的多变量优化问题,通过适当处理转 化成无约束优化 问题进行求解,最速下降法牛顿迭代法共轭梯度法修正牛顿迭代法,4.5 不等式约束的多变量优化问题,惩罚函数方法,引进一个辅助函数,其中 和 是正数，称作等式约束和不等式约束的惩罚因子。,惩罚项,可行解集合,当一个点不在可行解集合中时，R个等式约束和S个不等式约束中至少有一个不成立。这种情况下，惩罚项将是正的。该点偏离可行解集越远，惩罚项越大。因此，惩罚项的存在倾向于在可行解集上或可行解集附近寻找辅助函数的最小值。,4.5 不等式约束的多变量优化问题,惩罚函数的作用,标准化,辅助函数,4.5 不等式约束的多变量优化问题,4.5 不等式约束的多变量优化问题,求解无约束 优化 问题,验证约束 条件是否 近似成立,4.5 不等式约束的多变量优化问题,拉格朗日乘子方法,前面的拉格朗日乘子方法主要 用于等式约束的情况。对于具 有不等式约束的优化问题，使 用拉格朗日乘子方法的关键在 于如何把不等式约束转化为等 式约束。,不等式约束,等价于,存在某个数 使得等式成立,4.5 不等式约束的多变量优化问题,4.5 不等式约束的多变量优化问题,辅助函数,拉格朗日方程组,求解方程组,4.5 不等式约束的多变量优化问题,算例,作业,1.用拉格朗日乘子法求解问题,2.一电路由三个电阻R1,R2,R3并联，再与电阻R4串联而成。记Rk上的电流是Ik,电压是Vk,在下列情况下 确定Rk，使电路的总功率最小(k=1,2,3,4),其中 I1=4 I2=6 I3=8,2Vk 10。(列出优化问题即可）,