The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more
Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are … Read more
We present a clustering-based preconditioning strategy for KKT systems arising in stochastic programming within an interior-point framework. The key idea is to perform adaptive clustering of scenarios (inside-the-solver) based on their influence on the problem as opposed to cluster scenarios based on problem data alone, as is done in existing (outside-thesolver) approaches. We derive spectral … Read more
Motivated by the need to better understand the properties of sparse cutting-planes used in mixed integer programming solvers, the paper [1] studied the idealized problem of how well a polytope is approximated by the use of sparse valid inequalities. As an extension to this work, we study the following “less idealized” questions in this pa- … Read more
In this paper we discuss the complexity of a dynamic spectrum management problem within a multi-user communication system with K users and N available tones. In this problem a common utility function is optimized. In particular, so called min-rate, harmonic mean and geometric mean utility functions are considered. The complexity of the optimization problems with … Read more
We study the error introduced in the solution of an optimal control problem with first order state constraints, for which the trajectories are approximated with a classical Euler scheme. We obtain order one approximation results in the $L^\infty$ norm (as opposed to the order 2/3 obtained in the literature). We assume either a strong second … Read more
In traditional thinking, an arbitrageur will trade immediately once an arbitrage opportunity appears. Is this the best strategy for the arbitrageur or it is even better to wait for the best time to trade so as to achieve the maximum pro fit? To answer this question, this paper studies the optimal trading strategies of an arbitrageur … Read more
We introduce a family of subadditive functions called Generator Functions for mixed integer linear programs. These functions were previously defined for pure integer programs with non-negative entries by Klabjan [13]. They are feasible in the subadditive dual and we show that they are enough to achieve strong duality. Several properties of the functions are shown. … Read more
Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook, Kannan and Schrijver (1990) showed that the split closure of a rational polyhedron $P$ is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We … Read more
The usability of hub location models heavily depends on an appropriate modelling approach for the economies of scale. Realistic hub location models require more sophisticated transport cost structures than the traditional flow-independent discount. We develop a general modelling scheme for such problems allowing the definition of complicated (non-linear) costs and constraints; its structure allows an … Read more