数学建模社区-数学中国
标题:
[转帖]侃侃计算数学 （数值优化）
[打印本页]
作者:
god
时间:
2005-1-19 16:20
标题:
[转帖]侃侃计算数学 （数值优化）
谈到数值优化，不能不提的是单纯形算法。这被誉为20世纪最受人欢迎的算法为人们带来
/ g$ `% r2 g6 _- _+ {8 d
巨大的经济效益。不过有趣的是，这个最好的算法在算法复杂度理论里面却解释不通，
# r: d& [' X- s" V9 D s3 z$ Q
因为它不是多项式算法。
3 w" h5 [1 L$ D' h
5 o; B! ]. g) Y/ Y0 I7 a( X
数值优化以求解有约束或无约束条件下函数最值为目标。我想数值优化里面最
6 k+ Z* l! F+ B% B
令人头疼的是如何判断你找到的不是极值而是最值。因为二者的区分
- `0 ]% ?! V/ S( n4 H" L) @
似乎只能从函数值上得到，其它的信息包括各种导数似乎都没有什么区别。但是，
" L) p+ p- j5 D; T" F3 u
实际中的很多问题都有大量的极值点，如果挨个寻找根本不可能。
! C) D4 w- Q0 n( |
对付这个问题，现在最有效的武器应该是随机算法包括遗传算法等等。但是，
. f# i d. C' L6 S; F: B
其庞大的计算量有时也让人望而却步。
6 Y+ z) G+ O0 i1 d, {8 M r
优化里面另外一个困难的问题是整数优化，凡是涉及的整数的问题总是令人头疼的
0 P' O7 s# X+ @
，因为限制太为严格。直到今天，人们连线性方程组的整数解都没有完全解决，
6 R, H) r# ^1 C" `
何况在此基础上考虑整数规划等等。
, k5 m1 C% u$ W7 c% Q& E6 `
其它的诸如不可微优化、非线性规划等等发展到今天似乎很难有什么突破，也局限于在
) U% F) \9 D4 |' w1 o
理论上推导满足一些条件的算法，但实际中有几个问题能满足这些条件（我的愚见，未必正确）。
! `! y: @$ I$ d! A) q+ q( ]
+ s4 _8 p5 ?0 E5 d
现在，与计算机组合优化密切相关的计算复杂度理论异军突起，新千年7个悬赏问题之一
+ V& h( F0 U( g
就是与之相关的P是否等于NP.我想，结合图论组合优化计算机等学科，这一方面的发展是很有空间的。
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5