二次規(guī)劃0508課件

二次規(guī)劃問(wèn)題的數(shù)學(xué)模型二次規(guī)劃問(wèn)題的數(shù)學(xué)模型等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題直接消去法等式約束的二次規(guī)劃問(wèn)題直接消去法等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題例1等式約束的二次規(guī)劃問(wèn)題例1等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題拉格朗日乘子法等式約束的二次規(guī)劃問(wèn)題拉格朗日乘子法等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題例2等式約束的二次規(guī)劃問(wèn)題例2有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法迭代步驟有效集方法迭代步驟有效集方法例1有效集方法例1有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法收斂性分析有效集方法收斂性分析二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解調(diào)用格式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]=quadprog(...)二次規(guī)劃問(wèn)題的MATLAB求解調(diào)用格式二次規(guī)劃問(wèn)題的MATLAB求解輸入?yún)?shù)和輸出參數(shù)函數(shù)quadprog中的輸入?yún)?shù)和以前所介紹的線(xiàn)性規(guī)劃、整數(shù)規(guī)劃等問(wèn)題的求解參數(shù)類(lèi)似，含義基本相同，故在此不再贅述，輸出參數(shù)的含義可能有所不同，將參數(shù)exitflag、lambda和output所包含的屬性及其含義列于表中?？刂茀?shù)設(shè)置在使用函數(shù)quadprog求解二次規(guī)劃問(wèn)題時(shí)，可以對(duì)相關(guān)參數(shù)進(jìn)行設(shè)置，使得函數(shù)按照指定優(yōu)化設(shè)置進(jìn)行迭代，在quadprog函數(shù)中提供了中型規(guī)模算法和大型規(guī)模算法，那么在控制參數(shù)的設(shè)置時(shí)，對(duì)這些參數(shù)也要區(qū)別對(duì)待，例如有些參數(shù)是僅針對(duì)中型規(guī)模算法的，有些參數(shù)是僅針對(duì)大型規(guī)模算法的，有些參數(shù)是兩者共有的。quadprog函數(shù)提供的通用參數(shù)的設(shè)置方法如表所示。二次規(guī)劃問(wèn)題的MATLAB求解輸入?yún)?shù)和輸出參數(shù)二次規(guī)劃問(wèn)題的MATLAB求解命令詳解二次規(guī)劃問(wèn)題的MATLAB求解命令詳解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解quadprog函數(shù)可使用不同的優(yōu)化算法如下：大型規(guī)模優(yōu)化算法：當(dāng)優(yōu)化問(wèn)題只有上界和下界，而沒(méi)有線(xiàn)性不等式或等式約束，則默認(rèn)算法為大型算法?；蛘?，如果優(yōu)化問(wèn)題中只有線(xiàn)性等式，而沒(méi)有上界和下界或線(xiàn)性不等式時(shí)，默認(rèn)算法也是大型算法。大型算法是基于內(nèi)部反射牛頓法的子空間置信域法。該法的每一次迭代都與用PCG法求解大型線(xiàn)性系統(tǒng)得到的近似解有關(guān)。中型規(guī)模優(yōu)化算法：quadprog使用的是有效集算法，它是一種投影法，首先通過(guò)求解線(xiàn)性規(guī)劃問(wèn)題來(lái)求得問(wèn)題的初始可行解。使用quadprog求解二次規(guī)劃問(wèn)題的過(guò)程中需要注意的問(wèn)題如果問(wèn)題不是嚴(yán)格凸性的，用函數(shù)quadprog求得的最優(yōu)解可能是局部最優(yōu)解。如果在求解過(guò)程中，可以用Aeq和Beq明確的指定等式約束，而不是用1b和ub指定，則可以得到更好的數(shù)值解。若x的分量沒(méi)有上邊界或者下邊界，則quadprog函數(shù)希望將對(duì)應(yīng)的分量設(shè)置為Inf或者-Inf，而不是賦予一個(gè)很大的數(shù)或者很小的數(shù)對(duì)于大型規(guī)模優(yōu)化問(wèn)題，若沒(méi)有提供初值x0，或x0不是嚴(yán)格可行，則quadprog函數(shù)會(huì)選擇一個(gè)新的初始可行點(diǎn)。若為等式約束，且quadprog函數(shù)發(fā)現(xiàn)負(fù)曲率，則優(yōu)化過(guò)程終止。二次規(guī)劃問(wèn)題的MATLAB求解quadprog函數(shù)可使用不二次規(guī)劃問(wèn)題的MATLAB求解使用quadprog求解時(shí)的一些要求控制參數(shù)Display只能選擇off或者final，而iter無(wú)效；當(dāng)問(wèn)題不定或負(fù)定時(shí)，常常無(wú)解，此時(shí)exitflag參數(shù)將返回一個(gè)負(fù)值，表示優(yōu)化過(guò)程不收斂。若正定解存在，則quadprog函數(shù)可能只給出局部極小值，因?yàn)閱?wèn)題可能是非凸的；對(duì)于大型規(guī)模優(yōu)化問(wèn)題，線(xiàn)性等式約束必須是相互獨(dú)立的，也就是說(shuō)，Aeq必須是行滿(mǎn)秩的，如果不滿(mǎn)足要求，則必須調(diào)用中型規(guī)模優(yōu)化算法求解。二次規(guī)劃問(wèn)題的MATLAB求解使用quadprog求解時(shí)的二次規(guī)劃問(wèn)題的MATLAB求解例1二次規(guī)劃問(wèn)題的MATLAB求解例1二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解重點(diǎn)回顧二次規(guī)劃的數(shù)學(xué)模型；求解等式約束下二次規(guī)劃問(wèn)題的直接消去法和拉格朗日乘子法；求解一般二次規(guī)劃問(wèn)題的有效集算法；利用MATLAB求解二次規(guī)劃的quadprog函數(shù)的使用方法。重點(diǎn)回顧二次規(guī)劃的數(shù)學(xué)模型；二次規(guī)劃問(wèn)題的數(shù)學(xué)模型二次規(guī)劃問(wèn)題的數(shù)學(xué)模型等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題直接消去法等式約束的二次規(guī)劃問(wèn)題直接消去法等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題例1等式約束的二次規(guī)劃問(wèn)題例1等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題拉格朗日乘子法等式約束的二次規(guī)劃問(wèn)題拉格朗日乘子法等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題等式約束的二次規(guī)劃問(wèn)題例2等式約束的二次規(guī)劃問(wèn)題例2有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法迭代步驟有效集方法迭代步驟有效集方法例1有效集方法例1有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法有效集方法收斂性分析有效集方法收斂性分析二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解調(diào)用格式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]=quadprog(...)二次規(guī)劃問(wèn)題的MATLAB求解調(diào)用格式二次規(guī)劃問(wèn)題的MATLAB求解輸入?yún)?shù)和輸出參數(shù)函數(shù)quadprog中的輸入?yún)?shù)和以前所介紹的線(xiàn)性規(guī)劃、整數(shù)規(guī)劃等問(wèn)題的求解參數(shù)類(lèi)似，含義基本相同，故在此不再贅述，輸出參數(shù)的含義可能有所不同，將參數(shù)exitflag、lambda和output所包含的屬性及其含義列于表中。控制參數(shù)設(shè)置在使用函數(shù)quadprog求解二次規(guī)劃問(wèn)題時(shí)，可以對(duì)相關(guān)參數(shù)進(jìn)行設(shè)置，使得函數(shù)按照指定優(yōu)化設(shè)置進(jìn)行迭代，在quadprog函數(shù)中提供了中型規(guī)模算法和大型規(guī)模算法，那么在控制參數(shù)的設(shè)置時(shí)，對(duì)這些參數(shù)也要區(qū)別對(duì)待，例如有些參數(shù)是僅針對(duì)中型規(guī)模算法的，有些參數(shù)是僅針對(duì)大型規(guī)模算法的，有些參數(shù)是兩者共有的。quadprog函數(shù)提供的通用參數(shù)的設(shè)置方法如表所示。二次規(guī)劃問(wèn)題的MATLAB求解輸入?yún)?shù)和輸出參數(shù)二次規(guī)劃問(wèn)題的MATLAB求解命令詳解二次規(guī)劃問(wèn)題的MATLAB求解命令詳解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解二次規(guī)劃問(wèn)題的MATLAB求解quadprog函數(shù)可使用不同的優(yōu)化算法如下：大型規(guī)模優(yōu)化算法：當(dāng)優(yōu)化問(wèn)題只有上界和下界，而沒(méi)有線(xiàn)性不等式或等式約束，則默認(rèn)算法為大型算法?；蛘?，如果優(yōu)化問(wèn)題中只有線(xiàn)性等式，而沒(méi)有上界和下界或線(xiàn)性不等式時(shí)，默認(rèn)算法也是大型算法。大型算法是基于內(nèi)部反射牛頓法的子空間置信域法。該法的每一次迭代都與用PCG法求解大型線(xiàn)性系統(tǒng)得到的近似解有關(guān)。中型規(guī)模優(yōu)化算法：quadprog使用的是有效集算法，它是一種投影法，首先通過(guò)求解線(xiàn)性規(guī)劃問(wèn)題來(lái)求得問(wèn)題的初始可行解。使用quadprog求解二次規(guī)劃問(wèn)題的過(guò)程中需要注意的問(wèn)題如果問(wèn)題不是嚴(yán)格凸性的，用函數(shù)quadprog求得的最優(yōu)解可能是局部最優(yōu)解。如果在求解過(guò)程中，可以用Aeq和Beq明確的指定等式約束，而不是用1b和ub指定，則可以得到更好的數(shù)值解。若x的分量沒(méi)有上邊界或者下邊界，則quadprog函數(shù)希望將對(duì)應(yīng)的分量設(shè)置為Inf或者-Inf，而不是賦予一個(gè)很大的數(shù)或者很小的數(shù)對(duì)于大型規(guī)模優(yōu)化問(wèn)題，若沒(méi)有提供初值x0，或x0不是嚴(yán)格可行，則quadprog函數(shù)會(huì)選擇一個(gè)新的初始可行點(diǎn)。若為等式約束，且quadprog函數(shù)發(fā)現(xiàn)負(fù)曲率，則優(yōu)化過(guò)程終止。二次規(guī)劃問(wèn)題的MATLAB求解quadprog函數(shù)可使用不二次規(guī)劃問(wèn)題的MATLAB求解使用quadprog求解時(shí)的一些要求控制參數(shù)Display只能選擇off或者final，而iter無(wú)效；當(dāng)問(wèn)題不定或負(fù)定時(shí)，常常無(wú)解，此時(shí)exitflag參數(shù)將返回一個(gè)負(fù)值，表示優(yōu)化過(guò)程不收斂。若正定解存在，則quadprog函數(shù)可能只給出局部極小值，因?yàn)閱?wèn)題可能是非凸的；對(duì)于大型規(guī)模優(yōu)化問(wèn)題，線(xiàn)性等式約束必須是相互獨(dú)立的，也就是說(shuō)，Aeq必須是行滿(mǎn)秩的，如果不滿(mǎn)足要求，則必須調(diào)用中型規(guī)模優(yōu)化算法求解。二次規(guī)劃問(wèn)題的MATLAB求解使用quadprog求解時(shí)的二次規(guī)劃問(wèn)題的MATLAB求解例1二次規(guī)劃問(wèn)題的MATLAB求解例1二