• Login
    View Item 
    •   Maryland Shared Open Access Repository Home
    • ScholarWorks@UMBC
    • UMBC Interdepartmental Collections
    • UMBC Theses and Dissertations
    • View Item
    •   Maryland Shared Open Access Repository Home
    • ScholarWorks@UMBC
    • UMBC Interdepartmental Collections
    • UMBC Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Topics in Structured Convex Optimization and Nonlinear Programming

    Thumbnail
    Files
    75.pdf (549.7Kb)
    Permanent Link
    http://hdl.handle.net/11603/1030
    Collections
    • UMBC Graduate School
    • UMBC Mathematics and Statistics Department
    • UMBC Student Collection
    • UMBC Theses and Dissertations
    Metadata
    Show full item record
    Author/Creator
    Shevchenko, Olena
    Date
    2007-07-12
    Type of Work
    application/pdf
    Text
    dissertations
    Department
    Mathematics and Statistics
    Program
    Mathematics, Applied
    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.
    Subjects
    Mathematics (0405)
    Operations Research (0796)
    interior-point methods
    homogeneous programming
    homogeneos cones
    hyperbolicity cones
    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.


    Albin O. Kuhn Library & Gallery
    University of Maryland, Baltimore County
    1000 Hilltop Circle
    Baltimore, MD 21250
    www.umbc.edu/scholarworks

    Contact information:
    Email: scholarworks-group@umbc.edu
    Phone: 410-455-3544


    If you wish to submit a copyright complaint or withdrawal request, please email mdsoar-help@umd.edu.

     

     

    My Account

    LoginRegister

    Browse

    This CollectionBy Issue DateTitlesAuthorsSubjectsType

    Statistics

    View Usage Statistics


    Albin O. Kuhn Library & Gallery
    University of Maryland, Baltimore County
    1000 Hilltop Circle
    Baltimore, MD 21250
    www.umbc.edu/scholarworks

    Contact information:
    Email: scholarworks-group@umbc.edu
    Phone: 410-455-3544


    If you wish to submit a copyright complaint or withdrawal request, please email mdsoar-help@umd.edu.