<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T10:33:00Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/8155" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/8155</identifier><datestamp>2026-05-13T16:37:09Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Richtarik, Peter</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2007-08-03T13:21:58Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-08-03T06:11:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2007-08-03T13:21:58Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/8155</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6476399</dim:field>
   <dim:field mdschema="dc" element="description" lang="en_US">A dissertation written under the guidance of Michael J. Todd</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">This thesis is concerned with  the study of algorithms for approximately&#xd;
solving large-scale linear and nonsmooth convex minimization problems&#xd;
within a prescribed relative error $\delta$ of the optimum. The methods we&#xd;
propose converge in $O(1/\delta^2)$ or $O(1/\delta)$ iterations of a&#xd;
first-order type. While the theoretical lower iteration bound for&#xd;
approximately solving (in the absolute sense) nonsmooth convex&#xd;
minimization problems in the black-box computational model of complexity&#xd;
is $O(1/\epsilon^2)$, the algorithms developed in this thesis are able to&#xd;
perform better by effectively utilizing the information about the&#xd;
\emph{structure} of the problems.&#xd;
&#xd;
Chapter 1 contains a brief account of the relevant part of&#xd;
complexity theory for convex optimization problems. This is done in order&#xd;
to be able to better communicate the proper setting of our work within the&#xd;
current literature. We finish with concise synopses of the following&#xd;
chapters.&#xd;
&#xd;
In Chapter 2 we study the general problem of unconstrained&#xd;
convex minimization in  relative scale. Algorithms of this type are hard&#xd;
to find in the literature and are known perhaps only for a narrow class of&#xd;
specialized transportation problems. It was recently suggested by Nesterov&#xd;
\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\cite{Nesterov:2004:Rounding}&#xd;
that this problem can be efficiently treated via a conic reformulation and&#xd;
by utilizing the information gained from the computation of a pair of John&#xd;
ellipsoids for the subdifferential of the objective function evaluated at&#xd;
the origin. Our main contribution is the improvement of the theoretical&#xd;
performance of the algorithms in the cited papers by incorporating a&#xd;
simple bisection idea. We also show that it is possible to design&#xd;
potentially more practical ``nonrestarting" versions of these methods at&#xd;
no or only negligible cost in their theoretical guarantees.&#xd;
&#xd;
In Chapter 3 we consider the geometric problem of finding&#xd;
the intersection of a line and a centrally symmetric convex body&#xd;
$Q$ given as the convex hull of a collection of points. Our&#xd;
algorithms produce a sequence of ellipsoids inscribed in $Q$,&#xd;
``converging" towards the intersection points. It turns out that in&#xd;
doing so we simultaneously solve a number of closely related&#xd;
problems such as the problem of finding the minimum $\ell_1$ norm&#xd;
solution of a full rank underdetermined linear system, minimizing&#xd;
the maximum of absolute values of linear functions, or linear&#xd;
optimization over the polytope polar to $Q$. We finish the&#xd;
discussion by describing applications to truss topology design and&#xd;
optimal design of statistical experiments.</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">818288 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en_US">en_US</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="isformatof">bibid: 6476399</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">large-scale optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">linear programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">convex minimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">first-order methods</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">nonsmooth optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">relative scale</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">truss topology design</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">c-optimality</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">optimal design</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Frank-Wolfe algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">ellipsoid method</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">iteratively reweighted least squares</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">O(1/\epsilon) convergence</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale</dim:field>
   <dim:field mdschema="dc" element="type" lang="en_US">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Richtarik, Peter</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="5c928570-bdea-4192-9803-c5eeabf6bb5c">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en_US&lt;/Language>
   	&lt;Title>Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2007-08-03T13:21:58Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Richtarik, Peter&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>large-scale optimization&lt;/Keyword>
    &lt;Keyword>linear programming&lt;/Keyword>
    &lt;Keyword>convex minimization&lt;/Keyword>
    &lt;Keyword>first-order methods&lt;/Keyword>
    &lt;Keyword>nonsmooth optimization&lt;/Keyword>
    &lt;Keyword>relative scale&lt;/Keyword>
    &lt;Keyword>truss topology design&lt;/Keyword>
    &lt;Keyword>c-optimality&lt;/Keyword>
    &lt;Keyword>optimal design&lt;/Keyword>
    &lt;Keyword>Frank-Wolfe algorithm&lt;/Keyword>
    &lt;Keyword>ellipsoid method&lt;/Keyword>
    &lt;Keyword>iteratively reweighted least squares&lt;/Keyword>
    &lt;Keyword>O(1/\epsilon) convergence&lt;/Keyword>
   	&lt;Abstract>This thesis is concerned with  the study of algorithms for approximately&#xd;
solving large-scale linear and nonsmooth convex minimization problems&#xd;
within a prescribed relative error $\delta$ of the optimum. The methods we&#xd;
propose converge in $O(1/\delta^2)$ or $O(1/\delta)$ iterations of a&#xd;
first-order type. While the theoretical lower iteration bound for&#xd;
approximately solving (in the absolute sense) nonsmooth convex&#xd;
minimization problems in the black-box computational model of complexity&#xd;
is $O(1/\epsilon^2)$, the algorithms developed in this thesis are able to&#xd;
perform better by effectively utilizing the information about the&#xd;
\emph{structure} of the problems.&#xd;
&#xd;
Chapter 1 contains a brief account of the relevant part of&#xd;
complexity theory for convex optimization problems. This is done in order&#xd;
to be able to better communicate the proper setting of our work within the&#xd;
current literature. We finish with concise synopses of the following&#xd;
chapters.&#xd;
&#xd;
In Chapter 2 we study the general problem of unconstrained&#xd;
convex minimization in  relative scale. Algorithms of this type are hard&#xd;
to find in the literature and are known perhaps only for a narrow class of&#xd;
specialized transportation problems. It was recently suggested by Nesterov&#xd;
\cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\cite{Nesterov:2004:Rounding}&#xd;
that this problem can be efficiently treated via a conic reformulation and&#xd;
by utilizing the information gained from the computation of a pair of John&#xd;
ellipsoids for the subdifferential of the objective function evaluated at&#xd;
the origin. Our main contribution is the improvement of the theoretical&#xd;
performance of the algorithms in the cited papers by incorporating a&#xd;
simple bisection idea. We also show that it is possible to design&#xd;
potentially more practical ``nonrestarting&amp;quot; versions of these methods at&#xd;
no or only negligible cost in their theoretical guarantees.&#xd;
&#xd;
In Chapter 3 we consider the geometric problem of finding&#xd;
the intersection of a line and a centrally symmetric convex body&#xd;
$Q$ given as the convex hull of a collection of points. Our&#xd;
algorithms produce a sequence of ellipsoids inscribed in $Q$,&#xd;
``converging&amp;quot; towards the intersection points. It turns out that in&#xd;
doing so we simultaneously solve a number of closely related&#xd;
problems such as the problem of finding the minimum $\ell_1$ norm&#xd;
solution of a full rank underdetermined linear system, minimizing&#xd;
the maximum of absolute values of linear functions, or linear&#xd;
optimization over the polytope polar to $Q$. We finish the&#xd;
discussion by describing applications to truss topology design and&#xd;
optimal design of statistical experiments.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>