In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.

Multi-pitch estimation concerns the problem of estimating the fundamental frequencies (pitches) and amplitudes/phases of multiple superimposed harmonic signals with application in music, speech, vibration analysis, and other fields. In this paper we formulate a complex-valued multi-pitch estimator via a semidefinite programming method for continuous sparse optimization over an infinite dictionary of vectors of complex exponentials and extend this to real-valued data via a real semidefinite program with the same dimensions (i.e. half the size). We further impose a continuous frequency constraint naturally occurring from assuming a Nyquist sampled signal by adding an additional semidefinite constraint. In our numerical experiments, the proposed estimator shows superior performance compared to state-of-the-art methods for separating two closely spaced fundamentals and approximately achieves the asymptotic Cramér-Rao lower bound.

We present an extension of recent semidefinite programming formulations for atomic decomposition over continuous dictionaries, with applications to continuous or `gridless' compressed sensing. The dictionary considered in this paper is defined in terms of a general matrix pencil and is parameterized by a complex variable that varies over a segment of a line or circle in the complex plane. The main result of the paper is the formulation as a convex semidefinite optimization problem, and a simple constructive proof of the equivalence. The techniques are illustrated with a direction of arrival estimation problem, and an example of low-rank structured matrix decomposition.

We develop an effective distributed strategy for seeking the Pareto solution of an aggregate cost consisting of regularized risks. The focus is on stochastic optimization problems where each risk function is expressed as the expectation of some loss function and the probability distribution of the data is unknown. We assume each risk function is regularized and allow the regularizer to be non-smooth. Under conditions that are weaker than assumed earlier in the literature and, hence, applicable to a broader class of adaptation and learning problems, we show how the regularizers can be smoothed and how the Pareto solution can be sought by appealing to a multi-agent diffusion strategy. The formulation is general enough and includes, for example, a multi-agent proximal strategy as a special case.

We study a network utility maximization (NUM) decomposition in which the set of flow rates is grouped by source-destination pairs. We develop theorems for both single-path and multipath cases, which relate an arbitrary NUM problem involving all flow rates to a simpler problem involving only the aggregate rates for each source-destination pair. The optimal aggregate flows are then apportioned among the constituent flows of each pair. This apportionment is simple for the case of a-fair utility functions. We also show how the decomposition can be implemented with the alternating direction method of multipliers (ADMM) algorithm.

We present primal-dual decomposition algorithms for convex optimization problems with cost functions $f(x)+g(Ax)$, where $f$ and $g$ have inexpensive proximal operators and $A$ can be decomposed as a sum of two structured matrices. The methods are based on the Douglas--Rachford splitting algorithm applied to various splittings of the primal-dual optimality conditions. We discuss applications to image deblurring problems with nonquadratic data fidelity terms, different types of convex regularization, and simple convex constraints. In these applications, the primal-dual splitting approach allows us to handle general boundary conditions for the blurring operator. Numerical results indicate that the primal-dual splitting methods compare favorably with the alternating direction method of multipliers, the Douglas--Rachford algorithm applied to a reformulated primal problem, and the Chambolle--Pock primal-dual algorithm.

This paper presents a new method for fitting a convex piecewise-linear function to a given set of data, which can serve as an empirical modeling framework for circuit optimization via geometric programming. The method iteratively solves a series of linear optimization problems to minimize the fitting error. To reduce the fitting error in each iteration, an extra plane is added in the region where the largest error occurs. For verification, we apply the method to create transistor-level models in 90-nm complementary metal-oxide-semiconductor technology. Numerical results indicate that the proposed method can generate process-dependent transistor-level models with reasonable modeling accuracy.

We propose a convex optimization method for maximum likelihood estimation of autoregressive models, subject to conditional independence constraints. This problem is an extension to times series of the classical covariance selection problem in graphical modeling. The conditional independence constraints impose quadratic equalities on the autoregressive model parameters, which makes the maximum likelihood estimation problem nonconvex and difficult to solve. We formulate a convex relaxation and prove that it is exact when the sample covariance matrix is block-Toeplitz. We also observe experimentally that in practice the relaxation is exact under much weaker conditions. We discuss applications to topology selection in graphical models of time series, by enumerating all possible topologies, and ranking them using information-theoretic model selection criteria. The method is illustrated by an example of air pollution data.

We present a distributed algorithm for node localization based on the Gauss-Newton method. In this algorithm, each node updates its own location estimate using the pairwise distance measurements and the local information it receives from the neighboring nodes. Once the location estimate is updated, the sensor node broadcasts the updated estimate to all the neighboring nodes. A distributed and scalable local scheduling algorithm for updating nodes in the network is presented to avoid the use of the global coordinator or a routing loop. We analytically show that the proposed distributed algorithm converges under certain practical assumptions of the network. The performance of the algorithm is evaluated using both simulation and experimental results. Quantitative comparisons among different distributed algorithms are also presented.

We introduce mean excess delay as a statistical measure of circuit delay in the presence of parameter variations. The β-mean excess delay is defined as the expected delay of the circuits that exceed the β-quantile of the delay, so it is always an upper bound on the β-quantile. However, in contrast to the β-quantile, it preserves the convexity properties of the underlying delay distribution. We apply the β-mean excess delay to the circuit sizing problem, and use it to minimize the delay quantile over the gate sizes. We use the Analytic Centering Cutting Plane Method to perform the minimization and apply this sizing to the ISCAS ‘85 benchmarks. Depending on the structure of the circuit, it can make significant improvements on the 95%-quantile.

In this paper, we propose a distributed parallel support vector machine (DPSVM) training mechanism in a configurable network environment for distributed data mining. The basic idea is to exchange support vectors among a strongly connected network (SCN) so that multiple servers may work concurrently on distributed data set with limited communication cost and fast training speed. The percentage of servers that can work in parallel and the communication overhead may be adjusted through network configuration. The proposed algorithm further speeds up through online implementation and synchronization. We prove that the global optimal classifier can be achieved iteratively over an SCN. Experiments on a real-world data set show that the computing time scales well with the size of the training data for most networks. Numerical results show that a randomly generated SCN may achieve better performance than the state of the art method, cascade SVM, in terms of total training time.

A wide variety of optimization problems involving nonnegative polynomials or trigonometric polynomials can be formulated as convex optimization problems by expressing (or relaxing) the constraints using sum-of-squares representations. The semidefinite programming problems that result from this formulation are often difficult to solve due to the presence of large auxiliary matrix variables. In this paper we extend a recent technique for exploiting structure in semidefinite programs derived from sum-of-squares expressions to multivariate trigonometric polynomials. The technique is based on an equivalent formulation using discrete Fourier transforms and leads to a very substantial reduction in the computational complexity. Numerical results are presented and a comparison is made with general-purpose semidefinite programming algorithms. As an application, we consider a two-dimensional FIR filter design problem.

In this paper, an energy minimization problem for a quadrature amplitude modulation (QAM) system with automatic repeat request (ARQ) is considered. We formulate an optimization problem with constellation size and transmit power as the variables. We give an efficient and accurate geometric programming (GP) approximation to the problem and illustrate the solution using a numerical example. We learn that the transmit power or equivalently bit error rate (BER) should be carefully chosen for minimal energy. Our analysis provides guidelines for setting the BER in an energy optimal way for various packet lengths.

This paper presents a feasible study of fully-integrated switching voltage regulators for power-optimized systems-on-chip (SoCs). In order to evaluate the power efficiency across a number of design variables, a compact macro-model of a regulator is created and validated. A key focus of the study is on the characteristics of the active and passive devices that are needed in order to maximize the efficiency of an on-chip regulator. With the macro-model, geometric programming is used to find the optimal characteristics for a given set of constraints such as load condition, process technology, and area. The achievable efficiencies for various current loads and across a range of technologies from 0.35-mum to 90-nm CMOS process are analyzed. The power efficiency is found to be strongly dependent on the inductor technology and over 70% efficiency is possible with advanced inductor technologies.

Abstract — Trade-off curves for the exact and the relaxed QoS routing problem are presented and discussed. In addition, an efficient parametric linear programming algorithm to compute the trade-off curve of the relaxed problem is given. Trade-off curves enable a network operator to choose the set of constraints according to its QoS portfolio and are useful in the design of the network. In particular, the trade-off curves represent for the operator’s network the possible basic feasible solutions that can be computed rapidly. In some sense, we reverse the QoS routing problem by giving the network operator the means to advertise an appropriate set of QoS constraints for its network. Instead of offering the user the freedom to require desirable endto-end QoS levels from the operator, the user now can choose from the advertised QoS constraints portfolio those that best fit his application. The trade-off curve of the approximate, relaxed problem also gives insight in the computational complexity of QoS routing. I.

We consider the problem of evaluating the probability of error of binary communication systems in the presence of additive noise and intersymbol interferences whose statistics are inexactly known due to the estimation errors of the channel coefficients. We present a new method using semidefinite programming to evaluate tight bounds on the error probability based on the upper and lower bounds on the moments of those interferences. Numerical results are provided and compared with a previously published technique.

We present techniques for improving the accuracy of geometric-programming (GP) based analog circuit design optimization. We describe major sources of discrepancies between the results from optimization and simulation, and propose several methods to reduce the error. Device modeling based on convex piecewise-linear (PWL) function fitting is introduced to create accurate active and passive device models. We also show that in selected cases GP can enable nonconvex constraints such as bias constraints using monotonicity, which help reduce the error. Lastly, we suggest a simple method to take the modeling error into account in GP optimization, which results in a robust design over the inherent errors in GP device models. Two-stage operational amplifier and on-chip spiral inductor designs are given as examples to demonstrate the presented ideas.

We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.

We describe efficient interior-point methods for the design of FIR filters with constraints on the magnitude spectrum, for example, piecewise-constant upper and lower bounds, and arbitrary phase. Several researchers have observed that problems of this type can be solved via convex optimization and spectral factorization. The associated optimization problems are usually solved via linear programming or, more recently, semidefinite programming. The semidefinite programming approach is more accurate but also more expensive, because it requires the introduction of a large number of auxiliary variables. We propose a more efficient method, based on convex optimization duality, and on interior-point methods for problems with generalized inequalities.

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.

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 BSB (brain-state-in-a-box) neural network is restructured as a multivariable linear system with a nonlinear feedback. This reconstruction allows some well-developed techniques in the field of circuit and control theory to be used for resolving issues such as stability. The authors specifically consider the stability of the asymmetric BSB nets in terms of the nonexpansivity of the whole system and derive simple conditions to be satisfied by the weight matrix in order to guarantee the stability. It is seen that this framework can reproduce and generalize some of the previous results on the subject, like those previously developed by the authors (1989)

Some geometrically inspired concepts are studied for the identification of models for multivariable linear time-invariant systems from noisy input-output observations. Starting from a fundamental highly structured input-output matrix equation, it is shown how the singular value decomposition allows the order of the observable part of the system and its state-space model matrices to be estimated. Moreover, conditions for persistency of excitation of the inputs and the behavior of the algorithm when the data are perturbed by noise can easily be studied from a geometrical point of view. The singular values allow these concepts to be quantified. An example with an industrial plant identification is presented.>