2026-09-21T07:47:53Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/72531 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Loui, Michael C. Vaidya, Pravin M. Atkinson, David Steen 2014-12-17T23:17:44Z 2014-12-17T23:17:44Z 10000-01-01 1992 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. Made available in DSpace on 2014-12-17T23:17:44Z (GMT). No. of bitstreams: 1 9305458.pdf: 6145527 bytes, checksum: 17bf6595dbae9738ddbc7b2f1315892c (MD5) Previous issue date: 1992 Embargo set by: Seth Robbins for item 72699 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 150 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992. http://hdl.handle.net/2142/72531 (UMI)AAI9305458 Mathematics Operations Research Scaling and Interior Point Methods in Optimization text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.