线性规划与二次规划.pptx

第五讲第五讲: : 线性规划与二次规划线性规划与二次规划 -水鹏朗 雷达信号处理国防科技重点实验室 数学建模基础 雷达信号处理国防科技重点实验室 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 a的线性等式约束的线性等式约束 引进辅助变量控制所有样本点的偏差引进辅助变量控制所有样本点的偏差 转下页转下页 雷达信号处理国防科技重点实验室 5.1 线性规划举例 线性规划 雷达信号处理国防科技重点实验室 5.1 线性规划举例 线性分式规划问题线性分式规划问题-Linear Fractional Programming-Linear Fractional Programming 找出n维向量 ,使得线性分式函数 在非空、有界集合 基本假定：线性分式函线性分式函 数的分母在集合上是严数的分母在集合上是严 格正的格正的 上的最大 值。 带线性约束的优化问 题，可以直接求解， 但很难说明得到的 解是全局最优的。 问题：如何转化为线 性规划求解？ 雷达信号处理国防科技重点实验室 5.1 线性规划举例 线性分式规划问题线性分式规划问题-Linear Fractional Programming-Linear Fractional Programming 注意到目标函数是齐次的(分子-分母都是线性的),因 此，对分子分母同乘以正数 ，目标函数的值是不 边的。所以，可以引入辅助变量t，使得分母 优化变量： 固定，然后最大化分子 目标函数： 雷达信号处理国防科技重点实验室 5.1 线性规划举例 线性分式规划问题线性分式规划问题-Linear Fractional Programming-Linear Fractional Programming 约束条件： 雷达信号处理国防科技重点实验室 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)的最小值相等。 注：如果仅仅关心线性规划的最优函数值，求解线注：如果仅仅关心线性规划的最优函数值，求解线 性规划和它的对偶中较简单的一个就可以，但最性规划和它的对偶中较简单的一个就可以，但最 优点之间的对应关系不是简单直接的。优点之间的对应关系不是简单直接的。 平衡定理平衡定理( Equilibrium Theorem): ( Equilibrium Theorem): 设 和 是(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) returns an exitflagexitflag that describes the exit condition of Linprog. Possible values of exitflagexitflag 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. 搜索方向的幅度太小搜索方向的幅度太小 ，算法无法继续运行，算法无法继续运行 （问题可能是病态的！（问题可能是病态的！) ) 雷达信号处理国防科技重点实验室 5.5 二次规划举例 数字滤波器设计问题 输入-输出关系 时域(线性卷积)： 频域(乘积）： 滤波器的频率响应 线性时不变系统的传递函数 因果的因果的FIRFIR滤波器：滤波器： 滤波器 阶数线性相位：线性相位： 幅频响应 相频响应 雷达信号处理国防科技重点实验室 5.5 二次规划举例 线性相位滤波器的频率响应 线性相位：线性相位： 滤波器系数滤波器系数 频率响应频率响应 变量替换变量替换m=2N-nm=2N-n 欧拉公式欧拉公式 雷达信号处理国防科技重点实验室 5.5 二次规划举例 理想低通滤波器 通带通带过渡带过渡带 阻带阻带 低通滤波器频带分割结构 设计要求： 滤波器在通带的幅频响 应尽可能接近1； 滤波器在阻带的幅频响 应近可能接近于零； 滤波器在过渡带可以没 有约束条件。 雷达信号处理国防科技重点实验室 5.5 二次规划举例 阻带能量 雷达信号处理国防科技重点实验室 5.5 二次规划举例 阻带波纹(Stopband Ripple) 雷达信号处理国防科技重点实验室 5.5 二次规划举例 通带均方误差(Passband Mean Square Error) 雷达信号处理国防科技重点实验室 5.5 二次规划举例 通带均方误差(Passband Mean Square Error) 阻带能量和通带均方误差都是滤波器系数向量x的 二次非负函数，而阻带波纹约束是阻带区间上线性 函数的绝对值的最大值约束。 雷达信号处理国防科技重点实验室 5.5 二次规划举例 通带波纹(Passband Ripple) 雷达信号处理国防科技重点实验室 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:1:优化变量变成了向量优化变量变成了向量 注注2: 2: 约束条件含有约束条件含有 绝对值绝对值-非线性非线性 注注3: 3: 约束条件在区间上约束条件在区间上 的连续变量。的连续变量。 解决策略？解决策略？ 雷达信号处理国防科技重点实验室 5.5 二次规划举例 去掉绝对值，非线性约束简化为两个线性约束去掉绝对值，非线性约束简化为两个线性约束 新的优化变量和目标函数新的优化变量和目标函数 雷达信号处理国防科技重点实验室 5.5 二次规划举例 离散化离散化 阻带约束阻带约束 通带约束通带约束 雷达信号处理国防科技重点实验室 5.5 二次规划举例 雷达信号处理国防科技重点实验室 5.5 二次规划举例 滤波器系数 滤波器系数 幅频响应 幅频响应 通带波纹 通带波纹 雷达信号处理国防科技重点实验室 5.6 二次规划的一般形式 对称的n n的实矩阵 是m1 n的矩阵，m1个不 等式约束 是m2 n的矩阵，m2个等 式约束 是二次规划的可行域 雷达信号处理国防科技重点实验室 5.6 二次规划的一般形式 最优解的存在性条件最优解的存在性条件 1.如果矩阵 是非负定的，可行 域非空且目标函数在可行域上有 下界，则优化问题有全局最小值 点(但可能不唯一）。 是非负定的，如果对任意的非 零向量 ，有 矩阵的所有特征值非 负。 当优化问题的可行域是非空 有界集合适，优化问题存在 全局最小值点。 2.如果矩阵 是正定的，并且 可行域非空，那么优化问题具 有全局最小值点，并且该最小 值是唯一的。 是正定的，如果对任意的非 零向量 ，有 矩阵的所有特征值大于 零。 雷达信号处理国防科技重点实验室 5.6 二次规划的一般形式 二次规划解的几何示意图二次规划解的几何示意图 由5个线性不等式围成的 可行域-凸五边形区域 全局最小值点，可行域 边界与取值最小的二次 函数等高线的切点。 所有的等高线都是共心 相似椭圆； 在二次规划中，最优点 不总是在可行域边界多边 形的顶点上达到； 在线性规划中，最优点 总是在可行域边界多边形 的顶点上达到。 雷达信号处理国防科技重点实验室 5.6 二次规划的一般形式 纯线性等式约束的二次规划纯线性等式约束的二次规划 二次规划中仅包含线性的等 式约束，并且约束的数目小 于优化向量的维数。 拉格朗日乘子方法拉格朗日乘子方法 是m1 n的矩阵 拉格朗日方程组拉格朗日方程组 n+m1个未知量，n+m1个方 程的线性方程组，当方程组 有唯一解时，二次规划具有 唯一的全局最小值点。 雷达信号处理国防科技重点实验室 5.6 二次规划的一般形式 纯等式约束的二次规划求解举例纯等式约束的二次规划求解举例 拉格朗日乘子方法拉格朗日乘子方法 拉格朗日方程组拉格朗日方程组 -2.076502732240437 7.169398907103826 -0.754098360655737 -6.513661202185794 5.896174863387979 fmin=64.218579234972708 雷达信号处理国防科技重点实验室 5.7 二次规划M atlab程序使用 一般在使用程序之前，先要检验矩阵 是否对称，否则用 代替； 矩阵 是否是正定或非负定的，采用 矩阵的特征值分解，检验特征值是否全 正或非负。 雷达信号处理国防科技重点实验室 5.7 二次规划M atlab程序使用 限定解在n维空间中的超长方体内 x0是可以限定算法迭代求解过程中 的初始点。理论上，二次规划的最 优解不依赖于初始点，但计算时间 与初始点有关。 雷达信号处理国防科技重点实验室 5.7 二次规划M atlab程序使用 程序运行终止信息解读程序运行终止信息解读 1 QUADPROG converged with a sol