The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of “rank-sparsity incoherence” to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a … Read more
In the paper, we describe various applications of the closedness and duality theorems of [7] and [8]. First, the strong separability of a polyhedron and a linear image of a convex set is characterized. Then,it is shown how stability conditions (known from the generalized Fenchel-Rockafellar duality theory) can be reformulated as closedness conditions. Finally, we … Read more
We use smoothing techniques to solve approximately mildly structured semidefinite programs with many constraints. As smoothing techniques require a specific problem format, we introduce an alternative problem formulation that fulfills the structural assumptions. The resulting algorithm has a complexity that depends linearly both on the number of constraints and on the inverse of the accuracy. … Read more
This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular … Read more
We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods, and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization, and a new piecewise linear approximation method for convex single commodity network flow … Read more
We propose a Newton-CG primal proximal point algorithm for solving large scale log-determinant optimization problems. Our algorithm employs the essential ideas of the proximal point algorithm, the Newton method and the preconditioned conjugate gradient solver. When applying the Newton method to solve the inner sub-problem, we find that the log-determinant term plays the role of … Read more
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
Developing first order optimality conditions for a two-stage stochastic mathematical program with equilibrium constraints (SMPEC) whose second stage problem has multiple equilibria/solutions is a challenging undone work. In this paper we take this challenge by considering a general class of two-stage whose equilibrium constraints are represented by a parametric variational inequality (where the first stage … Read more
We present a novel sparse signal reconstruction method “ISD”, aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical l_1 minimization approach. ISD addresses failed reconstructions of l_1 minimization due to insufficient measurements. It estimates a support set I from a current reconstruction and obtains a new … Read more
In this paper, we apply the quadratic penalization technique to derive strong Lagrangian duality property for an inequality constrained invex program. Our results extend and improve the corresponding results in the literature. CitationBazara, M. S. and Shetty, C. M., Nonlinear Programming Theory and Algorithms, John Wiley \& Sons, New York, 1979. Ben-Israel, A. and Mond, … Read more