Topics in Structured Convex Optimization and Nonlinear Programming

Simple item page
dc.contributor.advisorGuler, Osman
dc.contributor.authorShevchenko, Olena
dc.contributor.departmentMathematics and Statistics
dc.contributor.programMathematics, Applied
dc.date.accessioned2015-10-14T03:12:48Z
dc.date.available2015-10-14T03:12:48Z
dc.date.issued2007-07-12
dc.description.abstractA 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.
dc.formatapplication/pdf
dc.genredissertations
dc.identifierdoi:10.13016/M2P666
dc.identifier.other1050
dc.identifier.urihttp://hdl.handle.net/11603/1030
dc.languageen
dc.relation.isAvailableAtThe University of Maryland, Baltimore County (UMBC)
dc.relation.ispartofUMBC Theses and Dissertations Collection
dc.relation.ispartofUMBC Graduate School Collection
dc.relation.ispartofUMBC Student Collection
dc.relation.ispartofUMBC Mathematics and Statistics Department Collection
dc.rightsThis 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.
dc.sourceOriginal File Name: umi-umbc-1050.pdf
dc.subjectMathematics (0405)
dc.subjectOperations Research (0796)
dc.subjectinterior-point methods
dc.subjecthomogeneous programming
dc.subjecthomogeneos cones
dc.subjecthyperbolicity cones
dc.titleTopics in Structured Convex Optimization and Nonlinear Programming
dc.typeText
dcterms.accessRightsAccess limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
75.pdf
Size:
549.79 KB
Format:
Adobe Portable Document Format
Download

Collections

UMBC Theses and Dissertations
UMBC Graduate School
UMBC Mathematics and Statistics Department
UMBC Student Collection