Inthispaper, weproposetwonewmultiple-setssplitfeasibilityproblem(MSFP)models, where the MSFP requires to find a point closest to the intersection of a family of closed convex sets in one space, such that its image under a linear transformation will be closest to the intersection of another family of closed convex sets in the image space. This problem arises in image restoration, … Read more
For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more
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
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 present algebraic multilevel preconditioners for linear systems arising from the discretization of systems of coupled elliptic partial differential equations (PDEs). These preconditioners are based on modifications of Schwarz methods and of the smoothed aggregation technique, where the coarsening strategy and the restriction and prolongation operators are defined using a point-based approach with a primary … Read more
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. GRASP heuristics are multistart procedures which apply local search to a set of starting solutions generated with a randomized greedy algorithm or semi-greedy method. The best local optimum found over the iterations is returned as the heuristic solution. Path-relinking is a search … Read more
Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented *without … Read more
This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or the max-norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the … Read more
We present a scalable approach and implementation for solving stochastic programming problems, with application to the optimization of complex energy systems under uncertainty. Stochastic programming is used to make decisions in the present while incorporating a model of uncertainty about future events (scenarios). These problems present serious computational difficulties as the number of scenarios becomes … Read more
Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work we present the distributed mini-batch algorithm, a method … Read more