{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/8155"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/8155","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale","abstract":"This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error $\\delta$ of the optimum. The methods we propose converge in $O(1/\\delta^2)$ or $O(1/\\delta)$ iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is $O(1/\\epsilon^2)$, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting\" versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging\" towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum $\\ell_1$ norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments.","abstract_html":"This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error <span class=\"etd-inline-math\">&delta;</span> of the optimum. The methods we propose converge in <span class=\"etd-inline-math\">O(1/&delta;<sup>2</sup>)</span> or <span class=\"etd-inline-math\">O(1/&delta;)</span> iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is <span class=\"etd-inline-math\">O(1/&epsilon;<sup>2</sup>)</span>, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting&quot; versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging&quot; towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum <span class=\"etd-inline-math\">\\ell<sub>1</sub></span> norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments.","abstract_has_math":true,"creators":["Richtarik, Peter"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007-08-03T13:21:58Z","date_published":"2007-08-03T13:21:58Z","updated_at":"2026-11-19T03:21:11Z","subjects":["large-scale optimization","linear programming","convex minimization","first-order methods","nonsmooth optimization","relative scale","truss topology design","c-optimality","optimal design","Frank-Wolfe algorithm","ellipsoid method","iteratively reweighted least squares","O(1/\\epsilon) convergence"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6476399"],"render_values":[{"text":"6476399","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/8155","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/8155","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F8155","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Richtarik, Peter"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2007-08-03T13:21:58Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-08-03T06:11:35Z"]},{"key":"dc:date.issued","label":"Date","values":["2007-08-03T13:21:58Z"]},{"key":"dc:relation.isformatof","label":"Dc Relation Isformatof","values":["bibid: 6476399"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["large-scale optimization","linear programming","convex minimization","first-order methods","nonsmooth optimization","relative scale","truss topology design","c-optimality","optimal design","Frank-Wolfe algorithm","ellipsoid method","iteratively reweighted least squares","O(1/\\epsilon) convergence"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6476399"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/8155"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"5c928570-bdea-4192-9803-c5eeabf6bb5c\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2007-08-03T13:21:58Z</PublicationDate> <Authors> <Author> <DisplayName>Richtarik, Peter</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>large-scale optimization</Keyword> <Keyword>linear programming</Keyword> <Keyword>convex minimization</Keyword> <Keyword>first-order methods</Keyword> <Keyword>nonsmooth optimization</Keyword> <Keyword>relative scale</Keyword> <Keyword>truss topology design</Keyword> <Keyword>c-optimality</Keyword> <Keyword>optimal design</Keyword> <Keyword>Frank-Wolfe algorithm</Keyword> <Keyword>ellipsoid method</Keyword> <Keyword>iteratively reweighted least squares</Keyword> <Keyword>O(1/\\epsilon) convergence</Keyword> <Abstract>This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error $\\delta$ of the optimum. The methods we propose converge in $O(1/\\delta^2)$ or $O(1/\\delta)$ iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is $O(1/\\epsilon^2)$, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting\" versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging\" towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum $\\ell_1$ norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Richtarik, Peter"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["A dissertation written under the guidance of Michael J. Todd"]},{"key":"dc:description.abstract","label":"Abstract","values":["This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error $\\delta$ of the optimum. The methods we propose converge in $O(1/\\delta^2)$ or $O(1/\\delta)$ iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is $O(1/\\epsilon^2)$, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting\" versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging\" towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum $\\ell_1$ norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["818288 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"5c928570-bdea-4192-9803-c5eeabf6bb5c\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2007-08-03T13:21:58Z</PublicationDate> <Authors> <Author> <DisplayName>Richtarik, Peter</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>large-scale optimization</Keyword> <Keyword>linear programming</Keyword> <Keyword>convex minimization</Keyword> <Keyword>first-order methods</Keyword> <Keyword>nonsmooth optimization</Keyword> <Keyword>relative scale</Keyword> <Keyword>truss topology design</Keyword> <Keyword>c-optimality</Keyword> <Keyword>optimal design</Keyword> <Keyword>Frank-Wolfe algorithm</Keyword> <Keyword>ellipsoid method</Keyword> <Keyword>iteratively reweighted least squares</Keyword> <Keyword>O(1/\\epsilon) convergence</Keyword> <Abstract>This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error $\\delta$ of the optimum. The methods we propose converge in $O(1/\\delta^2)$ or $O(1/\\delta)$ iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is $O(1/\\epsilon^2)$, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting\" versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging\" towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum $\\ell_1$ norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Richtarik, Peter"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Richtarik, Peter"],"dc:date.accessioned":["2007-08-03T13:21:58Z"],"dc:date.available":["2012-08-03T06:11:35Z"],"dc:date.issued":["2007-08-03T13:21:58Z"],"dc:description":["A dissertation written under the guidance of Michael J. Todd"],"dc:description.abstract":["This thesis is concerned with the study of algorithms for approximately solving large-scale linear and nonsmooth convex minimization problems within a prescribed relative error $\\delta$ of the optimum. The methods we propose converge in $O(1/\\delta^2)$ or $O(1/\\delta)$ iterations of a first-order type. While the theoretical lower iteration bound for approximately solving (in the absolute sense) nonsmooth convex minimization problems in the black-box computational model of complexity is $O(1/\\epsilon^2)$, the algorithms developed in this thesis are able to perform better by effectively utilizing the information about the \\emph{structure} of the problems. Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters. In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting\" versions of these methods at no or only negligible cost in their theoretical guarantees. In Chapter 3 we consider the geometric problem of finding the intersection of a line and a centrally symmetric convex body $Q$ given as the convex hull of a collection of points. Our algorithms produce a sequence of ellipsoids inscribed in $Q$, ``converging\" towards the intersection points. It turns out that in doing so we simultaneously solve a number of closely related problems such as the problem of finding the minimum $\\ell_1$ norm solution of a full rank underdetermined linear system, minimizing the maximum of absolute values of linear functions, or linear optimization over the polytope polar to $Q$. We finish the discussion by describing applications to truss topology design and optimal design of statistical experiments."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["818288 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6476399"],"dc:identifier.uri":["https://hdl.handle.net/1813/8155"],"dc:language.iso":["en_US"],"dc:relation.isformatof":["bibid: 6476399"],"dc:subject":["large-scale optimization","linear programming","convex minimization","first-order methods","nonsmooth optimization","relative scale","truss topology design","c-optimality","optimal design","Frank-Wolfe algorithm","ellipsoid method","iteratively reweighted least squares","O(1/\\epsilon) convergence"],"dc:title":["Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:21:11Z"}