We propose a novel asynchronous bundle method to solve distributed learning problems. Compared to existing asynchronous methods, our algorithm computes the next iterate based on a more accurate approximation of the objective function and does not require any prior information about the maximal information delay in the system. This makes the proposed method fast and easy to tune. We prove that the algorithm converges in both deterministic and stochastic (mini-batch) settings, and quantify how the convergence times depend on the level of asynchrony. The practical advantages of our method are illustrated through numerical experiments on classification problems of varying complexities and scales.

Convex quadratic optimization solvers are extensively utilized in various domains; however, achieving optimal performance in diverse situations remains a significant challenge due to the sparse nature of objective and constraint matrices. General-purpose architectures struggle with hardware utilization when performing critical sparse matrix operations, such as factorization and multiplication. To address this issue, we introduce a pipelined spatial architecture, Multi-Issue Butterfly (MIB), which supports all primitive scalar, vector, and matrix operations required by the Alternating Direction Method of Multipliers (ADMM) based solver algorithm. The proposed architecture features a butterfly computational network with innovative working modes for each node, controlled by runtime instructions. We developed a companion scheduling method for matrix operations based on their sparsity patterns. For factorization, an elimination tree guides the network instructions reordering to avoid data hazards caused by computation dependencies. For matrix-vector multiplication, data prefetching resolves structural hazards caused by read and write conflicts to register files. Instructions without hazards are issued simultaneously to increase pipeline throughput and function unit utilization. We evaluate the proposed architecture using FPGA prototypes, representing the first fully FPGA-based generic QP solver. Our assessment includes extensive performance and efficiency bench-marks across 100 QP problems from five application domains. Compared to the same algorithm variation running on CPU backends, our prototype achieves a geometric mean of$30.5\times$end-to-end speedup,$127.0 \times$greater energy efficiency, and$16.5\times$less runtime jitter. In comparison to GPU backends, the prototype attains a geometric mean of$4.3\times$faster end-to-end speedup,$21.7\times$higher energy efficiency, and$33.4\times$less runtime jitter.

We present a novel methodology for convex optimization algorithm design using ideas from electric RLC circuits. Given an optimization problem, the first stage of the methodology is to design an appropriate electric circuit whose continuous-time dynamics converge to the solution of the optimization problem at hand. Then, the second stage is an automated, computer-assisted discretization of the continuous-time dynamics, yielding a provably convergent discrete-time algorithm. Our methodology recovers many classical (distributed) optimization algorithms and enables users to quickly design and explore a wide range of new algorithms with convergence guarantees.

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.

Convex optimization is at the heart of many performance-critical applications across a wide range of domains. Although many high-performance hardware accelerators have been developed for specific optimization problems in the past, designing such accelerator is a challenging task and the resulting computing architecture is often so specific to the targeted application that they can hardly be reused even in a related application within the same domain. To accelerate general-purpose optimization solvers that must operate on diverse user input during run time, an ideal hardware solver should be able to adapt to the provided optimization problem dynamically while achieving high performance and power-efficiency. In this work, a hardware-accelerated general-purpose quadratic program solver, called RSQP, with reconfigurable functional units and data path that facilitate problem-specific customization is presented. RSQP uses a string-based encoding to describe the problem structure with fine granularity. Based on this encoding, functional units and datapath customized to the sparsity pattern of the problem are created by solving a dictionary-based lossless string compression problem and a mixed integer linear program respectively. RSQP has been integrated to accelerate the general-purpose quadratic programming solver OSQP and has been tested using an extensive benchmark with 120 optimization problems from 6 application domains. Through architectural customization, RSQP achieves up to 7× performance improvement over its baseline generic design. Furthermore, when compared with a CPU and a GPU-accelerated implementation, RSQP achieves up to 31.2× and 6.9× end-to-end speedup on these benchmark programs, respectively. Finally, the FPGA accelerator operates at up to 6.6× lower dynamic power consumption and up to 22.7× higher power efficiency over the GPU implementation, making it an attractive solution for power-conscious datacenter applications.

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.

Policy gradient methods are among the most effective methods for large-scale reinforcement learning, and their empirical success has prompted several works that develop the foundation of their global convergence theory. However, prior works have either required exact gradients or state-action visitation measure based mini-batch stochastic gradients with a diverging batch size, which limit their applicability in practical scenarios. In this paper, we consider classical policy gradient methods that compute an approximate gradient with a single trajectory or a fixed size mini-batch of trajectories under soft-max parametrization and log-barrier regularization, along with the widely-used REINFORCE gradient estimation procedure. By controlling the number of "bad" episodes and resorting to the classical doubling trick, we establish an anytime sub-linear high probability regret bound as well as almost sure global convergence of the average regret with an asymptotically sub-linear rate. These provide the first set of global convergence and sample efficiency results for the well-known REINFORCE algorithm and contribute to a better understanding of its performance in practice.

Resource allocation problems in many computer systems can be formulated as mathematical optimization problems. However, finding exact solutions to these problems using off-the-shelf solvers is often intractable for large problem sizes with tight SLAs, leading system designers to rely on cheap, heuristic algorithms. We observe, however, that many allocation problems are granular: they consist of a large number of clients and resources, each client requests a small fraction of the total number of resources, and clients can interchangeably use different resources. For these problems, we propose an alternative approach that reuses the original optimization problem formulation and leads to better allocations than domain-specific heuristics. Our technique, Partitioned Optimization Problems (POP), randomly splits the problem into smaller problems (with a subset of the clients and resources in the system) and coalesces the resulting sub-allocations into a global allocation for all clients. We provide theoretical and empirical evidence as to why random partitioning works well. In our experiments, POP achieves allocations within 1.5% of the optimal with orders-of-magnitude improvements in runtime compared to existing systems for cluster scheduling, traffic engineering, and load balancing.

Stratified models are models that depend in an arbitrary way on a set of selected categorical features, and depend linearly on the other features. In a basic and traditional formulation a separate model is fit for each value of the categorical feature, using only the data that has the specific categorical value. To this formulation we add Laplacian regularization, which encourages the model parameters for neighboring categorical values to be similar. Laplacian regularization allows us to specify one or more weighted graphs on the stratification feature values. For example, stratifying over the days of the week, we can specify that the Sunday model parameter should be close to the Saturday and Monday model parameters. The regularization improves the performance of the model over the traditional stratified model, since the model for each value of the categorical `borrows strength' from its neighbors. In particular, it produces a model even for categorical values that did not appear in the training data set. We propose an efficient distributed method for fitting stratified models, based on the alternating direction method of multipliers (ADMM). When the fitting loss functions are convex, the stratified model fitting problem is convex, and our method computes the global minimizer of the loss plus regularization; in other cases it computes a local minimizer. The method is very efficient, and naturally scales to large data sets or numbers of stratified feature values. We illustrate our method with a variety of examples.

Real-world, imaging systems acquire measurements that are degraded by noise, optical aberrations, and other imperfections that make image processing for human viewing and higher-level perception tasks challenging. Conventional cameras address this problem by compartmentalizing imaging from high-level task processing. As such, conventional imaging involves processing the RAW sensor measurements in a sequential pipeline of steps, such as demosaicking, denoising, deblurring, tone-mapping, and compression. This pipeline is optimized to obtain a visually pleasing image. High-level processing, however, involves steps such as feature extraction, classification, tracking, and fusion. While this silo-ed design approach allows for efficient development, it also dictates compartmentalized performance metrics without knowledge of the higher-level task of the camera system. For example, today’s demosaicking and denoising algorithms are designed using perceptual image quality metrics but not with domain-specific tasks such as object detection in mind. We propose an end-to-end differentiable architecture that jointly performs demosaicking, denoising, deblurring, tone-mapping, and classification (see Figure 1). The architecture does not require any intermediate losses based on perceived image quality and learns processing pipelines whose outputs differ from those of existing ISPs optimized for perceptual quality, preserving fine detail at the cost of increased noise and artifacts. We show that state-of-the-art ISPs discard information that is essential in corner cases, such as extremely low-light conditions, where conventional imaging and perception stacks fail. We demonstrate on captured and simulated data that our model substantially improves perception in low light and other challenging conditions, which is imperative for real-world applications such as autonomous driving, robotics, and surveillance. Finally, we found that the proposed model also achieves state-of-the-art accuracy when optimized for image reconstruction in low-light conditions, validating the architecture itself as a potentially useful drop-in network for reconstruction and analysis tasks beyond the applications demonstrated in this work. Our proposed models, datasets, and calibration data are available at https://github.com/princeton-computational-imaging/DirtyPixels .

This paper proposes an adaptive metric selection strategy called diagonal Barzilai-Borwein (DBB) stepsize for the popular Variable Metric Proximal Gradient (VM-PG) algorithm [1], [2]. The proposed approach better captures the local geometry of the problem while keeping the per-step computation cost similar to the widely used scalar Barzilai-Borwein (BB) stepsize. We provide the theoretical convergence analysis for VM-PG using DBB stepsize. Finally, our empirical results show ~10 - 40 % improvement in convergence times for the VM-PG using DBB compared to the BB stepsize for different machine learning problems on several datasets.

BACKGROUND: High-throughput omics technologies have enabled the comprehensive reconstructions of genome-scale metabolic networks for many organisms. However, only a subset of reactions is active in each cell which differs from tissue to tissue or from patient to patient. Reconstructing a subnetwork of the generic metabolic network from a provided set of context-specific active reactions is a demanding computational task. RESULTS: We propose SWIFTCC and SWIFTCORE as effective methods for flux consistency checking and the context-specific reconstruction of genome-scale metabolic networks which consistently outperform the previous approaches. CONCLUSIONS: We have derived an approximate greedy algorithm which efficiently scales to increasingly large metabolic networks. SWIFTCORE is freely available for non-commercial use in the GitHub repository at https://mtefagh.github.io/swiftcore/.

Recent work has shown how to embed differentiable optimization problems (that is, problems whose solutions can be backpropagated through) as layers within deep learning architectures. This method provides a useful inductive bias for certain problems, but existing software for differentiable optimization layers is rigid and difficult to apply to new settings. In this paper, we propose an approach to differentiating through disciplined convex programs, a subclass of convex optimization problems used by domain-specific languages (DSLs) for convex optimization. We introduce disciplined parametrized programming, a subset of disciplined convex programming, and we show that every disciplined parametrized program can be represented as the composition of an affine map from parameters to problem data, a solver, and an affine map from the solver’s solution to a solution of the original problem (a new form we refer to as affine-solver-affine form). We then demonstrate how to efficiently differentiate through each of these components, allowing for end-to-end analytical differentiation through the entire convex program. We implement our methodology in version 1.1 of CVXPY, a popular Python-embedded DSL for convex optimization, and additionally implement differentiable layers for disciplined convex programs in PyTorch and TensorFlow 2.0. Our implementation significantly lowers the barrier to using convex optimization problems in differentiable programs. We present applications in linear machine learning models and in stochastic control, and we show that our layer is competitive (in execution time) compared to specialized differentiable solvers from past work.

Radiation therapy is widely used in cancer treatment; however, plans necessarily involve tradeoffs between tumor coverage and mitigating damage to healthy tissue. Although current hardware can deliver custom-shaped beams from any angle around the patient, choosing (from all possible beams) an optimal set of beams that maximizes tumor coverage while minimizing collateral damage and treatment time is intractable. Furthermore, even though planning algorithms used in practice consider highly restricted sets of candidate beams, the time per run combined with the number of runs required to explore clinical tradeoffs results in planning times of hours to days. We propose a suite of cluster and bound methods that we hypothesize will (1) yield higher-quality plans by optimizing over much (i.e., 100-fold) larger sets of candidate beams, and/or (2) reduce planning time by allowing clinicians to search through candidate plans in real time. Our methods hinge on phrasing the treatment-planning problem as a convex problem. To handle large-scale optimizations, we form and solve compressed approximations to the full problem by clustering beams (i.e., columns of the dose deposition matrix used in the optimization) or voxels (rows of the matrix). Duality theory allows us to bound the error incurred when applying an approximate problem’s solution to the full problem. We observe that beam clustering and voxel clustering both yield excellent solutions while enabling a 10- to 200-fold speedup.

Models for predicting aircraft motion are an important component of modern aeronautical systems. These models help aircraft plan collision avoidance maneuvers and help conduct off-line performance and safety analyses. In this paper, we develop a method for learning a probabilistic generative model of aircraft motion in terminal airspace, the controlled airspace surrounding a given airport. The method fits the model based on a historical dataset of radar-based position measurements of aircraft landings and takeoffs at that airport. We find that the model generates realistic trajectories, provides accurate predictions, and captures the statistical properties of the aircraft trajectories. Furthermore, the model trains quickly, is compact, and allows for efficient real-time inference.

A matrix network is a family of matrices, with their relations modeled as a weighted graph. We consider the task of completing a partially observed matrix network. The observation comes from a novel sampling scheme where a fraction of matrices might be completely unobserved. How can we recover the entire matrix network from incomplete observations? This mathematical problem arises in many applications including medical imaging and social networks. To recover the matrix network, we propose a structural assumption that the matrices are low-rank after the graph Fourier transform on the network. We formulate a convex optimization problem and prove an exact recovery guarantee for the optimization problem. Furthermore, we numerically characterize the exact recovery regime for varying rank and sampling rate and discover a new phase transition phenomenon. Then we give an iterative imputation algorithm to efficiently solve optimization problem and complete large scale matrix networks. We demonstrate the algorithm with a variety of applications such as MRI and Facebook user network.

Subsequence clustering of multivariate time series is a useful tool for discovering repeated patterns in temporal data. Once these patterns have been discovered, seemingly complicated datasets can be interpreted as a temporal sequence of only a small number of states, or clusters. However, discovering these patterns is challenging because it requires simultaneous segmentation and clustering of the time series. Here we propose a new method of model-based clustering, which we call Toeplitz Inverse Covariance-based Clustering (TICC). Each cluster in the TICC method is defined by a correlation network, or Markov random field (MRF), characterizing the interdependencies between different observations in a typical subsequence of that cluster. Based on this graphical representation, TICC simultaneously segments and clusters the time series data. We solve the TICC problem through a scalable algorithm that is able to efficiently solve for tens of millions of observations. We validate our approach by comparing TICC to several state-of-the-art baselines in a series of synthetic experiments, and we then demonstrate on an automobile dataset how TICC can be used to learn interpretable clusters in real-world scenarios.

In typical cameras the optical system is designed first; once it is fixed, the parameters in the image processing algorithm are tuned to get good image reproduction. In contrast to this sequential design approach, we consider joint optimization of an optical system (for example, the physical shape of the lens) together with the parameters of the reconstruction algorithm. We build a fully-differentiable simulation model that maps the true source image to the reconstructed one. The model includes diffractive light propagation, depth and wavelength-dependent effects, noise and nonlinearities, and the image post-processing. We jointly optimize the optical parameters and the image processing algorithm parameters so as to minimize the deviation between the true and reconstructed image, over a large set of images. We implement our joint optimization method using autodifferentiation to efficiently compute parameter gradients in a stochastic optimization algorithm. We demonstrate the efficacy of this approach by applying it to achromatic extended depth of field and snapshot super-resolution imaging.

Markov random fields (MRFs) are a useful tool for modeling relationships present in large and high-dimensional data. Often, this data comes from various sources and can have diverse distributions, for example a combination of numerical, binary, and categorical variables. Here, we define the pairwise exponential Markov random field (PE-MRF), an approach capable of modeling exponential family distributions in heterogeneous domains. We develop a scalable method of learning the graphical structure across the variables by solving a regularized approximated maximum likelihood problem. Specifically, we first derive a tractable upper bound on the log-partition function. We then use this upper bound to derive the group graphical lasso, a generalization of the classic graphical lasso problem to heterogeneous domains. To solve this problem, we develop a fast algorithm based on the alternating direction method of multipliers (ADMM). We also prove that our estimator is sparsistent, with guaranteed recovery of the true underlying graphical structure, and that it has a polynomially faster runtime than the current state-of-the-art method for learning such distributions. Experiments on synthetic and real-world examples demonstrate that our approach is both efficient and accurate at uncovering the structure of heterogeneous data.

Many important problems can be modeled as a system of interconnected entities, where each entity is recording time-dependent observations or measurements. In order to spot trends, detect anomalies, and interpret the temporal dynamics of such data, it is essential to understand the relationships between the different entities and how these relationships evolve over time. In this paper, we introduce the time-varying graphical lasso (TVGL), a method of inferring time-varying networks from raw time series data. We cast the problem in terms of estimating a sparse time-varying inverse covariance matrix, which reveals a dynamic network of interdependencies between the entities. Since dynamic network inference is a computationally expensive task, we derive a scalable message-passing algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in an efficient way. We also discuss several extensions, including a streaming algorithm to update the model and incorporate new observations in real time. Finally, we evaluate our TVGL algorithm on both real and synthetic datasets, obtaining interpretable results and outperforming state-of-the-art baselines in terms of both accuracy and scalability.

Subsequence clustering of multivariate time series is a useful tool for discovering repeated patterns in temporal data. Once these patterns have been discovered, seemingly complicated datasets can be interpreted as a temporal sequence of only a small number of states, or clusters. For example, raw sensor data from a fitness-tracking application can be expressed as a timeline of a select few actions (i.e., walking, sitting, running). However, discovering these patterns is challenging because it requires simultaneous segmentation and clustering of the time series. Furthermore, interpreting the resulting clusters is difficult, especially when the data is high-dimensional. Here we propose a new method of model-based clustering, which we call Toeplitz Inverse Covariance-based Clustering (TICC). Each cluster in the TICC method is defined by a correlation network, or Markov random field (MRF), characterizing the interdependencies between different observations in a typical subsequence of that cluster. Based on this graphical representation, TICC simultaneously segments and clusters the time series data. We solve the TICC problem through alternating minimization, using a variation of the expectation maximization (EM) algorithm. We derive closed-form solutions to efficiently solve the two resulting subproblems in a scalable way, through dynamic programming and the alternating direction method of multipliers (ADMM), respectively. We validate our approach by comparing TICC to several state-of-the-art baselines in a series of synthetic experiments, and we then demonstrate on an automobile sensor dataset how TICC can be used to learn interpretable clusters in real-world scenarios.

In this paper, we examine a class of non-convex stochastic optimization problems which we call variationally coherent, and which properly includes pseudo-/quasiconvex and star-convex optimization problems. To solve such problems, we focus on the widely used stochastic mirror descent (SMD) family of algorithms (which contains stochastic gradient descent as a special case), and we show that the last iterate of SMD converges to the problem’s solution set with probability 1. This result contributes to the landscape of non-convex stochastic optimization by clarifying that neither pseudo-/quasi-convexity nor star-convexity is essential for (almost sure) global convergence; rather, variational coherence, a much weaker requirement, suffices. Characterization of convergence rates for the subclass of strongly variationally coherent optimization problems as well as simulation results are also presented.

SnapVX is a high-performance solver for convex optimization problems defined on networks. For problems of this form, SnapVX provides a fast and scalable solution with guaranteed global convergence. It combines the capabilities of two open source software packages: Snap.py and CVXPY. Snap.py is a large scale graph processing library, and CVXPY provides a general modeling framework for small-scale subproblems. SnapVX offers a customizable yet easy-to-use Python interface with out-of- the- box functionality. Based on the Alternating Direction Method of Multipliers (ADMM), it is able to efficiently store, analyze, parallelize, and solve large optimization problems from a variety of different applications. Documentation, examples, and more can be found on the SnapVX website at snap.stanford.edu/snapvx.

Vectoring is a well-known technique to mitigate multi- user interference in the downlink Digital Subscriber Line (DSL) transmission. While effective in canceling interference, vectoring does incur major computational overhead, resulting in significant energy consumption when the number of lines is large. To facilitate energy efficient transmission, a mechanism called discontinuous operation (DO) has been recently proposed. In this paper, we consider the key resource allocation problems in DSL: given the transmission opportunities, determine the optimal DO transmission scheme, and optimally adjust an existing DO transmission scheme for energy saving consideration. We formulate these problems and propose efficient real- time algorithms to solve them to global optimality. Simulation results are shown to demonstrate the efficiency and the effectiveness of the proposed algorithms.

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 www.cvxpy.org under the GPL license, along with documentation and examples.

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.

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 abstract linear operators, we arrive at a matrix-free cone program, i.e., one whose data matrix is represented by an abstract 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.

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 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.

We focus on crowd-powered filtering, i.e., filtering a large set of items using humans. Filtering is one of the most commonly used building blocks in crowdsourcing applications and systems. While solutions for crowd-powered filtering exist, they make a range of implicit assumptions and restrictions, ultimately rendering them not powerful enough for real-world applications. We describe two approaches to discard these implicit assumptions and restrictions: one, that carefully generalizes prior work, leading to an optimal, but often-times intractable solution, and another, that provides a novel way of reasoning about filtering strategies, leading to a sometimes suboptimal, but efficiently computable solution (that is asymptotically close to optimal). We demonstrate that our techniques lead to significant reductions in error of up to 30% for fixed cost over prior work in a novel crowdsourcing application: peer evaluation in online courses.

We introduce a new notion of classification accuracy based on the top $\tau$-quantile values of a scoring function, a relevant criterion in a number of problems arising for search engines. We define an algorithm optimizing a convex surrogate of the corresponding loss, and show how its solution can be obtained by solving several convex optimization problems. We also present margin-based guarantees for this algorithm based on the $\tau$-quantile of the functions in the hypothesis set. Finally, we report the results of several experiments evaluating the performance of our algorithm. In a comparison in a bipartite setting with several algorithms seeking high precision at the top, our algorithm achieves a better performance in precision at the top.

Convex optimization has emerged as useful tool for applications that include data analysis and model fitting, resource allocation, engineering design, network design and optimization, finance, and control and signal processing. After an overview, the talk will focus on two extremes: real-time embedded convex optimization, and distributed convex optimization. Code generation can be used to generate extremely efficient and reliable solvers for small problems, that can execute in milliseconds or microseconds, and are ideal for embedding in real-time systems. At the other extreme, we describe methods for large-scale distributed optimization, which coordinate many solvers to solve enormous problems.

This paper presents an integrated framework, together with control policies, for optimizing dynamic control of self-tuning parameters of a digital system over its lifetime in the presence of circuit aging. A variety of self-tuning parameters such as supply voltage, operating clock frequency, and dynamic cooling are considered, and jointly optimized using efficient algorithms described in this paper. Our optimized self-tuning approach satisfies performance constraints at all times, and maximizes a lifetime computational power efficiency (LCPE) metric, which is defined as the total number of clock cycles achieved over lifetime divided by the total energy consumed over lifetime. We present three control policies: 1) progressive-worst-case-aging (PWCA), which assumes worst-case aging at all times; 2) progressive-on-state-aging (POSA), which estimates aging by tracking active/sleep modes, and then assumes worst-case aging in active mode and long recovery effects in sleep mode; and 3) progressive-real-time-aging-assisted (PRTA), which acquires real-time information and initiates optimized control actions. Various flavors of these control policies for systems with dynamic voltage and frequency scaling (DVFS) are also analyzed. Simulation results on benchmark circuits, using aging models validated by 45 nm measurements, demonstrate the effectiveness and practicality of our approach in significantly improving LCPE and/or lifetime compared to traditional one-time worst-case guardbanding. We also derive system design guidelines to maximize self-tuning benefits.

We present a framework and control policies for optimizing dynamic control of various self-tuning parameters over lifetime in the presence of circuit aging. Our framework introduces dynamic cooling as one of the self-tuning parameters, in addition to supply voltage and clock frequency. Our optimized self-tuning satisfies performance constraints at all times and maximizes a lifetime computational power efficiency (LCPE) metric, which is defined as the total number of clock cycles achieved over lifetime divided by the total energy consumed over lifetime. Our framework features three control policies: 1. Progressive-worst-case-aging (PWCA), which assumes worst-case aging at all times; 2. Progressive-on-state-aging (POSA), which estimates aging by tracking active/sleep mode, and then assumes worst-case aging in active mode and long recovery effects in sleep mode; 3. Progressive-real-time-aging-assisted (PRTA), which estimates the actual amount of aging and initiates optimized control action. Simulation results on benchmark circuits, using aging models validated by 45nm CMOS stress measurements, demonstrate the practicality and effectiveness of our approach. We also analyze design constraints and derive system design guidelines to maximize self-tuning benefits.

We investigate flow rate optimization on a wireless link with randomly varying channel gain using techniques from adaptive modulation and network utility maximization. We consider the problem of choosing the data flow rate to optimally trade off average transmit power and the average utility of the smoothed data flow rate. The smoothing allows us to model the demands of an application that can tolerate variations in flow over a certain time interval; we will see that this smoothing leads to a substantially different optimal data flow rate policy than without smoothing. We pose the problem as a convex stochastic control problem. For the case of a single flow, the optimal data flow rate policy can be numerically computed using stochastic dynamic programming. For the case of multiple data flows on a single link, we propose an approximate dynamic programming approach to obtain suboptimal data flow rate policies. We illustrate, through numerical examples, that these approximate policies perform very well.

Meeting the temperature constraints and reducing the hot-spots are critical for achieving reliable and efficient operation of complex multi-core systems. The goal of thermal management is to meet maximum operating temperature constraints, while tracking timevarying performance requirements. Current approaches avoid thermal violations by forcing abrupt operating points changes, which cause sharp performance degradation. In this paper we aim at achieving an online smooth thermal control action, that minimizes the tracking error. We formulate this problem as a discrete-time optimal control problem, which can be solved via online by using an embedded convex optimization solver using a receding horizon approach. The optimization problem considers the thermal profile of the system, its evolution over time, current and past time-varying workload requirements. We perform experiments on a model of the 8-core Niagara-1 multicore architecture, which show that the proposed method outperforms state-of-the-art thermal management approaches by enabling performance speed-ups of up to 2:5£ and improvements up to 12x and 3.4x in relation to frequency and temperature variations over time, respectively.

We present a cross layer technique to find and characterize optimal control policies for wireless networks operating at different time scales at the upper layer and physical layer. The technique can also be directly applied to networks carrying traffic with different time dependencies such as data or video. Our approach combines network utility maximization and adaptive modulation over an infinite discrete time horizon using a class of performance measures we call time smoothed utility functions. We describe the properties of optimal physical layer power and link rate policies and characterize optimal upper layer policies, which determine when packets should be injected into the network. We also characterize the behavior of optimal policies as different system parameters are used.

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 anl1regularization term. Using a first order method developed by Hale et al, we demonstrate the performance of the methods through numerical simulation. We find that, using these methods, compressed sensing can be carried out even when the quantization is very coarse, e.g., 1 or 2 bits per measurement.

We consider a scheduled orthogonal frequency division multiplexed (OFDM) wireless cellular network where the channels from the base-station to the n mobile users undergo flat fading. Spectral resources are to be divided among the users in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an O(n) algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is O(n), with a modest constant. When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. We also show how our techniques can be extended to solve resource allocation problems that arise in wideband networks with frequency selective fading and when the utility of a user is also a function of the resource allocations in the past.

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.

We describe Wireless Network Utility Maximization, WNUM, and compare its performance to NUM for wireless networks of interfering links under random time varying channel conditions. WNUM is shown to simultaneously offer greater rate and reliability performance in simulations operating under Rayleigh fading. A general method for finding adaptive network control policies is presented that is sample- based and converges to the optimal control policies for the network.

Long design cycles due to the inability to predict silicon realities are a well-known problem that plagues analog/RF integrated circuit product development. As this problem worsens for nanoscale IC technologies, the high cost of design and multiple manufacturing spins causes fewer products to have the volume required to support full-custom implementation. Design reuse and analog synthesis make analog/RF design more affordable; however, the increasing process variability and lack of modeling accuracy remain extremely challenging for nanoscale analog/RF design. We propose a regular analog/RF IC using metal-mask configurability design methodology Optimization with Recourse of Analog Circuits including Layout Extraction (ORACLE), which is a combination of reuse and shared-use by formulating the synthesis problem as an optimization with recourse problem. Using a two-stage geometric programming with recourse approach, ORACLE solves for both the globally optimal shared and application-specific variables. Furthermore, robust optimization is proposed to treat the design with variability problem, further enhancing the ORACLE methodology by providing yield bound for each configuration of regular designs. The statistical variations of the process parameters are captured by a confidence ellipsoid. We demonstrate ORACLE for regular Low Noise Amplifier designs using metal-mask configurability, where a range of applications share common underlying structure and application-specific customization is performed using the metal-mask layers. Two RF oscillator design examples are shown to achieve robust designs with guaranteed yield bound.

With technology advances, the number of cores integrated on a chip and their speed of operation is increasing. This, in turn is leading to a significant increase in chip temperature. Temperature gradients and hot-spots not only affect the performance of the system, but also lead to unreliable circuit operation and affect the life-time of the chip. Meeting the temperature constraints and reducing the hot-spots are critical for achieving reliable and efficient operation of complex multi-core systems. In this work, we present Pro-Temp, a convex optimization based method that pro-actively controls the temperature of the cores, while minimizing the power consumption and satisfying application performance constraints. The method guarantees that the temperature of the cores are below a user- defined threshold at all instances of operation, while also reducing the hot-spots. We perform experiments on several realistic multi-core benchmarks, which show that the proposed method guarantees that the cores never exceed the maximum temperature limit, while matching the application performance requirements. We compare this to traditional methods, where we find several temperature violations during the operation of the system.

We present a cross-layer framework for optimizing the performance of wireless networks as measured by applications or upper layer protocols. The approach combines adaptive modulation with network utility maximization. We extend the approach to find optimal source rates and transmitter power and rate policies without explicit knowledge of the distribution of channel states. These optimal power and rate policies balance delay (backlog), transmission rate and energy to maximize network performance under constraints on average transmitter power and link buffer arrival and departure rates. Explicit policies are found for single links, and algorithmic methods presented to find optimal policies for complex interfering networks.

We consider a discrete-time dynamical system with Boolean and continuous states, with the continuous state propagating linearly in the continuous and Boolean state variables, and an additive Gaussian process noise, and where each Boolean state component follows a simple Markov chain. This model, which can be considered a hybrid or jump-linear system with very special form, or a standard linear Gauss-Markov dynamical system driven by a Boolean Markov process, arises in dynamic fault detection, in which each Boolean state component represents a fault that can occur. We address the problem of estimating the state, given Gaussian noise corrupted linear measurements. Computing the exact maximum a posteriori (MAP) estimate entails solving a mixed integer quadratic program, which is computationally difficult in general, so we propose an approximate MAP scheme, based on a convex relaxation, followed by rounding and (possibly) further local optimization. Our method has a complexity that grows linearly in the time horizon and cubicly with the state dimension, the same as a standard Kalman filter. Numerical experiments suggest that it performs very well in practice.

The performance of a kernel-based learning algorithm depends very much on the choice of the kernel. Recently, much attention has been paid to the problem of learning the kernel itself from given training examples. The main emphasis has been on formulating the problem as a tractable convex optimization problem. Only for a few very special cases such as support vector machines are explicit convex formulations known. In this paper, we show that, in a wide variety of kernel-based learning algorithms, the kernel learning problem can be formulated as a convex optimization problem which interior-point methods can solve globally and efficiently. The kernel learning method is illustrated with a regression problem that arises in petroleum engineering.

We investigate adaptive modulation using the network utility maximization framework. We derive new crosslayer optimal power and rate adaptation policies for several practical modulation schemes. The behavior of these crosslayer policies is found to differ from policies based on physical-layer optimization only. The multiple flow single link case is analyzed and optimal power and rate policies found. The multiple interfering link case is investigated and a numerical method presented to find optimal policies for this case.

In Chebyshev finite-impulse response (FIR) equalization, we design an FIR filter that minimizes the Chebyshev equalization error,i.e., the maximum absolute deviation between the equalized and the desired frequency response functions, assuming the unequalized response function is known exactly. In robust Chebyshev FIR equalization, we take into account uncertainty in the unequalized response function, described as a set of possible values for the unequalized response at each frequency, by designing an FIR filter that minimizes worst-case Chebyshev equalization error over all possible unequalized response functions. When the uncertainty in unequalized response function is described by a complex uncertainty ellipsoid, at each frequency, we show that the robust Chebyshev FIR equalization design problem can be formulated as a semidefinite program (SDP), and therefore efficiently (and globally) solved. When the uncertainty is given by a complex disk, the design problem can be formulated as a second-order cone program (SOCP), which can be solved almost as fast as the nominal Chebyshev equalization problem (ignoring uncertainty). The robust equalizer design method is demonstrated with a numerical example.

Compressed sensing or compressive sampling (CS) has been receiving a lot of interest as a promising method for signal recovery and sampling. CS problems can be cast as convex problems, and then solved by several standard methods such as interior-point methods, at least for small and medium size problems. In this paper we describe a specialized interior-point method for solving CS problems that uses a preconditioned conjugate gradient method to compute the search step. The method can efficiently solve large CS problems, by exploiting fast algorithms for the signal transforms used. The method is demonstrated with a medical resonance imaging (MRI) example.

In this letter, we show that worst-case robust beamforming, with uncertain weights subject to multiplicative variations, can be cast as a convex optimization problem. We interpret this problem as a weighted complex l1-regularization of the nominal beamforming problem, and show that it can be solved with the same computational complexity as nominal beamforming, ignoring the variations. We derive a simple lower bound on how much worse the robust beamformer will be compared to the nominal beamformer solution with no weight uncertainty. We demonstrate the robust approach with a simple narrowband beamformer

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 thus, can be solved using several standard algorithms for these problem classes. In this paper, we describe a custom interior-point algorithm for solving the FOP that exploits the specific structure of the problem, and is much faster than these standard methods. Our method has a complexity that is linear in the number of contact forces, whereas methods based on generic SDP or SOCP algorithms have complexity that is cubic in the number of forces. Our method is also much faster for smaller problems. We derive a compact dual problem for the FOP, which allows us to rapidly compute lower bounds on the minimum contact force and certify the infeasibility of a FOP. We use this dual problem to terminate our optimization method with a guaranteed accuracy. Finally, we consider the problem of solving a family of FOPs that are related. This occurs, for example, in determining whether force closure occurs, in analyzing the worst case contact force required over a set of external forces and torques, and in the problem of choosing contact points on an object so as to minimize the required contact force. Using dual bounds, and a warm-start version of our FOP method, we show how such families of FOPs can be solved very efficiently.

In Kernel Fisher discriminant analysis (KFDA), we carry out Fisher linear discriminant analysis in a high dimensional feature space defined implicitly by a kernel. The performance of KFDA depends on the choice of the kernel; in this paper, we consider the problem of finding the optimal kernel, over a given convex set of kernels. We show that this optimal kernel selection problem can be reformulated as a tractable convex optimization problem which interior-point methods can solve globally and efficiently. The kernel selection method is demonstrated with some UCI machine learning benchmark examples.

We consider the problem of choosing a linear classifier that minimizes misclassification probabilities in two-class classification, which is a bi-criterion problem, involving a trade-off between two objectives. We assume that the class-conditional distributions are Gaussian. This assumption makes it computationally tractable to find Pareto optimal linear classifiers whose classification capabilities are inferior to no other linear ones. The main purpose of this paper is to establish several robustness properties of those classifiers with respect to variations and uncertainties in the distributions. We also extend the results to kernel-based classification. Finally, we show how to carry out trade-off analysis empirically with a finite number of given labeled data.

We present a unified duality view of several recently emerged spectral methods for nonlinear dimensionality reduction, including Isomap, locally linear embedding, Laplacian eigenmaps, and maximum variance unfolding. We discuss the duality theory for the maximum variance unfolding problem, and show that other methods are directly related to either its primal formulation or its dual formulation, or can be interpreted from the optimality conditions. This duality framework reveals close connections between these seemingly quite different algorithms. In particular, it resolves the myth about these methods in using either the top eigenvectors of a dense matrix, or the bottom eigenvectors of a sparse matrix --- these two eigenspaces are exactly aligned at primal-dual optimality.

We consider a sensor network in which each sensor takes measurements, at various times, of some unknown parameters, corrupted by independent Gaussian noises. Each node can take a finite or infinite number of measurements, at arbitrary times (ie, asynchronously). We propose a space-time diffusion scheme, that relies only on peer-to-peer communication, and allows every node to asymptotically compute the global maximum-likelihood estimate of the unknown parameters. At each iteration, information is diffused across the network by a temporal update step and a spatial update step. Both steps update each node's state by a weighted average of its current value and locally available data: new measurements for the time update, and neighbors' data for the spatial update. At any time, any node can compute a local weighted least-squares estimate of the unknown parameters, which converges to the global maximum-likelihood solution. With an infinite number of measurements, these estimates converge to the true parameter values in the sense of mean-square convergence. We show that this scheme is robust to unreliable communication links, and works in a network with dynamically changing topology.

Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.

As the design-manufacturing interface becomes increasingly complicated with IC technology scaling, the corresponding process variability poses great challenges for nanoscale analog/RF design. Design optimization based on the enumeration of process corners has been widely used , but can suffer from inefficiency and overdesign. In this paper we propose to formulate the analog and RF design with variability problem as a special type of robust optimization problem, namely robust geometric programming. The statistical variations in both the process parameters and design variables are captured by a pre-specified confidence ellipsoid. Using such optimization with ellipsoidal uncertainy approach, robust design can be obtained with guaranteed yield bound and lower design cost, and most importantly, the problem size grows linearly with number of uncertain parameters. Numerical examples demonstrate the efficiency and reveal the trade-off between the design cost versus the yield requirement. We will also demonstrate significant improvement in the design cost using this approach compared with corner-enumeration optimization.

Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.

We consider a network of distributed sensors, where where each sensor takes a linear measurement of some unknown parameters, corrupted by independent Gaussian noises. We propose a simple distributed iterative scheme, based on distributed average consensus in the network, to compute the maximum-likelihood estimate of the parameters. This scheme doesn't involve explicit point-to-point message passing or routing; instead, it diffuses information across the network by updating each node's data with a weighted average of its neighbors' data (they maintain the same data structure). At each step, every node can compute a local weighted least-squares estimate, which converges to the global maximum-likelihood solution. This scheme is robust to unreliable communication links. We show that it works in a network with dynamically changing topology, provided that the infinitely occurring communication graphs are jointly connected.

This tutorial concerns a method for solving a variety of circuit sizing and optimization problems, which is based on formulating the problem as a geometric program (GP), or a generalized geometric program (GGP). These nonlinear, constrained optimization problems can be transformed to convex optimization problems, and then solved (globally) very efficiently.

Fisher linear discriminant analysis (LDA) can be sensitive to the problem data. Robust Fisher LDA can systematically alleviate the sensitivity problem by explicitly incorporating a model of data uncertainty in a classification problem and optimizing for the worst-case scenario under this model. The main contribution of this paper is show that with general convex uncertainty models on the problem data, robust Fisher LDA can be carried out using convex optimization. For a certain type of product form uncertainty model, robust Fisher LDA can be carried out at a cost comparable to standard Fisher LDA. The method is demonstrated with some numerical examples. Finally, we show how to extend these results to robust kernel Fisher discriminant analysis, i.e., robust Fisher LDA in a high dimensional feature space.

Long design cycles due to the inability to predict silicon realities is a well-known problem that plagues analog/RF integrated circuit product development. As this problem worsens for technologies below 100nm, the high cost of design and multiple manufacturing spins causes fewer products to have the volume required to support full custom implementation. Design reuse and analog synthesis make analog/RF design more affordable; however, the increasing process variability and lack of modeling accuracy remains extremely challenging for nanoscale analog/RF design. We propose an analog/RF circuit design methodology ORACLE, which is a combination of reuse and \emph{shared-use by formulating the synthesis problem as an \emph{optimization with recourse problem. Using a two-stage geometric programming with recourse approach, ORACLE solves for both the globally optimal shared and application-specific variables. Concurrently, we demonstrate ORACLE for novel metal-mask configurable designs, where a range of applications share common underlying structure and application-specific customization is performed using the metal-mask layers. We also include the silicon validation of the metal-mask configurable designs.

Intersymbol interference (ISI) due to modal dispersion is the dominant limitation to the bit rate-distance product in multimode fiber-optic communication systems. If the light launched into the fiber excites only the desired principal modes, modal dispersion can be eliminated. We can achieve this by using spatial light modulators (SLMs) to perform adaptive spatial filtering on the electric fields of the light. In this paper, we develop an optimization framework for setting the SLMs to obtain an upper bound on the achievable performance and develop heuristics that nearly reach this upper bound Using this framework, we show that both a sophisticated semidefinite programming-based algorithm and a simple adaptive algorithm achieve performance close to the upper bound. Performance and system complexity tradeoff curves are constructed, showing that a 20/spl times/20 array of SLM pixels with binary phase control performs within 15% of more complex implementations. Finally, we extend the framework and present preliminary results showing the promise of further increases in the capabilities of multimode fiber by using the fiber as a multiple-input multiple-output (MIMO) transmission medium.

We present a distributed cross layer approach to controlling the network performance under various QoS requirements in interference limited systems. The interaction between the different layers of the OSI protocol stack requires a cross layer approach in order to optimally allocate the resources of the network. The message passing direct step method presented here is an adaptive and distributed algorithm that achieves maximum network performance. Using the forward and backwards networks, this algorithm finds the left and right Perron Frobenius eigenvectors for the system and automatically adjusts the operating point of the system (data rates, link rates and transmitter powers) to their optimal values while satisfying QoS constraints. The approach is developed and simulated using the TCP Reno.

In wireless data networks, the optimal routing of data depends on the link capacities which, in turn, are determined by the allocation of communications resources (such as transmit powers and bandwidths) to the links. The optimal performance of the network can only be achieved by simultaneous optimization of routing and resource allocation. In this paper, we formulate the simultaneous routing and resource allocation (SRRA) problem, and exploit problem structure to derive efficient solution methods. We use a capacitated multicommodity flow model to describe the data flows in the network. We assume that the capacity of a wireless link is a concave and increasing function of the communications resources allocated to the link, and the communications resources for groups of links are limited. These assumptions allow us to formulate the SRRA problem as a convex optimization problem over the network flow variables and the communications variables. These two sets of variables are coupled only through the link capacity constraints. We exploit this separable structure by dual decomposition. The resulting solution method attains the optimal coordination of data routing in the network layer and resource allocation in the radio control layer via pricing on the link capacities.

We show that the Lagrange dual problems of the channel capacity problem with input cost and the rate distortion problem are simple geometric programs. Upper bounds on channel capacity and lower bounds on rate distortion can be efficiently generated from their duals. For channel capacity, the geometric programming dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in Csiszar et al. (1981). For rate distortion, the geometric programming dual is extended to rate distortion with two-sided state information. A "duality by mapping" is then given between the Lagrange dual problems of channel capacity with input cost and rate distortion, which resolves several apparent asymmetries between their primal problems in the familiar form of mutual information optimization problems. Both the primal and dual problems can be interpreted in a common framework of free energy optimization from statistical physics.

This note considers an n-letter alphabet in which the ith letter is accessed with probability p/sub i/. The problem is to design efficient algorithms for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector q/sup */=(q/sup *//sub 1/,...,q/sup *//sub n/) in an appropriate convex set, S, so as to minimize the relative entropy D(p/spl par/q) over all q/spl isin/S. Methods from convex optimization give an explicit solution for q/sup */ in terms of p. We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.

This paper proposes an efficient numerical algorithm to compute the optimal input distribution that maximizes the sum capacity of a Gaussian multiple-access channel with vector inputs and a vector output. The numerical algorithm has an iterative water-filling interpretation. The algorithm converges from any starting point, and it reaches within 1/2 nats per user per output dimension from the sum capacity after just one iteration. The characterization of sum capacity also allows an upper bound and a lower bound for the entire capacity region to be derived.

In this paper, we present a new methodology for managing power consumption of networks-on-chips (NOCs). A power management problem is formulated for the first time using closed-loop control concepts. We introduce an estimator and a controller that implement our power management methodology. The estimator is capable of very fast and accurate tracking of changes in the system parameters. Parameters estimated are used to form the system model. Our system model combines node and network centric power management decisions. Node centric power management assumes no a priori knowledge of requests coming in from outside the core. Thus, it implements a more traditional dynamic voltage scaling and power management control algorithms. Network-centric power management utilizes interaction with the other system cores regarding the power and the quality of service (QoS) needs. The overall system model is based on Renewal theory and, thus, guarantees globally optimal results. We introduce a fast optimization method that runs multiple orders of magnitude faster than the previous optimization approaches while still having the same accuracy in obtaining the power management control. Finally, our controller implements the results of optimization in either hardware or software. The new methodology for power management of NOCs is tested on a system consisting of four satellite units, each implementing an estimator and a controller capable of both node and network centric power management. Our results show large savings in power with good QoS.

The optimal routing of data in a wireless network depends on the link capacities, which, in turn, are determined by the allocation of transmit powers across the network. Thus, the optimal network performance can only be achieved by simultaneous optimization of routing and power allocation. In this paper, we study this joint optimization problem in CDMA data networks using convex optimization techniques. Although link capacity constraints of CDMA systems are not jointly convex in rates and powers, we show that coordinate projections or transformations allow the simultaneous routing and power allocation problem to be formulated as (in systems with interference cancellation) or approximated by (in systems without interference cancellation) a convex optimization problem which can be solved very efficiently. We also propose a heuristic link-removal procedure based on the convex approximation to further improve the system performance.

The increasing application space of interconnection networks now encompasses several applications, such as packet routing and I/O interconnect, where the throughput of a routing algorithm, not just its locality, becomes an important performance metric. We show that the problem of designing oblivious routing algorithms that have high worst-case or average-case throughput can be cast as a linear program. Globally optimal solutions to these optimization problems can be efficiently found, yielding provably good oblivious routing algorithms. Applying these techniques to k-ary 2-cube (tori) networks shows that previous routing algorithms sacrifice too much locality to achieve optimal worst-case throughput. This motivates the development of two new algorithms, IVAL and 2TURN, which improve locality to within 0.3% of optimal for an 8-ary 2-cube. Both algorithms have simple, deadlock-free implementations. Expanding the analysis of tori to average-case throughput reveals that there is a weak tradeoff between average-case and worst-case throughput. Specifically, both the IVAL and 2TURN algorithms developed for the worst-case also have good average-case throughput.

Systems on a chip (SOCs) are rapidly evolving into larger networks on a chip (NOCs). This work presents a new methodology for managing power consumption for NOCs. Power management problem is formulated using closed-loop control concepts, with the estimator tracking changes in the system parameters and recalculating the new power management policy accordingly. Dynamic voltage scaling and local power management are formulated in the node-centric manner, where each core has its local power manager that determines unit power states, The local power manager's interaction with the other system cores regarding the power and the QoS needs enables network-centric power management. The new methodology for power management of NOCs is tested on a system consisting of four satellite units, each with the local power manager capable of both node and network centric power management. The results show large savings in power with good QoS.

We present a systematic treatment of efficient nonlinear optimizations of queuing systems. The suite of formulations uses the computational tool of convex optimization, with fast polynomial time algorithms to obtain the global optimum for these nonlinear problems under various constraints. We first show convexity structures of several queuing systems, including some surprising transition patterns, followed by formulating and showing numerical examples of several convex performance optimizations for both single queues and queuing networks. Blocking probability minimization and service rate allocation through the effective bandwidth approach is also presented.

This paper introduces a computationally efficent outer approximation to the Hadamard, i.e., element-wise, product of two ellipsoids. This element-wise product corresponds to multiplicative uncertainties, which arrive commonly in practice. We consider the case where both ellipsoids describe real numbers and the case in which the ellipsoids correspond to the direct-sum representation of complex numbers.

For wireless cellular and ad hoc networks with QoS constraints, we propose a suite of problem formulations that allocate network resources to optimize SIR, maximize throughput and minimize delay. The distinguishing characteristics of these resource allocation formulations is that, by using convex optimization, they accommodate a variety of realistic QoS and fairness constraints. Their globally optimal solutions can be computed efficiently through polynomial time interior point methods, even though they use nonlinear objectives and constraints. Through power control in wireless cellular networks, we optimize SIR and delay for a particular QoS class, subject to QoS constraints for all other QoS classes. For wireless ad hoc networks with multihop transmissions and Rayleigh fading, we optimize various objectives, such as the overall system throughput, subject to constraints on power, probability of outage, and data rates. These formulations can also be used for admission control and relative pricing. Both proportional and minmax fairness can be implemented under the convex optimization framework, where fairness parameters can be jointly optimized with QoS criteria. Simple heuristics are also shown and tested using the convex optimization tools.

We propose a new method of power control for interference-limited wireless networks with Rayleigh fading of both the desired and interference signals. Our method explicitly takes into account the statistical variation of both the received signal and interference power and optimally allocates power subject to constraints on the probability of fading induced outage for each transmitter/receiver pair. We establish several results for this type of problem. We establish tight bounds that relate the outage probability caused by channel fading to the signal-to-interference margin calculated when the statistical variation of the signal and interference powers is ignored. This allows us to show that well-known methods for allocating power, based on Perron-Frobenius eigenvalue theory, can be used to determine power allocations that are provably close to achieving optimal (i.e., minimal) outage probability. We show that the problems of minimizing the transmitter power subject to constraints on outage probability and minimizing outage probability subject to power constraints can be posed as a geometric program (GP). A GP is a special type of optimization problem that can be transformed to a nonlinear convex optimization problem by a change of variables and therefore solved globally and efficiently by interior-point methods. We also give a fast iterative method for finding the optimal power allocation to minimize the outage probability.

We consider the problem of determining optimal wire widths for a power or ground network, subject to limits on wire widths, voltage drops, total wire area, current density, and power dissipation. To account for the variation of the current demand, we model it as a random vector with known statistics, possibly including correlation between subsystem currents. Other researchers have shown that when the variation in the current is not taken into account, the optimal network topology is a tree. A tree topology is, however, almost never used in practice, because it is not robust with respect to variations in the lock currents. We show that when the current variation is taken into account, the optimal network is usually not a tree.

We describe a new method for determining component values and transistor dimensions for CMOS operational amplifiers (op-amps). We observe that a wide variety of design objectives and constraints have a special form, i.e., they are posynomial functions of the design variables. As a result, the amplifier design problem can be expressed as a special form of optimization problem called geometric programming, for which very efficient global optimization methods have been developed. As a consequence we can efficiently determine globally optimal amplifier designs or globally optimal tradeoffs among competing performance measures such as power, open-loop gain, and bandwidth. Our method, therefore, yields completely automated sizing of (globally) optimal CMOS amplifiers, directly from specifications. In this paper, we apply this method to a specific widely used operational amplifier architecture, showing in detail how to formulate the design problem as a geometric program. We compute globally optimal tradeoff curves relating performance measures such as power dissipation, unity-gain bandwidth, and open-loop gain. We show how the method can he used to size robust designs, i.e., designs guaranteed to meet the specifications for a variety of process conditions and parameters.

The problem of route address lookup has received much attention recently and several algorithms and data structures for performing address lookups at high speeds have been proposed. In this paper we consider one such data structure-a binary search tree built on the intervals created by the routing table prefixes. We wish to exploit the difference in the probabilities with which the various leaves of the tree (where the intervals are stored) are accessed by incoming packets in order to speedup the lookup process. More precisely, we seek an answer to the question: How can the search tree be drawn so as to minimize the average packet lookup time while keeping the worst-case lookup time within a fixed bound?" We use ideas from information theory to derive efficient algorithms for computing near-optimal routing lookup trees. Finally, we consider the practicality of our algorithms through analysis and simulation.

We present an efficient method for optimal design and synthesis of CMOS inductors for use in RF circuits.This method uses the the physical dimensions of the inductor as the design parameters and handles a variety of specifications including fixed value of inductance, minimum self-resonant frequency, minimum quality factor, etc. Geometric constraints that can be handled include maximum and minimum values for every design parameter and a limit on total area.Our method is based on formulating the design problem as a special type of optimization problem called geometric programming, for which powerful efficient interior-point methods have recently been developed.This allows us to solve the inductor synthesis problem globally and extremely efficiently.Also, we can rapidly compute globally optimal trade-off curves between competing objectives such as quality factor and total inductor area.We have fabricated a number of inductors designed by the method, and found good agreement between the experimental data and the specifications predicted by our method.

Presents a method for optimizing and automating component and transistor sizing for CMOS LC oscillators. We observe that the performance measures can be formulated as posynomial functions of the design variables. As a result, the LC oscillator design problems can be posed as a geometric program, a special type of optimization problem for which very efficient global optimization methods have recently been developed. The synthesis method is therefore fast, and determines the globally optimal design; in particular, the final solution is completely independent of the starting point (which can even be infeasible), and infeasible specifications are unambiguously detected. We can rapidly compute globally optimal trade-off curves between competing objectives such as phase noise and power.

Article Free Access Share on GPCAD: a tool for CMOS op-amp synthesis Authors: Maria del Mar Hershenson Electrical Engineering Department, Stanford University, Stanford CA Electrical Engineering Department, Stanford University, Stanford CAView Profile , Stephen P. Boyd Electrical Engineering Department, Stanford University, Stanford CA Electrical Engineering Department, Stanford University, Stanford CAView Profile , Thomas H. Lee Electrical Engineering Department, Stanford University, Stanford CA Electrical Engineering Department, Stanford University, Stanford CAView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 296–303https://doi.org/10.1145/288548.288628Online:01 November 1998Publication History 45citation513DownloadsMetricsTotal Citations45Total Downloads513Last 12 Months41Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Conventional methods for optimal sizing of wires and transistors use linear resistor-capacitor (RC) circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing problem reduces to a convex optimization problem that can be solved using geometric programming. The tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design, including for example, circuits with loops of resistors, e.g., clock distribution meshes and circuits with coupling capacitors, e.g., buses with crosstalk between the wires. In this paper, we propose a new optimization method that can be used to address these problems. The method is based on the dominant time constant as a measure of signal propagation delay in an RC circuit instead of Elmore delay. Using this measure, sizing of any RC circuit can be cast as a convex optimization problem and solved using recently developed efficient interior-point methods for semidefinite programming. The method is applied to three important sizing problems: clerk mesh sizing and topology design, sizing of tristate buses, and sizing of bus line widths and spacings taking crosstalk into account.

Conventional methods for optimal sizing of wires and transistors use linear RC circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing problem reduces to a convex optimization problem which can be solved using geometric programming. The tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design including, for example, circuits with loops of resistors, e.g. clock distribution meshes, and circuits with coupling capacitors, e.g. buses with crosstalk between the lines. The paper proposes a new optimization method which can be used to address these problems. The method uses the dominant time constant as a measure of signal propagation delay in an RC circuit, instead of Elmore delay. Using this measure, sizing of any RC circuit can be cast as a convex optimization problem which can be solved using the recently-developed efficient interior-point methods for semidefinite programming. The method is applied to two important sizing problems-the sizing of clock meshes and the sizing of buses in the presence of crosstalk.

The demand for integrated services local area networks is increasing at a rapid pace with the advent of many new and exciting applications: office and factory automation, distributed computing, and multimedia communications. To support these new applications, it is imperative to integrate traffic with diverse statistical characteristics and differing delay requirements on the same network. An attractive approach for integrating traffic has been adopted in two token passing local area network standards, the IEEE 802.4 token bus standard and FDDI. The idea is to control the transmissions of each station based on a distributed timing algorithm, so as to achieve the following goals: (i) to limit the token cycles so that time-critical traffic can be accommodated, and (ii) to allocate pre-specified bandwidths to different stations when the network is overloaded. We have investigated the analysis and design of this protocol previously (see Pang and Tobagi, 1989). In this paper, we generalize the transmission control algorithm used with that protocol. The major advantages of the generalization over the original protocol are: (i) it provides a much expanded design space, (ii) it guarantees convergent behavior, and (iii) it gives meaningful insights into the dynamics of the basic control algorithm.>

The maximum data rate that can be reliably communicated given a linear, time-invariant, dispersive channel, a receiver that samples the channel output to within an accuracy of +or-d where d>0, and a transmitter with an output amplitude constraint is evaluated. For any dispersive channel the maximum rate depends on d and is finite. The transmitted waveforms must be designed so that two channel outputs associated with two distinct transmitted signals are separated in amplitude at a particular time by d. It is shown that given any channel impulse response with rational Laplace transform, there exists an optimal sets of inputs that are +or-A everywhere where A is the maximum allowable amplitude. Furthermore, in any finite time interval, each input changes sign a finite number of times. If the channel impulse response is a single decaying exponential, it is shown that simple binary signaling, in which A or -A, depending on the current message bit, is transmitted during each symbol interval, maximizes the data rate.>

The problem of finding the maximum achievable data rate over a linear time-invariant channel is considered under constraints different from those typically assumed. The limiting factor is taken to be the accuracy with which the receiver can measure the channel output. More precisely, the following problem is considered. Given a channel with known impulse response h(t), a transmitter with an output amplitude constraint, and a receiver that can distinguish between two signals only if they are separated in amplitude at some time t/sub 0/ by at least some small positive constant d, what is the maximum number of messages, N/sub max/, that can be transmitted in a given time interval (0,T)? Lower bounds on N/sub max/ can be easily computed by constructing a particular set of inputs to the channel. The main result is an upper bound on N/sub max/ for arbitrary h(t). The upper bound depends on the spread of h(t), which is the maximum range of values the channel output may take at some time t/sub 0/>0 given that the output takes on a particular value alpha at time t=0. Numerical results are shown for different impulse responses, including two simulated telephone subscriber loop impulse responses.>