Convex Relaxations: Beyond Polynomials, Splitting Methods and Average Case Analysis

The first part of this thesis concerns the use of semidefinite programming for solving optimisation problems involving non-polynomial and non-semialgebraic functions. We start with the problem of determining the logarithmic Sobolev constant of a finite Markov chain, which can be framed as a nonconvex optimisation problem involving an entropy-like objective function. We demonstrate that it is possible to apply techniques from sum-of-squares programming to these problems. The main obstacle is that sum-of-squares relaxations only work on *polynomial* optimisation problems. We show how to overcome this obstacle via the stepping stone of rational approximations to entropy-like functions, which allow us to formulate sum-of-squares relaxations of entropic functional inequalities including logarithmic Sobolev inequalities. We prove that our semidefinite programming hierarchies converge to the true logarithmic Sobolev constant of the finite Markov chain. This approach extends to other entropic functional inequalities such as modified logarithmic Sobolev inequalities and strong data processing inequalities. We illustrate our semidefinite relaxations on various examples of finite Markov chains. Next, we consider the problem of obtaining accurate semidefinite approximations of the quantum relative entropy, and of more general quantum $f$-divergences. The quantum relative entropy is a jointly convex function of two positive semidefinite Hermitian matrices, but it cannot be expressed as the optimal value a semidefinite program because it is not semialgebraic. Fawzi, Parrilo, and Saunderson used integral representations of the logarithm to define functions which approximate the quantum relative entropy and which have semidefinite representations of modest size. Our focus is on quantifying the dependence of the approximation error for approximations of this form on the size of the semidefinite program. To do this, we are led to study weighted minimax rational approximations to certain operator convex and operator monotone functions. In particular, we prove that the approximation error can decay root-exponentially in the size of the semidefinite approximation, when the approximation is chosen optimally. Our analysis extends beyond the quantum relative entropy to the α-quasi-entropies. The second part of the thesis makes contributions to the study of first-order algorithms for convex optimisation and non-convex optimisation. We begin by considering first-order methods for solving linear programs. It is known that Douglas-Rachford splitting when applied to a feasible and bounded linear program eventually enters a region of linear convergence towards a solution. We are concerned with quantifying the rate of linear convergence for random linear programs. We prove that for a quite natural class of random linear programs with $n$ nonnegative variables and $m$ linear constraints, conditional on feasibility of the linear program, on the order of m(n-m)\log(1/ε) iterations are required for an ε-accurate solution once the iteration reaches the region of linear convergence. We also consider the problem of certifying infeasibility of a linear program via Dykstra's alternating projections algorithm. We show that as the size $(n,m)$ of the random linear program grows with a fixed ratio $m/n\approx p$, the rate of eventual linear convergence converges in probability to an explicit constant $r(p)$, i.e. it does not deteriorate with the size of the problem. Finally, motivated by an application involving the quantum conditional entropy we consider the difference-of-convex algorithm, which is a method for minimizing (non)convex functions which are expressed as a difference of two convex functions. By interpreting the difference-of-convex algorithm as a Bregman proximal point method, we are able to simplify and strengthen existing non-asymptotic convergence guarantees for the DC algorithm in the nonconvex setting. Under a relative strong convexity assumption we prove a new linear convergence result, and we also present a new DC Polyak-Łojasiewicz condition which ensures a linear convergence rate.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2023

Author dc:creator

• Faust, Oisin

Advisor dc:contributor.advisor

• Fawzi, Hamza

• convex optimisation

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/908f8d5a-3e16-4cad-8c5f-0a23b38ea195/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.112941

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/375171