An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems

Our interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.     

Stability conditions for multiclass fluid queueing networks

We introduce a new method to investigate stability of work-conserving policies in multiclass queueing networks. The method decomposes feasible trajectories and uses linear programming to test stability. We show that this linear program is a necessary and sufficient condition for the stability of all work-conserving policies for multiclass fluid queueing networks with two stations. Furthermore, we find new sufficient conditions for the stability of multiclass queueing networks involving any number of stations and conjecture that these conditions are also necessary. Previous research had identified sufficient conditions through the use of a particular class of (piecewise linear convex) Lyapunov functions. Using linear programming duality, we show that for two-station systems the Lyapunov function approach is equivalent to ours and therefore characterizes stability exactly     

Constrained Stochastic LQC: A Tractable Approach

Despite the celebrated success of dynamic programming for optimizing quadratic cost functions over linear systems, such an approach is limited by its inability to tractably deal with even simple constraints. In this paper, we present an alternative approach based on results from robust optimization to solve the stochastic linear-quadratic control (SLQC) problem. In the unconstrained case, the problem may be formulated as a semidefinite optimization problem (SDP). We show that we can reduce this SDP to optimization of a convex function over a scalar variable followed by matrix multiplication in the current state, thus yielding an approach that is amenable to closed-loop control and analogous to the Riccati equation in our framework. We also consider a tight, second-order cone (SOCP) approximation to the SDP that can be solved much more efficiently when the problem has additional constraints. Both the SDP and SOCP are tractable in the presence of control and state space constraints; moreover, compared to the Riccati approach, they provide much greater control over the stochastic behavior of the cost function when the noise in the system is distributed normally.     

Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach

We propose a convex optimization approach to solving the nonparametric regression estimation problem when the underlying regression function is Lipschitz continuous. This approach is based on the minimization of the sum of empirical squared errors, subject to the constraints implied by Lipschitz continuity. The resulting optimization problem has a convex objective function and linear constraints, and as a result, is efficiently solvable. The estimated function computed by this technique, is proven to convergeto the underlying regression function uniformly and almost surely, when the sample size grows to infinity, thus providing a very strong form of consistency. Wealso propose a convex optimization approach to the maximum likelihood estimation of unknown parameters in statistical models, where the parameters depend continuously on some observable input variables. For a number of classical distributional forms, the objective function in the underlying optimization problem is convex and the constraints are linear. These problems are, therefore, also efficiently solvable.     

Sparse hierarchical regression with polynomials

Machine Learning - We present a novel method for sparse polynomial regression. We are interested in that degree r polynomial which depends on at most k inputs, counting at most $$\ell$$ monomial...     

Imputation of clinical covariates in time series

Machine Learning - Missing data is a common problem in longitudinal datasets which include multiple instances of the same individual observed at different points in time. We introduce a new...     

Robust multiperiod portfolio management in the presence of transaction costs

We study the viability of different robust optimization approaches to multiperiod portfolio selection. Robust optimization models treat future asset returns as uncertain coefficients in an optimization problem, and map the level of risk aversion of the investor to the level of tolerance of the total error in asset return forecasts. We suggest robust optimization formulations of the multiperiod portfolio optimization problem that are linear and computationally efficient. The linearity of the optimization problems is an advantage when complex additional requirements need to be imposed on the portfolio structure, e.g., limitations on positions in certain assets or tax constraints. We compare the performance of our robust formulations to the performance of the traditional single period mean-variance formulation frequently employed in the financial industry.     

Robust chirped mirrors

Optimized chirped mirrors may perform suboptimally, or completely fail to satisfy specifications, when manufacturing errors are encountered. We present a robust optimization method for designing these dispersion-compensating mirror systems that are used in ultrashort pulse lasers. Possible implementation errors in layer thickness are taken into account within an uncertainty set. The algorithm identifies worst-case scenarios with respect to reflectivity as well as group delay. An iterative update improves the robustness and warrants a high manufacturing yield, even when the encountered errors are larger than anticipated.     

Asymptotic buffer overflow probabilities in multiclassmultiplexers: an optimal control approach

We consider a multiclass multiplexer with support for multiple service classes and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among these classes, we seek the asymptotic (as the buffer size goes to infinity) tail of the buffer overflow probability for each dedicated buffer. We assume dependent arrival and service processes as is usually the case in models of bursty traffic. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We introduce a novel optimal control approach to address these problems. In particular, we relate the lower bound derivation to a deterministic optimal control problem, which we explicitly solve. Optimal state trajectories of the control problem correspond to typical congestion scenarios. We explicitly and in detail characterize the most likely modes of overflow. We specialize our results to the generalized processor sharing policy (GPS) and the generalized longest queue first policy (GLQF). The performance of strict priority policies is obtained as a corollary. We compare the GPS and GLQF policies and conclude that GLQF achieves smaller overflow probabilities than GPS for all arrival and service processes for which our analysis holds. Our results have important implications for traffic management of high-speed networks and can be used as a basis for an admission control mechanism which guarantees a different loss probability for each class