In this paper we consider sparse approximation problems, that is, general $l_0$ minimization problems with the $l_0$-“norm” of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of … Read more
G. P. McCormick [Math Prog 1976] provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form F(f(z)), where F is a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions F, and theory for the propagation of subgradients is presented. … Read more
Let B be the set of n-dimensional binary vectors and let V be a subset of m of its elements. We give an extended formulation of the convex hull of B\V which is polynomial in n and m. In developing this result, we give a two-sided extension of a result in Laurent and Sassano (1992) … Read more
Given a closed cone C in the Euclidean n-space, the completely positive cone of C is the convex cone K generated by matrices of the form uu^T as u varies over C. Examples of completely positive cones include the positive semidefinite cone (when C is the entire Euclidean n-space) and the cone of completely positive … Read more
We will derive two main results related to the primal simplex method for an LP on a 0-1 polytope. One of the results is that, for any 0-1 polytope and any two vertices of it, there exists an LP instance for which the simplex method finds a path between them, whose length is at most … Read more
We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of … Read more
In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a … Read more
The approximation of stochastic processes by trees is an important topic in multistage stochastic programming. In this paper we focus on improving the approximation of large trees by smaller (tractable) trees. The quality of the approximation is measured by the nested distance, recently introduced in [Pflug]. The nested distance is derived from the Wasserstein distance. … Read more
We prove that uniform second order growth, tilt stability, and strong metric regularity of the subdifferential — three notions that have appeared in entirely different settings — are all essentially equivalent for any lower-semicontinuous, extended-real-valued function. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. May 2012.ArticleDownload … Read more
We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. In order to improve the performance of mixed-integer programming (MIP) based schemes for these problems, we introduce and analyze a … Read more