This paper describes a new approach for computing nonnegative matrix factorizations (NMFs) with linear programming. The key idea is a data-driven model for the factorization, in which the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that … Read more
In this paper, we consider the solution of the standard linear programming (LP). A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The … Read more
We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal … Read more
We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new … Read more
When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented … Read more
Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users … Read more
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
In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a certain convex polyhedral objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized simplex method. (Regularization is performed in the dual space and … Read more
In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more
Kitahara and Mizuno (2011a) obtained an upper bound for the number of different solutions generated by the primal simplex method with Dantzig’s (the most negative) pivoting rule. In this paper, we obtain an upper bound with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. The bound is … Read more