Convex Optimization

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

    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

    Generalization of the primal and dual affine scaling algorithms

  • F. G. M. Cunha
  • João Xavier da Cruz Neto
  • Paulo Roberto Oliveira
  • A. W. Martins Pinto
    • Categories Convex Optimization, Linear Programming

    We obtain a class of primal ane scaling algorithms which generalize some known algorithms. This class, depending on a r-parameter, is constructed through a family of metrics generated by ��r power, r  1, of the diagonal iterate vector matrix. We prove the so-called weak convergence of the primal class for nondegenerate linearly constrained convex … Read more

    Approximating K-means-type clustering via semidefinite programming

  • Jiming Peng
  • Yu Wei
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining Tags , , ,

    One of the fundamental clustering problems is to assign $n$ points into $k$ clusters based on the minimal sum-of-squares(MSSC), which is known to be NP-hard. In this paper, by using matrix arguments, we first model MSSC as a so-called 0-1 semidefinite programming (SDP). We show that our 0-1 SDP model provides an unified framework for … Read more