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

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

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

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

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

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

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

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