Topics in Structured Convex Optimization and Nonlinear Programming

Abstract

A convex programming problem in a conic form is a minimization of a linear function $\langle c, x\rangle$ over the intersection of an affine space $\{x\in \mathbb{R}^n:\;Ax=b\}$ and a convex cone $K$. In this thesis, we study two broad subclasses of convex programming problems with $K$ having special structure. We treat \emph{homogeneous} programming problems. These are convex programming problems in which $K$ is a homogeneous cone. These problems are more general than well-studied semi-definite or symmetric programming problems. We explain the key steps of Vinberg's classification of homogeneous cones in terms of so-called $T$-algebras, and discuss some properties of a $T$-algebraic barrier associated with $K$. We also consider two alternative constructions of homogeneous cones by means of Siegel domains, and provide a new expression for an \emph{optimal} dual self-concordant barrier for $K$ using the dual construction of Rothaus. A self-concordant barrier is \emph{optimal} if it has the smallest parameter among all self-concordant barriers for $K$. It is important for a barrier to have the smallest possible parameter $\theta$, since $\theta$ enters directly into the complexity estimates for interior-point methods. We give a simplified self-concordance proof for the primal barrier of Guler and Tuncel, and consider several examples. The class of \emph{hyperbolic} programming problems is discussed in the thesis as well. These are conic problems with $K$ being a hyperbolicity cone corresponding to some homogeneous hyperbolic polynomial. We provide descriptions of hyperbolicity cones and their derivative relaxations. We discuss the three-dimensional Lax's theorem, which states that any hyperbolic polynomial of three variables can be written as a determinant of a linear combination of $m\times m$ symmetric matrices. This is a very important theorem since it implies semidefinite representability of any hyperbolicity cone in three dimensions. We show that the Lax's theorem is a powerful and unifying tool by applying it in the proofs of various important results in interior-point methods and convex analysis, and by providing some interesting connections with other branches of mathematics. Finally, the thesis deals with variational problems in quasi-Newton methods. We consider variational problems associated with popular DFP and BFGS updates, and obtain these updates in a very simple manner. Our approach is coordinate free; we eliminate symmetry constraints imposed on the updates by working directly in the space of symmetric matrices. We consider the dual problems. A novel feature of our work is that we construct several new variational problems whose optimal solutions coincide with quasi-Newton update matrices. These new variational problems may be useful in suggesting new quasi-Newton methods in the future.