Yun-Bin Zhao

RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

    New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more

    Reweighted $\ell_1hBcMinimization for Sparse Solutions to Underdetermined Linear Systems

  • Duan Li
  • Yun-Bin Zhao
    • Categories Basic Sciences Applications, Linear Programming, Nonsmooth Optimization Tags , , , , ,

    Numerical experiments have indicated that the reweighted $\ell_1$-minimization performs exceptionally well in locating sparse solutions of underdetermined linear systems of equations. Thus it is important to carry out a further investigation of this class of methods. In this paper, we point out that reweighted $\ell_1$-methods are intrinsically associated with the minimization of the so-called merit … Read more

    Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations

  • Yun-Bin Zhao
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization … Read more

    Convexity Conditions of Kantorovich Function and Related Semi-infinite Linear Matrix Inequalities

  • Yun-Bin Zhao
    • Categories Convex Optimization, Robust Optimization, Semi-infinite Programming Tags , , , ,

    The Kantorovich function $(x^TAx)( x^T A^{-1} x)$, where $A$ is a positive definite matrix, is not convex in general. From a matrix or convex analysis point of view, it is interesting to address the question: When is this function convex? In this paper, we prove that the 2-dimensional Kantorovich function is convex if and only … Read more

    Convexity Conditions and the Legendre-Fenchel Transform for the Product of Finitely Many Positive Definite Quadratic Forms

  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    While the product of finitely many convex functions has been investigated in the field of global optimization, some fundamental issues such as the convexity condition and the Legendre-Fenchel transform for the product function remain unresolved. Focusing on quadratic forms, this paper is aimed at addressing the question: \emph{When is the product of finitely many positive … Read more

    The Legendre-Fenchel Conjugate of the Product of Two positive definite Quadratic Forms

  • Yun-Bin Zhao
    • Categories Convex Optimization Tags , , ,

    It is well-known that the Legendre-Fenchel conjugate of a positive definite quadratic form can be explicitly expressed as another positive definite quadratic form, and that the conjugate of the sum of several positive definite quadratic forms can be expressed via inf-convolution. However, the Legendre-Fenchel conjugate of the product of two positive definite quadratic forms is … Read more

    Explicit reformulations for robust optimization problems with general uncertainty sets

  • Igor Averbakh
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Robust Optimization Tags ,

    We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be equivalently reformulated as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty … Read more

    Geometric Dual Formulation for First-derivative-based Univariate Cubic $ Splines

  • S.C. Fang
  • Yun-Bin Zhao
  • J.E. Lavery
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    With the objective of generating “shape-preserving” smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based ${\cal C}^1$-smooth univariate cubic $L_1$ splines. An $L_1$ spline minimizes the $L_1$ norm of the difference between the first-order derivative of the spline and the local divided difference of … Read more

    Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

  • Yun-Bin Zhao
    • Categories Linear Programming Tags , , ,

    It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more