<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.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-22T21:03:51Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/2922" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/2922</identifier><datestamp>2017-03-21T21:38:42Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="f54ac3d0-a920-4dad-818a-5606bd91dbcb" confidence="600">Wei, Hua</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2007-05-08T14:00:50Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2007-05-08T14:00:50Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/2922</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We study numerical stability for interior-point methods applied to Linear  Programming, LP, and Semidefinite Programming, SDP.   We analyze the difficulties  inherent in current methods and present robust algorithms.    &amp;lt;br /&amp;gt;&amp;lt;br /&amp;gt;  We start with the error bound analysis of the search directions   for the normal equation approach for LP.   Our  error analysis explains the surprising fact that the ill-conditioning   is not a significant problem for the normal equation system.    We also explain why most of the popular LP  solvers have a default stop tolerance of only 10&amp;lt;sup&amp;gt;-8&amp;lt;/sup&amp;gt; when  the machine precision on a 32-bit computer is approximately 10&amp;lt;sup&amp;gt;-16&amp;lt;/sup&amp;gt;.    &amp;lt;br /&amp;gt;&amp;lt;br /&amp;gt;  We then propose a simple alternative approach for  the normal equation based interior-point method.   This approach has better  numerical stability than the normal equation based method.   Although, our  approach is not competitive in terms of CPU time for the NETLIB problem set,  we do obtain higher accuracy.   In addition, we obtain significantly smaller CPU  times compared to  the normal equation based direct solver,  when we solve  well-conditioned, huge, and sparse problems by using our iterative based  linear solver.   Additional techniques discussed are:   crossover; purification step; and no backtracking.    &amp;lt;br /&amp;gt;&amp;lt;br /&amp;gt;  Finally, we present an algorithm to construct SDP problem instances with prescribed  strict complementarity gaps.   We then introduce two &amp;lt;em&amp;gt;measures of strict complementarity gaps&amp;lt;/em&amp;gt;.   We  empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the  strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver,  as well as with the local asymptotic convergence rate; and (iii) large strict complementarity  gaps, coupled with the failure of Slater&amp;apos;s condition, correlate well with loss of accuracy in  the solutions.   In addition, the numerical tests show that there is no correlation between the  strict complementarity gaps and the geometrical measure used in [31], or with Renegar&amp;apos;s  condition number.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">1001905 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">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2006, 
  Wei, Hua. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Mathematics</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Linear Programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Semidefinite Programming</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">numerical stability</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">normal equation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">strict complementarity gap</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">stable method</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">crossover</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Numerical Stability in Linear Programming and Semidefinite Programming</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>