<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1031</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-08</completedDate>
    <publishedDate>2007-11-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Inertia Revealing Preconditioning For Large-Scale Nonconvex Constrained Optimization</title>
    <abstract language="eng">Fast nonlinear programming methods following the all-at-once approach usually employ Newton's method for solving linearized Karush-Kuhn-Tucker (KKT) systems. In nonconvex problems, the Newton direction is only guaranteed to be a descent direction if the Hessian of the Lagrange function is positive definite on the nullspace of the active constraints, otherwise some modifications to Newton's method are necessary. This condition can be verified using the signs of the KKT's eigenvalues (inertia), which are usually available from direct solvers for the arising linear saddle point problems. Iterative solvers are mandatory for very large-scale problems, but in general do not provide the inertia. Here we present a preconditioner based on a multilevel incomplete $LBL^T$ factorization, from which an approximation of the inertia can be obtained. The suitability of the heuristics for application in optimization methods is verified on an interior point method applied to the CUTE and COPS test problems, on large-scale 3D PDE-constrained optimal control problems, as well as 3D PDE-constrained optimization in biomedical cancer hyperthermia treatment planning. The efficiency of the preconditioner is demonstrated on convex and nonconvex problems with $150^3$ state variables and $150^2$ control variables, both subject to bound constraints.</abstract>
    <identifier type="serial">07-32</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1060</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10314</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM J. Scientific Computing 31 (2008) 939-960</enrichment>
    <author>Olaf Schenk</author>
    <submitter>unknown unknown</submitter>
    <author>Andreas Wächter</author>
    <author>Martin Weiser</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-32</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex constrained optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>interior-point method</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>inertia</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>multilevel incomplete factorization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="49M15">Newton-type methods</collection>
    <collection role="msc" number="65F10">Iterative methods for linear systems [See also 65N22]</collection>
    <collection role="msc" number="65K10">Optimization and variational techniques [See also 49Mxx, 93B40]</collection>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="institutes" number="compmed">Computational Medicine</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="projects" number="MATHEON-A17">MATHEON-A17</collection>
    <collection role="projects" number="ZIB-Kaskade7">ZIB-Kaskade7</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1031/ZR_07_32.pdf</file>
  </doc>
  <doc>
    <id>1139</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>TU Berlin, Zuse Institute Berlin, University of Basel</creatingCorporation>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-07-29</completedDate>
    <publishedDate>2009-07-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Factorization of Simplex Basis Matrices</title>
    <abstract language="eng">In the simplex algorithm, solving linear systems with the basis matrix and its transpose accounts for a large part of the total computation time. We investigate various methods from modern numerical linear algebra to improve the computation speed of the basis updates arising in LPs. The experiments are executed on a large real-world test set. The most widely used solution technique is sparse LU factorization, paired with an updating scheme that allows to use the factors over several iterations. Clearly, small number of ﬁll-in elements in the LU factors is critical for the overall performance. Using a wide range of LPs we show numerically that after a simple permutation the non-triangular part of the basis matrix is so small, that the whole matrix can be factorized with (relative) ﬁll-in close to the optimum. This permutation has been exploited by simplex practitioners for many years. But to our knowledge no systematic numerical study has been published that demonstrates the eﬀective reduction to a surprisingly small non-triangular problem, even for large scale LPs. For the factorization of the non-triangular part most existing simplex codes use some variant of dynamic Markowitz pivoting, which originated in the late 1950s. We also show numerically that, in terms of ﬁll-in and in the simplex context, dynamic Markowitz is quite consistently superior to other, more recently developed techniques.</abstract>
    <identifier type="serial">09-24</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1188</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11392</identifier>
    <author>Robert Luce</author>
    <submitter>unknown unknown</submitter>
    <author>Jurjen Duintjer Tebbens</author>
    <author>Jörg Liesen</author>
    <author>Robert Nabben</author>
    <author>Martin Grötschel</author>
    <author>Thorsten Koch</author>
    <author>Olaf Schenk</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-24</number>
    </series>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="65F05">Direct methods for linear systems and matrix inversion</collection>
    <collection role="msc" number="90C05">Linear programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1139/ZR_09_24.pdf</file>
  </doc>
</export-example>
