Large scale optimization

背景：在之前遇見的線性規劃問題中，給出的限制條件和變量雖然比較ugly, 但都是在可以接受的，起碼我們一眼能看完，但是實際運用中，給的變量和限制條件的數量往往是巨大的。如果碰到的問題裡變量和限制條件數量都很大的話，兩手一攤隻能放棄，如果隻是變量或者是限制條件一方很大的話，我們可以想辦法解決。

6.1Delayed cloumn generation

考慮到标準形問題

min c’x

s.t. Ax = B ,x ≥ 0

其中變量x ∈ Rn ,限額系數b ∈ Rm ，mxn矩陣A通常是行線性無關。假設列的數量十分巨大，矩陣A無法生成且儲存。從過往解決大問題的經驗中推斷，有些沒用到的列并不需要生成。這和修正後的單純型法（Revised Simplex Method）類似，在每次疊代中，隻需要目前的列向量和将要進基的列向量。在這裡有一個難點需要提出來，我們需要一個方法找到負檢驗數 ci¯¯¯ 相對應的變量 xi ，而不需要找到所有的列。有時候，這可以被這個問題轉化為一下問題

minimize ci¯¯¯ （6.1）

在這裡，對所有的i 的最小化問題都成立。在很多例子中，這個優化問題有一種特殊的結構：不用生成所有的 ci¯¯¯ 即可高效地找到最小的 ci¯¯¯ （怎麼找到的）。

這個優化問題中如果最小值非負，那麼所有的檢驗數都是非負的，對于原線性規劃問題，我們有了最優解； 如果最小值是負數，最小值索引i 對應的變量 xi 檢驗數小于零，列 Ai 進基。

以上簡要介紹的方法核心是，如何有效率地解決（6.1）這個優化問題。在Dantzig-Wolfe分解法（Dantzig-Wolfe decomposition method）裡，這個問題化成一個更小的可以用單純型法解決的輔助（auxiliary）線性規劃問題。在下料問題（Cutting Stock Problem）裡，這個是一個确定的離散優化問題，可以用一些特殊的方法非常有效地解決。當然，在一些情況下沒有很好的特殊結構和方法去解決（6.1）

A variant involving retained columns

在剛才讨論的延遲列生成法（delayed column generaton），所有出基的列都被從儲存中删除，沒有任何特殊地位。在這個方法的一個變種中，算法儲存了所有或者部分在之前生成的列，在有限制條件的額限制線性規劃問題中，隻對儲存的列操作。

我們把我這個算法描述成一系列主疊代（master iterations）。在這些主疊代的開始，我們對原問題有一組基可行解和相對應的基矩陣。我們找一個檢驗數為負的變量，可能是通過對所有的索引i 尋找最小的 ci¯¯¯ 得出。如果找不到這樣的 ci ，那麼算法中止。假設找到索引j 使得 cj¯¯¯ < 0. 那麼我們建立一個列的集合 Ai , i ∈ I, 其中包含所有的基列和将要進基的列 Aj , 可能也有其他的列。我們定義如下限制問題

∑i∈I cixi

s.t. Aixi = b ,x ≥ 0

回憶一下，目前原問題的可行基對應的變量在限制條件中。從未我們有了對限制問題的一個基可行解（大問題的解一定适用于小問題的解）,可以用于這個解過程的起始點。然後進行單純型疊代，直到限制問題達到了最優化。這時候就可以進行下一次主疊代。

我們剛才讨論的方法是修正單純型法的一個特殊情形，都存在特殊的規則：優先選擇在之前獲得的索引集合I 所對應的元素進基，即進基變量 xi ,i ∈ I，隻當這些變量的檢驗數都為非負的時候（僅發生在限制問題的最優解）算法開始檢驗剩餘變量的檢驗數。我們希望優先對已經生成并存儲的列所對應的變量，或者對檢驗數更可能為負的變量

進行操作。這個方法還有其他幾個變種，根據每次疊代中集合I 是如何選擇的。

1. 在一個極端，I 僅僅是目前基變量和進基變量的索引，離基變量的索引立刻從集合I 中剔除。因為限制問題有m+1個變量和m個限制，其可行解是一維的，能夠在一次單純型法疊代中得出，即列 Ai 進基之後即得出
2. 在另外一個極端，我們讓I 為某個時間點之前所有進過基的變量的集合。也就是說，沒有變量被剔除，每次進基的變量的索引都被加入I 。如果主疊代的次數非常多，這個方法實施起來可能有困難，因為集合I 持續在增長
3. 最後，有一個折中的方法，集合I 隻保持在一個适當的大小，僅把很久之前進基并沒再入基的變量剔除

【1.】m*m+1矩陣中m*m為基矩陣，隻有一個非基變量可以進基，除了出基的變量對應的維數，其餘m-1維是不變的。【2】顯然不推薦，因為這章我們考慮的就是體量很大的問題，一般來說我們要考慮到最壞的情況【3】先進先出

不考慮退化的情況下，以上所有的變體都能夠中止，因為他們都是修正單純型法的變體。如果存在退化問題，利用修正單純型法和布蘭特法則可以避免循環問題。

6.2 The cutting stock problem

在本小節，我們将讨論延遲列生成法（Delayed Column generation）的經典例子—下料問題(The cutting stock problem)

考慮一個有很多寬度為正整數W 卷紙供應的紙業公司。然而，消費者隻對寬度更小的紙有需求，具體需求為 bi 卷寬度為 ωi ，i =1,2,…,m,都需要生産出來。我們假設 ∀i,ωi≥ W, ωi 為整數。小卷紙是通過特定的方法切割大卷紙，這稱為模式(pattern)。例如，寬度為70的大卷紙可以被去成三卷寬度為 ω1 =17和一卷寬度 ω2 =15的紙，并産生4的廢料。

未完待續，突然發現期中考試不考這裡，我還是先複習對偶和單純型法吧