非线性规划

在数学中，非线性规划是求解由一系列未知实函数组成的组方程和不等式（统称为约束）定义的最佳化問題，伴随着一个要被最大化或最小化的目标函数，只是一些约束或目标函数是非線性的。[1] 它是最优化处理非线性问题的一个子领域。

适用性

从一系列运输方法中选择优化运输成本的一个或多个表现规模经济的连通性和容量约束不同的非凸问题。例如从管道、铁路油槽车、罐车、河驳船或沿海油船中选择或组合的石油产品运输。由于经济批量大小，除了平滑变化之外，成本函数可以有不连续性。

现代工程实践涉及到大量的数值优化。除了在很少一部分重要情形（如无源电路）中，工程问题是非线性的，它们通常是非常复杂。

在实验科学中，一些简单的数据分析（如已知位置和形状但未知幅度的峰的总和的光谱的拟合）可以用线性方法来完成，但一般来说这些问题也是非线性的。通常研究的是含有变量参数的系统的理论模型以及含有未知参数的试验模型。可以试着用数值寻找最优值。这种情况下，除了最优值本身通常还需要对结果的精度进行量度。

定义

令 n、m、p为正整数。令 X 为 Rn 的一个子集，令 f、gi 和 hj 为 X 的实值函数，对每个 i 属于 {1, …, m} 及每个 j 属于 {1, …, p}。

非线性最小化问题是下面形式的最佳化問題

非线性最大化问题定义方式类似。

约束集的可能类型

约束集的性质有若干可能性，也被称为可行集或可行域。

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

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

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

求解問題的方法

若目標函數f為線性，約束的空间為多胞形，此問題是线性规划問題，可以用許多著名的线性规划解來求解。

若目標函數為凹函数（最大化問題）或是凸函数（最小化問題），且約束為凸集，此問題稱為凸規劃問題，大部份情形下可以用凸優化的方式來求解。

若目標函數是凹函数和凸函数的比值（最大化問題）及約束為凸集，此問題可以用分數規劃的方式轉換為凸集的最佳化問題。

許多方式可以解非凸集的問題。其一個方式是用線性規劃問題的特殊公式，另一種方式則是用分支定界法，將問題分為幾個可以用凸集法（最小化問題）求解或是線性近似的子集合，較小區域內的總成本會有一下限。在隨後的分區後，在一些點上其成成本會等於所有近似解的下限，此解即為實際解。此解雖然不一定唯一，不過是為最佳解。若已確認可能的最佳解和已找到的解之間的誤差在容許值內，可以提早結束此演算法。這些點稱為ε-最佳。若要在有限內結束，一般就需要在ε-最佳點結束。尤其在大型的、困難的問題，或是問題有不確定的成本或價值，但不確定以由適當的信賴性估測所估測時，更需要在ε-最佳點結束的技巧。

在可微函数及約束規范的條件下，卡羅需－庫恩－塔克條件（KKT條件）是有最佳解的必要條件。在凸集的條件下，這也是充份條件。若其中有些函數是不可微分的，也可以用次导数條件的卡羅需－庫恩－塔克條件。[2]

例子

2维实例
线的交点及约束空间表示了该解。可达到的最优值轮廓线（目标值为给定值的轨迹）。

可以用下列约束来定义一个简单问题

x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2

需要最大化的目标函数为

f(x) = x1 + x2

其中 x = (x1, x2)。解决二维问题.

3维实例
位于中部的上面曲面与约束空间相交的部分表示解

用下面这些约束就可以定义另一个简单的问题

x12 − x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10

需要最大化的目标函数为

f(x) = x1x2 + x2x3

其中 x = (x1, x2，x3). 解决三维问题。

应用

工程中用到非线性优化，例如建立储油池的计算模型，[3] 或油气藏工程的决策制定。[4]

参见

参考文献
  1. Bertsekas, Dimitri P. Second. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0.
  2. Ruszczyński, Andrzej. . 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. . Universitext Second revised ed. of translation of 1997 French. Berlin: Springer-Verlag. 2006: xiv+490. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5.
  • Luenberger, David G.; Ye, Yinyu. . 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

外部链接
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.