闲谈对偶 （三） BY cw

无墨

 

极小极大对偶定理，几乎是搞优化的人必然注目的结构，它们通常都有很“美”的表达、“漂亮”的证明、“广泛”的应用和“有效”的算法。神奇之处，不能不让人感叹大自然造化美妙。

- ?- E) y+ ~' h- U2 M& j

 

数学的第一个对偶定理，是冯。诺伊曼（Von Neumann）一九二八年证明的对策论的二人零和搏弈极小极大定理。冯。诺伊曼开创性的对偶定理，不仅奠定了对策论的基础，更是给世界上无数的数学家和数学匠提供了饭碗。后者从每年发表的和对偶性有关的论文上就可以看到。在残酷的现实里，Tenure是要拿论文来换的。

 

在二人零和搏弈里，大家得到的好处加起来总是一个常数，和大家的策略方式无关。一个人得到的好处就是另一个人的损失。围棋象棋就是二人零和搏弈的典型例子。只是围棋象棋变化太多，一步之差后，最优的下法就可能会不同。没有人能记得住不同布局下的不同最优对策。哪怕是现在最大最快的计算机也不行。

 

# F' {# y# m; ]" O0 U

下面是一个有趣的二人零和搏弈例子。特别之处，在于最好的策略和结果都一目了然，可以一步定乾坤。有趣的是，麻雀虽小，五脏俱全。它涉及到的思想方法、对偶量和对偶性分析，在对偶论里很典型，很有代表性。

 

这例子说的是两个饥饿的艺术家为分一块小烧饼争执。因为都不希望自己少吃，谁也不放心让对方来分这个饼。于是两人找到数学家，希望数学家有一个公平可信的办法让两人都能接受。数学家于是建议，由两人中的一个把饼分为两块，怎么分都可以，当然越有艺术性越好。而另一个则可以在分出来两块里任选一块，选择标准不限。

! _& W6 l, m! b+ z: Z

 

在数学家制定的规则下，两人应该怎么分这块饼？尽管艺术家不一定知道搏弈论的定理，但形象思维能力很强。可以先在纸上画个饼，试一试。当然这也是数学家的老一套：当基本命题太复杂而不知从何下手的时侯，先看看特例，缩小范围，减少复杂性。

1 B" _ o; D: A6 U7 Z& [4 h, ?

 

; G/ x) @# y8 t0 b+ k* ~! P

如果稍微想一想，有一点可能很显然，那就是一旦第一个人把烧饼分开，他能得到多少完全在于第二个人的选择。所以第一个人在行动的时候必须首先考虑对方的行为。另一方面，如果第一个人切出大小不同的两块，那第二个人肯定会选大的一块，留给第一个人一块小的。

所以，如果分饼的人把饼分成两块，他应该让那块可能大一些的尽量的小，也应该让那块可能小一些的尽量的大。前者是为了尽量地减少可能的损失，即极小化最大损失（Minimize the maximum）。后者是尽量地争取可能的好处，既极大化最小利益（Maximize the minimum）。

* L; l# @5 {/ E

 

; R6 [$ v8 R6 @1 k( n. f1 f$ H/ V

这时候，也许你已经可以看出来，在数学家的规则下，不管由谁来分，最好的就是把烧饼分成同样大小的两块，一人一半。这样，两个人都得到最大可能的利益，而可能的损失则减到了最低。

2 r) w3 j9 q4 l4 x* l! z

 

6 @! n4 Y& K' \8 i" X+ q- @+ O8 r

这也就是冯。诺伊曼的对偶定理：在满足一定条件的零和搏弈中，有策略使搏弈的一方同时取得代表利益的极大极小值和代表损失的极小极大值。

 

冯。诺伊曼对偶定理的精华在于分析和思想方法的精妙有趣和它们给数学研究带来的深远影响。在分析烧饼的时候我们看到，在从不同的角度来考虑同一个问题的时候，我们可以把问题的目的叙述成两个完全背道相驰的对偶量分别的极大化和极小化。而精彩就在最后一瞬间的灿烂中：两个对偶量殊途同归，在一个点上相遇。

 

5 t; v! I# j, J+ }6 G( ?. L2 G

当然，话说回来，灿烂的前提是你要找对了对偶量。另外，要证明两个对偶量之间的关系也常常很难。好消息是，一旦你找对了并证明了对偶关系，你也很可能得到了一套一劳永逸的方法。这是后话。

 

0 T! s, ^$ L* g$ V

回到题头的这幅画。这是从一幅照片的局部开始，用Photoshop处理，再加上一番手画。内容其实和对偶性没有什么直接关系。放在这里的原因，一来它是我在写这一段的时候画的，算是对偶性的“闲作”，副产品。二来是在作这幅画的过程里，也得到了一套方式，从此可以很快的搞出很多类似这样的画，大概十到二十分钟就可以搞定一幅。

# e" i" t6 _% q! t" ]2 @; H: I1 M

 

这也算是体现了做数学的精神。数学家一般很懒，更关心的是一个方法、或一种分析方式能不能推而广之，放之四海皆准，一劳永逸。不然的话，如果每吃一个烧饼都要动脑筋，生活就太累人了。