無約束問題

無約束問題是指在無約束條件的非線性規劃問題，即 n元實函式f在整個n維向量空間Rn上的最優值點問題。

基本介紹

• 中文名：無約束問題
• 外文名：Unconstrained problem
• 別名：無約束極值問題
• 拼音：Wú yuē shù wèn tí
• 學科：運籌學
• 隸屬：非線性規劃

基本內容

在科學管理和其他領域中，很多實際問題可以歸結為線性規劃問題，其目標函式和約束條件都是自變數的一次函式。但是，還有另外一些問題，其目標函式和(或)約束條件很難用線性函式來表達。如果目標函式或約束條件中含有非線性函式，就稱這種規劃問題為非線性規劃問題。

由於線性規劃的目標函式為線性函式，可行域為凸集，因而求出的最優解就是在整個可行域的全局最優解。非線性規劃則不然，有時求出的某個解雖是一部分可行域中的極值點，但卻並不一定是整個可行域上的全局最優解。

分類

無約束極值問題包括局部極值和全局極值。

設f(X)為定義在n維歐氏空間 的某一區域R上的n元實函式，其中 。對於 ，如果存在某個 ，使所有與 的距離小於 的 均滿足不等式 ，則稱 為f(X)在R上的局部極小點(或相對極小點)， 為局部極小值。

若點 ，而對於所有 都有 ，則稱 為f(X)在R上的全局極小點， 為全局極小值。

求解方法

對於無約束極值問題，時常使用疊代法，疊代法可大體分為兩大類。一類需要用目標函式的導函式，稱為解析法。另一類不涉及導數，只用到函式值，稱為直接法。

這些算法的基本思想是：在一個近似點處選定一個有利搜尋方向，沿這個方向進行一維尋查，得出新的近似點。然後對新點施行同樣手續，如此反覆疊代，直到滿足預定的精度要求為止。根據搜尋方向的取法不同，可以有各種算法。

一般來說，直接法的收斂速度較慢，只是在變數較少時才適用。但是直接法的疊代簡單，特別是當目標函式的解析表達式十分複雜，甚至寫不出具體表達式時，它們的導數很難求得，或者根本不存在。這時解析法就無能為力了。

解析法

1. 在求解無約束極值問題的解析法中，梯度法是最為古老但又十分基本的一種數值方法。它的疊代過程簡單，使用方便，而且又是理解某些其他最最佳化方法的基礎，收斂速度較慢。
2. 共軛梯度法是共軛方向法的一種，它的搜尋方向是利用一維搜尋所得極小點處函式的梯度生成的，收斂較快，效果較好。
3. 變尺度法是求解無約束極值問題的一種有效方法。由於它既避免了計算二階層數矩陣及其求逆過程，又經梯度法的收斂速度快，特別是對高維問題具有顯著的優越性。

直接法

1. 坐標輪換法是每次允許一個變數變化，其餘變數保持不變，即沿坐標方向輪流進行搜尋的尋優方法。它把多變數的最佳化問題輪流的轉化成單變數的最佳化問題。方法結構簡單，易於掌握，但計算效率低，對維數較高的最佳化問題更為突出，通常用於低維最佳化問題。
2. 模式搜尋法是一種在計算時不需要目標函式的導數，所以在解決不可導的函式或者求導異常麻煩的函式的最佳化問題時非常有效。
3. 鮑威爾共軛方向法是在無約束最佳化共扼方向，從某個初始點出發，求目標函式在這些方向上的極小值點，然後以該點為新的出發點，取復這一過程直到獲得滿意解，其優點是不必計算目標函式的 梯度就可以在有限步內找到極值點。

實際意義

由於很多實際問題要求進一步精確化以及電子計算機的發展，使非線性規劃在近幾十年來得以快速發展。目前，它已成為運籌學的重要分支之一，並在最優設計、管理科學、系統控制等許多領域得到越來越廣泛的套用。因此選擇無約束問題的最優解決方法，有助於獲取無約束問題的極大值或極小值，從而實現在各個領域的最優工作效率。