Large-sized extended formulations have the potential for providing high-quality bounds on some combinatorial optimization problems where the natural formulations perform poorly. This chapter discusses the use of some families of cuts that have been recently applied on extended formulations that are obtained by the discretization of the continuous variables occurring in the natural formulation of … Read more
The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an … Read more
We introduce and study the Split Common Null Point Problem (SCNPP) for set-valued maximal monotone mappings in Hilbert space. This problem generalizes our Split Variational Inequality Problem (SVIP) [Y. Censor, A. Gibali and S. Reich, Algorithms for the split variational inequality problem, Numerical Algorithms, accepted for publication, DOI 10.1007/s11075-011-9490-5]. The SCNPP with only two set-valued … Read more
Many derivative-free methods for constrained problems are not efficient for minimizing functions on “thin” domains. Other algorithms, like those based on Augmented Lagrangians, deal with thin constraints using penalty-like strategies. When the constraints are computationally inexpensive but highly nonlinear, these methods spend many potentially expensive objective function evaluations motivated by the difficulties of improving feasibility. … Read more
Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … 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 Citation report, Department of Mathematics, University of Notre Dame, July, 2011 Article Download View Sampling with respect to a class of measures … Read more
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
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
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