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. Citation … Read more
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 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
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
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
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
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
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
In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a … Read more