2005 (3)
2008 (126)
2010 (2)
2021 (2)
極小極大對偶定理，幾乎是搞優化的人必然注目的結構，它們通常都有很“美”的表達、“漂亮”的證明、“廣泛”的應用和“有效”的算法。神奇之處，不能不讓人感歎大自然造化美妙。
數學的第一個對偶定理，是馮。諾伊曼（Von Neumann）一九二八年證明的對策論的二人零和搏弈極小極大定理。馮。諾伊曼開創性的對偶定理，不僅奠定了對策論的基礎，更是給世界上無數的數學家和數學匠提供了飯碗。後者從每年發表的和對偶性有關的論文上就可以看到。在殘酷的現實裏，Tenure是要拿論文來換的。
在二人零和搏弈裏，大家得到的好處加起來總是一個常數，和大家的策略方式無關。一個人得到的好處就是另一個人的損失。圍棋象棋就是二人零和搏弈的典型例子。隻是圍棋象棋變化太多，一步之差後，最優的下法就可能會不同。沒有人能記得住不同布局下的不同最優對策。哪怕是現在最大最快的計算機也不行。
下麵是一個有趣的二人零和搏弈例子。特別之處，在於最好的策略和結果都一目了然，可以一步定乾坤。有趣的是，麻雀雖小，五髒俱全。它涉及到的思想方法、對偶量和對偶性分析，在對偶論裏很典型，很有代表性。
這例子說的是兩個饑餓的藝術家為分一塊小燒餅爭執。因為都不希望自己少吃，誰也不放心讓對方來分這個餅。於是兩人找到數學家，希望數學家有一個公平可信的辦法讓兩人都能接受。數學家於是建議，由兩人中的一個把餅分為兩塊，怎麽分都可以，當然越有藝術性越好。而另一個則可以在分出來兩塊裏任選一塊，選擇標準不限。
在數學家製定的規則下，兩人應該怎麽分這塊餅？盡管藝術家不一定知道搏弈論的定理，但形象思維能力很強。可以先在紙上畫個餅，試一試。當然這也是數學家的老一套：當基本命題太複雜而不知從何下手的時侯，先看看特例，縮小範圍，減少複雜性。
如果稍微想一想，有一點可能很顯然，那就是一旦第一個人把燒餅分開，他能得到多少完全在於第二個人的選擇。所以第一個人在行動的時候必須首先考慮對方的行為。另一方麵，如果第一個人切出大小不同的兩塊，那第二個人肯定會選大的一塊，留給第一個人一塊小的。
所以，如果分餅的人把餅分成兩塊，他應該讓那塊可能大一些的盡量的小，也應該讓那塊可能小一些的盡量的大。前者是為了盡量地減少可能的損失，即極小化最大損失（Minimize the maximum）。後者是盡量地爭取可能的好處，既極大化最小利益（Maximize the minimum）。
這時候，也許你已經可以看出來，在數學家的規則下，不管由誰來分，最好的就是把燒餅分成同樣大小的兩塊，一人一半。這樣，兩個人都得到最大可能的利益，而可能的損失則減到了最低。
這也就是馮。諾伊曼的對偶定理：在滿足一定條件的零和搏弈中，有策略使搏弈的一方同時取得代表利益的極大極小值和代表損失的極小極大值。
馮。諾伊曼對偶定理的精華在於分析和思想方法的精妙有趣和它們給數學研究帶來的深遠影響。在分析燒餅的時候我們看到，在從不同的角度來考慮同一個問題的時候，我們可以把問題的目的敘述成兩個完全背道相馳的對偶量分別的極大化和極小化。而精彩就在最後一瞬間的燦爛中：兩個對偶量殊途同歸，在一個點上相遇。
當然，話說回來，燦爛的前提是你要找對了對偶量。另外，要證明兩個對偶量之間的關係也常常很難。好消息是，一旦你找對了並證明了對偶關係，你也很可能得到了一套一勞永逸的方法。這是後話。
回到題頭的這幅畫。這是從一幅照片的局部開始，用Photoshop處理，再加上一番手畫。內容其實和對偶性沒有什麽直接關係。放在這裏的原因，一來它是我在寫這一段的時候畫的，算是對偶性的“閑作”，副產品。二來是在作這幅畫的過程裏，也得到了一套方式，從此可以很快的搞出很多類似這樣的畫，大概十到二十分鍾就可以搞定一幅。
這也算是體現了做數學的精神。數學家一般很懶，更關心的是一個方法、或一種分析方式能不能推而廣之，放之四海皆準，一勞永逸。不然的話，如果每吃一個燒餅都要動腦筋，生活就太累人了。
這類的讀物還不怎麽知道。覺得小孩隻要把加法表和乘發表背好了，以後就一往無前了。:)
不當大廚也可以上餐館。腦筋讓數學家動就行:)
些有趣的讀物? 謝謝！