数学建模社区-数学中国
标题:
[转帖]侃侃计算数学 （数值优化）
[打印本页]
作者:
god
时间:
2005-1-19 16:20
标题:
[转帖]侃侃计算数学 （数值优化）
谈到数值优化，不能不提的是单纯形算法。这被誉为20世纪最受人欢迎的算法为人们带来
! r1 X2 w. V R$ V9 e
巨大的经济效益。不过有趣的是，这个最好的算法在算法复杂度理论里面却解释不通，
2 ^' v1 ]: G/ I4 v* X ]# ~
因为它不是多项式算法。
. B7 P6 i) v; L- o: Y3 j1 V
; _- l; p& p! \( y5 g
数值优化以求解有约束或无约束条件下函数最值为目标。我想数值优化里面最
$ i5 E# A# L9 W; J/ a
令人头疼的是如何判断你找到的不是极值而是最值。因为二者的区分
/ n% b* E3 z& w" Z: w$ L- H$ S
似乎只能从函数值上得到，其它的信息包括各种导数似乎都没有什么区别。但是，
) e" R4 @' r; [- e
实际中的很多问题都有大量的极值点，如果挨个寻找根本不可能。
4 u; f! p! w. ^6 r( z; T1 N
对付这个问题，现在最有效的武器应该是随机算法包括遗传算法等等。但是，
* E, c0 D, D h
其庞大的计算量有时也让人望而却步。
O4 a. @( R" T8 c3 {
优化里面另外一个困难的问题是整数优化，凡是涉及的整数的问题总是令人头疼的
5 v6 x5 t- o- U# v$ \: P/ o
，因为限制太为严格。直到今天，人们连线性方程组的整数解都没有完全解决，
9 S0 O+ m- d5 C( H
何况在此基础上考虑整数规划等等。
0 N* N9 ?7 m* }/ I
其它的诸如不可微优化、非线性规划等等发展到今天似乎很难有什么突破，也局限于在
! w& W2 X Q3 L
理论上推导满足一些条件的算法，但实际中有几个问题能满足这些条件（我的愚见，未必正确）。
C8 y2 [# r( o0 P7 S
2 w5 f1 y9 i6 S) @/ x
现在，与计算机组合优化密切相关的计算复杂度理论异军突起，新千年7个悬赏问题之一
8 T$ |6 n) t3 W& R
就是与之相关的P是否等于NP.我想，结合图论组合优化计算机等学科，这一方面的发展是很有空间的。
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5