fbpx
维基百科

非线性规划

十二月 28, 2023

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

适用性 编辑

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

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

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

定义 编辑

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

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

 

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

约束集的可能类型 编辑

约束集的性质有若干可能性，也被称为可行集或可行域（英语：feasible region）。

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

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

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

求解問題的方案分析 编辑

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

外部链接 编辑

十二月 28, 2023
非线性规划, 在数学中, 是求解由一系列未知实函数组成的组方程和不等式, 统称为约束, 定义的最佳化問題, 伴随着一个要被最大化或最小化的目标函数, 只是一些约束或目标函数是非線性的, 它是最优化处理非线性问题的一个子领域, 目录, 适用性, 定义, 约束集的可能类型, 求解問題的方案分析, 例子, 2维实例, 3维实例, 应用, 参见, 参考文献, 延伸阅读, 外部链接适用性, 编辑从一系列运输方法中选择优化运输成本的一个或多个表现规模经济的连通性和容量约束不同的非凸问题, 例如从管道, 铁路油槽车, 罐车, 河. 在数学中 非线性规划是求解由一系列未知实函数组成的组方程和不等式 统称为约束 定义的最佳化問題 伴随着一个要被最大化或最小化的目标函数 只是一些约束或目标函数是非線性的 1 它是最优化处理非线性问题的一个子领域 目录 1 适用性 2 定义 3 约束集的可能类型 4 求解問題的方案分析 5 例子 5 1 2维实例 5 2 3维实例 6 应用 7 参见 8 参考文献 9 延伸阅读 10 外部链接适用性 编辑从一系列运输方法中选择优化运输成本的一个或多个表现规模经济的连通性和容量约束不同的非凸问题 例如从管道 铁路油槽车 罐车 河驳船或沿海油船中选择或组合的石油产品运输 由于经济批量大小 除了平滑变化之外 成本函数可以有不连续性 现代工程实践涉及到大量的数值优化 除了在很少一部分重要情形 如无源电路 中 工程问题是非线性的 它们通常是非常复杂 在实验科学中 一些简单的数据分析 如已知位置和形状但未知幅度的峰的总和的光谱的拟合 可以用线性方法来完成 但一般来说这些问题也是非线性的 通常研究的是含有变量参数的系统的理论模型以及含有未知参数的试验模型 可以试着用数值寻找最优值 这种情况下 除了最优值本身通常还需要对结果的精度进行量度 定义 编辑令 n m p为正整数 令 X 为 Rn 的一个子集 令 f gi 和 hj 为 X 的实值函数 英语 real valued function 对每个 i 属于 1 m 及每个 j 属于 1 p 非线性最小化问题等效为下面形式的最佳化問題 minimize f x subject to g i x 0 for each i 1 m h j x 0 for each j 1 p x X displaystyle begin aligned text minimize amp f x text subject to amp g i x leq 0 text for each i in 1 dotsc m amp h j x 0 text for each j in 1 dotsc p amp x in X end aligned nbsp 非线性最大化问题定义方式类似 约束集的可能类型 编辑约束集的性质有若干可能性 也被称为可行集或可行域 英语 feasible region 無解問題 infeasible problem 是指沒有一組變數可以滿足所有的約束 也就是約束之間有互相矛盾的情形 沒有解存在 有解問題 feasible problem 是指至少有一組變數可以滿足所有的約束條件 无界限問題 unbounded problem 是一個有解問題 其變數沒有上限限制 因此沒有最佳解 因為總會有一組變數使得目標函數比其他組的變數有更好的結果 求解問題的方案分析 编辑若目標函數f x 為線性 約束的空间為多胞形 对应线性规划問題 采用著名的线性规划法求解 若目標函數為凹函数 最大化 或是凸函数 最小化 且約束為凸集 对应凸規劃問題 常采用凸優化求解 若目標函數是凹函数和凸函数的比值 最大化問題 及約束為凸集 对应分數規劃 英语 fractional programming 的方式轉換為凸集的求解問題 許多方式可以解非凸集的問題 其一個方式是用線性規劃問題的特殊公式 另一種方式則是用分支定界法 將問題分為幾個可以用凸集法 最小化問題 求解或是線性近似的子集合 較小區域內的總成本會有一下限 在隨後的分區後 在一些點上其成成本會等於所有近似解的下限 此解即為實際解 此解雖然不一定唯一 不過是為最佳解 若已確認可能的最佳解和已找到的解之間的誤差在容許值內 可以提早結束此演算法 這些點稱為e 最佳 若要在有限內結束 一般就需要在e 最佳點結束 尤其在大型的 困難的問題 或是問題有不確定的成本或價值 但不確定以由適當的信賴性估測所估測時 更需要在e 最佳點結束的技巧 在可微函数及約束規范的條件下 卡羅需 庫恩 塔克條件 KKT條件 是有最佳解的必要條件 在凸集的條件下 這也是充份條件 若其中有些函數是不可微分的 也可以用次导数條件的卡羅需 庫恩 塔克條件 2 例子 编辑2维实例 编辑 nbsp 线的交点及约束空间表示了该解 可达到的最优值轮廓线 目标值为给定值的轨迹 可以用下列约束来定义一个简单问题 x1 0 x2 0 x12 x22 1 x12 x22 2需要最大化的目标函数为 f x x1 x2其中 x x1 x2 解决二维问题 页面存档备份 存于互联网档案馆 3维实例 编辑 nbsp 位于中部的上面曲面与约束空间相交的部分表示解用下面这些约束就可以定义另一个简单的问题 x12 x22 x32 2 x12 x22 x32 10需要最大化的目标函数为 f x x1x2 x2x3其中 x x1 x2 x3 解决三维问题 页面存档备份 存于互联网档案馆 应用 编辑工程中用到非线性优化 例如建立储油池的计算模型 3 或油气藏工程的决策制定 4 参见 编辑曲線擬合 最小二乘法 线性规划 nl 文件格式 英语 nl format 最优化 最优化软件列表 英语 List of optimization software 维尔纳 费恩雪尔 英语 Werner Fenchel 参考文献 编辑 Bertsekas Dimitri P Nonlinear Programming Second Cambridge MA Athena Scientific 1999 ISBN 1 886529 00 0 Ruszczynski Andrzej Nonlinear Optimization Princeton NJ Princeton University Press 2006 xii 454 ISBN 978 0691119151 MR 2199043 History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm http www sciencedirect com science article pii S0920410513003227 页面存档备份 存于互联网档案馆 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 amp Sons ISBN 0 471 78610 1 Bertsekas Dimitri P 1999 Nonlinear Programming 2nd Edition Athena Scientific ISBN 1 886529 00 0 Bonnans J Frederic Gilbert J Charles Lemarechal Claude Sagastizabal 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 amp 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 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 非线性规划 amp oldid 72965649, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。