Scaling and Interior Point Methods in Optimization

150 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.We present four algorithms that use either scaling or interior point methods for convex optimization problems; two of the algorithms use both.We first present an algorithm that uses scaling of weights to find the weighted analytic center of a polytope defined by m hyperplanes. We prove that after we solve the problem at the base level--all weights set equal to 1--we can determine the solution with original weights in $O(\sqrt{m}\log W)$ iterations, where W is the largest original weight. Our second algorithm is a companion to the first: it determines the weighted analytic center of convex bodies defined by m convex constraints. We prove that convex constraints that lead to a self-concordant logarithmic barrier function define a convex set for which Newton's method is an efficient technique for finding the weighted analytic center. When we scale the weights, we can also solve this more general case in $O(\sqrt{m}\log W)$ iterations after the base problem is solved. For both algorithms, the complexity of each iteration is dominated by the time to find the Newton direction for minimization of a function.The convex feasibility problem is a general optimization problem in which the goal is to find any point that lies in a convex set S. We present a new cutting plane algorithm for the convex feasibility problem. Our algorithm uses the analytic center of a polytope known to contain S as the test point for feasibility. We give the first analysis of the time complexity of a cutting plane algorithm using analytic centers. Our algorithm requires $O((T+n\sp2 L+n\sp3)nL\sp2)$ arithmetic operations, where n is the dimension of the space, L is a parameter describing the size of S, and T is the time required to check the feasibility of a test point.Finally, we present an algorithm for the transportation problem in the plane. Our algorithm synthesizes several ideas--the two most important are scaling and common data structures from computational geometry--to achieve time complexity $O(n\sp{2.5}\log n \log N),$ where n is the number of nodes and N is the largest supply or demand. No currently known general transportation algorithm has better than $O(n\sp3)$ time complexity; the plane setting allows improvement.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD