Английская Википедия:Affine scaling
In mathematical optimization, affine scaling is an algorithm for solving linear programming problems. Specifically, it is an interior point method, discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.
History
Affine scaling has a history of multiple discovery. It was first published by I. I. Dikin at Energy Systems Institute of Russian Academy of Sciences (Siberian Energy Institute, USSR Academy of Sc. at that time) in the 1967 Doklady Akademii Nauk SSSR, followed by a proof of its convergence in 1974.Шаблон:R Dikin's work went largely unnoticed until the 1984 discovery of Karmarkar's algorithm, the first practical polynomial time algorithm for linear programming. The importance and complexity of Karmarkar's method prompted mathematicians to search for a simpler version.
Several groups then independently came up with a variant of Karmarkar's algorithm. E. R. Barnes at IBM,[1] a team led by R. J. Vanderbei at AT&T,[2] and several others replaced the projective transformations that Karmarkar used by affine ones. After a few years, it was realized that the "new" affine scaling algorithms were in fact reinventions of the decades-old results of Dikin.[3][4] Of the re-discoverers, only Barnes and Vanderbei et al. managed to produce an analysis of affine scaling's convergence properties. Karmarkar, who had also came with affine scaling in this timeframe, mistakenly believed that it converged as quickly as his own algorithm.[5]Шаблон:Rp
Algorithm
Affine scaling works in two phases, the first of which finds a feasible point from which to start optimizing, while the second does the actual optimization while staying strictly inside the feasible region.
Both phases solve linear programs in equality form, viz.
- minimize Шаблон:Math
- subject to Шаблон:Math, Шаблон:Math.
These problems are solved using an iterative method, which conceptually proceeds by plotting a trajectory of points strictly inside the feasible region of a problem, computing projected gradient descent steps in a re-scaled version of the problem, then scaling the step back to the original problem. The scaling ensures that the algorithm can continue to do large steps even when the point under consideration is close to the feasible region's boundary.Шаблон:RШаблон:Rp
Formally, the iterative method at the heart of affine scaling takes as inputs Шаблон:Mvar, Шаблон:Mvar, Шаблон:Mvar, an initial guess Шаблон:Math that is strictly feasible (i.e., Шаблон:Math), a tolerance Шаблон:Mvar and a stepsize Шаблон:Mvar. It then proceeds by iteratingШаблон:RШаблон:Rp
- Let Шаблон:Mvar be the diagonal matrix with Шаблон:Mvar on its diagonal.
- Compute a vector of dual variables:
- <math>w^k = (A D_k^2 A^\operatorname{T})^{-1} A D_k^2 c.</math>
- Compute a vector of reduced costs, which measure the slackness of inequality constraints in the dual:
- <math>r^k = c - A^\operatorname{T} w^k.</math>
- If <math>r^k > 0</math> and <math>\mathbf{1}^\operatorname{T} D_k r^k < \varepsilon</math>, the current solution Шаблон:Math is Шаблон:Mvar-optimal.
- If <math>-D_k r^k \ge 0</math>, the problem is unbounded.
- Update <math>x^{k+1} = x^k - \beta \frac{D_k^2 r^k}{\|D_k r^k\|}</math>
Initialization
Phase I, the initialization, solves an auxiliary problem with an additional variable Шаблон:Mvar and uses the result to derive an initial point for the original problem. Let Шаблон:Math be an arbitrary, strictly positive point; it need not be feasible for the original problem. The infeasibility of Шаблон:Math is measured by the vector
- <math>v = b - Ax^0</math>.
If Шаблон:Math, Шаблон:Math is feasible. If it is not, phase I solves the auxiliary problem
- minimize Шаблон:Math
- subject to Шаблон:Math, Шаблон:Math, Шаблон:Math.
This problem has the right form for solution by the above iterative algorithm,Шаблон:Efn and
- <math>\begin{pmatrix} x^0 \\ 1 \end{pmatrix}</math>
is a feasible initial point for it. Solving the auxiliary problem gives
- <math>\begin{pmatrix} x^* \\ u^* \end{pmatrix}</math>.
If Шаблон:Math, then Шаблон:Math is feasible in the original problem (though not necessarily strictly interior), while if Шаблон:Math, the original problem is infeasible.Шаблон:RШаблон:Rp
Analysis
While easy to state, affine scaling was found hard to analyze. Its convergence depends on the step size, Шаблон:Mvar. For step sizes Шаблон:Math, Vanderbei's variant of affine scaling has been proven to converge, while for Шаблон:Math, an example problem is known that converges to a suboptimal value.Шаблон:RШаблон:Rp Other variants of the algorithm have been shown to exhibit chaotic behavior even on small problems when Шаблон:Math.[6][7]
Notes
References
Further reading
External links
Шаблон:Optimization algorithms
