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 :subject to , . 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. Formally, the iterative method at the heart of affine scaling takes as inputs , , , an initial guess that is strictly feasible (i.e., ), a tolerance and a stepsize . It then proceeds by iterating • Let be the
diagonal matrix with 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 , the current solution 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 and uses the result to derive an initial point for the original problem. Let be an arbitrary, strictly positive point; it need not be feasible for the original problem. The infeasibility of is measured by the vector :v = b - Ax^0. If , is feasible. If it is not, phase I solves the auxiliary problem :minimize :subject to , , . This problem has the right form for solution by the above iterative algorithm, 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 , then is feasible in the original problem (though not necessarily strictly interior), while if , the original problem is infeasible. ==Analysis==