Bracketing to speed convergence illustrated on the von Newmann algorithm for finding a feasible solution to a linear program with a convexity constraint. Technical report

摘要

Analogous to gunners firing trial shots to bracket a target in order to adjust direction and distance, we demonstate that it is sometimes faster not to apply an algorithm directly, but to roughly approximately solve several perturbations of the problem and then combine these rough approximations to get an exact solution. To find a feasible solution to an m-equation linear program with a convexity constraint, the von Neumann Algorithm generates a sequence of approximate solutions which converge very slowly to the right hand side b(sup 0). However, it can be redirected so that in the first few iterations it is guaranteed to move rapidly towards the neighborhood of one of m + 1 perturbed right hand sides (cflx b)(sup i), then redirected in turn to the next (cflx b)(sup i). Once within the neighborhood of each (cflx b)(sup i), a weighted sum of the approximate solutions. (bar x)(sup i) yields the exact solution of the unperturbed problem where the weights are found by solving a system of m + 1 equations in m + 1 unknowns. It is assumed an r > 0 is given for which the problem is feasible for all right hand sides b whose distance (parallel)b - b(sup 0)(parallel)(sub 2) (le) r. The feasible solution is found in less than 4(m+ 1)(sup 3)/r(sup 2) iterations. The work per iteration is (delta)mn + 2m + n + 9 multiplications plus (delta)mn + m + n + 9 additions or comparisons where (delta) is the density of nonzero coeffients in the matrix.