Topics in Structured Convex Optimization and Nonlinear Programming
Loading...
Files
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2007-07-12
Type of Work
Department
Mathematics and Statistics
Program
Mathematics, Applied
Citation of Original Publication
Rights
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.
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.