BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Stephen Boyd

Stephen Boyd appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCMachine Learningq-fin.PMq-fin.CPphysics.opticsSystems and ControlMethodologyphysics.comp-phApplicationsArtificial IntelligenceDistributed, Parallel, and Cluster Computingeess.SPeess.SYMathematical Softwarephysics.med-phq-fin.TRComputationComputational Engineering, Finance, and ScienceData Structures and AlgorithmsInformation Theorymath.CAmath.ITmath.STQuantitative MethodsRoboticsSocial and Information NetworksStatistics Theory

Catalog footprint

What is connected

58works
27topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

58 published item(s)

preprint2024arXiv

Fast Path Planning Through Large Collections of Safe Boxes

We present a fast algorithm for the design of smooth paths (or trajectories) that are constrained to lie in a collection of axis-aligned boxes. We consider the case where the number of these safe boxes is large, and basic preprocessing of them (such as finding their intersections) can be done offline. At runtime we quickly generate a smooth path between given initial and terminal positions. Our algorithm designs trajectories that are guaranteed to be safe at all times, and detects infeasibility whenever such a trajectory does not exist. Our algorithm is based on two subproblems that we can solve very efficiently: finding a shortest path in a weighted graph, and solving (multiple) convex optimal-control problems. We demonstrate the proposed path planner on large-scale numerical examples, and we provide an efficient open-source software implementation, fastpathplanning.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Light-Weight Multi-Objective Asynchronous Hyper-Parameter Optimizer

We describe a light-weight yet performant system for hyper-parameter optimization that approximately minimizes an overall scalar cost function that is obtained by combining multiple performance objectives using a target-priority-limit scalarizer. It also supports a trade-off mode, where the goal is to find an appropriate trade-off among objectives by interacting with the user. We focus on the common scenario where there are on the order of tens of hyper-parameters, each with various attributes such as a range of continuous values, or a finite list of values, and whether it should be treated on a linear or logarithmic scale. The system supports multiple asynchronous simulations and is robust to simulation stragglers and failures.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Confidence bands for a log-concave density

We present a new approach for inference about a log-concave distribution: Instead of using the method of maximum likelihood, we propose to incorporate the log-concavity constraint in an appropriate nonparametric confidence set for the cdf $F$. This approach has the advantage that it automatically provides a measure of statistical uncertainty and it thus overcomes a marked limitation of the maximum likelihood estimate. In particular, we show how to construct confidence bands for the density that have a finite sample guaranteed confidence level. The nonparametric confidence set for $F$ which we introduce here has attractive computational and statistical properties: It allows to bring modern tools from optimization to bear on this problem via difference of convex programming, and it results in optimal statistical inference. We show that the width of the resulting confidence bands converges at nearly the parametric $n^{-\frac{1}{2}}$ rate when the log density is $k$-affine.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Embedded Code Generation with CVXPY

We introduce CVXPYgen, a tool for generating custom C code, suitable for embedded applications, that solves a parametrized class of convex optimization problems. CVXPYgen is based on CVXPY, a Python-embedded domain-specific language that supports a natural syntax (that follows the mathematical description) for specifying convex optimization problems. Along with the C implementation of a custom solver, CVXPYgen creates a Python wrapper for prototyping and desktop (non-embedded) applications. We give two examples, position control of a quadcopter and back-testing a portfolio optimization model. CVXPYgen outperforms a state-of-the-art code generation tool in terms of problem size it can handle, binary code size, and solve times. CVXPYgen and the generated solvers are open-source.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Operator Splitting for Adaptive Radiation Therapy with Nonlinear Health Dynamics

We present an optimization-based approach to radiation treatment planning over time. Our approach formulates treatment planning as an optimal control problem with nonlinear patient health dynamics derived from the standard linear-quadratic cell survival model. As the formulation is nonconvex, we propose a method for obtaining an approximate solution by solving a sequence of convex optimization problems. This method is fast, efficient, and robust to model error, adapting readily to changes in the patient's health between treatment sessions. Moreover, we show that it can be combined with the operator splitting method ADMM to produce an algorithm that is highly scalable and can handle large clinical cases. We introduce an open-source Python implementation of our algorithm, AdaRad, and demonstrate its performance on several examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Routing for Constant Function Market Makers

We consider the problem of optimally executing an order involving multiple crypto-assets, sometimes called tokens, on a network of multiple constant function market makers (CFMMs). When we ignore the fixed cost associated with executing an order on a CFMM, this optimal routing problem can be cast as a convex optimization problem, which is computationally tractable. When we include the fixed costs, the optimal routing problem is a mixed-integer convex problem, which can be solved using (sometimes slow) global optimization methods, or approximately solved using various heuristics based on convex optimization. The optimal routing problem includes as a special case the problem of identifying an arbitrage present in a network of CFMMs, or certifying that none exists.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Portfolio Construction as Linearly Constrained Separable Optimization

Mean-variance portfolio optimization problems often involve separable nonconvex terms, including penalties on capital gains, integer share constraints, and minimum position and trade sizes. We propose a heuristic algorithm for such problems based on the alternating direction method of multipliers (ADMM). This method allows for solve times in tens to hundreds of milliseconds with around 1000 securities and 100 risk factors. We also obtain a bound on the achievable performance. Our heuristic and bound are both derived from similar results for other optimization problems with a separable objective and affine equality constraints. We discuss a concrete implementation in the case where the separable terms in the objective are piecewise quadratic, and we empirically demonstrate its effectiveness for tax-aware portfolio construction.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Portfolio Construction with Gaussian Mixture Returns and Exponential Utility via Convex Optimization

We consider the problem of choosing an optimal portfolio, assuming the asset returns have a Gaussian mixture (GM) distribution, with the objective of maximizing expected exponential utility. In this paper we show that this problem is convex, and readily solved exactly using domain-specific languages for convex optimization, without the need for sampling or scenarios. We then show how the closely related problem of minimizing entropic value at risk can also be formulated as a convex optimization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Strategic Asset Allocation with Illiquid Alternatives

We address the problem of strategic asset allocation (SAA) with portfolios that include illiquid alternative asset classes. The main challenge in portfolio construction with illiquid asset classes is that we do not have direct control over our positions, as we do in liquid asset classes. Instead we can only make commitments; the position builds up over time as capital calls come in, and reduces over time as distributions occur, neither of which the investor has direct control over. The effect on positions of our commitments is subject to a delay, typically of a few years, and is also unknown or stochastic. A further challenge is the requirement that we can meet the capital calls, with very high probability, with our liquid assets. We formulate the illiquid dynamics as a random linear system, and propose a convex optimization based model predictive control (MPC) policy for allocating liquid assets and making new illiquid commitments in each period. Despite the challenges of time delay and uncertainty, we show that this policy attains performance surprisingly close to a fictional setting where we pretend the illiquid asset classes are completely liquid, and we can arbitrarily and immediately adjust our positions. In this paper we focus on the growth problem, with no external liabilities or income, but the method is readily extended to handle this case.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Certainty Equivalent Merton Problem

The Merton problem is the well-known stochastic control problem of choosing consumption over time, as well as an investment mix, to maximize expected constant relative risk aversion (CRRA) utility of consumption. Merton formulated the problem and provided an analytical solution in 1970; since then a number of extensions of the original formulation have been solved. In this note we identify a certainty equivalent problem, i.e., a deterministic optimal control problem with the same optimal value function and optimal policy, for the base Merton problem, as well as a number of extensions. When time is discretized, the certainty equivalent problem becomes a second-order cone program (SOCP), readily formulated and solved using domain specific languages for convex optimization. This makes it a good starting point for model predictive control, a policy that can handle extensions that are either too cumbersome or impossible to handle exactly using standard dynamic programming methods.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Covariance Prediction via Convex Optimization

We consider the problem of predicting the covariance of a zero mean Gaussian vector, based on another feature vector. We describe a covariance predictor that has the form of a generalized linear model, i.e., an affine function of the features followed by an inverse link function that maps vectors to symmetric positive definite matrices. The log-likelihood is a concave function of the predictor parameters, so fitting the predictor involves convex optimization. Such predictors can be combined with others, or recursively applied to improve performance.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Heuristic Methods and Performance Bounds for Photonic Design

In the photonic design problem, a scientist or engineer chooses the physical parameters of a device to best match some desired device behavior. Many instances of the photonic design problem can be naturally stated as a mathematical optimization problem that is computationally difficult to solve globally. Because of this, several heuristic methods have been developed to approximately solve such problems. These methods often produce very good designs, and, in many practical applications, easily outperform 'traditional' designs that rely on human intuition. Yet, because these heuristic methods do not guarantee that the approximate solution found is globally optimal, the question remains of just how much better a designer might hope to do. This question is addressed by performance bounds or impossibility results, which determine a performance level that no design can achieve. We focus on algorithmic performance bounds, which involve substantial computation to determine. We illustrate a variety of both heuristic methods and performance bounds on two examples. In these examples (and many others not reported here) the performance bounds show that the heuristic designs are nearly optimal, and can considered globally optimal in practice. This review serves to clearly set up the photonic design problem and unify existing approaches for calculating performance bounds, while also providing some natural generalizations and properties.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Low Rank Forecasting

We consider the problem of forecasting multiple values of the future of a vector time series, using some past values. This problem, and related ones such as one-step-ahead prediction, have a very long history, and there are a number of well-known methods for it, including vector auto-regressive models, state-space methods, multi-task regression, and others. Our focus is on low rank forecasters, which break forecasting up into two steps: estimating a vector that can be interpreted as a latent state, given the past, and then estimating the future values of the time series, given the latent state estimate. We introduce the concept of forecast consistency, which means that the estimates of the same value made at different times are consistent. We formulate the forecasting problem in general form, and focus on linear forecasters, for which we propose a formulation that can be solved via convex optimization. We describe a number of extensions and variations, including nonlinear forecasters, data weighting, the inclusion of auxiliary data, and additional objective terms. We illustrate our methods with several examples.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Pareto Optimal Projection Search (POPS): Automated Radiation Therapy Treatment Planning by Direct Search of the Pareto Surface

Objective: Radiation therapy treatment planning is a time-consuming, iterative process with potentially high inter-planner variability. Fully automated treatment planning processes could reduce a planner's active treatment planning time and remove inter-planner variability, with the potential to tremendously improve patient turnover and quality of care. In developing fully automated algorithms for treatment planning, we have two main objectives: to produce plans that are 1) Pareto optimal and 2) clinically acceptable. Here, we propose the Pareto optimal projection search (POPS) algorithm, which provides a general framework for directly searching the Pareto front. Methods: Our POPS algorithm is a novel automated planning method that combines two main search processes: 1) gradient-free search in the decision variable space and 2) projection of decision variables to the Pareto front using the bisection method. We demonstrate the performance of POPS by comparing with clinical treatment plans. As one possible quantitative measure of treatment plan quality, we construct a clinical acceptability scoring function (SF) modified from the previously developed general evaluation metric (GEM). Results: On a dataset of 21 prostate cases collected as part of clinical workflow, our proposed POPS algorithm produces Pareto optimal plans that are clinically acceptable in regards to dose conformity, dose homogeneity, and sparing of organs-at-risk. Conclusion: Our proposed POPS algorithm provides a general framework for fully automated treatment planning that achieves clinically acceptable dosimetric quality without requiring active planning from human planners. Significance: Our fully automated POPS algorithm addresses many key limitations of other automated planning approaches, and we anticipate that it will substantially improve treatment planning workflow.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Portfolio Construction Using Stratified Models

In this paper we develop models of asset return mean and covariance that depend on some observable market conditions, and use these to construct a trading policy that depends on these conditions, and the current portfolio holdings. After discretizing the market conditions, we fit Laplacian regularized stratified models for the return mean and covariance. These models have a different mean and covariance for each market condition, but are regularized so that nearby market conditions have similar models. This technique allows us to fit models for market conditions that have not occurred in the training data, by borrowing strength from nearby market conditions for which we do have data. These models are combined with a Markowitz-inspired optimization method to yield a trading policy that is based on market conditions. We illustrate our method on a small universe of 18 ETFs, using three well known and publicly available market variables to construct 1000 market conditions, and show that it performs well out of sample. The method, however, is general, and scales to much larger problems, that presumably would use proprietary data sources and forecasts along with publicly available data.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Portfolio Performance Attribution via Shapley Value

We consider an investment process that includes a number of features, each of which can be active or inactive. Our goal is to attribute or decompose an achieved performance to each of these features, plus a baseline value. There are many ways to do this, which lead to potentially different attributions in any specific case. We argue that a specific attribution method due to Shapley is the preferred method, and discuss methods that can be used to compute this attribution exactly, or when that is not practical, approximately.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Tax-Aware Portfolio Construction via Convex Optimization

We describe an optimization-based tax-aware portfolio construction method that adds tax liability to standard Markowitz-based portfolio construction. Our method produces a trade list that specifies the number of shares to buy of each asset and the number of shares to sell from each tax lot held. To avoid wash sales (in which some realized capital losses are disallowed), we assume that we trade monthly, and cannot simultaneously buy and sell the same asset. The tax-aware portfolio construction problem is not convex, but it becomes convex when we specify, for each asset, whether we buy or sell it. It can be solved using standard mixed-integer convex optimization methods at the cost of very long solve times for some problem instances. We present a custom convex relaxation of the problem that borrows curvature from the risk model. This relaxation can provide a good approximation of the true tax liability, while greatly enhancing computational tractability. This method requires the solution of only two convex optimization problems: the first determines whether we buy or sell each asset, and the second generates the final trade list. In our numerical experiments, our method almost always solves the nonconvex problem to optimality, and when it does not, it produces a trade list very close to optimal. Backtests show that the performance of our method is indistinguishable from that obtained using a globally optimal solution, but with significantly reduced computational effort.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A New Heuristic for Physical Design

In a physical design problem, the designer chooses values of some physical parameters, within limits, to optimize the resulting field. We focus on the specific case in which each physical design parameter is the ratio of two field variables. This form occurs for photonic design with real scalar fields, diffusion-type systems, and others. We show that such problems can be reduced to a convex optimization problem, and therefore efficiently solved globally, given the sign of an optimal field at every point. This observation suggests a heuristic, in which the signs of the field are iteratively updated. This heuristic appears to have good practical performance on diffusion-type problems (including thermal design and resistive circuit design) and some control problems, while exhibiting moderate performance on photonic design problems. We also show in many practical cases there exist globally optimal designs whose design parameters are maximized or minimized at each point in the domain, i.e., that there is a discrete globally optimal structure.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Automatic Repair of Convex Optimization Problems

Given an infeasible, unbounded, or pathological convex optimization problem, a natural question to ask is: what is the smallest change we can make to the problem's parameters such that the problem becomes solvable? In this paper, we address this question by posing it as an optimization problem involving the minimization of a convex regularization function of the parameters, subject to the constraint that the parameters result in a solvable problem. We propose a heuristic for approximately solving this problem that is based on the penalty method and leverages recently developed methods that can efficiently evaluate the derivative of the solution of a convex cone program with respect to its parameters. We illustrate our method by applying it to examples in optimal control and economics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Convex Optimization Over Risk-Neutral Probabilities

We consider a collection of derivatives that depend on the price of an underlying asset at expiration or maturity. The absence of arbitrage is equivalent to the existence of a risk-neutral probability distribution on the price; in particular, any risk neutral distribution can be interpreted as a certificate establishing that no arbitrage exists. We are interested in the case when there are multiple risk-neutral probabilities. We describe a number of convex optimization problems over the convex set of risk neutral price probabilities. These include computation of bounds on the cumulative distribution, VaR, CVaR, and other quantities, over the set of risk-neutral probabilities. After discretizing the underlying price, these problems become finite dimensional convex or quasiconvex optimization problems, and therefore are tractable. We illustrate our approach using real options and futures pricing data for the S&P 500 index and Bitcoin.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

CVXR: An R Package for Disciplined Convex Optimization

CVXR is an R package that provides an object-oriented modeling language for convex optimization, similar to CVX, CVXPY, YALMIP, and Convex.jl. It allows the user to formulate convex optimization problems in a natural mathematical syntax rather than the restrictive form required by most solvers. The user specifies an objective and set of constraints by combining constants, variables, and parameters using a library of functions with known mathematical properties. CVXR then applies signed disciplined convex programming (DCP) to verify the problem's convexity. Once verified, the problem is converted into standard conic form using graph implementations and passed to a cone solver such as ECOS or SCS. We demonstrate CVXR's modeling framework with several applications.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Differentiating Through a Cone Program

We consider the problem of efficiently computing the derivative of the solution map of a convex cone program, when it exists. We do this by implicitly differentiating the residual map for its homogeneous self-dual embedding, and solving the linear systems of equations required using an iterative method. This allows us to efficiently compute the derivative operator, and its adjoint, evaluated at a vector. These correspond to computing an approximate new solution, given a perturbation to the cone program coefficients (i.e., perturbation analysis), and to computing the gradient of a function of the solution with respect to the coefficients. Our method scales to large problems, with numbers of coefficients in the millions. We present an open-source Python implementation of our method that solves a cone program and returns the derivative and its adjoint as abstract linear maps; our implementation can be easily integrated into software systems for automatic differentiation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Differentiating through Log-Log Convex Programs

We show how to efficiently compute the derivative (when it exists) of the solution map of log-log convex programs (LLCPs). These are nonconvex, nonsmooth optimization problems with positive variables that become convex when the variables, objective functions, and constraint functions are replaced with their logs. We focus specifically on LLCPs generated by disciplined geometric programming, a grammar consisting of a set of atomic functions with known log-log curvature and a composition rule for combining them. We represent a parametrized LLCP as the composition of a smooth transformation of parameters, a convex optimization problem, and an exponential transformation of the convex optimization problem's solution. The derivative of this composition can be computed efficiently, using recently developed methods for differentiating through convex optimization problems. We implement our method in CVXPY, a Python-embedded modeling language and rewriting system for convex optimization. In just a few lines of code, a user can specify a parametrized LLCP, solve it, and evaluate the derivative or its adjoint at a vector. This makes it possible to conduct sensitivity analyses of solutions, given perturbations to the parameters, and to compute the gradient of a function of the solution with respect to the parameters. We use the adjoint of the derivative to implement differentiable log-log convex optimization layers in PyTorch and TensorFlow. Finally, we present applications to designing queuing systems and fitting structured prediction models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Disciplined Quasiconvex Programming

We present a composition rule involving quasiconvex functions that generalizes the classical composition rule for convex functions. This rule complements well-known rules for the curvature of quasiconvex functions under increasing functions and pointwise maximums. We refer to the class of optimization problems generated by these rules, along with a base set of quasiconvex and quasiconcave functions, as disciplined quasiconvex programs. Disciplined quasiconvex programming generalizes disciplined convex programming, the class of optimization problems targeted by most modern domain-specific languages for convex optimization. We describe an implementation of disciplined quasiconvex programming that makes it possible to specify and solve quasiconvex programs in CVXPY 1.0.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Eigen-Stratified Models

Stratified models depend in an arbitrary way on a selected categorical feature that takes $K$ values, and depend linearly on the other $n$ features. Laplacian regularization with respect to a graph on the feature values can greatly improve the performance of a stratified model, especially in the low-data regime. A significant issue with Laplacian-regularized stratified models is that the model is $K$ times the size of the base model, which can be quite large. We address this issue by formulating eigen-stratifed models, which are stratified models with an additional constraint that the model parameters are linear combinations of some modest number $m$ of bottom eigenvectors of the graph Laplacian, i.e., those associated with the $m$ smallest eigenvalues. With eigen-stratified models, we only need to store the $m$ bottom eigenvectors and the corresponding coefficients as the stratified model parameters. This leads to a reduction, sometimes large, of model size when $m \leq n$ and $m \ll K$. In some cases, the additional regularization implicit in eigen-stratified models can improve out-of-sample performance over standard Laplacian regularized stratified models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fitting a Linear Control Policy to Demonstrations with a Kalman Constraint

We consider the problem of learning a linear control policy for a linear dynamical system, from demonstrations of an expert regulating the system. The standard approach to this problem is policy fitting, which fits a linear policy by minimizing a loss function between the demonstrations and the policy's outputs plus a regularization function that encodes prior knowledge. Despite its simplicity, this method fails to learn policies with low or even finite cost when there are few demonstrations. We propose to add an additional constraint to policy fitting, that the policy is the solution to some LQR problem, i.e., optimal in the stochastic control sense for some choice of quadratic cost. We refer to this constraint as a Kalman constraint. Policy fitting with a Kalman constraint requires solving an optimization problem with convex cost and bilinear constraints. We propose a heuristic method, based on the alternating direction method of multipliers (ADMM), to approximately solve this problem. Numerical experiments demonstrate that adding the Kalman constraint allows us to learn good, i.e., low cost, policies even when very few data are available.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fitting Laplacian Regularized Stratified Gaussian Models

We consider the problem of jointly estimating multiple related zero-mean Gaussian distributions from data. We propose to jointly estimate these covariance matrices using Laplacian regularized stratified model fitting, which includes loss and regularization terms for each covariance matrix, and also a term that encourages the different covariances matrices to be close. This method `borrows strength' from the neighboring covariances, to improve its estimate. With well chosen hyper-parameters, such models can perform very well, especially in the low data regime. We propose a distributed method that scales to large problems, and illustrate the efficacy of the method with examples in finance, radar signal processing, and weather forecasting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fundamental bounds for scattering from absorptionless electromagnetic structures

The ability to design the scattering properties of electromagnetic structures is of fundamental interest in optical science and engineering. While there has been great practical success applying local optimization methods to electromagnetic device design, it is unclear whether the performance of resulting designs is close to that of the best possible design. This question remains unsettled for absorptionless electromagnetic devices since the absence of material loss makes it difficult to provide provable bounds on their scattering properties. We resolve this problem by providing non-trivial lower bounds on performance metrics that are convex functions of the scattered fields. Our bounding procedure relies on accounting for a constraint on the electric fields inside the device, which can be provably constructed for devices with small footprints or low dielectric constrast. We illustrate our bounding procedure by studying limits on the scattering cross-sections of dielectric and metallic particles in the absence of material losses.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning Convex Optimization Models

A convex optimization model predicts an output from an input by solving a convex optimization problem. The class of convex optimization models is large, and includes as special cases many well-known models like linear and logistic regression. We propose a heuristic for learning the parameters in a convex optimization model given a dataset of input-output pairs, using recently developed methods for differentiating the solution of a convex optimization problem with respect to its parameters. We describe three general classes of convex optimization models, maximum a posteriori (MAP) models, utility maximization models, and agent models, and present a numerical experiment for each.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multi-Period Liability Clearing via Convex Optimal Control

We consider the problem of determining a sequence of payments among a set of entities that clear (if possible) the liabilities among them. We formulate this as an optimal control problem, which is convex when the objective function is, and therefore readily solved. For this optimal control problem, we give a number of useful and interesting convex costs and constraints that can be combined in any way for different applications. We describe a number of extensions, for example to handle unknown changes in cash and liabilities, to allow bailouts, to find the minimum time to clear the liabilities, or to minimize the number of non-cleared liabilities, when fully clearing the liabilities is impossible.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal Representative Sample Weighting

We consider the problem of assigning weights to a set of samples or data records, with the goal of achieving a representative weighting, which happens when certain sample averages of the data are close to prescribed values. We frame the problem of finding representative sample weights as an optimization problem, which in many cases is convex and can be efficiently solved. Our formulation includes as a special case the selection of a fixed number of the samples, with equal weights, i.e., the problem of selecting a smaller representative subset of the samples. While this problem is combinatorial and not convex, heuristic methods based on convex optimization seem to perform very well. We describe rsw, an open-source implementation of the ideas described in this paper, and apply it to a skewed sample of the CDC BRFSS dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

OSQP: An Operator Splitting Solver for Quadratic Programs

We present a general-purpose solver for convex quadratic programs based on the alternating direction method of multipliers, employing a novel operator splitting technique that requires the solution of a quasi-definite linear system with the same coefficient matrix at almost every iteration. Our algorithm is very robust, placing no requirements on the problem data such as positive definiteness of the objective function or linear independence of the constraint functions. It can be configured to be division-free once an initial matrix factorization is carried out, making it suitable for real-time applications in embedded systems. In addition, our technique is the first operator splitting method for quadratic programs able to reliably detect primal and dual infeasible problems from the algorithm iterates. The method also supports factorization caching and warm starting, making it particularly efficient when solving parametrized problems arising in finance, control, and machine learning. Our open-source C implementation OSQP has a small footprint, is library-free, and has been extensively tested on many problem instances from a wide variety of application areas. It is typically ten times faster than competing interior-point methods, and sometimes much more when factorization caching or warm start is used. OSQP has already shown a large impact with tens of thousands of users both in academia and in large corporations.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Computational Bounds For Photonic Design

Physical design problems, such as photonic inverse design, are typically solved using local optimization methods. These methods often produce what appear to be good or very good designs when compared to classical design methods, but it is not known how far from optimal such designs really are. We address this issue by developing methods for computing a bound on the true optimal value of a physical design problem; physical designs with objective smaller than our bound are impossible to achieve. Our bound is based on Lagrange duality and exploits the special mathematical structure of these physical design problems. For a multi-mode 2D Helmholtz resonator, numerical examples show that the bounds we compute are often close to the objective values obtained using local optimization methods, which reveals that the designs are not only good, but in fact nearly optimal. Our computational bounding method also produces, as a by-product, a reasonable starting point for local optimization methods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A General System for Heuristic Solution of Convex Problems over Nonconvex Sets

We describe general heuristics to approximately solve a wide variety of problems with convex objective and decision variables from a nonconvex set. The heuristics, which employ convex relaxations, convex restrictions, local neighbor search methods, and the alternating direction method of multipliers (ADMM), require the solution of a modest number of convex problems, and are meant to apply to general problems, without much tuning. We describe an implementation of these methods in a package called NCVX, as an extension of CVXPY, a Python package for formulating and solving convex optimization problems. We study several examples of well known nonconvex problems, and show that our general purpose heuristics are effective in finding approximate solutions to a wide variety of problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A New Architecture for Optimization Modeling Frameworks

We propose a new architecture for optimization modeling frameworks in which solvers are expressed as computation graphs in a framework like TensorFlow rather than as standalone programs built on a low-level linear algebra interface. Our new architecture makes it easy for modeling frameworks to support high performance computational platforms like GPUs and distributed clusters, as well as to generate solvers specialized to individual problems. Our approach is particularly well adapted to first-order and indirect optimization algorithms. We introduce cvxflow, an open-source convex optimization modeling framework in Python based on the ideas in this paper, and show that it outperforms the state of the art.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bounding Duality Gap for Separable Problems with Linear Constraints

We consider the problem of minimizing a sum of non-convex functions over a compact domain, subject to linear inequality and equality constraints. Approximate solutions can be found by solving a convexified version of the problem, in which each function in the objective is replaced by its convex envelope. We propose a randomized algorithm to solve the convexified problem which finds an $ε$-suboptimal solution to the original problem. With probability one, $ε$ is bounded by a term proportional to the maximal number of active constraints in the problem. The bound does not depend on the number of variables in the problem or the number of terms in the objective. In contrast to previous related work, our proof is constructive, self-contained, and gives a bound that is tight.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Concave Quadratic Cuts for Mixed-Integer Quadratic Problems

The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice ${\bf Z}^n$, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding

We introduce a first order method for solving very large convex cone programs. The method uses an operator splitting method, the alternating directions method of multipliers, to solve the homogeneous self-dual embedding, an equivalent feasibility problem involving finding a nonzero point in the intersection of a subspace and a cone. This approach has several favorable properties. Compared to interior-point methods, first-order methods scale to very large problems, at the cost of requiring more time to reach very high accuracy. Compared to other first-order methods for cone programs, our approach finds both primal and dual solutions when available or a certificate of infeasibility or unboundedness otherwise, is parameter-free, and the per-iteration cost of the method is the same as applying a splitting method to the primal or dual alone. We discuss efficient implementation of the method in detail, including direct and indirect methods for computing projection onto the subspace, scaling the original problem data, and stopping criteria. We describe an open-source implementation, which handles the usual (symmetric) non-negative, second-order, and semidefinite cones as well as the (non-self-dual) exponential and power cones and their duals. We report numerical results that show speedups over interior-point cone solvers for large problems, and scaling to very large general cone programs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

CVXPY: A Python-Embedded Modeling Language for Convex Optimization

CVXPY is a domain-specific language for convex optimization embedded in Python. It allows the user to express convex optimization problems in a natural syntax that follows the math, rather than in the restrictive standard form required by solvers. CVXPY makes it easy to combine convex optimization with high-level features of Python such as parallelism and object-oriented design. CVXPY is available at http://www.cvxpy.org/ under the GPL license, along with documentation and examples.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Disciplined Convex-Concave Programming

In this paper we introduce disciplined convex-concave programming (DCCP), which combines the ideas of disciplined convex programming (DCP) with convex-concave programming (CCP). Convex-concave programming is an organized heuristic for solving nonconvex problems that involve objective and constraint functions that are a sum of a convex and a concave term. DCP is a structured way to define convex optimization problems, based on a family of basic convex and concave functions and a few rules for combining them. Problems expressed using DCP can be automatically converted to standard form and solved by a generic solver; widely used implementations include YALMIP, CVX, CVXPY, and Convex.jl. In this paper we propose a framework that combines the two ideas, and includes two improvements over previously published work on convex-concave programming, specifically the handling of domains of the functions, and the issue of nondifferentiability on the boundary of the domains. We describe a Python implementation called DCCP, which extends CVXPY, and give examples.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Disciplined Multi-Convex Programming

A multi-convex optimization problem is one in which the variables can be partitioned into sets over which the problem is convex when the other variables are fixed. Multi-convex problems are generally solved approximately using variations on alternating or cyclic minimization. Multi-convex problems arise in many applications, such as nonnegative matrix factorization, generalized low rank models, and structured control synthesis, to name just a few. In most applications to date the multi-convexity is simple to verify by hand. In this paper we study the automatic detection and verification of multi-convexity using the ideas of disciplined convex programming. We describe an implementation of our proposed method that detects and verifies multi-convexity, and then invokes one of the general solution methods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Line Search for Averaged Operator Iteration

Many popular first order algorithms for convex optimization, such as forward-backward splitting, Douglas-Rachford splitting, and the alternating direction method of multipliers (ADMM), can be formulated as averaged iteration of a nonexpansive mapping. In this paper we propose a line search for averaged iteration that preserves the theoretical convergence guarantee, while often accelerating practical convergence. We discuss several general cases in which the additional computational cost of the line search is modest compared to the savings obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Linear Programming Heuristics for the Graph Isomorphism Problem

An isomorphism between two graphs is a bijection between their vertices that preserves the edges. We consider the problem of determining whether two finite undirected weighted graphs are isomorphic, and finding an isomorphism relating them if the answer is positive. In this paper we introduce effective probabilistic linear programming (LP) heuristics to solve the graph isomorphism problem. We motivate our heuristics by showing guarantees under some conditions, and present numerical experiments that show effectiveness of these heuristics in the general case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Current Waveforms for Switched-Reluctance Motors

In this paper, we address the problem of finding current waveforms for a switched reluctance motor that minimize a user-defined combination of torque ripple and RMS current. The motor model we use is fairly general, and includes magnetic saturation, voltage and current limits, and highly coupled magnetics (and therefore, unconventional geometries and winding patterns). We solve this problem by approximating it as a mixed-integer convex program, which we solve globally using branch and bound. We demonstrate our approach on an experimentally verified model of a fully pitched switched reluctance motor, for which we find the globally optimal waveforms, even for high rotor speeds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Risk-Constrained Kelly Gambling

We consider the classic Kelly gambling problem with general distribution of outcomes, and an additional risk constraint that limits the probability of a drawdown of wealth to a given undesirable level. We develop a bound on the drawdown probability; using this bound instead of the original risk constraint yields a convex optimization problem that guarantees the drawdown risk constraint holds. Numerical experiments show that our bound on drawdown probability is reasonably close to the actual drawdown risk, as computed by Monte Carlo simulation. Our method is parametrized by a single parameter that has a natural interpretation as a risk-aversion parameter, allowing us to systematically trade off asymptotic growth rate and drawdown risk. Simulations show that this method yields bets that out perform fractional-Kelly bets for the same drawdown risk level or growth rate. Finally, we show that a natural quadratic approximation of our convex problem is closely connected to the classical mean-variance Markowitz portfolio selection problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Stochastic Matrix-Free Equilibration

We present a novel method for approximately equilibrating a matrix $A \in {\bf R}^{m \times n}$ using only multiplication by $A$ and $A^T$. Our method is based on convex optimization and projected stochastic gradient descent, using an unbiased estimate of a gradient obtained by a randomized method. Our method provably converges in expectation with an $O(1/t)$ convergence rate and empirically gets good results with a small number of iterations. We show how the method can be applied as a preconditioner for matrix-free iterative algorithms such as LSQR and Chambolle-Cremers-Pock, substantially reducing the iterations required to reach a given level of precision. We also derive a novel connection between equilibration and condition number, showing that equilibration minimizes an upper bound on the condition number over all choices of row and column scalings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights

We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming

In this paper we propose a fast optimization algorithm for approximately minimizing convex quadratic functions over the intersection of affine and separable constraints (i.e., the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimization problems. We discuss the favorable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we find that in many cases, it finds the global solution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generalized Low Rank Models

Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in data analysis, such as nonnegative matrix factorization, matrix completion, sparse and robust PCA, $k$-means, $k$-SVD, and maximum margin matrix factorization. The method handles heterogeneous data sets, and leads to coherent schemes for compressing, denoising, and imputing missing entries across all data types simultaneously. It also admits a number of interesting interpretations of the low rank factors, which allow clustering of examples or of features. We propose several parallel algorithms for fitting generalized low rank models, and describe implementations and numerical results.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Matrix-Free Convex Optimization Modeling

We introduce a convex optimization modeling framework that transforms a convex optimization problem expressed in a form natural and convenient for the user into an equivalent cone program in a way that preserves fast linear transforms in the original problem. By representing linear functions in the transformation process not as matrices, but as graphs that encode composition of linear operators, we arrive at a matrix-free cone program, i.e., one whose data matrix is represented by a linear operator and its adjoint. This cone program can then be solved by a matrix-free cone solver. By combining the matrix-free modeling framework and cone solver, we obtain a general method for efficiently solving convex optimization problems involving fast linear transforms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Network Lasso: Clustering and Optimization in Large Graphs

Convex optimization is an essential tool for modern data analysis, as it provides a framework to formulate and solve many problems in machine learning and data mining. However, general convex optimization solvers do not scale well, and scalable solvers are often specialized to only work on a narrow class of problems. Therefore, there is a need for simple, scalable algorithms that can solve many common optimization problems. In this paper, we introduce the \emph{network lasso}, a generalization of the group lasso to a network setting that allows for simultaneous clustering and optimization on graphs. We develop an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in a distributed and scalable manner, which allows for guaranteed global convergence even on large graphs. We also examine a non-convex extension of this approach. We then demonstrate that many types of problems can be expressed in our framework. We focus on three in particular - binary classification, predicting housing prices, and event detection in time series data - comparing the network lasso to baseline approaches and showing that it is both a fast and accurate method of solving large optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameter Selection and Pre-Conditioning for a Graph Form Solver

In a recent paper, Parikh and Boyd describe a method for solving a convex optimization problem, where each iteration involves evaluating a proximal operator and projection onto a subspace. In this paper we address the critical practical issues of how to select the proximal parameter in each iteration, and how to scale the original problem variables, so as the achieve reliable practical performance. The resulting method has been implemented as an open-source software package called POGS (Proximal Graph Solver), that targets multi-core and GPU-based systems, and has been tested on a wide variety of practical problems. Numerical results show that POGS can solve very large problems (with, say, more than a billion coefficients in the data), to modest accuracy in a few tens of seconds. As just one example, a radiation treatment planning problem with around 100 million coefficients in the data can be solved in a few seconds, as compared to around one hour with an interior-point method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Volume Weighted Average Price Optimal Execution

We study the problem of optimal execution of a trading order under Volume Weighted Average Price (VWAP) benchmark, from the point of view of a risk-averse broker. The problem consists in minimizing mean-variance of the slippage, with quadratic transaction costs. We devise multiple ways to solve it, in particular we study how to incorporate the information coming from the market during the schedule. Most related works in the literature eschew the issue of imperfect knowledge of the total market volume. We instead incorporate it in our model. We validate our method with extensive simulation of order execution on real NYSE market data. Our proposed solution, using a simple model for market volumes, reduces by 10% the VWAP deviation RMSE of the standard "static" solution (and can simultaneously reduce transaction costs).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Convex Optimization in Julia

This paper describes Convex, a convex optimization modeling framework in Julia. Convex translates problems from a user-friendly functional language into an abstract syntax tree describing the problem. This concise representation of the global structure of the problem allows Convex to infer whether the problem complies with the rules of disciplined convex programming (DCP), and to pass the problem to a suitable solver. These operations are carried out in Julia using multiple dispatch, which dramatically reduces the time required to verify DCP compliance and to parse a problem into conic form. Convex then automatically chooses an appropriate backend solver to solve the conic form problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An ADMM Algorithm for a Class of Total Variation Regularized Estimation Problems

We present an alternating augmented Lagrangian method for convex optimization problems where the cost function is the sum of two terms, one that is separable in the variable blocks, and a second that is separable in the difference between consecutive variable blocks. Examples of such problems include Fused Lasso estimation, total variation denoising, and multi-period portfolio optimization with transaction costs. In each iteration of our method, the first step involves separately optimizing over each variable block, which can be carried out in parallel. The second step is not separable in the variables, but can be carried out very efficiently. We apply the algorithm to segmentation of data based on changes inmean (l_1 mean filtering) or changes in variance (l_1 variance filtering). In a numerical example, we show that our implementation is around 10000 times faster compared with the generic optimization solver SDPT3.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Message Passing for Dynamic Network Energy Management

We consider a network of devices, such as generators, fixed loads, deferrable loads, and storage devices, each with its own dynamic constraints and objective, connected by lossy capacitated lines. The problem is to minimize the total network objective subject to the device and line constraints, over a given time horizon. This is a large optimization problem, with variables for consumption or generation in each time period for each device. In this paper we develop a decentralized method for solving this problem. The method is iterative: At each step, each device exchanges simple messages with its neighbors in the network and then solves its own optimization problem, minimizing its own objective function, augmented by a term determined by the messages it has received. We show that this message passing method converges to a solution when the device objective and constraints are convex. The method is completely decentralized, and needs no global coordination other than synchronizing iterations; the problems to be solved by each device can typically be solved extremely efficiently and in parallel. The method is fast enough that even a serial implementation can solve substantial problems in reasonable time frames. We report results for several numerical experiments, demonstrating the method's speed and scaling, including the solution of a problem instance with over 30 million variables in 52 minutes for a serial implementation; with decentralized computing, the solve time would be less than one second.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Distributed Large Scale Network Utility Maximization

Recent work by Zymnis et al. proposes an efficient primal-dual interior-point method, using a truncated Newton method, for solving the network utility maximization (NUM) problem. This method has shown superior performance relative to the traditional dual-decomposition approach. Other recent work by Bickson et al. shows how to compute efficiently and distributively the Newton step, which is the main computational bottleneck of the Newton method, utilizing the Gaussian belief propagation algorithm. In the current work, we combine both approaches to create an efficient distributed algorithm for solving the NUM problem. Unlike the work of Zymnis, which uses a centralized approach, our new algorithm is easily distributed. Using an empirical evaluation we show that our new method outperforms previous approaches, including the truncated Newton method and dual-decomposition methods. As an additional contribution, this is the first work that evaluates the performance of the Gaussian belief propagation algorithm vs. the preconditioned conjugate gradient method, for a large scale problem.

0 citations0 reviewsNo code linkedOpen access