蒙特卡罗方法解线性规划

warmsnowman

求蒙特卡罗方法解线性规划详细的步骤和程序代码

liwenhui

它的核心思想是构造一个“摸球”的马尔可夫过程，目前国内好像没这方面的书籍出版，英文的书籍倒是有。

warmsnowman

liwenhui 发表于 2012-6-25 17:05
* b+ S# i4 \5 B" \9 f它的核心思想是构造一个“摸球”的马尔可夫过程，目前国内好像没这方面的书籍出版，英文的书籍倒是有。

% F+ a1 f% W0 ]+ D我后来是在线性规划的约束条件下产生随机数然后代入价值函数中求值。
你说的“构造一个“摸球”的马尔可夫过程”，我有点难以理解。能不能给出个例子具体说明下。谢谢

liwenhui

' }+ y5 \+ ]* y2 c9 g7 i" ]

warmsnowman 发表于 2012-6-28 12:25
$ h) h  c! d6 e! d- {- H我后来是在线性规划的约束条件下产生随机数然后代入价值函数中求值。
你说的“构造一个“摸球”的马尔可 ...

( s5 ?( G( c! F* _1 |+ b- c
这个过程一两句话说不清楚，我看能不能找到相关的资料给你看看。
) t' z. t. e0 K4 F用蒙特卡罗方法可以求解线性方程组、偏微分方程等，其主要思路俱是构造马尔可夫过程。
1 u2 C  m1 X: u+ y  E
" C. z+ }3 x1 @8 ?, m' P你的思路其实是“随机搜索”爬山法
如果目标函数只有个极值的话它能收敛到最优解，但是如果有多个极值，它只能收敛到局部解。
' V* _# H% Y& [9 [对于多元情况，你如何产生随机数？是“多维联合分布"产生还是单独地一个一个地产生随机数？
5 h( C# A) C. m- z5 r: Y我在知网上面见过类似的论文，是一些老师写的，我感它他们的理论推导不够，不能保证全局最优
其实，有类似的算法来求最优值，并且保证结果的收敛，它就是“模拟退火过程”，我一直想证明
2 C; n) f  [; i1 ?+ N6 g( U! s模拟退火过程与MCMC方法的等价性。

warmsnowman

liwenhui 发表于 2012-6-28 12:48
这个过程一两句话说不清楚，我看能不能找到相关的资料给你看看。
用蒙特卡罗方法可以求解线性方程组、 ...

多元的情况，产生随机数也是方便的吧，比如取分布都是独立同分布。（这样也就是一个一个产生的了）
! d3 }$ Q; m. l. S$ B6 {- f
# s0 H% s0 }. F. q7 G的确我那样做的话，不能保证是全局最优的

liwenhui

线性规划最好用单纯型迭代，不必要使用蒙特卡罗方法
2 i2 [" \) L- N" X4 t. E每个方法都其实用范围，如果为了结果的准确性的话就选用最合适的方法
: k8 t: H' d. ~, F( j/ v当人，如果为了探索而得到标新立异的方法话，另当别论。

warmsnowman

liwenhui 发表于 2012-6-29 17:28
! |# I8 w2 o' r- }( R  P! M线性规划最好用单纯型迭代，不必要使用蒙特卡罗方法
1 Y& B$ z0 o: K. U3 @$ V: X8 M每个方法都其实用范围，如果为了结果的准确性的话就选 ...

) H+ o" c) T+ h. I6 M& Q那是当然，在实际应用中如果有针对性的算法就用针对性的算法最好。
( Q4 ^) z/ c5 x/ Y但我这是只是想研究拓展下蒙特卡罗的用法，看下他在其他方面的应用，说不定有新的发现