2025年大學《數(shù)理基礎科學》專業(yè)題庫——數(shù)學最優(yōu)化理論與方法考試時間：______分鐘總分：______分姓名：______一、1.設非線性規(guī)劃問題minf(x)=x?2+2x?2-4x?-4x?x?+2x?s.t.g?(x)=x?+x?-3≤0g?(x)=-x?+x?-1≤0g?(x)=x?≥0g?(x)=x?≥0其中x∈?2。寫出該問題的KKT條件。2.某無約束優(yōu)化問題使用牛頓法進行求解，其Hessian矩陣為正定。若在某次迭代中，搜索方向p_k滿足B_kp_k=-?f(x_k)，其中B_k是Hessian矩陣在x_k處的近似。請寫出該近似所對應的牛頓方向q_k的表達式，并簡述該近似方法可能的理論依據(jù)。二、1.考慮線性規(guī)劃問題maxz=3x?+5x?s.t.x?+x?≤42x?+x?≤5x?,x?≥0使用單純形法求解該問題。請完整寫出迭代過程，包括初始表格、每一步的基變量選擇、旋轉運算以及最終結果（最優(yōu)解、最優(yōu)值）。在表格運算中，僅要求列出關鍵步驟和最終結果，無需展示所有中間計算。2.已知線性規(guī)劃問題maxz=c?xs.t.Ax≤bx≥0的最優(yōu)解為x*，最優(yōu)單純形基為B。其對偶問題是minw=b?ys.t.A?y≥cy≥0請寫出對偶問題的最優(yōu)解y*，并說明理由（依據(jù)對偶理論）。三、1.設函數(shù)f(x)=x3-3x+1在區(qū)間[-2,2]上定義。請找出f(x)在該區(qū)間上的所有局部最優(yōu)解（包括局部最小值點和局部最大值點），并判斷其是最小值點還是最大值點。僅要求列出求解過程的關鍵步驟和結論。2.在使用梯度法求解無約束優(yōu)化問題時，如何確定步長參數(shù)α_k？請簡述兩種常用的線搜索策略（如精確線搜索、黃金分割法或Armijo條件）的基本思想。3.考慮約束優(yōu)化問題minf(x)=x?2+x?2s.t.h(x)=x?+x?-1=0使用拉格朗日乘子法求解。請寫出拉格朗日函數(shù)，并推導最優(yōu)性條件（KKT條件的一個特例）。若進一步假設f和h在所考慮的區(qū)域上都是二階連續(xù)可微的，請補充推導二階最優(yōu)性條件。四、1.簡述整數(shù)規(guī)劃與線性規(guī)劃的主要區(qū)別，并舉例說明為什么某些優(yōu)化問題需要引入整數(shù)約束。2.動態(tài)規(guī)劃適用于求解哪些類型的最優(yōu)化問題？請簡述動態(tài)規(guī)劃的基本思想（包括狀態(tài)定義、狀態(tài)轉移方程、基本方程和邊界條件）。3.在實際應用中，如何判斷一個無約束優(yōu)化問題的目標函數(shù)可能存在多個局部最優(yōu)解？當算法陷入局部最優(yōu)解時，可以采取哪些策略來嘗試尋找更好的全局最優(yōu)解？請簡述其中兩種策略的基本思想。試卷答案一、1.KKT條件：(i)?f(x)+∑?λ??g?(x)=0(ii)λ?≥0,g?(x)≤0(對于所有i)(iii)λ?*g?(x)=0(對于所有i)其中，?f(x)=[2-4-2x?,4-4x?]?,?g?(x)=[1,1]?,?g?(x)=[-1,1]?,?g?(x)=[1,0]?,?g?(x)=[0,1]?。2.由B_kp_k=-?f(x_k)和牛頓法方向定義q_k=-[?f(x_k)+?2f(x_k)δ_k]，其中δ_k是沿方向p_k的步長。若令δ_k=1，則q_k=-[?f(x_k)+B_kp_k]。代入B_kp_k=-?f(x_k)，得q_k=0。這表明該近似導致牛頓法方向為零，通常是因為B_k不再是對Hessian矩陣的良好近似。該近似可能的理論依據(jù)是認為在牛頓法迭代的當前點x_k附近，函數(shù)f(x)可以較好地用其二次部分近似，即f(x_k+δ_kp_k)≈f(x_k)+?f(x_k)?δ_kp_k+1/2δ_k?B_kδ_k。如果B_k是Hessian矩陣的某個近似（如B_k=?2f(x_k)+E_k，E_k為誤差），則q_k=-[?f(x_k)+(?2f(x_k)+E_k)p_k]=-(?2f(x_k)p_k+E_kp_k)。若B_kp_k=-?f(x_k)，則q_k=-E_kp_k。選擇B_k使得q_k具有有利的收斂性性質(zhì)，例如下降性或線搜索步長容易確定。二、1.單純形法求解過程：初始基本可行解：x=(0,0)?,z=0?；兞縳?,x?=0。初始表格：|基變量|x?|x?|s?|s?|RHS||-------|----|----|----|----|-----||z|-3|-5|0|0|0||s?|1|1|1|0|4||s?|2|1|0|1|5|檢驗行：z-row=[-3,-5,0,0]?。檢驗數(shù)-5<-3，選擇x?入基。最小比：4/1=4,5/1=5。選擇s?出基。旋轉運算（以x?行和z-row為主元）：新x?行：[1,1,1,0,4]→[1,1,1,0,4](除主元外不變)新z-row：[-3,-5,0,0,0]+5*(新x?行)=[-3,0,5,0,20]新s?行：[1,1,1,0,4]→[0,0,1,-1,0](新s?=s?-x?)新s?行：[2,1,0,1,5]→[0,-1,0,1,1](新s?=s?-x?)新表格：|基變量|x?|x?|s?|s?|RHS||-------|----|----|----|----|-----||z|-3|0|5|0|20||x?|0|1|1|0|4||s?|0|0|1|-1|0||s?|0|-1|0|1|1|檢驗行：z-row=[-3,0,5,0]?。檢驗數(shù)-3<0。所有檢驗數(shù)≤0，達到最優(yōu)。最優(yōu)解：x?=0,x?=4。最優(yōu)值：z=20。2.對偶問題的最優(yōu)解y*為原問題最優(yōu)解x*在其對偶變量處的值。即y*?=c?*x*?(對于所有i)。依據(jù)強對偶定理，若原問題有最優(yōu)解x*，則其對偶問題也有最優(yōu)解y*，且二者目標函數(shù)值相等。若原問題的最優(yōu)單純形基為B，則對偶問題的最優(yōu)解y*=(c_B?B?1b,c_N?B?1A_N)?，其中c_B,c_N分別是對應基變量和非基變量的系數(shù)向量，A_B,A_N是矩陣A按B和非基變量分塊得到的子矩陣。當原問題采用單純形法迭代到最終階段，最優(yōu)解為x*，最優(yōu)基為B時，此時x*_B=B?1b(基變量取值為B?1乘以右側向量)，x*_N=0(非基變量取值為0)。將x*代入KKT條件?f(x*)?+∑?λ??g?(x*)?=0，即c?+A?y*=0。若原問題最終形式為z=c_Bx*_B+c_Nx*_N=c_B(B?1b)+0=c_B?B?1b，則c_B?B?1b=z*。結合c_B=c?，得z*=c?B?1b=c_B?B?1b。由強對偶定理z*=w*，其中w*=b?y*。因此b?y*=c_B?B?1b。若原問題最優(yōu)解為x*，且x*的基變量部分為x*_B=B?1b，則對偶問題的最優(yōu)解y*應滿足y*_B=c_B?B?1。即y*=(c_B?B?1,c_N?B?1A_N)?。當原問題最終解為x*，最優(yōu)基為B時，x*_B=B?1b，所以y*_B=c_B?B?1=c_B?(B?1b)=c_B?x*_B=c?x*_B=c?*x*?(僅對基變量i成立)。對于非基變量i∈N，g?(x*)=0，λ?=0，KKT條件自動滿足。所以y*?=c?*x*?(對所有i)。三、1.求局部最優(yōu)解：求導：f'(x)=3x2-3。令f'(x)=0，得x=±1。求二階導：f''(x)=6x。在x=1處，f''(1)=6>0，為局部最小值點。在x=-1處，f''(-1)=-6<0，為局部最大值點。檢查邊界：f(-2)=-5,f(2)=5。結論：局部最小值點為x=1，最小值f(1)=-1；局部最大值點為x=-1，最大值f(-1)=3。全局最小值為f(1)=-1，全局最大值為f(2)=5。2.線搜索策略：(a)精確線搜索：尋找步長α_k使得f(x_k+α_kp_k)達到在方向p_k上f(x_k)的最小值，即α_k=argmin_αf(x_k+αp_k)。這通常需要解決一個一維優(yōu)化問題，計算量可能較大。(b)黃金分割法（或Armijo條件）：不直接尋找精確步長，而是采用一種啟發(fā)式方法。黃金分割法保持兩個搜索區(qū)間，在每步迭代中根據(jù)黃金比例縮減其中一個區(qū)間，直到區(qū)間足夠小，認為其內(nèi)點即為步長α_k的近似值。Armijo條件（或稱為精確線搜索的弱形式）則通過選擇步長α_k滿足f(x_k+α_kp_k)≤f(x_k)+c*α_k*?f(x_k)?p_k(其中0<c<1)，即保證搜索方向是下降的，且下降量至少為某個固定比例。這種策略計算量相對較小。3.拉格朗日乘子法：拉格朗日函數(shù)：L(x,λ)=f(x)+λ(h(x))其中x∈??,λ∈?(或λ∈??,若h(x)是向量)。最優(yōu)性條件：?L(x_k,λ_k)=?f(x_k)+λ_k?h(x_k)=0對應KKT條件中的?f(x)+∑?λ??g?(x)=0，這里?h(x_k)=?g?(x_k)。對于等式約束h(x)=0，KKT條件還包括互補松弛條件g?(x)≤0,λ?*g?(x)=0，這里變?yōu)閔(x)=0(總是成立)和λ*h(x)=0。后者在最優(yōu)解處自動滿足（因為h(x)=0），故KKT條件簡化為?f(x)+λ?h(x)=0和h(x)=0。若f和h在所考慮區(qū)域上二階連續(xù)可微，則二階最優(yōu)性條件要求Hessian矩陣?2L(x_k,λ_k)在x_k處正定（對于無約束部分，或在該點沿可行方向的正定性分析），且滿足?2f(x_k)+λ_k?2h(x_k)是半負定的。這通常需要更復雜的條件。四、1.整數(shù)規(guī)劃與線性規(guī)劃的區(qū)別：主要區(qū)別在于對變量的取值限制。線性規(guī)劃(LP)要求所有變量取連續(xù)值（通常在實數(shù)域內(nèi)），而整數(shù)規(guī)劃(IP)要求至少部分或全部變量取整數(shù)值（通常是0或1，或某個整數(shù)范圍）。LP求解后得到的解可能是非整數(shù)，而IP求解得到的最優(yōu)解（對于整數(shù)規(guī)劃）必須是整數(shù)。由于整數(shù)約束的引入，IP通常比LP更難求解，其可行域更小，可能存在多個最優(yōu)解（整數(shù)最優(yōu)解可能不同于LP最優(yōu)解）。例子：LP問題maxz=x?+5x?s.t.2x?+x?≤10,x?+3x?≤15,x?,x?≥0。最優(yōu)解可能為x?=4.8,x?=2.4,z=28.8。若增加x?,x?必須為整數(shù)，則最優(yōu)整數(shù)解可能為x?=5,x?=2,z=25，或x?=4,x?=3,z=23。2.動態(tài)規(guī)劃適用類型與思想：動態(tài)規(guī)劃適用于具有“最優(yōu)子結構”和“重疊子問題”特征的最優(yōu)化問題，通常用于解決多階段決策問題或序列決策問題?；舅枷耄?a)狀態(tài)定義：將復雜問題分解為一系列關聯(lián)的子問題，定義合適的狀態(tài)變量（S）來表示在某個階段（或決策點）所達到的狀態(tài)。(b)狀態(tài)轉移方程：描述從一個狀態(tài)到下一個狀態(tài)的過程，即如何根據(jù)當前狀態(tài)和決策選擇來得到下一個狀態(tài)。形式為：S(k+1)=T(S(k),a(k))，其中k是階段索引，a(k)是第k階段的決策。(c)基本方程（遞歸關系）：基于最優(yōu)子結構性質(zhì)，將問題的最優(yōu)解值表示為其子問題的最優(yōu)解值（通常是遞歸地）的組合。對于最短路徑或最小成本問題，形式常為：Opt(S_k)=min/min/max{a(k)*Cost(S_k,a(k))+Opt(S_{k+1})}，其中O