Projection algorithms for linear programming
Identifieur interne : 001100 ( Istex/Corpus ); précédent : 001099; suivant : 001101Projection algorithms for linear programming
Auteurs : U. Betke ; P. GritzmannSource :
- European Journal of Operational Research [ 0377-2217 ] ; 1992.
Abstract
Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.
Url:
DOI: 10.1016/0377-2217(92)90080-S
Links to Exploration step
ISTEX:6FE9317EF4EAD706B992EBF43CB0DA5558B022BCLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Projection algorithms for linear programming</title><author><name sortKey="Betke, U" sort="Betke, U" uniqKey="Betke U" first="U." last="Betke">U. Betke</name><affiliation><mods:affiliation>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:6FE9317EF4EAD706B992EBF43CB0DA5558B022BC</idno><date when="1992" year="1992">1992</date><idno type="doi">10.1016/0377-2217(92)90080-S</idno><idno type="url">https://api.istex.fr/document/6FE9317EF4EAD706B992EBF43CB0DA5558B022BC/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001100</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001100</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Projection algorithms for linear programming</title><author><name sortKey="Betke, U" sort="Betke, U" uniqKey="Betke U" first="U." last="Betke">U. Betke</name><affiliation><mods:affiliation>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</mods:affiliation></affiliation></author><author><name sortKey="Gritzmann, P" sort="Gritzmann, P" uniqKey="Gritzmann P" first="P." last="Gritzmann">P. Gritzmann</name><affiliation><mods:affiliation>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">European Journal of Operational Research</title><title level="j" type="abbrev">EOR</title><idno type="ISSN">0377-2217</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1992">1992</date><biblScope unit="volume">60</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="287">287</biblScope><biblScope unit="page" to="295">295</biblScope></imprint><idno type="ISSN">0377-2217</idno></series><idno type="istex">6FE9317EF4EAD706B992EBF43CB0DA5558B022BC</idno><idno type="DOI">10.1016/0377-2217(92)90080-S</idno><idno type="PII">0377-2217(92)90080-S</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0377-2217</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>U. Betke</name><affiliations><json:string>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</json:string></affiliations></json:item><json:item><name>P. Gritzmann</name><affiliations><json:string>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Linear programming</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>convex programming</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>nearest-point map</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>ellipsoid method</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>polynomial-time algorithms</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>variable metric algorithms</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>DFP-method</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>BFGS-method</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.</abstract><qualityIndicators><score>5.96</score><pdfVersion>1.2</pdfVersion><pdfPageSize>576 x 792 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>8</keywordCount><abstractCharCount>585</abstractCharCount><pdfWordCount>5253</pdfWordCount><pdfCharCount>26954</pdfCharCount><pdfPageCount>9</pdfPageCount><abstractWordCount>80</abstractWordCount></qualityIndicators><title>Projection algorithms for linear programming</title><pii><json:string>0377-2217(92)90080-S</json:string></pii><refBibs><json:item><author><json:item><name>S. Agmon</name></json:item></author><host><volume>6</volume><pages><last>392</last><first>382</first></pages><author></author><title>Canadian Journal of Mathematics</title></host><title>The relaxation method for linear inequalities</title></json:item><json:item><host><author></author><title>Topics in Relaxation and Ellipsoidal Methods</title></host></json:item><json:item><author><json:item><name>R.G. Bland</name></json:item><json:item><name>D. Goldfarb</name></json:item><json:item><name>M.J. Todd</name></json:item></author><host><volume>29</volume><pages><last>1091</last><first>1039</first></pages><author></author><title>Operations Research</title></host><title>The ellipsoidal method: A survey</title></json:item><json:item><author><json:item><name>L.M. Bregman</name></json:item></author><host><volume>6</volume><pages><last>692</last><first>688</first></pages><author></author><title>Soviet Mathematics Doklady</title></host><title>The method of successive projection for finding a common point of convex sets</title></json:item><json:item><author><json:item><name>C.G. Broyden</name></json:item></author><host><volume>16</volume><pages><first>670</first></pages><author></author><title>Notices of the American Mathematical Society</title></host><title>A new double-rank minimization algorithm</title></json:item><json:item><author><json:item><name>C.G. Broyden</name></json:item></author><host><volume>24</volume><pages><last>382</last><first>365</first></pages><author></author><title>Mathematics of Computing</title></host><title>The convergence of single-rank quasi-Newton methods</title></json:item><json:item><author><json:item><name>W.C. Davidon</name></json:item></author><host><author></author><title>AEC Research and Development Report ANL-5990</title></host><title>Variable metric methods for minimization</title></json:item><json:item><host><author></author><title>Nonlinear Programming: Sequential Unconstrained Minimization Techniques</title></host></json:item><json:item><author><json:item><name>R. Fletcher</name></json:item></author><host><volume>13</volume><pages><last>322</last><first>317</first></pages><author></author><title>Computer Journal</title></host><title>A new approach to variable metric algorithms</title></json:item><json:item><author><json:item><name>R. Fletcher</name></json:item><json:item><name>M.J.D. Powell</name></json:item></author><host><volume>6</volume><pages><last>168</last><first>163</first></pages><author></author><title>Computer Journal</title></host><title>A rapidly convergent descent method for minimization</title></json:item><json:item><author><json:item><name>P. Gaćz</name></json:item><json:item><name>L. Lovász</name></json:item></author><host><volume>14</volume><pages><last>68</last><first>61</first></pages><author></author><title>Mathematical Programming Study</title></host><title>Khachians's algorithm for linear programming</title></json:item><json:item><host><author></author><title>Computers and Intractability</title></host></json:item><json:item><author><json:item><name>P.E. Gill</name></json:item><json:item><name>M.A. Murray</name></json:item><json:item><name>J.A. Saunders</name></json:item><json:item><name>J.A. Tomlin</name></json:item><json:item><name>M.H. Wright</name></json:item></author><host><volume>36</volume><pages><last>209</last><first>183</first></pages><author></author><title>Mathematical Programming</title></host><title>On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method</title></json:item><json:item><author><json:item><name>J.L. Goffin</name></json:item></author><host><volume>22</volume><pages><last>103</last><first>93</first></pages><author></author><title>Mathematical Programming</title></host><title>On the nonpolynomiality of the relaxation method for systems of linear inequalities</title></json:item><json:item><author><json:item><name>D. Goldfarb</name></json:item></author><host><volume>24</volume><pages><last>26</last><first>23</first></pages><author></author><title>Mathematics of Computing</title></host><title>A family of variable metric methods derived by variational means</title></json:item><json:item><author><json:item><name>M. Grötschel</name></json:item><json:item><name>L. Lovaśz</name></json:item><json:item><name>A. Schrijver</name></json:item></author><host><volume>1</volume><pages><last>197</last><first>169</first></pages><author></author><title>Combinatorica</title></host><title>The ellipsoid method and its consequences in combinatorial optimization</title></json:item><json:item><author><json:item><name>M. Grötschel</name></json:item><json:item><name>L. Lovaśz</name></json:item><json:item><name>A. Schrijver</name></json:item></author><host><volume>4</volume><pages><last>295</last><first>291</first></pages><author></author><title>Combinatorica</title></host><title>The ellipsoid method and its consequences in combinatorial optimization</title></json:item><json:item><host><author></author><title>Geometric Algorithms and Combinatorial Optimization</title></host></json:item><json:item><author><json:item><name>N. Karmarkar</name></json:item></author><host><volume>4</volume><pages><last>397</last><first>373</first></pages><author></author><title>Combinatorica</title></host><title>A new polynomial-time algorithm for linear programming</title></json:item><json:item><author><json:item><name>L.G. Khachian</name></json:item></author><host><volume>244</volume><pages><last>1096</last><first>1093</first></pages><author></author><title>Doklady Academiia Nauk SSSR</title></host><title>A polynomial algorithm in linear programming</title></json:item><json:item><host><volume>20</volume><pages><last>194</last><first>191</first></pages><author></author><title>Soviet Mathematics Doklady</title></host></json:item><json:item><author><json:item><name>L.G. Khachian</name></json:item></author><host><volume>20</volume><pages><last>72</last><first>53</first></pages><author></author><title>U.S.S.R. Computational Mathematics and Mathematical Physics</title></host><title>Polynomial algorithms in linear programming</title></json:item><json:item><author><json:item><name>L.G. Khachian</name></json:item></author><host><volume>22</volume><pages><last>1003</last><first>999</first></pages><author></author><title>U.S.S.R. Computational Mathematics and Mathematical Physics</title></host><title>On exact solutions of systems of linear inequalities and LP-problems</title></json:item><json:item><author><json:item><name>J.F. Maurras</name></json:item><json:item><name>K. Truemper</name></json:item><json:item><name>M. Akgül</name></json:item></author><host><volume>21</volume><pages><last>136</last><first>121</first></pages><author></author><title>Mathematical Programming</title></host><title>Polynomial algorithms for a class of linear programs</title></json:item><json:item><host><author></author><title>Convex Polytopes and the Upper Bound Conjecture</title></host></json:item><json:item><author><json:item><name>J.E. Mitchell</name></json:item><json:item><name>M.J. Todd</name></json:item></author><host><author></author><title>Technical Report No. 725</title></host><serie><author></author><title>Technical Report No. 725</title></serie><title>On the relationship between the search directions in the affine and projective variants of Karmarkar's linear programming algorithm</title></json:item><json:item><author><json:item><name>T.S. Motzkin</name></json:item><json:item><name>I.J. Schoenberg</name></json:item></author><host><volume>6</volume><pages><last>404</last><first>393</first></pages><author></author><title>Canadian Journal of Mathematics</title></host><title>The relaxation method for linear inequalities</title></json:item><json:item><author><json:item><name>A.S. Nemirovski</name></json:item><json:item><name>D.B. Yudin</name></json:item></author><host><volume>12</volume><pages><last>369</last><first>357</first></pages><author></author><title>Ekonomika i Mathematicheskie Metody</title></host><title>Informational complexity and effective methods of solution for convex extremal problems</title></json:item><json:item><host><volume>13</volume><pages><last>45</last><first>25</first></pages><author></author><title>Russian and East European Mathematics and Economics</title></host></json:item><json:item><host><author></author><title>Problem Complexity and Method Efficiency in Optimization</title></host></json:item><json:item><host><author></author><title>Convex Analysis</title></host></json:item><json:item><author><json:item><name>D.F. Shanno</name></json:item></author><host><volume>24</volume><pages><last>656</last><first>647</first></pages><author></author><title>Mathematics of Computing</title></host><title>Conditioning of quasi-Newton methods for function minimizing</title></json:item><json:item><author><json:item><name>N.Z. Shor</name></json:item></author><host><volume>6</volume><pages><last>12</last><first>6</first></pages><author></author><title>Kibernetika</title></host><title>Utilization of the operation of space dilatation in the minimization of convex functions</title></json:item><json:item><host><volume>6</volume><pages><last>15</last><first>7</first></pages><author></author><title>Cybernetics</title></host></json:item><json:item><author><json:item><name>N.Z. Shor</name></json:item></author><host><volume>6</volume><pages><last>85</last><first>80</first></pages><author></author><title>Kibernetika</title></host><title>Convergence rate of the gradient descent method with dilatation of space</title></json:item><json:item><host><volume>6</volume><pages><last>108</last><first>102</first></pages><author></author><title>Cybernetics</title></host></json:item><json:item><author><json:item><name>N.Z. Shor</name></json:item></author><host><volume>13</volume><pages><last>95</last><first>94</first></pages><author></author><title>Kibernetika</title></host><title>Cut-off method with space extension in convex programming problems</title></json:item><json:item><host><volume>13</volume><pages><last>96</last><first>94</first></pages><author></author><title>Cybernetics</title></host></json:item><json:item><host><author></author><title>Minimization Methods for Non-differentiable Functions</title></host></json:item><json:item><author><json:item><name>M.J. Todd</name></json:item></author><host><author></author><title>Technical Report No. 419</title></host><serie><author></author><title>Technical Report No. 419</title></serie><title>Some remarks on the relaxation method for linear inequalities</title></json:item><json:item><author><json:item><name>R. Vanderbei</name></json:item><json:item><name>M. Meketon</name></json:item><json:item><name>B. Freedman</name></json:item></author><host><volume>1</volume><pages><last>407</last><first>395</first></pages><author></author><title>Algorithmica</title></host><title>A modification of Karmarkar's linear programming algorithm</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><serie><language><json:string>unknown</json:string></language><title>Technical Report No. 725</title></serie><host><volume>60</volume><pii><json:string>S0377-2217(00)X0334-7</json:string></pii><pages><last>295</last><first>287</first></pages><issn><json:string>0377-2217</json:string></issn><issue>3</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>European Journal of Operational Research</title><publicationDate>1992</publicationDate></host><publicationDate>1992</publicationDate><copyrightDate>1992</copyrightDate><doi><json:string>10.1016/0377-2217(92)90080-S</json:string></doi><id>6FE9317EF4EAD706B992EBF43CB0DA5558B022BC</id><score>0.7075073</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/6FE9317EF4EAD706B992EBF43CB0DA5558B022BC/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/6FE9317EF4EAD706B992EBF43CB0DA5558B022BC/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/6FE9317EF4EAD706B992EBF43CB0DA5558B022BC/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Projection algorithms for linear programming</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1992</date></publicationStmt><notesStmt><note type="content">Section title: Theory and methodology</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Projection algorithms for linear programming</title><author xml:id="author-1"><persName><forename type="first">U.</forename><surname>Betke</surname></persName><affiliation>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">P.</forename><surname>Gritzmann</surname></persName><note type="biography">Research supported in part by the Alexander von Humboldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.</note><affiliation>Research supported in part by the Alexander von Humboldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.</affiliation><affiliation>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</affiliation></author></analytic><monogr><title level="j">European Journal of Operational Research</title><title level="j" type="abbrev">EOR</title><idno type="pISSN">0377-2217</idno><idno type="PII">S0377-2217(00)X0334-7</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1992"></date><biblScope unit="volume">60</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="287">287</biblScope><biblScope unit="page" to="295">295</biblScope></imprint></monogr><idno type="istex">6FE9317EF4EAD706B992EBF43CB0DA5558B022BC</idno><idno type="DOI">10.1016/0377-2217(92)90080-S</idno><idno type="PII">0377-2217(92)90080-S</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1992</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Linear programming</term></item><item><term>convex programming</term></item><item><term>nearest-point map</term></item><item><term>ellipsoid method</term></item><item><term>polynomial-time algorithms</term></item><item><term>variable metric algorithms</term></item><item><term>DFP-method</term></item><item><term>BFGS-method</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1992">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/6FE9317EF4EAD706B992EBF43CB0DA5558B022BC/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>EOR</jid><aid>9290080S</aid><ce:pii>0377-2217(92)90080-S</ce:pii><ce:doi>10.1016/0377-2217(92)90080-S</ce:doi><ce:copyright type="unknown" year="1992"></ce:copyright></item-info><head><ce:dochead><ce:textfn>Theory and methodology</ce:textfn></ce:dochead><ce:title>Projection algorithms for linear programming</ce:title><ce:author-group><ce:author><ce:given-name>U.</ce:given-name><ce:surname>Betke</ce:surname></ce:author><ce:affiliation><ce:textfn>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</ce:textfn></ce:affiliation></ce:author-group><ce:author-group><ce:author><ce:given-name>P.</ce:given-name><ce:surname>Gritzmann</ce:surname><ce:cross-ref refid="FN1"><ce:sup>∗</ce:sup></ce:cross-ref></ce:author><ce:affiliation><ce:textfn>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</ce:textfn></ce:affiliation><ce:footnote id="FN1"><ce:label>∗</ce:label><ce:note-para>Research supported in part by the Alexander von Humboldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.</ce:note-para></ce:footnote></ce:author-group><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Linear programming</ce:text></ce:keyword><ce:keyword><ce:text>convex programming</ce:text></ce:keyword><ce:keyword><ce:text>nearest-point map</ce:text></ce:keyword><ce:keyword><ce:text>ellipsoid method</ce:text></ce:keyword><ce:keyword><ce:text>polynomial-time algorithms</ce:text></ce:keyword><ce:keyword><ce:text>variable metric algorithms</ce:text></ce:keyword><ce:keyword><ce:text>DFP-method</ce:text></ce:keyword><ce:keyword><ce:text>BFGS-method</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Projection algorithms for linear programming</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Projection algorithms for linear programming</title></titleInfo><name type="personal"><namePart type="given">U.</namePart><namePart type="family">Betke</namePart><affiliation>Universität Siegen, Fachbereich Mathematik, Hölderlinstr. 3, D-5900 Siegen, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">P.</namePart><namePart type="family">Gritzmann</namePart><affiliation>Universität Trier, Fb IV, Mathematik, D-5500 Trier, Germany</affiliation><description>Research supported in part by the Alexander von Humboldt-foundation, by the Institute for Mathematics and its Applications through grands of the NSF and by the Deutsche Forschungsgemeinschaft.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1992</dateIssued><copyrightDate encoding="w3cdtf">1992</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.</abstract><note type="content">Section title: Theory and methodology</note><subject><genre>Keywords</genre><topic>Linear programming</topic><topic>convex programming</topic><topic>nearest-point map</topic><topic>ellipsoid method</topic><topic>polynomial-time algorithms</topic><topic>variable metric algorithms</topic><topic>DFP-method</topic><topic>BFGS-method</topic></subject><relatedItem type="host"><titleInfo><title>European Journal of Operational Research</title></titleInfo><titleInfo type="abbreviated"><title>EOR</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19920810</dateIssued></originInfo><identifier type="ISSN">0377-2217</identifier><identifier type="PII">S0377-2217(00)X0334-7</identifier><part><date>19920810</date><detail type="volume"><number>60</number><caption>vol.</caption></detail><detail type="issue"><number>3</number><caption>no.</caption></detail><extent unit="issue pages"><start>233</start><end>366</end></extent><extent unit="pages"><start>287</start><end>295</end></extent></part></relatedItem><identifier type="istex">6FE9317EF4EAD706B992EBF43CB0DA5558B022BC</identifier><identifier type="DOI">10.1016/0377-2217(92)90080-S</identifier><identifier type="PII">0377-2217(92)90080-S</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001100 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001100 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:6FE9317EF4EAD706B992EBF43CB0DA5558B022BC
|texte= Projection algorithms for linear programming
}}
| This area was generated with Dilib version V0.6.31. |  |