数学建模社区-数学中国

标题: 侃侃计算数学 [打印本页]
作者: luoyezi    时间: 2005-1-8 22:48
标题: 侃侃计算数学
3 Q2 `9 Q6 M$ } D$ v: J) @" G* F: l. ]+ J% _) A) m. G- j$ C6 Y" U; S
侃侃计算数学 （数值优化）
! F/ z9 U7 l7 ~8 I* ?% [1 H6 n
; [/ e& @, |/ Y1 z% d" B- U9 H' R
谈到数值优化，不能不提的是单纯形算法。这被誉为20世纪最受人欢迎的算法为人们带来 & u+ Q; P8 G- F 巨大的经济效益。不过有趣的是，这个最好的算法在算法复杂度理论里面却解释不通， 2 M! o. X. v) n因为它不是多项式算法。 # d3 ^" D2 L8 i2 m0 B' z5 W4 F+ |4 V 数值优化以求解有约束或无约束条件下函数最值为目标。我想数值优化里面最 " r, Z$ z0 k7 u8 u5 s" I& t8 U9 j令人头疼的是如何判断你找到的不是极值而是最值。因为二者的区分 # p. G6 f Z- E4 n' m( J9 J Y似乎只能从函数值上得到，其它的信息包括各种导数似乎都没有什么区别。但是， % L# `3 t3 m) \8 y3 S 实际中的很多问题都有大量的极值点，如果挨个寻找根本不可能。 8 v. {7 [) H0 ? 对付这个问题，现在最有效的武器应该是随机算法包括遗传算法等等。但是， - L. a# z4 d, E" R, P4 U 其庞大的计算量有时也让人望而却步。 3 j/ \8 k$ a6 W, D优化里面另外一个困难的问题是整数优化，凡是涉及的整数的问题总是令人头疼的 ( P& s2 `$ Q$ K" V6 q/ w7 ^# x9 ]，因为限制太为严格。直到今天，人们连线性方程组的整数解都没有完全解决， . N$ b+ J1 S9 a* |' `8 F 何况在此基础上考虑整数规划等等。 . ~: p2 m: Q' t. J6 L+ | 其它的诸如不可微优化、非线性规划等等发展到今天似乎很难有什么突破，也局限于在 , x# Y( b, B4 Q A理论上推导满足一些条件的算法，但实际中有几个问题能满足这些条件（我的愚见，未必正确）。 2 f7 ]! a0 g6 Y8 N0 k 1 t- r/ G b7 ]4 o4 y, P% @现在，与计算机组合优化密切相关的计算复杂度理论异军突起，新千年7个悬赏问题之一 ! Y$ C/ o3 a6 G% `1 W 就是与之相关的P是否等于NP.我想，结合图论组合优化计算机等学科，这一方面的发展是很有空间的。 6 Z4 X$ ]- t' {& x( h# e; Q




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5