<?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-21T09:32:40Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/2197" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/2197</identifier><datestamp>2026-05-14T13:54:40Z</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">Zinchenko, Yuriy A.</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2005-09-15T19:35:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2005-09-15T19:35:28Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2005-09-15T19:35:28Z</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/2197</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">6476034</dim:field>
   <dim:field mdschema="dc" element="description" lang="en_US">James Renegar, ORIE&#xd;
Sidney Resnick, ORIE&#xd;
Louis Billera, Mathematics</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en_US">Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these&#xd;
structures have drawn considerable attention in the optimization community as well. It turns out that most of interior point methods (IPM) theory applies naturally to the class of conic programming problems arising from hyperbolicity cones. In particular, linear programming (LP), second-order conic programming (SOCP) and positive&#xd;
semi-definite programming (SDP) are themselves instances of conic programming problems of this kind.&#xd;
&#xd;
The thesis consists of two parts. The first part is devoted to the structure of a particular family of hyperbolicity cones which give a sequence of relaxations to the nonnegative orthant. The second part contains analysis of the newly proposed algorithm for LP based on these relaxations.&#xd;
&#xd;
While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an&#xd;
arbitrary hyperbolic polynomial $p$, little is known about its dual cone ${K_p}_*$. This problem is closely related to LP itself: for the case of $p(x)=E_n(x)=\prod_{i=1 \ldots n} x_i$ the (closure of the) hyperbolicity cone is self-dual and is, in fact, $\Re^n_+$. Elementary symmetric polynomials can be thought of as derivative&#xd;
polynomials (in a certain sense) of $E_n(x)$, and are building blocks for hyperbolic polynomials themselves, their associated hyperbolicity cones giving a natural sequence of relaxations for&#xd;
$\Re^n_{++}$. We give an algebraic characterization for the dual cone associated with $p'(x)=E_{n-1}(x)=\sum_{1 \leq i \leq n}&#xd;
\prod_{j \neq i} x_j$ which was previously unknown and show how one can easily construct a SCB functional for this cone. We comment on&#xd;
possible extensions of this result.&#xd;
&#xd;
Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant&#xd;
using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a&#xd;
central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution&#xd;
demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy&#xd;
assumptions).</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">763735 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en_US</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Mathematical programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Linear programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Hyperbolic polynomials</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Elementary symmetric polynomials</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Conic programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en_US">Interior-point methods</dim:field>
   <dim:field mdschema="dc" element="title" lang="en_US">THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING</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">Zinchenko, Yuriy A.</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="9a6bb12e-f7bd-4323-af38-ec1ee3cc1871">
	&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>THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2005-09-15T19:35:28Z&lt;/PublicationDate>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Zinchenko, Yuriy A.&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>Mathematical programming&lt;/Keyword>
    &lt;Keyword>Linear programming&lt;/Keyword>
    &lt;Keyword>Hyperbolic polynomials&lt;/Keyword>
    &lt;Keyword>Elementary symmetric polynomials&lt;/Keyword>
    &lt;Keyword>Conic programming&lt;/Keyword>
    &lt;Keyword>Interior-point methods&lt;/Keyword>
   	&lt;Abstract>Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these&#xd;
structures have drawn considerable attention in the optimization community as well. It turns out that most of interior point methods (IPM) theory applies naturally to the class of conic programming problems arising from hyperbolicity cones. In particular, linear programming (LP), second-order conic programming (SOCP) and positive&#xd;
semi-definite programming (SDP) are themselves instances of conic programming problems of this kind.&#xd;
&#xd;
The thesis consists of two parts. The first part is devoted to the structure of a particular family of hyperbolicity cones which give a sequence of relaxations to the nonnegative orthant. The second part contains analysis of the newly proposed algorithm for LP based on these relaxations.&#xd;
&#xd;
While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an&#xd;
arbitrary hyperbolic polynomial $p$, little is known about its dual cone ${K_p}_*$. This problem is closely related to LP itself: for the case of $p(x)=E_n(x)=\prod_{i=1 \ldots n} x_i$ the (closure of the) hyperbolicity cone is self-dual and is, in fact, $\Re^n_+$. Elementary symmetric polynomials can be thought of as derivative&#xd;
polynomials (in a certain sense) of $E_n(x)$, and are building blocks for hyperbolic polynomials themselves, their associated hyperbolicity cones giving a natural sequence of relaxations for&#xd;
$\Re^n_{++}$. We give an algebraic characterization for the dual cone associated with $p&amp;apos;(x)=E_{n-1}(x)=\sum_{1 \leq i \leq n}&#xd;
\prod_{j \neq i} x_j$ which was previously unknown and show how one can easily construct a SCB functional for this cone. We comment on&#xd;
possible extensions of this result.&#xd;
&#xd;
Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant&#xd;
using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a&#xd;
central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution&#xd;
demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy&#xd;
assumptions).&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>