二次规划0508课件.ppt

1、二次规划问题的数学模型 等式约束的二次规划问题 等式约束的二次规划问题 v 直接消去法 等式约束的二次规划问题 等式约束的二次规划问题 v 例1 222123123123mins.t.242fxxxxxxxxx x等式约束的二次规划问题 等式约束的二次规划问题 v 拉格朗日乘子法 等式约束的二次规划问题等式约束的二次规划问题v 例2有效集方法 有效集方法 有效集方法 有效集方法()()()()1min2s.t.0,TTkkkkTkikfiIdHdxda d有效集方法 v 迭代步骤 有效集方法 v 例1有效集方法 有效集方法 有效集方法有效集方法有效集方法v 收敛性分析二次规划问题的MATLAB

2、求解 二次规划问题的MATLAB求解 v 调用格式x=quadprog(H,c,A,b)x=quadprog(H,c,A,b,Aeq,beq)x=quadprog(H,c,A,b,Aeq,beq,lb,ub)x=quadprog(H,c,A,b,Aeq,beq,lb,ub,x0)x=quadprog(H,c,A,b,Aeq,beq,lb,ub,x0,options)x,fval=quadprog(.)x,fval,exitflag=quadprog(.)x,fval,exitflag,output=quadprog(.)x,fval,exitflag,output,lambda=quadpro

3、g(.)二次规划问题的MATLAB求解 v 输入参数和输出参数 函数quadprog中的输入参数和以前所介绍的线性规划、整数规划等问题的求解参数类似，含义基本相同，故在此不再赘述，输出参数的含义可能有所不同，将参数exitflag、lambda和output所包含的属性及其含义列于表中。v 控制参数设置 在使用函数quadprog求解二次规划问题时，可以对相关参数进行设置，使得函数按照指定优化设置进行迭代，在quadprog函数中提供了中型规模算法和大型规模算法，那么在控制参数的设置时，对这些参数也要区别对待，例如有些参数是仅针对中型规模算法的，有些参数是仅针对大型规模算法的，有些参数是两者共

4、有的。quadprog函数提供的通用参数的设置方法如表所示。二次规划问题的MATLAB求解 v 命令详解 二次规划问题的MATLAB求解 二次规划问题的MATLAB求解 二次规划问题的MATLAB求解 v quadprog函数可使用不同的优化算法如下：大型规模优化算法：当优化问题只有上界和下界，而没有线性不等式或等式约束，则默认算法为大型算法。或者，如果优化问题中只有线性等式，而没有上界和下界或线性不等式时，默认算法也是大型算法。大型算法是基于内部反射牛顿法的子空间置信域法。该法的每一次迭代都与用PCG法求解大型线性系统得到的近似解有关。中型规模优化算法：quadprog使用的是有效集算法，它

5、是一种投影法，首先通过求解线性规划问题来求得问题的初始可行解。v 使用quadprog求解二次规划问题的过程中需要注意的问题 如果问题不是严格凸性的，用函数quadprog求得的最优解可能是局部最优解。如果在求解过程中，可以用Aeq和Beq明确的指定等式约束，而不是用1b和ub指定，则可以得到更好的数值解。若x的分量没有上边界或者下边界，则quadprog函数希望将对应的分量设置为Inf或者-Inf，而不是赋予一个很大的数或者很小的数 对于大型规模优化问题，若没有提供初值x0，或x0不是严格可行，则quadprog函数会选择一个新的初始可行点。若为等式约束，且quadprog函数发现负曲率，则

6、优化过程终止。二次规划问题的MATLAB求解 v 使用quadprog求解时的一些要求 控制参数Display只能选择off或者final，而iter无效；当问题不定或负定时，常常无解，此时exitflag参数将返回一个负值，表示优化过程不收敛。若正定解存在，则quadprog函数可能只给出局部极小值，因为问题可能是非凸的；对于大型规模优化问题，线性等式约束必须是相互独立的，也就是说，Aeq必须是行满秩的，如果不满足要求，则必须调用中型规模优化算法求解。二次规划问题的MATLAB求解 v 例1二次规划问题的MATLAB求解 二次规划问题的MATLAB求解 二次规划问题的MATLAB求解二次规划问题的MATLAB求解重点回顾v 二次规划的数学模型；v 求解等式约束下二次规划问题的直接消去法和拉格朗日乘子法；v 求解一般二次规划问题的有效集算法；v 利用MATLAB求解二次规划的quadprog函数的使用方法。