最優(yōu)化方法復(fù)習(xí)題

《最優(yōu)化方法》復(fù)習(xí)題概述(包括凸規(guī)劃)判斷與填空題√設(shè)假設(shè)，對(duì)于一切恒有，那么稱為最優(yōu)化問(wèn)題的全局最優(yōu)解.設(shè)假設(shè)，存在的某鄰域，使得對(duì)一切恒有，那么稱為最優(yōu)化問(wèn)題的嚴(yán)格局部最優(yōu)解.給定一個(gè)最優(yōu)化問(wèn)題，那么它的最優(yōu)值是一個(gè)定值.√非空集合為凸集當(dāng)且僅當(dāng)中任意兩點(diǎn)連線段上任一點(diǎn)屬于.√非空集合為凸集當(dāng)且僅當(dāng)中任意有限個(gè)點(diǎn)的凸組合仍屬于.√任意兩個(gè)凸集的并集為凸集.函數(shù)為凸集上的凸函數(shù)當(dāng)且僅當(dāng)為上的凹函數(shù).√設(shè)為凸集上的可微凸函數(shù)，.那么對(duì)，有假設(shè)是凹函數(shù)，那么是凸集?！淘O(shè)為由求解的算法A產(chǎn)生的迭代序列，假設(shè)算法A為下降算法，那么對(duì)，恒有.算法迭代時(shí)的終止準(zhǔn)那么〔寫出三種〕：_____________________________________。凸規(guī)劃的全體極小點(diǎn)組成的集合是凸集?！毯瘮?shù)在點(diǎn)沿著迭代方向進(jìn)行精確一維線搜索的步長(zhǎng)，那么其搜索公式為.函數(shù)在點(diǎn)沿著迭代方向進(jìn)行精確一維線搜索的步長(zhǎng)，那么0.設(shè)為點(diǎn)處關(guān)于區(qū)域的一個(gè)下降方向，那么對(duì)于，使得簡(jiǎn)述題寫出Wolfe-Powell非精確一維線性搜索的公式。怎樣判斷一個(gè)函數(shù)是否為凸函數(shù).〔例如:判斷函數(shù)是否為凸函數(shù)〕證明題證明一個(gè)優(yōu)化問(wèn)題是否為凸規(guī)劃.〔例如判斷〔其中G是正定矩陣〕是凸規(guī)劃.熟練掌握凸規(guī)劃的性質(zhì)及其證明.線性規(guī)劃考慮線性規(guī)劃問(wèn)題：其中，為給定的數(shù)據(jù)，且rank判斷與選擇題(LP)的基解個(gè)數(shù)是有限的.√假設(shè)(LP)有最優(yōu)解，那么它一定有基可行解為最優(yōu)解.√(LP)的解集是凸的.√對(duì)于標(biāo)準(zhǔn)型的(LP)，設(shè)由單純形算法產(chǎn)生，那么對(duì)，有×假設(shè)為(LP)的最優(yōu)解，為(DP)的可行解，那么√設(shè)是線性規(guī)劃(LP)對(duì)應(yīng)的基的基可行解，與基變量對(duì)應(yīng)的標(biāo)準(zhǔn)式中，假設(shè)存在，那么線性規(guī)劃(LP)沒(méi)有最優(yōu)解?！燎蠼饩€性規(guī)劃(LP)的初始基可行解的方法：____________________.對(duì)于線性規(guī)劃(LP)，每次迭代都會(huì)使目標(biāo)函數(shù)值下降.×簡(jiǎn)述題將以下線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型：寫出以下線性規(guī)劃的對(duì)偶線性規(guī)劃：計(jì)算題熟練掌握利用單純形表求解線性規(guī)劃問(wèn)題的方法〔包括大M法及二階段法〕.見(jiàn)書本：(利用單純形表求解);(利用大M法求解);(利用二階段法求解).證明題熟練掌握對(duì)偶理論〔弱對(duì)偶理論、強(qiáng)對(duì)偶理論以及互補(bǔ)松弛條件〕及利用對(duì)偶理論證明相關(guān)結(jié)論。無(wú)約束最優(yōu)化方法一、判斷與選擇題設(shè)為正定矩陣，那么關(guān)于共軛的任意向量必線性相關(guān).√在牛頓法中，每次的迭代方向都是下降方向.×經(jīng)典Newton法在相繼兩次迭代中的迭代方向是正交的.×PRP共軛梯度法與BFGS算法都屬于Broyden族擬Newton算法.×用DFP算法求解正定二次函數(shù)的無(wú)約束極小化問(wèn)題，那么算法中產(chǎn)生的迭代方向一定線性無(wú)關(guān).√FR共軛梯度法、PRP共軛梯度法、DFP算法、及BFGS算法均具有二次收斂性.×共軛梯度法、共軛方向法、DFP算法以及BFGS算法都具有二次終止性.√函數(shù)在處的最速下降方向?yàn)?求解的經(jīng)典Newton法在處的迭代方向?yàn)?假設(shè)在的鄰域內(nèi)具有一階連續(xù)的偏導(dǎo)數(shù)且，那么為的局部極小點(diǎn).×假設(shè)在的某鄰域內(nèi)具有二階連續(xù)的偏導(dǎo)數(shù)且為的嚴(yán)格局部極小點(diǎn)，那么正定.×求解的最速下降法在處的迭代方向?yàn)?求解的阻尼Newton法在處的迭代方向?yàn)?用牛頓法求解時(shí)，至多迭代一次可達(dá)其極小點(diǎn).×牛頓法具有二階收斂性.√二次函數(shù)的共軛方向法具有二次終止性.×共軛梯度法的迭代方向?yàn)椋篲____________________.二、證明題設(shè)為一階連續(xù)可微的凸函數(shù)，且，那么為的全局極小點(diǎn).給定和正定矩陣.如果為求解的迭代點(diǎn)，為其迭代方向，且為由精確一維搜索所的步長(zhǎng)，那么試證：Newton法求解正定二次函數(shù)時(shí)至多一次迭代可達(dá)其極小點(diǎn).簡(jiǎn)述題簡(jiǎn)述牛頓法或者阻尼牛頓法的優(yōu)缺點(diǎn).簡(jiǎn)述共軛梯度法的根本思想.計(jì)算題利用最優(yōu)性條件求解無(wú)約束最優(yōu)化問(wèn)題.例如：求解用FR共軛梯度法無(wú)約束最優(yōu)化問(wèn)題.見(jiàn)書本：例3.4.1.用PRP共軛梯度法無(wú)約束最優(yōu)化問(wèn)題.見(jiàn)書本：例3.4.1.例如：約束最優(yōu)化方法考慮約束最優(yōu)化問(wèn)題：其中，一、判斷與選擇題外罰函數(shù)法、內(nèi)罰函數(shù)法、及乘子法均屬于SUMT.×使用外罰函數(shù)法和內(nèi)罰函數(shù)法求解〔NLP〕時(shí)，得到的近似最優(yōu)解往往不是〔NLP〕的可行解.×在求解〔NLP〕的外罰函數(shù)法中，所解無(wú)約束問(wèn)題的目標(biāo)函數(shù)為.在〔NLP〕中，那么在求解該問(wèn)題的內(nèi)罰函數(shù)法中，常使用的罰函數(shù)為.在〔NLP〕中，那么在求解該問(wèn)題的乘子法中，乘子的迭代公式為，對(duì).在〔NLP〕中，那么在求解該問(wèn)題的乘子法中，增廣的Lagrange函數(shù)為：_________________________________對(duì)于(NLP)的KT條件為：_______________二、計(jì)算題利用最優(yōu)性條件(KT條件)求解約束最優(yōu)化問(wèn)題.用外罰函數(shù)法求解約束最優(yōu)化問(wèn)題.見(jiàn)書本：例4.2.1；例4.2.2.用內(nèi)罰函數(shù)法求解約束最優(yōu)化問(wèn)題.見(jiàn)書本：例4.2.3.用乘子法求解約束最優(yōu)化問(wèn)題.見(jiàn)書本：例4.2.7；例4.2.8.三、簡(jiǎn)述題簡(jiǎn)述SUMT外點(diǎn)法的優(yōu)缺點(diǎn).簡(jiǎn)述SUMT內(nèi)點(diǎn)法的優(yōu)缺點(diǎn).四、證明題利用最優(yōu)性條件證明相關(guān)問(wèn)題.例如：設(shè)為正定矩陣，為列滿秩矩陣.試求規(guī)劃的最優(yōu)解，并證明解是唯一的.多目標(biāo)最優(yōu)化方法一、判斷與選擇題求解多目標(biāo)最優(yōu)化問(wèn)題的評(píng)價(jià)函數(shù)法包括線性加權(quán)法極大極小法理想點(diǎn)法平方和加權(quán)法乘除法.通過(guò)使用評(píng)價(jià)函數(shù)，多目標(biāo)最優(yōu)化問(wèn)題能夠轉(zhuǎn)化為單目標(biāo)最優(yōu)化問(wèn)題.√設(shè)，那么在上的一般多目標(biāo)最優(yōu)化問(wèn)題的數(shù)學(xué)形式為.對(duì)于規(guī)劃，設(shè)，假設(shè)不存在使得，那么為該最優(yōu)化問(wèn)題的有效解.√一般多目標(biāo)最優(yōu)化問(wèn)題的絕對(duì)最優(yōu)解必是有效解.√對(duì)于規(guī)劃，設(shè)為相應(yīng)于的權(quán)系數(shù)，那么求解以上問(wèn)題的線性加權(quán)和法中所求解優(yōu)化的目標(biāo)函數(shù)為.利用求解的線性加權(quán)和法所得到的解，或者為原問(wèn)題的有效解，或者為原問(wèn)題的弱有效解.√二、簡(jiǎn)述題簡(jiǎn)單證明題☆絕對(duì)最優(yōu)解、有效解、及弱有效解之間