最優(yōu)算法機制設(shè)計若干問題的研究結(jié)題摘要

我們從計算經(jīng)濟學(xué)和算法設(shè)計等兩方面對該項目進行了研究： 1) 我們給出了隨機的誠實機制的等價條件。它刻畫出了隨機的誠實機制的內(nèi)在的組合特性。該結(jié)果能夠指導(dǎo)我們設(shè)計誠實的機制。 2) 在此基礎(chǔ)上，我們給出了一個框架可以將一系列優(yōu)化問題的近似算法在不改變近似度的前提下，轉(zhuǎn)換成誠實機制，這將有助于我們設(shè)計收益最優(yōu)化的誠實機制。 3) 我們從理論上證明了如果一個競拍者以多個身份進行拍賣的話，則廣義二價拍賣機制將不一定會收斂到一個穩(wěn)定的狀態(tài)，甚至不存在一個誠實的而且社會效益最大化的機制。而在目前的現(xiàn)實的廣告位置拍賣中，這種現(xiàn)象卻屢見不鮮。因此，該研究成果告訴我們在設(shè)計拍賣機制的時候，應(yīng)當(dāng)嚴(yán)格禁止一個拍賣者以多個身份進行拍賣。 4) 我們提出了弱支配策略刪除均衡的概念，并且證明在通用二價拍賣中，在只有兩個參與者以及兩個廣告位的情況下，無論其刪除過程怎樣，其最終結(jié)果幾乎滿足社會效益最大化。 5) 我們對網(wǎng)絡(luò)論壇中的帖子的文本內(nèi)容設(shè)計了分析工具，并進行情感分析。該分析能夠?qū)墒羞M行較為準(zhǔn)確的分析和預(yù)測。我們利用數(shù)據(jù)挖掘技術(shù)對網(wǎng)絡(luò)論壇對股市進行分析的研究思路和技術(shù)可以幫助我們來挖掘廣告競拍者的競拍行為。 6) 我們研究了世界上最大的B2C市場—eBay下的買家的策略行為，并給出了對稱貝葉斯-納什均衡。我們比較了在此均衡基礎(chǔ)上的拍賣商的收益和帶有兩份拷貝的二價拍賣模型下的拍賣商的收益。我們證明了在絕大多數(shù)情況下前者的收益要小于后者的收益。 7) 我們研究了基于約束規(guī)劃方法的調(diào)度問題中不確定信息的建模和求解算法，分析了調(diào)度問題中的不確定控制行為，運用定量約束滿足問題模型對實時調(diào)度問題中的不確定控制行為進行基于定量化策略的建模，在約束求解前進行基于約束一致性驗證的可調(diào)度性分析，并將其融合到已有的約束求解框架，以提高調(diào)度算法和系統(tǒng)的可靠性與可信度。此外，我們還分別研究了行車路線為樹和圖的情況下的車輛調(diào)度問題。我們證明了該優(yōu)化問題的難解性，并給出了相應(yīng)的近似算法。 8) 我們研究了二進制串在“與”、“或”、“非”等操作下的判定問題、計數(shù)問題和優(yōu)化問題。評審專家紛紛表示該問題描述簡單，結(jié)論非常有趣。

隨著Internet技術(shù)的迅猛發(fā)展，越來越多的計算逐漸轉(zhuǎn)移到并依賴于Internet這個巨大的計算平臺。為了更好地理解Internet，理論計算機科學(xué)除了運用傳統(tǒng)的邏輯、組合等數(shù)學(xué)工具外，也開始引入微觀經(jīng)濟學(xué)以及博弈論的相關(guān)知識。本項目正是著眼于由理論計算機領(lǐng)域中的算法和博弈論中的機制設(shè)計相結(jié)合所產(chǎn)生的新的研究領(lǐng)域- - 算法機制設(shè)計中的優(yōu)化問題。. 本項目將著手刻畫收益最優(yōu)的算法機制的內(nèi)在組合特性，以及滿足不同均衡解的誠實的算法機制的等價條件；并將研究結(jié)果應(yīng)用到廣告位置拍賣模型中，設(shè)計出公平、合理、實際的收益最優(yōu)的拍賣機制。. 本項目屬于計算機理論科學(xué)和經(jīng)濟學(xué)中博弈論的交叉學(xué)科，是當(dāng)前國際理論計算機科學(xué)界的一個研究熱點。本項目扎根于算法設(shè)計，研究內(nèi)容為算法機制設(shè)計理論，研究背景為網(wǎng)絡(luò)廣告位置拍賣。其研究結(jié)果既可以增進兩個學(xué)科的融合，又可以推動網(wǎng)絡(luò)經(jīng)濟的發(fā)展。

非線性最優(yōu)控制簡介

解決最優(yōu)控制問題最大的難點在于HJB方程的求解，只有當(dāng)系統(tǒng)模型是低階線性模型時，才有可能給出具有顯式表達式的最優(yōu)控制解。在實際系統(tǒng)里，乃至自然界中，幾乎絕大多數(shù)系統(tǒng)都是非線性的系統(tǒng)，想得到具有顯式表達式的控制量幾乎不可能，這就需要借助計算機，以及選擇合適的最優(yōu)的數(shù)值解法，以得到最優(yōu)解。一般的，最優(yōu)控制問題的求解方法為數(shù)值算法。極大值原理和動態(tài)規(guī)劃從理論方面研究了最優(yōu)控制所應(yīng)遵循的方程和條件，而最優(yōu)控制的數(shù)值算法則是從計算方面來確定最優(yōu)控制量的具體方法和步驟。

評價最優(yōu)控制數(shù)值算法優(yōu)劣的三個主要方面是算法的收斂性、計算復(fù)雜性以及數(shù)值穩(wěn)定性。算法的收斂性是保證計算過程能達到正確結(jié)果的前提。算法的計算復(fù)雜性也尤其重要，這對實時控制具有特別重要的意義。一個好的算法應(yīng)使計算量和存儲量盡可能小，以便能由盡可能簡單的計算機來實現(xiàn)計算。好的算法還應(yīng)具有較好的數(shù)值穩(wěn)定性，即計算的結(jié)果對初始數(shù)據(jù)和運算過程的誤差不能過于敏感，同時具有處理病態(tài)問題的能力。典型的最優(yōu)控制數(shù)值算法包括:求解由極大值原理導(dǎo)出的微分或差分方程的兩點邊值問題的各種算法，對動態(tài)規(guī)劃中的貝爾曼方程進行數(shù)值求解_的算法，求解線性二次型最優(yōu)控制問題的黎卡提方程的各種算法，處理控制或狀態(tài)受約束問題的懲罰函數(shù)法，在控制策略的函數(shù)空間中利用搜索尋優(yōu)或梯度尋優(yōu)技術(shù)和牛頓一拉夫森方法等直接求解非線性系統(tǒng)最優(yōu)控制問題的算法等。其中，針對非線性系統(tǒng)的開環(huán)最優(yōu)控制問題和線性二次型最優(yōu)控制問題展開的數(shù)值算法研究尤多。

非線性最優(yōu)控制最優(yōu)問題間接求解法

在間接法中，我們依靠最小值原理和其它一些必要條件得到一個兩點邊值問題，然后通過數(shù)值求解該問題得到相應(yīng)的最優(yōu)軌跡。在幾種基于打靶法求解兩點邊值問題的方法中，多重打靶法是最引人矚目的。而其它的一些間接數(shù)值求解法，比如伴隨方程的向前一向后積分法、函數(shù)空間梯度法等，在過去的幾年中應(yīng)用并不十分廣泛。間接法的主要優(yōu)點是解的精度高，同時方法保證了求解滿足最優(yōu)條件。然而間接法常常會遇到比較嚴(yán)重的解的收斂性問題。如果在求解中，沒有關(guān)于系統(tǒng)初始值的一個好的選取，或是沒有關(guān)于約束和非約束下系統(tǒng)運動軌跡的先驗知識，收斂過程可能需要花費很長的計算時間，甚至可能根本無法找到最優(yōu)解。

非線性最優(yōu)控制最優(yōu)問題直接求解法

在直接法中，連續(xù)性的最優(yōu)控制問題通過參數(shù)化的過程被轉(zhuǎn)化為了一個有限維的優(yōu)化問題。轉(zhuǎn)化后的問題可以通過一些已有的比較成熟的約束優(yōu)化算法進行數(shù)值求解。相對于間接法而言，直接法無需考慮最優(yōu)化條件，而是直接求解問題本身。直接法不易受到收斂問題的影響，但估計的精度不如間接法。最優(yōu)的必要條件不是直接滿足的，而且伴隨量的估計精度有時也會很差?，F(xiàn)在比較常用的幾種直接求解方法包括最優(yōu)參數(shù)控制法，有限差分方法，配點法，微分包含方法和偽譜方法。在最優(yōu)參數(shù)控制法中，控制量被單獨參數(shù)化，同時數(shù)值積分方法被用來求解微分方程;在有限差分方法中，原微分方程和邊界條件被近似為有限差分方程組:在配點法中，狀態(tài)量和控制量同時被參數(shù)化，在各個節(jié)點處，局部分段多項式被用來近似微分方程;微分包含方法只是將狀態(tài)量參數(shù)化，并使用由速端曲線定義的狀態(tài)變化率;在偽譜方法中，通過全局多項式將狀態(tài)量和控制量同時參數(shù)化，積分方程和微分方程通過求積法被近似。配點法和偽譜方法的一個重要的特點就是伴隨量的相合估計。

將委托代理理論和拍賣理論進行有機結(jié)合，構(gòu)建雙重委托代理模型，從理論、模型和實證三個層面，深入考察招投標(biāo)中串謀發(fā)生的內(nèi)在機理及其對招投標(biāo)結(jié)果的影響。在此基礎(chǔ)上，考慮到現(xiàn)有招投標(biāo)機制的缺陷，對招投標(biāo)中的最優(yōu)激勵機制設(shè)計進行探討。主要特色與創(chuàng)新在于：（1）著重于從多項目、多期重復(fù)動態(tài)兩個維度來研究串謀，而且在研究中將串謀人數(shù)和賄賂進行內(nèi)生；（2）將橫向串謀與縱向串謀放在統(tǒng)一分析框架下進行研究，現(xiàn)有研究將兩種串謀孤立開來進行研究，而實際上兩種串謀是緊密聯(lián)系且常常會同時發(fā)生；（3）現(xiàn)有研究只是籠統(tǒng)地認(rèn)為增加透明度可以減少串謀的發(fā)生，但是沒有對合理透明度水平進行系統(tǒng)研究。我們需要對招投標(biāo)不同階段應(yīng)該采取什么樣的合理透明度水平（包括披露什么信息，在哪個階段披露以及對誰披露信息）進行系統(tǒng)深入研究；（4）運用實驗經(jīng)濟學(xué)的方法對理論研究中的關(guān)鍵性結(jié)論進行實證分析，并對最優(yōu)的招投標(biāo)激勵機制進行績效評估。