最優(yōu)化方法復習題

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