<?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-22T16:24:56Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/8189" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/8189</identifier><datestamp>2017-03-21T14:11:43Z</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="ee2524dc-0c08-415c-8f27-73ae7383a216" confidence="600">Karimi, Sahar</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2014-01-23T20:23:30Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2014-01-23T20:23:30Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2014-01-23</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2014</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/8189</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In a series of work initiated by Nemirovsky and Yudin, and later extended by Nesterov, first-order algorithms for unconstrained minimization with optimal theoretical complexity bound have been proposed. On the other hand, conjugate gradient algorithms as one of the widely used first-order techniques suffer from the lack of a finite complexity bound. In fact their performance can possibly be quite poor. This dissertation is partially on tightening the gap between these two classes of algorithms, namely the traditional conjugate gradient methods and optimal first-order techniques.  We derive conditions under which conjugate gradient methods attain the same complexity bound as in Nemirovsky-Yudin&amp;apos;s and Nesterov&amp;apos;s methods. Moreover, we propose a conjugate gradient-type algorithm named CGSO, for Conjugate Gradient with Subspace Optimization, achieving the optimal complexity bound with the payoff of a little extra computational cost. &#xd;
&#xd;
We extend the theory of CGSO to convex problems with linear constraints. In particular we focus on solving $l_1$-regularized least square problem, often referred to as Basis Pursuit Denoising (BPDN) problem in the optimization community. BPDN arises in many practical fields including sparse signal recovery, machine learning, and statistics. Solving BPDN is fairly challenging because the size of the involved signals can be quite large; therefore first order methods are of particular interest for these problems. We propose a quasi-Newton proximal method for solving BPDN. Our numerical results suggest that our technique is computationally effective, and can compete favourably with the other state-of-the-art solvers.</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="subject" lang="en">Convex Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">First-Order Methods</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Conjugate Gradient</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Proximal Quasi-Newton Methods</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Basis Pursuit Denoising Problem</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">L1-regularized Least Square problem</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">On the Relationship between Conjugate Gradient and Optimal First-Order Methods for Convex Optimization</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="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>