Stephen Boyd The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well-known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive … Read more
We consider the problem of estimating a sparse signal from a set of quantized, Gaussian noise corrupted measurements, where each measurement corresponds to an interval of values. We give two methods for (approximately) solving this problem, each based on minimizing a differentiable convex function plus an l1 regularization term. Using a first order method developed … Read more
We consider a general worst-case robust convex optimization problem, with arbitrary dependence on the uncertain parameters, which are assumed to lie in some given set of possible values. We describe a general method for solving such a problem, which alternates between optimization and worst-case analysis. With exact worst-case analysis, the method is shown to converge … Read more
Mean-variance (MV) analysis is often sensitive to model mis-specification or uncertainty, meaning that the MV efficient portfolios constructed with an estimate of the model parameters (i.e., the expected return vector and covariance of asset returns) can give very poor performance for another set of parameters that is similar and statistically hard to distinguish from the … Read more
This paper concerns a fractional function of the form $x^Ta/\sqrt{x^TBx}$, where $B$ is positive definite. We consider the game of choosing $x$ from a convex set, to maximize the function, and choosing $(a,B)$ from a convex set, to minimize it. We prove the existence of a saddle point and describe an efficient method, based on … Read more
We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP), or a second-order cone problem (SOCP), and so … 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 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. Citation … 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