Files in this item
Files  Description  Format 

application/pdf 9305458.pdf (6MB)  (no description provided) 
Description
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 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
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 levelall weights set equal to 1we 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 selfconcordant 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 ideasthe two most important are scaling and common data structures from computational geometryto 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 
Type:  Text 
Description:  150 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1992. 
URI:  http://hdl.handle.net/2142/72531 
Other Identifier(s):  (UMI)AAI9305458 
Date Available in IDEALS:  20141217 
Date Deposited:  1992 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois