strict complementarity

Dual-density-based reweighted $\ell_{1}hBcalgorithms for a class of $\ell_{0}hBcminimization problems

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

    The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $\ell_{1}$-algorithms for a class of $\ell_{0}$-minimization models which can be used to model a wide range of practical problems. This class of … Read more

    Strict Complementarity in MaxCut SDP

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    The MaxCut SDP is one of the most well-known semidefinite programs, and it has many favorable properties. One of its nicest geometric/duality properties is the fact that the vertices of its feasible region correspond exactly to the cuts of a graph, as proved by Laurent and Poljak in 1995. Recall that a boundary point x … Read more

    Constructing New Weighted l1-Algorithms for the Sparsest Points of Polyhedral Sets

  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Basic Sciences Applications, Convex and Nonsmooth Optimization Tags , , , , , ,

    The l0-minimization problem that seeks the sparsest point of a polyhedral set is a longstanding challenging problem in the fields of signal and image processing, numerical linear algebra and mathematical optimization. The weighted l1-method is one of the most plausible methods for solving this problem. In this paper, we develop a new weighted l1-method through … Read more

    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

    Generating and Measuring Instances of Hard Semidefinite Programs, SDP

  • Hua Wei
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

    Invariance and efficiency of convex representations

  • Chek Beng Chua
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    We consider two notions for the representations of convex cones: $G$-representation and lifted-$G$-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones … Read more

    Properties of the Log-Barrier Function on Degenerate Nonlinear Programs

  • Dominique Orban
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We examine the sequence of local minimizers of the log-barrier function for a nonlinear program near a solution at which second-order sufficient conditions and the Mangasarian-Fromovitz constraint qualifications are satisfied, but the active constraint gradients are not necessarily linearly independent. When a strict complementarity condition is satisfied, we show uniqueness of the local minimizer of … Read more