By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2^{n}n^{\frac{5}{2}}), we prove that solving this n-dimensional linear optimization problem requires at least $2^n-1$ … Read more
We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given (close to one) probability, a system of randomly perturbed convex constraints. Our goal is to build a computationally tractable approximation of this (typically intractable) problem, i.e., an explicitly given convex optimization program with the feasible … Read more
A framework for proving global convergence for a class of nonlinear constraints infeasibility problem is presented without assuming that the Jacobian has full rank everywhere. The underlying method is based on the simple sufficient reduction criteria where trial points are accepted provided there is a sufficient decrease in the constraints violation function. The proposed methods … Read more
The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of … Read more
A systematic study of the proximity properties of Bregman distances is carried out. This investigation leads to the introduction of a new type of proximity operator which complements the usual Bregman proximity operator. We establish key properties of these operators and utilize them to devise a new alternating procedure for solving a broad class of … Read more
We study analyticity, differentiability, and semismoothness of Lowner’s operator and spectral functions under the framework of Euclidean Jordan algebras. In particular, we show that many optimization-related classical results in the symmetric matrix space can be generalized within this framework. For example, the metric projection operator over any symmetric cone defined in a Euclidean Jordan algebra … Read more
Both cutting plane methods and traditional decomposition methods are procedures that compute a bound on the optimal value of an integer linear program (ILP) by constructing an approximation to the convex hull of feasible solutions. This approximation is obtained by intersecting the polyhedron associated with the continuous relaxation, which has an explicit representation, with an … Read more
We present an overview of noncommercial software tools for the solution of mixed-integer linear programs (MILPs). We first review solution methodologies for MILPs and then present an overview of the available software, including detailed descriptions of eight software packages available under open source or other noncommercial licenses. Each package is categorized as a black box … Read more
We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more
This paper studies theoretical and practical properties of interior-penalty methods for mathematical programs with complementarity constraints. A framework for implementing these methods is presented, and the need for adaptive penalty update strategies is motivated with examples. The algorithm is shown to be globally convergent to strongly stationary points, under standard assumptions. These results are then … Read more