We consider a multi-period variation of the network utility maximization problem that includes delivery constraints. We allow the flow utilities, link capacities and routing matrices to vary over time, and we introduce the concept of delivery contracts, which couple the flow rates across time. We describe a distributed algorithm, based on dual decomposition, that solves … Read more
We describe graph implementations, a generic method for representing a convex function via its epigraph, described in a disciplined convex programming framework. This simple and natural idea allows a very wide variety of smooth and nonsmooth convex programs to be easily specified and efficiently solved, using interior-point methods for smooth or cone convex programs. CitationTo … Read more
We describe a specialized truncated-Newton primal-dual interior-point method that solves large scale network utility maximization problems, with concave utility functions, efficiently and reliably. Our method is not decentralized, but easily scales to problems with a million flows and links. We compare our method to a standard decentralized algorithm based on dual decomposition, and show by … Read more
The problem of estimating underlying trends in time series data arises in a variety of disciplines. In this paper we propose a variation on Hodrick-Prescott (H-P) filtering, a widely used method for trend estimation. The proposed l_1 trend filtering method substitutes a sum of absolute values (i.e., l_1-norm) for the sum of squares used in … Read more
We consider the problem of adjusting speeds of multiple computer processors sharing the same thermal environment, such as a chip or multi-chip package. We assume that the speed of processor (and associated variables, such as power supply voltage) can be controlled, and we model the dissipated power of a processor as a positive and strictly … Read more
An Adaptive Cubic Overestimation (ACO) algorithm for unconstrained optimization is proposed, generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, Univ. of Cambridge), an algorithm by Nesterov & Polyak (Math. Programming 108(1), 2006, pp 177-205) and a proposal by Weiser, Deuflhard & Erdmann (Optim. Methods Softw. 22(3), 2007, … Read more
It is known that quasi-Newton updates can be characterized by variational means, sometimes in more than one way. This paper has two main goals. We first formulate variational problems appearing in quasi-Newton methods within the space of symmetric matrices. This simplies both their formulations and their subsequent solutions. We then construct, for the first time, … Read more
The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more
In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte … Read more
We present a suite of tools for visualizing the status and progress of branch-and-bound algorithms for mixed integer programming. By integrating these tools with the open-source codes CBC, SYMPHONY, and GLPK, we demonstrate the potential usefulness of visual representations in helping a user predict future progress of the algorithm or analyzing the algorithm’s performance. We … Read more