查看“︁非线性规划”︁的源代码

{{NoteTA|G1=Math}}
在[[数学]]中，'''非线性规划'''是求解由一系列未知[[实函数]]组成的[[方程组|组]][[方程]]和[[不等|不等式]]（统称为[[約束 (數學)|约束]]）定义的[[最佳化問題]]，伴随着一个要被最大化或最小化的目标[[函数]]，只是一些约束或目标函数是[[非線性]]的。<ref>{{cite book
  | last = Bertsekas
  | first = Dimitri P.
  | authorlink = Dimitri P. Bertsekas
  | title = Nonlinear Programming
  | edition = Second
  | publisher = Athena Scientific
  | year = 1999
  | location = Cambridge, MA.
  | isbn = 1-886529-00-0 
}}</ref>它是[[最优化]]处理非线性问题的一个子领域。

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

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

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

== 定义 ==

令 ''n''、''m''、''p''为正整数。令 ''X'' 为 ''R<sup>n</sup>'' 的一个子集，令 ''f''、''g<sub>i</sub>'' 和 ''h<sub>j</sub>'' 为 ''X'' 的{{le|实值函数|real-valued function}}，对每个 ''i'' 属于 {''1'', &hellip;, ''m''} 及每个 ''j'' 属于 {''1'', &hellip;, ''p''}。

非线性最小化问题等效为下面形式的[[最佳化問題]]

:<math>
\begin{align}
  \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{align}
</math>

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

== 约束集的可能类型 ==

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

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

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

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

==求解問題的方案分析==
#若目標函數''f(x)''為線性，約束的[[欧几里得空间|空间]]為[[多胞形]]，对应[[线性规划]]問題，采用著名的线性规划法求解。
#若目標函數為[[凹函数]]（最大化）或是[[凸函数]]（最小化），且約束為[[凸集]]，对应凸規劃問題，常采用[[凸優化]]求解。若目標函數是凹函数和凸函数的比值（最大化問題）及約束為凸集，对应{{le|分數規劃|fractional programming}}的方式轉換為凸集的求解問題。
#許多方式可以解非凸集的問題。其一個方式是用線性規劃問題的特殊公式；另一種方式則是用[[分支定界|分支定界法]]：將問題分為幾個可以用凸集法（最小化問題）求解或是線性近似的子集合，較小區域內的總成本會有一下限。在隨後的分區後，在一些點上其成成本會等於所有近似解的下限，此解即為實際解。此解雖然不一定唯一，不過是為最佳解。若已確認可能的最佳解和已找到的解之間的誤差在容許值內，可以提早結束此演算法。這些點稱為ε-最佳。若要在有限內結束，一般就需要在ε-最佳點結束。尤其在大型的、困難的問題，或是問題有不確定的成本或價值，但不確定以由適當的信賴性估測所估測時，更需要在ε-最佳點結束的技巧。
#在[[可微函数]]及[[卡羅需－庫恩－塔克條件|約束規范]]的條件下，[[卡羅需－庫恩－塔克條件]]（KKT條件）是有最佳解的必要條件。在凸集的條件下，這也是充份條件。若其中有些函數是不可微分的，也可以用[[次导数]]條件的[[卡羅需－庫恩－塔克條件]]。<ref>
{{cite book|last=Ruszczyński|first=Andrzej|title=Nonlinear Optimization|publisher=[[普林斯頓大學出版社|Princeton University Press]]|location=Princeton, NJ|year=2006|pages=xii+454|isbn=978-0691119151 |mr=2199043}}</ref>

==例子==

===2维实例===

[[Image:Nonlinear programming.svg|200px|thumb|right|线的交点及约束空间表示了该解。可达到的最优值轮廓线（目标值为给定值的轨迹）。]]
可以用下列约束来定义一个简单问题
:''x''<sub>1</sub> &ge; 0
:''x''<sub>2</sub> &ge; 0
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> &ge; 1
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> &le; 2
需要最大化的目标函数为
:''f''('''x''') = ''x''<sub>1</sub> + ''x''<sub>2</sub>
其中 '''x''' = (''x''<sub>1</sub>, ''x''<sub>2</sub>)。[http://apmonitor.com/online/view_pass.php?f=2d.apm 解决二维问题] {{Wayback|url=http://apmonitor.com/online/view_pass.php?f=2d.apm |date=20210124014953 }}.

===3维实例===
[[Image:Nonlinear programming 3D.svg|thumb|right|位于中部的上面曲面与约束空间相交的部分表示解]]
用下面这些约束就可以定义另一个简单的问题
:''x''<sub>1</sub><sup>2</sup> &minus; ''x''<sub>2</sub><sup>2</sup> + ''x''<sub>3</sub><sup>2</sup> &le; 2
:''x''<sub>1</sub><sup>2</sup> + ''x''<sub>2</sub><sup>2</sup> + ''x''<sub>3</sub><sup>2</sup> &le; 10
需要最大化的目标函数为
:''f''('''x''') = ''x''<sub>1</sub>''x''<sub>2</sub> + ''x''<sub>2</sub>''x''<sub>3</sub>
其中 '''x''' = (''x''<sub>1</sub>, ''x''<sub>2</sub>，''x''<sub>3</sub>).  [http://apmonitor.com/online/view_pass.php?f=3d.apm 解决三维问题] {{Wayback|url=http://apmonitor.com/online/view_pass.php?f=3d.apm |date=20210124032109 }}。

==应用==
工程中用到非线性优化，例如建立储油池的计算模型，<ref>History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, http://www.sciencedirect.com/science/article/pii/S0920410513003227 {{Wayback|url=http://www.sciencedirect.com/science/article/pii/S0920410513003227 |date=20170117171625 }}</ref> 或油气藏工程的决策制定。<ref>Closed-loop field development under uncertainty using optimization with sample validation. http://dx.doi.org/10.2118/173219-PA</ref>

==参见==
* [[曲線擬合]]
* [[最小二乘法]]
* [[线性规划]]
* {{le|nl (文件格式)|nl (format)}}
* [[最优化]]
* {{le|最优化软件列表|List of optimization software}}
*{{le|维尔纳·费恩雪尔|Werner Fenchel}}

==参考文献==
<references/>

==延伸阅读==

* 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.
* {{cite book|last1=Bonnans|first1=J.&nbsp;Frédéric|last2=Gilbert|first2=J.&nbsp;Charles|last3=Lemaréchal|first3=Claude|authorlink3=Claude Lemaréchal|last4=Sagastizábal|first4=Claudia&nbsp;A.|title=Numerical optimization: Theoretical and practical aspects|url=http://www.springer.com/mathematics/applications/book/978-3-540-35445-1|edition=Second revised ed. of  translation of 1997 <!-- ''Optimisation numérique: Aspects théoriques et pratiques'' --> French|series=Universitext|publisher=Springer-Verlag|location=Berlin|year=2006|pages=xiv+490|isbn=3-540-35445-X|doi=10.1007/978-3-540-35447-5|mr=2265882|access-date=2015-09-19|archive-date=2013-07-19|archive-url=https://web.archive.org/web/20130719050442/http://www.springer.com/mathematics/applications/book/978-3-540-35445-1}}
* {{cite book|last1=Luenberger|first1=David G.|authorlink1=David G. Luenberger|last2=Ye|first2=Yinyu|authorlink2=Yinyu Ye|title=Linear and nonlinear programming|edition=Third|series=International Series in Operations Research & Management Science|volume=116|publisher=Springer|location=New York|year=2008|pages=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

==外部链接==
*[http://neos-guide.org/non-lp-faq Nonlinear programming FAQ] {{Wayback|url=http://neos-guide.org/non-lp-faq |date=20210506130349 }}
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] {{Wayback|url=http://glossary.computing.society.informs.org/ |date=20100328165516 }}
*[https://web.archive.org/web/20090724004340/http://lionhrtpub.com/orms/surveys/nlp/nlp.html Nonlinear Programming Survey OR/MS Today]
*[http://apmonitor.com/wiki/index.php/Main/Background Overview of Optimization in Industry] {{Wayback|url=http://apmonitor.com/wiki/index.php/Main/Background |date=20160306102503 }}

{{DEFAULTSORT:非线性规划}}
[[Category:數學最佳化]]