非線性規劃

在數學中，非線性規劃是求解由一系列未知實函數組成的組方程和不等式（統稱為約束）定義的最佳化問題，伴隨着一個要被最大化或最小化的目標函數，只是一些約束或目標函數是非線性的。^[1]它是最佳化處理非線性問題的一個子領域。

適用性

從一系列運輸方法中選擇最佳化運輸成本的一個或多個表現規模經濟的連通性和容量約束不同的非凸問題。例如從管道、鐵路油槽車、罐車、河駁船或沿海油船中選擇或組合的石油產品運輸。由於經濟批量大小，除了平滑變化之外，成本函數可以有不連續性。

現代工程實踐涉及到大量的數值最佳化。除了在很少一部分重要情形（如無源電路）中，工程問題是非線性的，它們通常是非常複雜。

在實驗科學中，一些簡單的數據分析（如已知位置和形狀但未知幅度的峰的總和的光譜的擬合）可以用線性方法來完成，但一般來說這些問題也是非線性的。通常研究的是含有變量參數的系統的理論模型以及含有未知參數的試驗模型。可以試着用數值尋找最優值。這種情況下，除了最優值本身通常還需要對結果的精度進行量度。

定義

令 n、m、p為正整數。令 X 為 Rⁿ 的一個子集，令 f、g_i 和 h_j 為 X 的實值函數（英語：real-valued function），對每個 i 屬於 {1, …, m} 及每個 j 屬於 {1, …, p}。

非線性最小化問題等效為下面形式的最佳化問題

${\displaystyle {\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}}$

非線性最大化問題定義方式類似。

約束集的可能類型

約束集的性質有若干可能性，也被稱為可行集或可行域。

無解問題（infeasible problem）是指沒有一組變量可以滿足所有的約束，也就是約束之間有互相矛盾的情形，沒有解存在。

有解問題（feasible problem）是指至少有一組變量可以滿足所有的約束條件。

無界限問題（unbounded problem）是一個有解問題，其變量沒有上限限制，因此沒有最佳解，因為總會有一組變量使得目標函數比其他組的變量有更好的結果。

求解問題的方案分析

1. 若目標函數f(x)為線性，約束的空間為多胞形，對應線性規劃問題，採用著名的線性規劃法求解。
2. 若目標函數為凹函數（最大化）或是凸函數（最小化），且約束為凸集，對應凸規劃問題，常採用凸優化求解。若目標函數是凹函數和凸函數的比值（最大化問題）及約束為凸集，對應分數規劃（英語：fractional programming）的方式轉換為凸集的求解問題。
3. 許多方式可以解非凸集的問題。其一個方式是用線性規劃問題的特殊公式；另一種方式則是用分支定界法：將問題分為幾個可以用凸集法（最小化問題）求解或是線性近似的子集合，較小區域內的總成本會有一下限。在隨後的分區後，在一些點上其成成本會等於所有近似解的下限，此解即為實際解。此解雖然不一定唯一，不過是為最佳解。若已確認可能的最佳解和已找到的解之間的誤差在容許值內，可以提早結束此演算法。這些點稱為ε-最佳。若要在有限內結束，一般就需要在ε-最佳點結束。尤其在大型的、困難的問題，或是問題有不確定的成本或價值，但不確定以由適當的信賴性估測所估測時，更需要在ε-最佳點結束的技巧。
4. 在可微函數及約束規范的條件下，卡羅需－庫恩－塔克條件（KKT條件）是有最佳解的必要條件。在凸集的條件下，這也是充份條件。若其中有些函數是不可微分的，也可以用次導數條件的卡羅需－庫恩－塔克條件。^[2]

例子

2維實例

線的交點及約束空間表示了該解。可達到的最優值輪廓線（目標值為給定值的軌跡）。

可以用下列約束來定義一個簡單問題

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

需要最大化的目標函數為

f(x) = x₁ + x₂

其中 x = (x₁, x₂)。解決二維問題 （頁面存檔備份，存於互聯網檔案館）.

3維實例

位於中部的上面曲面與約束空間相交的部分表示解

用下面這些約束就可以定義另一個簡單的問題

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

需要最大化的目標函數為

f(x) = x₁x₂ + x₂x₃

其中 x = (x₁, x₂，x₃). 解決三維問題 （頁面存檔備份，存於互聯網檔案館）。

應用

工程中用到非線性最佳化，例如建立儲油池的計算模型，^[3] 或油氣藏工程的決策制定。^[4]

參見

• 曲線擬合
• 最小平方法
• 線性規劃
• nl (文件格式)（英語：nl (format)）
• 最佳化
• 最佳化軟件列表（英語：List of optimization software）
• 維爾納·費恩雪爾（英語：Werner Fenchel）

參考文獻

1. Bertsekas, Dimitri P. Nonlinear Programming Second. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0.
2. Ruszczyński, Andrzej. Nonlinear Optimization. Princeton, NJ: Princeton University Press. 2006: xii+454. ISBN 978-0691119151. MR 2199043.
3. History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, http://www.sciencedirect.com/science/article/pii/S0920410513003227 （頁面存檔備份，存於互聯網檔案館）
4. Closed-loop field development under uncertainty using optimization with sample validation. http://dx.doi.org/10.2118/173219-PA

延伸閱讀

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
• Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. Numerical optimization: Theoretical and practical aspects. Universitext Second revised ed. of translation of 1997 French. Berlin: Springer-Verlag. 2006: xiv+490 [2015-09-19]. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5. （原始內容存檔於2013-07-19）.
• Luenberger, David G.; Ye, Yinyu. Linear and nonlinear programming. International Series in Operations Research & Management Science 116 Third. New York: Springer. 2008: xiv+546. ISBN 978-0-387-74502-2. MR 2423726.
• Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
• Jan Brinkhuis and Vladimir Tikhomirov, 'Optimization: Insights and Applications', 2005, Princeton University Press

外部連結

• Nonlinear programming FAQ （頁面存檔備份，存於互聯網檔案館）
• Mathematical Programming Glossary （頁面存檔備份，存於互聯網檔案館）
• Nonlinear Programming Survey OR/MS Today
• Overview of Optimization in Industry （頁面存檔備份，存於互聯網檔案館）