{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/2197"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/2197","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING","abstract":"Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an 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 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 $\\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} \\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 possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions).","abstract_html":"Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone <span class=\"etd-inline-math\">K<sub>p</sub></span> associated to an arbitrary hyperbolic polynomial $p$, little is known about its dual cone <span class=\"etd-inline-math\">{K<sub>p</sub>}<sub>*</sub></span>. This problem is closely related to LP itself: for the case of <span class=\"etd-inline-math\">p(x)=E<sub>n</sub>(x)=\\prod<sub>i=1 \\ldots n</sub> x<sub>i</sub></span> the (closure of the) hyperbolicity cone is self-dual and is, in fact, <span class=\"etd-inline-math\">\\Re<sup>n</sup><sub>+</sub></span>. Elementary symmetric polynomials can be thought of as derivative polynomials (in a certain sense) of <span class=\"etd-inline-math\">E<sub>n</sub>(x)</span>, and are building blocks for hyperbolic polynomials themselves, their associated hyperbolicity cones giving a natural sequence of relaxations for <span class=\"etd-inline-math\">\\Re<sup>n</sup><sub>++</sub></span>. We give an algebraic characterization for the dual cone associated with <span class=\"etd-inline-math\">p&#x27;(x)=E<sub>n-1</sub>(x)=\\sum<sub>1 \\leq i \\leq n</sub> \\prod<sub>j \\neq i</sub> x<sub>j</sub></span> which was previously unknown and show how one can easily construct a SCB functional for this cone. We comment on possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions).","abstract_has_math":true,"creators":["Zinchenko, Yuriy A."],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005-09-15T19:35:28Z","date_published":"2005-09-15T19:35:28Z","updated_at":"2026-11-19T03:14:48Z","subjects":["Mathematical programming","Linear programming","Hyperbolic polynomials","Elementary symmetric polynomials","Conic programming","Interior-point methods"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6476034"],"render_values":[{"text":"6476034","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/2197","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/2197","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%2F2197","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Zinchenko, Yuriy A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-09-15T19:35:28Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-09-15T19:35:28Z"]},{"key":"dc:date.issued","label":"Date","values":["2005-09-15T19:35:28Z"]},{"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":["Mathematical programming","Linear programming","Hyperbolic polynomials","Elementary symmetric polynomials","Conic programming","Interior-point methods"]}]},{"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":["6476034"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/2197"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"9a6bb12e-f7bd-4323-af38-ec1ee3cc1871\"> <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>THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2005-09-15T19:35:28Z</PublicationDate> <Authors> <Author> <DisplayName>Zinchenko, Yuriy A.</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Mathematical programming</Keyword> <Keyword>Linear programming</Keyword> <Keyword>Hyperbolic polynomials</Keyword> <Keyword>Elementary symmetric polynomials</Keyword> <Keyword>Conic programming</Keyword> <Keyword>Interior-point methods</Keyword> <Abstract>Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an 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 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 $\\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} \\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 possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions).</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Zinchenko, Yuriy A."]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["James Renegar, ORIE Sidney Resnick, ORIE Louis Billera, Mathematics"]},{"key":"dc:description.abstract","label":"Abstract","values":["Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an 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 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 $\\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} \\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 possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions)."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["763735 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING"]},{"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=\"9a6bb12e-f7bd-4323-af38-ec1ee3cc1871\"> <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>THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2005-09-15T19:35:28Z</PublicationDate> <Authors> <Author> <DisplayName>Zinchenko, Yuriy A.</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Mathematical programming</Keyword> <Keyword>Linear programming</Keyword> <Keyword>Hyperbolic polynomials</Keyword> <Keyword>Elementary symmetric polynomials</Keyword> <Keyword>Conic programming</Keyword> <Keyword>Interior-point methods</Keyword> <Abstract>Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an 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 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 $\\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} \\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 possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions).</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Zinchenko, Yuriy A."],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Zinchenko, Yuriy A."],"dc:date.accessioned":["2005-09-15T19:35:28Z"],"dc:date.available":["2005-09-15T19:35:28Z"],"dc:date.issued":["2005-09-15T19:35:28Z"],"dc:description":["James Renegar, ORIE Sidney Resnick, ORIE Louis Billera, Mathematics"],"dc:description.abstract":["Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these 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 semi-definite programming (SDP) are themselves instances of conic programming problems of this kind. 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. While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an 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 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 $\\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} \\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 possible extensions of this result. Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions)."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["763735 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6476034"],"dc:identifier.uri":["https://hdl.handle.net/1813/2197"],"dc:language.iso":["en_US"],"dc:subject":["Mathematical programming","Linear programming","Hyperbolic polynomials","Elementary symmetric polynomials","Conic programming","Interior-point methods"],"dc:title":["THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:14:48Z"}