The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more
The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, … Read more
Up to orthogonal transformation, a solid closed convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is the epigraph of a nonnegative sublinear function $f:\mathbb{R}^n\to \mathbb{R}$. This work explores the link between the geometric properties of $K$ and the analytic properties of $f$. Citation JOURNAL OF CONVEX ANALYSIS, 2011, in press. Article Download View Epigraphical cones … Read more
This is the second part of a work devoted to the theory of epigraphical cones and their applications. A convex cone $K$ in the Euclidean space $\mathbb{R}^{n+1}$ is an epigraphical cone if it can be represented as epigraph of a nonnegative sublinear function $f: \mathbb{R}^n\to \mathbb{R}$. We explore the link between the geometric properties of … Read more
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the … Read more
Kitahara and Mizuno (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the … Read more
We extend the target map, together with the weighted barriers and the notions of weighted analytic centers, from linear programming to general convex conic programming. This extension is obtained from a novel geometrical perspective of the weighted barriers, that views a weighted barrier as a weighted sum of barriers for a strictly decreasing sequence of … Read more
The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more
In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees … Read more
We provide convergent hierarchies for the cone C of copositive matrices and its dual, the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for C (resp. for its dual), thus complementing previous inner (resp. outer) approximations for C (for its dual). In … Read more