This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds 1 and s ≥ 1, so that the overall finishing time, i.e. the makespan, is earliest possible. We consider a semi- online variant introduced (for equal speeds) by Azar and Regev, where the jobs are … Read more
Natural image statistics indicate that we should use non-convex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge of optimization. Recently, iteratively reweighed $\ell_1$ minimization (IRL1) has been proposed as a way to tackle a class of non-convex functions by solving a … Read more
In this paper, we analyze the convergence of Alternating Direction Method of Multipliers (ADMM) on convex quadratic programs (QPs) with linear equality and bound constraints. The ADMM formulation alternates between an equality constrained QP and a projection on the bounds. Under the assumptions of: (i) positive definiteness of the Hessian of the objective projected on … Read more
We present a method for computing lower bounds in the Progressive Hedging Algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using … Read more
In this paper, we present a unified framework for decision making under uncertainty. Our framework is based on the composite of two risk measures, where the inner risk measure accounts for the risk of decision given the exact distribution of uncertain model parameters, and the outer risk measure quantifies the risk that occurs when estimating … Read more
This paper shows that the optimal subgradient algorithm, OSGA, proposed in \cite{NeuO} can be used for solving structured large-scale convex constrained optimization problems. Only first-order information is required, and the optimal complexity bounds for both smooth and nonsmooth problems are attained. More specifically, we consider two classes of problems: (i) a convex objective with a … Read more
This paper shows that the OSGA algorithm — which uses first-order information to solve convex optimization problems with optimal complexity — can be used to efficiently solve arbitrary bound-constrained convex optimization problems. This is done by constructing an explicit method as well as an inexact scheme for solving the bound-constrained rational subproblem required by OSGA. … Read more
Until now it has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm with its combinatorial nature does not even offer a polynomial bound, whereas the complexity of the polynomial algorithms by Khachiyan and Karmarkar is based on the number of variables n, and … Read more
Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost-effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time, i.e., the carrier must solve a Service Network Design problem. Most service network design models rely on discretization of time, i.e., instead of determining the exact … Read more
We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to … Read more