Files in this item



application/pdf9305458.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Scaling and Interior Point Methods in Optimization
Author(s):Atkinson, David Steen
Doctoral Committee Chair(s):Loui, Michael C.; Vaidya, Pravin M.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Operations Research
Abstract: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.
Issue Date:1992
Description:150 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
Other Identifier(s):(UMI)AAI9305458
Date Available in IDEALS:2014-12-17
Date Deposited:1992

This item appears in the following Collection(s)

Item Statistics