仿射尺度算法

仿射尺度算法，是一種求解線性規劃的內點算法，其計算複雜性為多項式。所謂“內點算法”是指一類算法，他們的一個共同特點是不像單純形那樣從可行域的頂點開始疊代，而是選取可行域內部的一個適當的點，沿某個下降方向開始疊代到達最優解。仿射尺度算法使用簡單的放射變換替代了Karmarkar原來的投影變換，從而使人們可以直接解一般形式的線性規劃問題，Karmarkar算法對單純性結構的特殊要求被放鬆了。仿射尺度法的基本思想是：每步疊代先做仿射尺度變換，然後使用最速下降步驟。