<?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-22T11:42:27Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9719" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9719</identifier><datestamp>2021-05-21T19:53:37Z</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" authority="bf93b659-8eab-4b61-a1c2-0c0ee321e961" confidence="600">Myklebust, Tor Gunnar Josefsson Jay</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-09-25T13:12:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-09-25T13:12:36Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-09-25</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9719</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This thesis studies the theory and implementation of interior-point methods&#xd;
  for convex optimisation.  A number of important problems from mathematics and&#xd;
  engineering can be cast naturally as convex optimisation problems, and a&#xd;
  great many others have useful convex relaxations.  Interior-point methods&#xd;
  are among the successful algorithms for solving convex optimisation problems.&#xd;
  One class of interior-point methods, called primal-dual interior-point&#xd;
  methods, have been particularly successful at solving optimisation problems&#xd;
  defined over symmetric cones, which are self-dual cones whose&#xd;
  linear automorphisms act transitively on their interiors.&#xd;
&#xd;
  The main theoretical contribution is the design and analysis of a primal-dual&#xd;
  interior-point method for general convex optimisation that is ``primal-dual&#xd;
  symmetric&amp;apos;&amp;apos;---if arithmetic is done exactly, the sequence of iterates&#xd;
  generated is invariant under interchange of primal and dual problems.&#xd;
&#xd;
  The proof of this algorithm&amp;apos;s correctness and asymptotic worst-case iteration&#xd;
  complexity hinges on a new analysis of a certain rank-four update formula&#xd;
  akin to the Hessian estimate updates performed by quasi-Newton methods.&#xd;
&#xd;
  This thesis also gives simple, explicit constructions of primal-dual&#xd;
  scalings---linear maps from the dual space to the primal space that map the&#xd;
  dual iterate to the primal iterate and the barrier gradient at the primal&#xd;
  iterate to the barrier gradient at the dual iterate---by averaging the primal&#xd;
  or dual Hessian over a line segment.  These scalings are called the primal&#xd;
  and dual integral scalings in this thesis.  The primal and dual integral&#xd;
  scalings can inherit certain kinds of good behaviour from the barrier whose&#xd;
  Hessian is averaged.  For instance, if the primal barrier Hessian at every&#xd;
  point maps the primal cone into the dual cone, then the primal integral&#xd;
  scaling also maps the primal cone into the dual cone.&#xd;
&#xd;
  This gives the idea that primal-dual interior-point methods based on the&#xd;
  primal integral scaling might be effective on problems in which the primal&#xd;
  barrier is somehow well-behaved, but the dual barrier is not.&#xd;
&#xd;
  One such class of problems is \emph{hyperbolicity cone&#xd;
  optimisation}---minimising a linear function over the intersection of an&#xd;
  affine space with a so-called hyperbolicity cone.  Hyperbolicity cones arise&#xd;
  from hyperbolic polynomials, which can be seen as a generalisation of the&#xd;
  determinant polynomial on symmetric matrices.  Hyperbolic polynomials&#xd;
  themselves have been of considerable recent interest in mathematics, their&#xd;
  theory playing a role in the resolution of the Kadison-Singer problem.&#xd;
&#xd;
  In the setting of hyperbolicity cone optimisation, the primal barrier&amp;apos;s&#xd;
  Hessian satisfies ``the long-step Hessian estimation property&amp;apos;&amp;apos; with which&#xd;
  the primal barrier may be easily estimated everywhere in the interior of the&#xd;
  cone in terms of the primal barrier anywhere else in the interior of the&#xd;
  cone, and the primal barrier Hessian at every point in the interior of the&#xd;
  cone maps the primal cone into the dual cone.  In general, however, the dual&#xd;
  barrier satisfies neither of these properties.&#xd;
&#xd;
  This thesis also describes an adaptation of the Mizuno-Todd-Ye method for&#xd;
  linear optimisation to hyperbolicity cone optimisation and its implementation.&#xd;
  This implementation is meant as a window into the algorithm&amp;apos;s convergence&#xd;
  behaviour on hyperbolicity cone optimisation problems rather than as a useful&#xd;
  software package for solving hyperbolicity cone optimisation problems that&#xd;
  might arise in practice.&#xd;
&#xd;
  In the final chapter of this thesis is a description of an implementation of&#xd;
  an interior-point method for linear optimisation.  This implementation can&#xd;
  efficiently use primal-dual scalings based on rank-four updates to an old&#xd;
  scaling matrix and was meant as a platform to evaluate that technique.&#xd;
  This implementation is modestly slower than CPLEX&amp;apos;s barrier optimiser on&#xd;
  problems with no free or double-bounded variables.  A computational&#xd;
  comparison between the ``standard&amp;apos;&amp;apos; interior-point algorithm for solving LPs&#xd;
  with one instance of the rank-four update technique is given.&#xd;
&#xd;
  The rank-four update formula mentioned above has an interesting&#xd;
  specialisation to linear optimisation that is also described in this thesis.&#xd;
  A serious effort was made to improve the running time of an interior-point&#xd;
  method for linear optimisation using this technique, but it ultimately failed.&#xd;
&#xd;
  This thesis revisits work from the early 1990s by Rothberg and Gupta on&#xd;
  cache-efficient data structures for Cholesky factorisation.  This thesis&#xd;
  proposes a variant of their data structure, showing that, in this variant,&#xd;
  the time needed to perform triangular solves can be reduced substantially&#xd;
  from the time needed by either the usual supernodal or simplicial data&#xd;
  structures.&#xd;
  The linear optimisation problem solver described in this thesis is also used&#xd;
  to study the impact of these different data structures on the overall time&#xd;
  required to solve a linear optimisation problem.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">On primal-dual interior-point algorithms for convex optimisation</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Combinatorics and Optimization</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>