第五讲---线性规划与二次规划

第五讲:线性规划与二次规划,-水鹏朗雷达信号处理国防科技重点实验室,数学建模基础,5.1线性规划举例,例1某工厂每日8小时产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。问题：为使总检验费用最省，应聘一级、二级检验员各几名？,优化变量：设需要一级和二级检验员的人数分别为x1，x2人,工资花费：,错检损失：,总花费：,约束条件：,5.1线性规划举例,线性规划：目标函数是线性函数，约束条件是线性不等式或等式约束。满足约束条件的所有点构成的集合称作可行解集合。,可行解集合,凸多边形区域,5.1线性规划举例,配餐问题,有m种不同类型的食物,，这些食物提供了有益于健康的n种营养成分。是人体每天对营养成分的最小需求量。是食物的单价.是每单位质量的食物包含营养成分的量。问题：如何配餐的花费代价最小？,优化变量：设每天食物的量分别是,花费代价：,营养约束：,5.1线性规划举例,线性规划,5.1线性规划举例,运输问题,有I个生产基地存储着某种货物，这些货物必须运至J个港口装船出口。生产基地存储货物的总量是,港口对货物运输能力是.设从基地到港口单位质量货品的运输价格是。问题：给出最节省的运输方案。,优化变量：设从基地运输到港口的货物量为,总运费：,存货量约束：,运输能力约束：,非负约束：,5.1线性规划举例,线性规划,标准化,5.1线性规划举例,数据拟合问题-Min_Max问题,设测定了一组数据,用次的多项式拟合变量和,问题:找一个n次多项式使得所有数据点的最大偏差是最小的。,问题描述,设多项式函数为,在每个数据点的偏差,5.1线性规划举例,问题描述(续),绝对值约束转化为线性约束,关于a的线性等式约束,引进辅助变量控制所有样本点的偏差,转下页,5.1线性规划举例,线性规划,5.1线性规划举例,线性分式规划问题-LinearFractionalProgramming,找出n维向量,使得线性分式函数,在非空、有界集合,基本假定：线性分式函数的分母在集合上是严格正的,上的最大值。,带线性约束的优化问题，可以直接求解，但很难说明得到的解是全局最优的。问题：如何转化为线性规划求解？,5.1线性规划举例,线性分式规划问题-LinearFractionalProgramming,注意到目标函数是齐次的(分子-分母都是线性的),因此，对分子分母同乘以正数，目标函数的值是不边的。所以，可以引入辅助变量t，使得分母,优化变量：,固定，然后最大化分子,目标函数：,5.1线性规划举例,线性分式规划问题-LinearFractionalProgramming,约束条件：,5.2线性规划的标准形式,求最大值的线性规划,求最小值的线性规划,5.3线性规划的性质,满足所有约束条件的向量构成的集合是线性规划的可行域，最优解是否存在取决于可行域的性质,线性规划的可行域是凸集；线性规划可能有解、无解或无界；线性规划的最优解在顶点上；,D是凸集对任意D内任意两点x、y的连线上所有点都在集合内，即对任意的实数0a1，点ax(1a)y在D中。,可行域有界,线性规划有解,可行域空集,线性规划无解,可行域无界,线性规划有解或无界,5.3线性规划的对偶问题,对偶优化问题,是一个mn的约束矩阵,在nm的情况下，可以把低维空间中带有很多约束的线性规划转换为高维空间中具有很少约束的线性规划。通过这种转化可以使一些线性规划的求解和分析更容易。,资源给定情况下最大化收益,收益固定情况下花费资源最小化,5.3线性规划的对偶问题,对偶优化问题,线性规划的有界可行是指目标函数在可行域上存在最大值(或最小值).可行域有界则线性规划必然有界可行；但线性规划有界可行不一定可行域一定有界。,例如：,可行域无界，但最大值是10，最小值是5,(I),(II),对偶定理：如果线性规划(I)是有界可行的，那么它的对偶规划(II)也是有界可行的，并且(I)的最大值与(II)的最小值相等。注：如果仅仅关心线性规划的最优函数值，求解线性规划和它的对偶中较简单的一个就可以，但最优点之间的对应关系不是简单直接的。,平衡定理(EquilibriumTheorem):设和是(I)和(II)的可行解，它们是(I)和(II)的最优解如果对所有i,则；如果对所有j,则,5.4线性规划求解软件,x,fval=Linprog(f,A,b),x,fval=Linprog(f,A,b,Aeq,beq),x,fval=Linprog(f,A,b,Aeq,beq,LB,UB),5.4线性规划求解软件,x,fval,exitflag=Linprog(f,A,b,Aeq,beq,LB,UB)returnsanexitflagthatdescribestheexitconditionofLinprog.Possiblevaluesofexitflagandthecorrespondingexitconditionsare1LinprogconvergedtoasolutionX.成功，得到了全局最优解！0Maximumnumberofiterationsreached.迭代次数达到了上限！-2Nofeasiblepointfound.没有可行点(可行区域可能是空集）！-3Problemisunbounded.目标函数在可行域上无下界！-4NaNvalueencounteredduringexecutionofalgorithm.算法运行中溢出！-5Bothprimalanddualproblemsareinfeasible.原规划与对偶规划都不可行！-7Magnitudeofsearchdirectionbecametoosmall;nofurtherprogresscanbemade.Theproblemisill-posedorbadlyconditioned.搜索方向的幅度太小，算法无法继续运行（问题可能是病态的！),5.5二次规划举例,数字滤波器设计问题,输入-输出关系时域(线性卷积)：频域(乘积）：,滤波器的频率响应线性时不变系统的传递函数,因果的FIR滤波器：,滤波器阶数,线性相位：,幅频响应,相频响应,5.5二次规划举例,线性相位滤波器的频率响应,线性相位：,滤波器系数,频率响应,变量替换m=2N-n,欧拉公式,5.5二次规划举例,理想低通滤波器,低通滤波器频带分割结构,设计要求：滤波器在通带的幅频响应尽可能接近1；滤波器在阻带的幅频响应近可能接近于零；滤波器在过渡带可以没有约束条件。,5.5二次规划举例,阻带能量,5.5二次规划举例,阻带波纹(StopbandRipple),5.5二次规划举例,通带均方误差(PassbandMeanSquareError),5.5二次规划举例,通带均方误差(PassbandMeanSquareError),阻带能量和通带均方误差都是滤波器系数向量x的二次非负函数，而阻带波纹约束是阻带区间上线性函数的绝对值的最大值约束。,5.5二次规划举例,通带波纹(PassbandRipple),5.5二次规划举例,设计策略1：阻带能量与通带均方误差加权最小化,最小化函数,加权系数(0,1),目标函数是多元二次函数，二次项矩阵正定，目标函数存在唯一最小值点,5.5二次规划举例,=0.25,=0.5,通带波纹比较,5.5二次规划举例,设计策略2：约束通带波纹下最小化阻带能量,在通带上对角频率进行等间隔采样离散化,目标函数是优化向量的二次函数，约束由2(K+1)个线性不等式构成,二次规划,5.5二次规划举例,设计策略2：约束通带波纹下最小化阻带能量,标准化,5.5二次规划举例,5.5二次规划举例,设计策略3：约束阻带波纹下最小化通带MSE,在阻带上对角频率进行等间隔采样离散化,目标函数是优化向量的二次函数，约束由2(K+1)个线性不等式构成.注意目标函数中的常数项可以去掉。,5.5二次规划举例,5.5二次规划举例,设计策略4：通带和阻带波纹约束设计(线性规划）,是两个辅助变量,用于控制阻带和通带波纹；而是一个预先给定的加权因子，用于实现阻带和通带波纹之间的一个折衷(妥协).,注1:优化变量变成了向量,注2:约束条件含有绝对值-非线性,注3:约束条件在区间上的连续变量。,解决策略？,5.5二次规划举例,去掉绝对值，非线性约束简化为两个线性约束,新的优化变量和目标函数,5.5二次规划举例,离散化,阻带约束,通带约束,5.5二次规划举例,5.5二次规划举例,滤波器系数,滤波器系数,幅频响应,幅频响应,通带波纹,通带波纹,5.6二次规划的一般形式,对称的nn的实矩阵,是m1n的矩阵，m1个不等式约束,是m2n的矩阵，m2个等式约束,是二次规划的可行域,5.6二次规划的一般形式,最优解的存在性条件,1.如果矩阵是非负定的，可行域非空且目标函数在可行域上有下界，则优化问题有全局最小值点(但可能不唯一）。,当优化问题的可行域是非空有界集合适，优化问题存在全局最小值点。,2.如果矩阵是正定的，并且可行域非空，那么优化问题具有全局最小值点，并且该最小值是唯一的。,5.6二次规划的一般形式,二次规划解的几何示意图,由5个线性不等式围成的可行域-凸五边形区域,全局最小值点，可行域边界与取值最小的二次函数等高线的切点。所有的等高线都是共心相似椭圆；在二次规划中，最优点不总是在可行域边界多边形的顶点上达到；在线性规划中，最优点总是在可行域边界多边形的顶点上达到。,5.6二次规划的一般形式,纯线性等式约束的二次规划,二次规划中仅包含线性的等式约束，并且约束的数目小于优化向量的维数。,拉格朗日乘子方法,是m1n的矩阵,拉格朗日方程组,n+m1个未知量，n+m1个方程的线性方程组，当方程组有唯一解时，二次规划具有唯一的全局最小值点。,5.6二次规划的一般形式,纯等式约束的二次规划求解举例,拉格朗日乘子方法,拉格朗日方程组,-2.0765027322404377.169398907103826-0.754098360655737-6.5136612021857945.896174863387979,fmin=64.218579234972708,5.7二次规划Matlab程序使用,一般在使用程序之前，先要检验矩阵是否对称，否则用代替；矩阵是否是正定或非负定的，采用矩阵的特征值分解，检验特征值是否全正或非负。,5.7二次规划Matlab程序使用,限定解在n维空间中的超长方体内x0是可以限定算法迭代求解过程中的初始点。理论上，二次规划的最优解不依赖于初始点，但计算时间与初始点有关。,5.7二次规划Matlab程序使用,程序运行终止信息解读,1QUADPROGconvergedwithasolutionX.(得到最优解）3Changeinobjectivefunctionvaluesmallerthanthespecifiedtolerance.(前后两次迭代中目标函数值的变化小于算法设定的最小变化，迭代终止）4Localminimizerfound.(陷入局部极小值点）0Maximumnumberofiterationsexceeded.(达到算法设定的最大迭代次数，迭代终止，输出终止时的点和函数值）-2Nofeasiblepointfound.(没有发现可行解，一般算法采用内点法，首先需要找到可行域内的一点作为初始点，原因：可行域是空集或可行域形状奇异）-3Problemisunbounded.(目标函数在可行域上无下界，一般因为矩阵H不是非负定的）-4Currentsearchdirectionisno