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

,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,雷达信号处理国防科技重点实验室,第五讲,:,线性规划与二次规划,-,雷达信号处理国防科技重点实验室,数学建模基础,1,5.1,线性规划举例,例,1,某工厂,每日,8,小时产量,不低于,1800,件。为了进行质量控制，计划聘请两种不同水平的检验员,。,一级,检验,员：,速度,25,件,/,小时，正确率,98%,，计时工资,4,元,/,小时；,二级检验,员：,速度,15,件,/,小时，,正确率,95%,，计时工资,3,元,/,小时。检验员每错检一次，工厂要损失,2,元,。,问题：,为,使总检验费用最省,，应聘,一级、二级检验员各几名？,优化变量：,设需要一级和二级检验员的人数分别为,x,1,，,x,2,人,工资花费：,错检损失：,总花费：,约束条件：,2,5.1,线性规划举例,线性规划：,目标函数是线性函数，约束,条件是线性不等式或等式约束。,满足约束条件的所有点构成的集合称作,可行解集合,。,可行解集合,凸多边形区域,3,5.1,线性规划举例,配餐问题,有,m,种不同类型的食物,，这些食物提供了有益于健康的,n,种营养成分 。 是人体每天对营养成分,的最小需求量。 是食物 的单价,.,是每单位质量的食物 包含营养成分 的量。,问题：,如何配餐的花费代价最小 ？,优化变量：,设每天食物 的量分别是,花费代价：,营养约束：,4,5.1,线性规划举例,线性规划,5,5.1,线性规划举例,运输问题,有,I,个生产基地 存储着某种货物，这些货物必须运至,J,个港口 装船出口。生产基地 存储货物的总量是,港口 对货物运输能力是,.,设从基地 到港口 单位质量货品的运输价格是 。,问题：,给出最节省的运输方案。,优化变量：,设从基地 运输到港口 的货物量为,总运费：,存货量约束：,运输能力约束：,非负约束：,6,5.1,线性规划举例,线性规划,标准化,7,5.1,线性规划举例,数据拟合问题,-Min_Max,问题,设测定了一组数据,用 次的多项式拟合变量 和,问题,:,找一个,n,次多项式使得所有数据点的最大偏差是最小的。,问题描述,设多项式函数为,在每个数据点的偏差,8,5.1,线性规划举例,问题描述,(,续,),绝对值约束转,化为线性约束,关于,a,的线性等式约束,引进辅助变量控制所有样本点的偏差,转下页,9,5.1,线性规划举例,线性规划,10,5.1,线性规划举例,线性分式规划问题,-Linear Fractional Programming,找出,n,维向量,使得线性分式函数,在非空、有界集合,基本假定：,线性分式函数的分母在集合上是严格正的,上的最大值。,带线性约束的优化问题，可以直接求解，但很难说明得到的,解是全局最优的。,问题：如何转化为线性规划求解？,11,5.1,线性规划举例,线性分式规划问题,-Linear Fractional Programming,注意到目标函数是齐次的,(,分子,-,分母都是线性的,),因此，对分子分母同乘以正数 ，目标函数的值是不,边的。所以，可以引入辅助变量,t,，使得分母,优化变量：,固定，然后最大化分子,目标函数：,12,5.1,线性规划举例,线性分式规划问题,-Linear Fractional Programming,约束条件：,13,5.2,线性规划的标准形式,求最大值的线性规划,求最小值的线性规划,14,5.3,线性规划的性质,满足所有约束条件的向量构成的集合,是线性规划的可行域，最优解是否存,在取决于可行域的性质,线性规划的可行域是,凸集,；,线性规划可能,有解、无解,或,无界,；,线性规划的最优解,在,顶点,上,；,凸集,凸集,非凸集,顶点,D,是凸集,对任意,D,内任意两点,x,、,y,的连线上所有点都在集合 内，即对任意的实数,0,a,1,，点,ax,(1,a,),y,在,D,中。,可行域有界,线性规划有解,可行域空集,线性规划无解,可行域无界,线性规划有解或无界,15,5.3,线性规划的对偶问题,对偶优化问题,是一个,m,n,的约束矩阵,在,n,m,的情况下，可以把低维空间中带有很多约束的线性规划转换为高维空间中具有很少约束的线性规划。通过这种转化可以使一些线性,规划的求解和分析更容易。,资源给定情况下最大化收益,收益固定情况下花费资源最小化,16,5.3,线性规划的对偶问题,对偶优化问题,线性规划的有界可行是,指目标函数在可行域上,存在最大值,(,或最小值,).,可行域有界则线性规划,必然有界可行；但线性,规划有界可行不一定可,行域一定有界,。,例如,：,可行域无界，但,最大值是,10,，最小值是,5,(I),(II),对偶定理,：如果线性规划,(I),是有界可行的，,那么它的对偶规划,(II),也是有界可行的，并,且,(I),的最大值与,(II),的最小值相等。,注：如果仅仅关心线性规划的最优函数值，求解线,性规划和它的对偶中较简单的一个就可以，但最,优点之间的对应关系不是简单直接的。,平衡定理,( Equilibrium Theorem):,设 和 是,(I),和,(II),的可行解，它们是,(I),和,(II),的最优解 如果对所有,i,则,；如果对所有,j,则,17,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),18,5.4,线性规划求解软件,x,fval,exitflag = Linprog(f, A, b, Aeq, beq, LB, UB) returns an,exitflag,that describes the exit condition of Linprog. Possible values of,exitflag,and the corresponding exit conditions are,1 Linprog converged to a solution X.,成功，得到了全局最优解！,0 Maximum number of iterations reached.,迭代次数达到了上限！,-2 No feasible point found.,没有可行点,(,可行区域可能是空集）！,-3 Problem is unbounded.,目标函数在可行域上无下界！,-4 NaN value encountered during execution of algorithm.,算法运行中溢出！,-5 Both primal and dual problems are infeasible.,原规划与对偶规划都不可行！,-7 Magnitude of search direction became too small; no further progress can be made. The problem is ill-posed or badly conditioned.,搜索方向的幅度太小，算法无法继续运行 （问题可能是病态的！,),19,5.5,二次规划举例,数字滤波器设计问题,输入,-,输出关系,时域,(,线性卷积,),：,频域,(,乘积）：,滤波器的频率响应,线性时不变系统的传递函数,因果的,FIR,滤波器：,滤波器阶数,线性相位：,幅频响应,相频响应,20,5.5,二次规划举例,线性相位滤波器的频率响应,线性相位：,滤波器系数,频率响应,变量替换,m=2N-n,欧拉公式,21,5.5,二次规划举例,理想低通滤波器,通带,过渡带,阻带,低通滤波器频带分割结构,设计要求：,滤波器在通带的幅频响应尽可能接近,1,；,滤波器在阻带的幅频响应近可能接近于零；,滤波器在过渡带可以没有约束条件。,22,5.5,二次规划举例,阻带能量,23,5.5,二次规划举例,阻带波纹,(Stopband Ripple),24,5.5,二次规划举例,通带均方误差,(Passband Mean Square Error),25,5.5,二次规划举例,通带均方误差,(Passband Mean Square Error),阻带能量和通带均方误差都是滤波器系数向量,x,的,二次非负函数，而阻带波纹约束是阻带区间上线性,函数的绝对值的最大值约束。,26,5.5,二次规划举例,通带波纹,(Passband Ripple),27,5.5,二次规划举例,设计策略,1,：阻带能量与通带均方误差加权最小化,最小化函数,加权系数,(0,1),目标函数是多元二次函数，二次项矩阵正定，目标函数存在唯一最小值点,28,5.5,二次规划举例,=0.25,=0.5,通带波纹比较,29,5.5,二次规划举例,设计策略,2,：约束通带波纹下最小化阻带能量,在通带 上对角频率,进行等间隔采样离散化,目标函数是优化向量的二次函数，,约束由,2(K+1),个线性不等式构成,二次规划,30,5.5,二次规划举例,设计策略,2,：约束通带波纹下最小化阻带能量,标准化,31,5.5,二次规划举例,32,5.5,二次规划举例,设计策略,3,：约束阻带波纹下最小化通带,MSE,在阻带 上对角频率,进行等间隔采样离散化,目标函数是优化向量的二次函数，,约束由,2(K+1),个线性不等式构成,.,注意目标函数中的常数项可以去,掉。,33,5.5,二次规划举例,34,5.5,二次规划举例,设计策略,4,：通带和阻带波纹约束设计,(,线性规划）,是两个辅助变量,用于,控制阻带和通带波纹；而,是一个预先给定的,加权因子，用于实现阻带和通带波纹之间的一个折衷,(,妥协,).,注,1:,优化变量变成了向量,注,2:,约束条件含有,绝对值,-,非线性,注,3:,约束条件在区间上,的连续变量。,解决策略？,35,5.5,二次规划举例,去掉绝对值，非线性约束简化为两个线性约束,新的优化变量和目标函数,36,5.5,二次规划举例,离散化,阻带约束,通带约束,37,5.5,二次规划举例,38,5.5,二次规划举例,滤波器系数,滤波器系数,幅频响应,幅频响应,通带波纹,通带波纹,39,5.6,二次规划的一般形式,对称的,n n,的实矩阵,是,m1 n,的矩阵，,m1,个不等式约束,是,m2 n,的矩阵，,m2,个等式约束,是二次规划的可行域,40,5.6,二次规划的一般形式,最优解的存在性条件,1.,如果矩阵 是非负定的，可行,域非空且目标函数在可行域上有,下界，则优化问题有全局最小值,点,(,但可能不唯一）。,是非负定的，如果对任意的非,零向量 ，有,矩阵的所有特征值非负。,当优化问题的可行域是非空,有界集合适，优化问题存在,全局最小值点。,2.,如果矩阵 是正定的，并且可行域非空，那么优化问题具有全局最小值点，并且该最小值是唯一的。,是正定的，如果对任意的非,零向量 ，有,矩阵的所有特征值大于零。,41,5.6,二次规划的一般形式,二次规划解的几何示意图,由,5,个线性不等式围成的,可行域,-,凸五边形区域,全局最小值点，可行域,边界与取值最小的二次,函数等高线的切点。,所有的等高线都是共心,相似椭圆；,在二次规划中，最优点,不总是在可行域边界多边,形的顶点上达到；,在线性规划中，最优点,总是在可行域边界多边形,的顶点上达到。,42,5.6,二次规划的一般形式,纯线性等式约束的二次规划,二次规划中仅包含线性的等,式约束，并且约束的数目小,于优化向量的维数。,拉格朗日乘子方法,是,m1 n,的矩阵,拉格朗日方程组,n+m1,个未知量，,n+m1,个方程的线性方程组，当方程组有唯一解时，二次规划具有唯一的全局最小值点。,43,5.6,二次规划的一般形式,纯等式约束的二次规划求解举例,拉格朗日乘子方法,拉格朗日方程组,-2.0437,7.169398907103826,-0.7547,-6.5794,5.896174863387979,fmin=64.218579234972708,44,5.7,二次规划,M atlab,程序使用,一般在使用程序之前，先要检验矩阵,是否对称，否则用 代替；,矩阵 是否是正定或非负定的，采用,矩阵的特征值分解，检验特征值是否全,正或非负。,45,5.7,二次规划,M atlab,程序使用,限定解在,n,维空间中的超长方体内,x0,是可以限定算法迭代求解过程中,的初始点。理论上，二次规划的最优解不依赖于初始点，但计算时间,与初始点有关。,46,5.7,二次规划,M atlab,程序使用,程序运行终止信息解读,1 QUADPROG converged with a solution X.,(,得到最优解）,3 Change in objective function value smaller than the specified tolerance.,(,前后两次迭代中目标函数值的变化小于算法设定的最小变化，迭代终止,）,4 Local minimizer found.,(,陷入局部极小值点）,0 Maximum number of iterations exceeded.,(,达到算法设定的最大迭代次数，迭代终止，输出终止时的点和函数值,）,-2 No feasible point found.,(,没有发现可行解，一般算法采用内点法，首先需要找到可行域内的一点作为初始点，原因：可行域是空集或可行域形状奇异）,-3 Problem is unbounded.,(,目标函数在可行域上无下界，一般因为矩阵,H,不是非负定的）,-4 Current search direction is not a descent direction; no further progress can be made,. (,从当前点出发，找不到下降方向，算法终止）,-7 Magnitude of search direction became too small; no further progress can be made. The problem is ill-posed or badly conditioned.,(,搜素方向幅度太小）,47,作业,用前面讲的四种设计策略之一，设计偶数长度的线性相位低通滤波器。滤波器阶数,49,通带截止频率,0.2,，通带截止频率,0.25,优化变量,48,