Affine scaling

The affine scaling method is an interior point method, meaning that it forms a trajectory of points strictly inside the feasible region of a linear program (as opposed to the simplex algorithm, which walks the corners of the feasible region).

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 in the 1967 Doklady Akademii Nauk SSSR, followed by a proof of its convergence in 1974.^[1] 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,^[2] a team led by R. J. Vanderbei at AT&T,^[3] 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.^[1]^[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]^:346

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

c \cdot x

subject to

Ax = b

x \geq 0

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.^[5]^:337

Formally, the iterative method at the heart of affine scaling takes as inputs $A$ , $b$ , $c$ , an initial guess $x 0 > 0$ that is strictly feasible (i.e., $Ax 0 = b$ ), a tolerance $ε$ and a stepsize $β$ . It then proceeds by iterating^[1]^:111

Let $D k$ be the diagonal matrix with $x k$ on its diagonal.
Compute a vector of dual variables:
$w^k = (A D_k^2 A^\operatorname{T})^{-1} A D_k^2 c.$
Compute a vector of reduced costs, which measure the slackness of inequality constraints in the dual:
$r^k = c - A^\operatorname{T} w^k.$
If $r^k > 0$ and $\mathbf{1}^\operatorname{T} D_k r^k < \varepsilon$ , the current solution $x k$ is $ε$ -optimal.
If $-D_k r^k \ge 0$ , the problem is unbounded.
Update $x^{k+1} = x^k - \beta \frac{D_k^2 r^k}{\|D_k r^k\|}$

Initialization

Phase I, the initialization, solves an auxiliary problem with an additional variable $u$ and uses the result to derive an initial point for the original problem. Let $x 0$ be an arbitrary, strictly positive point; it need not be feasible for the original problem. The infeasibility of $x 0$ is measured by the vector

v = b - Ax^0

If $v = 0$ , $x 0$ is feasible. If it is not, phase I solves the auxiliary problem

minimize

- u

subject to

Ax + uv = b

x \geq 0

u \geq 0

This problem has the right form for solution by the above iterative algorithm,^{[lower-alpha 1]} and

\begin{pmatrix} x^0 \\ 1 \end{pmatrix}

is a feasible initial point for it. Solving the auxiliary problem gives

\begin{pmatrix} x^* \\ u^* \end{pmatrix}

If $u * = 0$ , then $x * = 0$ is feasible in the original problem (though not necessarily strictly interior), while if $u * > 0$ , the original problem is infeasible.^[5]^:343

Analysis

While easy to state, affine scaling was found hard to analyze. Its convergence depends on the step size, $β$ . For step sizes $β \leq 2 / 3$ , Vanderbei's variant of affine scaling has been proven to converge, while for $β > 0.995$ , an example problem is known that converges to a suboptimal value.^[5]^:342 Other variants of the algorithm have been shown to exhibit chaotic behavior even on small problems when $β > 2 / 3$ .^[6]^[7]

Notes

↑ The structure in the auxiliary problem permits some simplification of the formulas.^[5]^:344

References

1 2 3 Vanderbei, R. J.; Lagarias, J. C. (1990). "I. I. Dikin's Convergence Result for the Affine-Scaling Algorithm" (PDF). Contemporary Mathematics 114.
↑ Barnes, Earl R. (1986). "A variation on Karmarkar's algorithm for solving linear programming problems". Mathematical programming 36 (2): 174–182. doi:10.1007/BF02592024.
↑ Vanderbei, Robert J.; Meketon, Marc S.; Freedman, Barry A. (1986). "A Modification of Karmarkar's Linear Programming Algorithm" (PDF). Algorithmica 1: 395–407. doi:10.1007/BF01840454.
↑ Bayer, D. A.; Lagarias, J. C. (1989). "The nonlinear geometry of linear programming I: Affine and projective scaling trajectories" (PDF). Trans. AMS 314 (2).
1 2 3 4 5 Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Springer Verlag. pp. 333–347.
↑ Bruin, H.; Fokkink, R.J.; Gu, G.; Roos, C. (2014). "On the chaotic behavior of the primal–dual affine–scaling algorithm for linear optimization" (PDF). Chaos. doi:10.1063/1.4902900.
↑ Castillo, Ileana; Barnes, Earl R. (2006). "Chaotic Behavior of the Affine Scaling Algorithm for Linear Programming". SIAM J. Optim. 11 (3): 781–795. doi:10.1137/S1052623496314070.

External links

"15.093 Optimization Methods, Lecture 21: The Affine Scaling Algorithm" (PDF). MIT OpenCourseWare. 2009.
Mitchell, John (November 2010). "Interior Point Methods". Rensselaer Polytechnic Institute.
"Lecture 6: Interior point method" (PDF). NCTU OpenCourseWare.

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling …

… functions

… and gradients

Convergence	Trust region Wolfe conditions

Quasi–Newton	BFGS and L-BFGS DFP Symmetric rank-one (SR1)

Other methods	Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient Truncated Newton

… and Hessians

Newton's method

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

Constrained nonlinear

General	Barrier methods Penalty methods

Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar

Basis-Exchange	Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Graph
algorithms

Minimum spanning tree	Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal

Network flows

Metaheuristics

Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search

Categories
- Algorithms and methods
- Heuristics
Software

This article is issued from Wikipedia - version of the Saturday, February 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.