Convex and Nonsmooth Optimization

On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more

    Computational acceleration of projection algorithms for the linear best approximation problem

  • Yair Censor
    • Categories Convex Optimization

    This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches … Read more

    Fast Moreau Envelope Computation I: Numerical Algorithms

  • Yves Lucet
    • Categories Convex Optimization, Nonsmooth Optimization, Problem Solving Environments Tags , , , , , ,

    The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, … Read more

    On Khachiyan’s Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids

  • Michael J. Todd
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , , ,

    Given $\cA := \{a^1,\ldots,a^m\} \subset \R^d$ whose affine hull is $\R^d$, we study the problems of computing an approximate rounding of the convex hull of $\cA$ and an approximation to the minimum volume enclosing ellipsoid of $\cA$. In the case of centrally symmetric sets, we first establish that Khachiyan’s barycentric coordinate descent (BCD) method is … Read more

    Sparse Covariance Selection via Robust Maximum Likelihood Estimation

  • Onureena Banerjeee
  • Alexandre d'Aspremont
  • Laurent El Ghaoui
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , ,

    We address a problem of covariance selection, where we seek a trade-off between a high likelihood against the number of non-zero elements in the inverse covariance matrix. We solve a maximum likelihood problem with a penalty term given by the sum of absolute values of the elements of the inverse covariance matrix, and allow for … Read more

    Analyticity of weighted central path and error bound for semidefinite programming

  • Chek Beng Chua
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary … Read more

    Constructing Generalized Mean Functions Using Convex Functions with Regularity Conditions

  • S.C. Fang
  • Duan Li
  • Yun-Bin Zhao
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , , ,

    The generalized mean function has been widely used in convex analysis and mathematical programming. This paper studies a further generalization of such a function. A necessary and sufficient condition is obtained for the convexity of a generalized function. Additional sufficient conditions that can be easily checked are derived for the purpose of identifying some classes … Read more

    Computing Proximal Points on Nonconvex Functions

  • Warren Hare
  • Claudia Sagastizábal
    • Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

    The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with … Read more

    An analytic center cutting plane approach for conic programming

  • Vasile L. Basescu
  • John E. Mitchell
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We analyze the problem of finding a point strictly interior to a bounded, fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the LP, SDP and SOCP cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number … Read more

    A Dual Optimization Approach to Inverse Quadratic Eigenvalue Problems with Partial Eigenstructure

  • Zheng-Jian Bai
  • Defeng Sun
  • Delin Chu
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags ,

    The inverse quadratic eigenvalue problem (IQEP) arises in the field of structural dynamics. It aims to find three symmetric matrices, known as the mass, the damping and the stiffness matrices, respectively such that they are closest to the given analytical matrices and satisfy the measured data. The difficulty of this problem lies in the fact … Read more