{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72531"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72531","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scaling and Interior Point Methods in Optimization","abstract":"We present four algorithms that use either scaling or interior point methods for convex optimization problems; two of the algorithms use both.","abstract_html":"We present four algorithms that use either scaling or interior point methods for convex optimization problems; two of the algorithms use both.","abstract_has_math":false,"creators":["Atkinson, David Steen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Loui, Michael C.","Vaidya, Pravin M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T23:17:44Z","date_published":"2014-12-17T23:17:44Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Mathematics","Operations Research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305458"],"render_values":[{"text":"(UMI)AAI9305458","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72531","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Loui, Michael C.","Vaidya, Pravin M."]},{"key":"dc:creator","label":"Author","values":["Atkinson, David Steen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T23:17:44Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Operations Research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72531","(UMI)AAI9305458"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Scaling and Interior Point Methods in Optimization"]}]}],"canonical_facts":{"dc:contributor":["Loui, Michael C.","Vaidya, Pravin M."],"dc:creator":["Atkinson, David Steen"],"dc:date":["2014-12-17T23:17:44Z","10000-01-01","1992"],"dc:description":["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."],"dc:identifier":["http://hdl.handle.net/2142/72531","(UMI)AAI9305458"],"dc:subject":["Mathematics","Operations Research"],"dc:title":["Scaling and Interior Point Methods in Optimization"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}