線性規劃（273）：
我們將通過考慮線性規劃問題繼續隨機抽樣的研究。線性規劃問題是體現兩個主要隨機化優點（簡單和速度）最顯著的例子。在9.10.1節我們將針對這一問題研究隨機遞增演算法。
線性規劃問題就是尋找線性目標函式的極值問題，線性目標函式受到一些真實變數的約束。下面，我們將用d來表示變數的數量，用n來表示約束條件的數量。每個約束條件都可以將d維空間劃分成兩部分，這樣的多個兩部分組成乙個交叉區域，我們所尋找的極值就會被限制在這個區域的一些點上。
這個交叉區域是d維空間中的乙個多面體，我們把這個區域稱為可行域。在這個過程中，我們要測量我們所執行的算術操作的數量，把在連續的時間內算術運算被執行的運算元作為真實的資料，這個和我們本節的觀點是一致的，但有一點要提醒的是線性規劃問題的很多任務作都與運算元的有限精度有關。對於這種有限精度的運算元，在通過各種演算法進行在操作時都需要認真考慮它們。
我們對於少量的操作不會太關心，但是會把所有的數量作為原子運算元來考慮。
讓, 表示線性問題中的d個變數，讓, 表示這些變數的係數，讓, , ,表示第i個約束中的係數。讓a表示矩陣），c表示矩陣中的向量（, ），x表示矩陣中的向量（, ），線性規劃問題可以如下表示：
條件axb9.12)
b是常數列向量。
我們用a和b來表示可行域，表示為向量c在d空間中指定了乙個方向。從幾何上說，我們在可行域中沿著指向c的方向尋找最遠的點，前提是存在乙個這樣的有限點。線性規劃問題有很長的歷史，在注釋部分有介紹。
在我們處理的點中，伴隨著起始點會有一系列的假設，這將有助於捕捉到線性規劃問題；這些假設不會從設計演算法的立場上不具有專業性和簡潔性。所有這些假設都可以通過標準技術來去除；這一點會在問題9.8中會有進一步的研究。
1. 多面體是非空並且是有界的。既然我們不假定我們能測試任意乙個多面體為非空或有界的；這就相當於去解決乙個線性規劃。我們僅僅對做出這種假定。
2. 我們把目標函式的最小值定義為；換句話說，假設c=(1,0,…,0)，以此我們用最小值在中尋找乙個點。
3. 我們尋找的最小值是在上的唯一的頂點。
4. 的每乙個頂點都恰好符合d個約束條件。
讓h表示a和b定義的約束集，s為h的約束子集。我們經常考慮由子集s和c定義的線性規劃定義的線性規劃。當這樣乙個線性規劃達到最小時，我們將會假定假設3-4仍然成立：
（i）最小值是唯一的；（ii）可行域中的每乙個點都是d個約束條件限定的。我們用o（s）表示由c和s定義的線性規劃問題中目標函式的值。子集b是基礎，因此對於任何b』 b ，o（b），並且o（b』） o（b） 。
的基礎是乙個最小的子集b屬於h，並且o（b）=o（h）。我們的目標是找到，由於定義了線性規劃的最優點，我們有時會稱或者o（）為線性規劃的最優解。
解決線性規劃問題的乙個方法是採用半空間相交演算法來計算，然後對多面體的每乙個頂點估算它的目標函式值。由於頂點的數量有可能是ω，這種詳細的估算過程一般來說會很慢。因此我們要尋找一種演算法，不需要列舉中的每個頂點。
在對線性規劃進行隨機演算法研究之前，我們將會回想一下經典單純行法的原理。這是乙個確定的演算法，從的乙個頂點開始，隨後每一次迭代，在目標函式有乙個低值時演算法會進行到鄰近的乙個點。如果不存在這樣的點，那我們就找到了最小值。
不過，這只是單純行法的主要思想，當相鄰點有同樣的目標函式值，而且問題中沒有最小值時，這種演算法的複雜性也會增加。對於單純形法我們將會避免詳細的討論；，當然這個最優解應該是存在的。
我們稱約束h如果o（h\）o(h); 中的約束。直覺上說不是極端的約束h是冗餘的約束，這種約束的缺失不會改變最優化。我們的第乙個演算法samplp用隨機抽樣來迅速的去掉冗餘約束。
從空集開始，samplp通過一系列階段建立了約束集合s。在每乙個階段，集合v屬於h但不屬於s時，v被加入到s中。集合v有兩個重要的效能：
（i）它將會很小，（ii）在（不包括s）中至少包含乙個極端約束。因此當| |=d,我們會在d階段後停止。
samplp演算法：
輸入：約束集h。
輸出：最優解。
1. s;
2. 如果 n9
返回單純形（h）
否則2.1. vs；
2.2. 當|v|0
隨機選擇r，並且|r|=r=min;
xsamplp(r);
v;如果|v|2
那麼 ss；
2.3. 返回x；
因此對於n9samplp選擇r約束裡的乙個隨機子集。r的值通常是d，除非比d包含更少的約束。它遞迴地解決被r定義的線性規劃，並且決定了vh妨礙了最優解；因此這些違反約束事實上**於h\s。
如果v僅僅有2個原理，我們把v新增到s裡。當v變成空時，我們返回x。
練習9.24：構建乙個簡單的例子表明，在通過samplp的迴圈語句後，v可能不包含所有的。因此，我們可能僅僅指出v至少包含中的乙個約束，而這個約束不在s裡。
常規的單純形僅僅在9或更少的約束時呼叫。對於這種小的線性規劃問題，我們可以像下面一樣繫結呼叫單純形的成本。對於這樣乙個成本，多面體的頂點總數不會超過（）,最多為。
我們有乙個常數a,像這樣單純形法花在每個頂點上的很多時間是,因此，我們有：
引理9.14：在9或更少的約束時呼叫單純形的總成本是o。
下一步，我們希望討論v，不遵循x的約束集是小的。
引理9.15：讓sh，rh\s是大小為r 的乙個隨機子集。讓m表示|h\s|。不屬於o(r)的h的約束集的期望數不超過d(m-r+1)/(r-d)。
證明：對於由約束子集形成的線性規劃，我們定義兩個最優集。讓表示最優集，因此samplp的訪問返回本集的乙個元素。
相同地，對於特定的子集r，我們定義最優集為。現在在中o(r)是唯一能滿足r中每個約束的元素。對於每乙個元素x,讓表示約束集侵犯x的數量。
當x是o(r)時讓指數為1，否則為0。
我們可以寫為
e=e9.13）
現在， x為最優解o(r)的概率為。這一事件一旦發生，約束條件d一定在r中，r中剩餘的r-d條約束一定是h\s中的m--d條約束。m--d條約束既沒有被x定義也沒有被x侵犯。因此
9.14）
練習9.25：將（9.13）和（9.14）結合，並簡潔化，得到如下所示
e9.15）
我們將會通過計算公式（9.15）右邊的求和結果不超過d來完成證明。中的元素x恰巧侵犯r中的乙個約束可能性為。
通過給它加權，對中恰巧違反r中乙個約束的元素的期望數進行求和。然而這種元素的數量最多為d，因為每乙個這樣的元素是r \集中的最優解，r \是指在h約束下的最優解o(r)。這有d條約束定義了最優集o(r)。
隨著這種違反約束的期望數目的繫結，馬爾科夫不等式在samplp中揭示了任何隨機抽樣，pr[|v|>2] 1/2。它遵循在2.2步驟中擴增到s的迭代的期望數目最多為2。
讓t(n)表示samplp中最大期望執行時間。s最初為空集，在d階段中的每一階段，最多增加2個約束。因此，| r |從來不超過3d。
因為在每一階段，我們最多執行n個違反約束的測試，每次測試的成本為o（d）；因此在約束檢測中的總的工作為o（）。當在乙個遞迴訪問中，約束的數目下降到9或者更少，我們把時間繫結到單純形（9.14）的訪問中。
將這些觀察結果結合在一起，我們有
t(n) 2dt(3d)+o(), n>99.16)
練習9.26：在(9.16)中獲得繫結t(n)的最大的可能性，與引理9.14互相協調。
我們現在開始描述itersamplp演算法。而不是一點點發現，在抽樣中使用權值迭代技術來增加包括有用約束的可能性。我們選擇約束r的乙個隨機子集，並且確定約束子集vh，這一子集違反了由r定義的線性規劃的最優集。
在samplp中我們把v新增到集合s中，在這裡，約束集v被選入未來迴圈的可能性的首次增加後，我們把v返回到h中。直覺上來說，在集合v中的約束會不斷的發現其本身，因此他們被包含在r中的可能性會迅速的增加。像這樣有限的幾次迭代後，中所有的約束都有可能在r中，然後終止執行。
下面是itersamplp的詳細描述，我們將會給每乙個約束h賦予乙個正的整數值,hh；約束h將會根據的現值按一定比例放入r中。
在2.2步驟，約束h被選擇的可能性按一定比例賦給。我們轉向itersamplp的分析。
如果 (2)/(9d-1)
成立，訪問迴圈語句的乙個執行
（因此，對於每乙個，將加倍）
itersamplp演算法：
輸入：約束集h。
輸出：最優集。
1. 1；
2. 如果n<9
返回單純形（h）
否則2.1. h；
2.2. |v|>0
隨機選擇rh，|r|=r=9;
x單純形（r）;
v；如果(2)/(9d-1)
那麼 ；
2.3. 返回 x
引理9.16 ：成功迭代中迴圈迭代的期望值最多為2。
我們不能直接呼叫引理9.15的結論來分析itersamplp，因為隨機約束子集r不會等概率的被選擇。引理9.
16是引理9.15分析的乙個擴充套件；讀者可以根據問題9.9中的提示來完成證明。
定理9.17： 存在連續的，itersamplp期望的執行時間最多為
證明：我們將會證明迴圈語句執行的期望值為o（）。思路是增長的要快，因此在次迭代後，v=除非》,否則就會相矛盾。
在每次迴圈成功，至少有乙個約束h的權值加倍。成功執行迴圈kd之後，我們有=, 為h進入v的次數。很顯然kd。這些事實一起表明：
9.17)
另一方面，在每次成功執行迴圈語句後增加的網路不會超過。初始化=n。成功執行kd次迭代後它不會超過
n9.18)
將(9.17)和(9.18)相比較，在經過o（）次迭代後，我們跳出迴圈。
在迴圈語句的成功迭代時，我們要花費多長時間？通過引理9.16，成功迭代數中期望迭代數目為2。
在每次迭代期間，產生了單純形訪問的成本，在時間o（nd）中確定v。把這些因素一起放在定理中。
9.10.1 遞增的線性規劃
到目前為止，我們學習的線性規劃都是基於隨機抽樣的。現在我們為線性規劃開發隨機遞增的演算法。下面的演算法會立刻證明它本身：
隨機的新增n條約束，一次增加乙個。目前為止，每增加一條約束，就會增加約束的最優集。這種演算法可能被認為是在後退，但在續集中它會被證明是有用的。
非線性規劃理論和演算法
非線性最優化理論與演算法 第一章引論 本章首先給出了一些常見的最優化問題和非線性最優化問題解的定義，並且根據不同的條件對其進行了劃分。接著給出了求解非線性優化問題的方法，如 法等，同時又指出乙個好的數值方法應對一些指標有好的特性，如收斂速度與二次終止性 穩定性等。隨後給出了在非線性最優化問題的理論分...
線性規劃及演算法的應用案例
例2 某校高二 1 班舉行元旦文藝晚會，布置會場要製作 中國結 班長購買了甲 乙兩種顏色不同的彩繩，把它們截成a b c三種規格 甲種彩繩每根8元，乙種彩繩每根6元，已知每根彩繩可同時截得三種規格彩繩的根數如下表所示 今需要a b c三種規格的彩繩各15 18 27根，問各截這兩種彩繩多少根，可得所...
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...