Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more
We describe a classof measures on second-order cones as a push-forward of the Cartesian product of a probabilistic measure on positive semi-line corresponding to Gamma distribution and the uniform measure on the sphere Citationreport, Department of Mathematics, University of Notre Dame, July, 2011ArticleDownload View PDF
This paper introduces the generalized forward-backward splitting algorithm for minimizing convex functions of the form $F + \sum_{i=1}^n G_i$, where $F$ has a Lipschitz-continuous gradient and the $G_i$’s are simple in the sense that their Moreau proximity operators are easy to compute. While the forward-backward algorithm cannot deal with more than $n = 1$ non-smooth … Read more
We present and discuss a method to relax sets described by finitely many smooth convex inequality constraints by the level set of a single smooth convex inequality constraint. Based on error bounds and Lipschitz continuity, special attention is paid to the maximal approximation error and a guaranteed safety margin. Our results allow to safely avoid … Read more
We propose a convergence analysis of accelerated forward-backward splitting methods for minimizing composite functions, when the proximity operator is not available in closed form, and is thus computed up to a certain precision. We prove that the $1/k^2$ convergence rate for the function values can be achieved if the admissible errors are of a certain … Read more
In this paper, we consider a job scheduling problem with random local generation, in which some jobs must be scheduled day-ahead while the others can be scheduled in a real time fashion. To capture the randomness of the local distributed generation, we develop a two-stage robust optimization model by assuming an uncertainty set without probability … Read more
In this paper we consider minimization problems with constraints. We will show that if the set of constraints is a Finslerian manifold of non positive flag curvature, and the objective function is di fferentiable and satisfi es the property Kurdyka-Lojasiewicz, then the proximal point method is naturally extended to solve that class of problems. We will prove … Read more
There are $n$ individual assets and $k$ of them are to be sold over two stages. The first-stage prices are known and the second-stage prices have a known distribution. The sell or hold problem (SHP) is to determine which assets are to be sold at each stage to maximize the total expected revenue. We show … Read more
We present inexact accelerated proximal point algorithms for minimizing a proper lower semicon- tinuous and convex function. We carry on a convergence analysis under different types of errors in the evaluation of the proximity operator, and we provide corresponding convergence rates for the objective function values. The proof relies on a generalization of the strategy … Read more
We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation [A. Frieze and M. Jerrum. Improved approximation algorithms for … Read more