We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost … Read more
We discuss an application of the well-known Multiplicative Weights Update (MWU) algorithm to non-convex and mixed-integer nonlinear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of … Read more
Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more
We propose a framework for sensitivity analysis of linear programs (LPs) in minimiza- tion form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties … Read more
In this note we show that multiple solutions exist for the production-inventory example in the seminal paper on adjustable robust optimization in [2]. All these optimal robust solutions have the same worst-case objective value, but the mean objective values differ up to 21.9% and for individual realizations this difference can be up to 59.4%. We … Read more
We establish connections between the facial reduction algorithm of Borwein and Wolkowicz and the self-dual homogeneous model of Goldman and Tucker when applied to conic optimization problems. Specifically, we show the self-dual homogeneous model returns facial reduction certificates when it fails to return a primal-dual optimal solution or a certificate of infeasibility. Using this observation, … Read more
A new method is proposed for solving optimization problems with equality constraints and bounds on the variables. In the spirit of Sequential Quadratic Programming and Sequential Linearly-Constrained Programming, the new method approximately solves, at each iteration, an equality-constrained optimization problem. The bound constraints are handled in outer iterations by means of an Augmented Lagrangian scheme. … Read more
The choice of a risk measure reflects a subjective preference of the decision maker in many managerial, or real world economic problem formulations. To evaluate the impact of personal preferences it is thus of interest to have comparisons with other risk measures at hand. This paper develops a framework for comparing different risk measures. We … Read more
Many uncertainty sets encountered in control systems analysis and design can be expressed in terms of semialgebraic sets, that is as the intersection of sets described by means of polynomial inequalities. Important examples are for instance the solution set of linear matrix inequalities or the Schur/Hurwitz stability domains. These sets often have very complicated shapes … Read more
This paper presents an approach to non-stationary policy search for finite-horizon, discrete-time Markovian decision problems with large state spaces, constrained action sets, and a risk-sensitive optimality criterion. The methodology relies on modeling time variant policy parameters by a non-parametric response surface model for an indirect parametrized policy motivated by the Bellman equation. Through the interpolating … Read more