Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first … Read more

Decomposition in Integer Programming

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

On the Relationship between Bilevel Decomposition Algorithms and Direct Interior-Point Methods

Engineers have been using \emph{bilevel decomposition algorithms} to solve certain nonconvex large-scale optimization problems arising in engineering design projects. These algorithms transform the large-scale problem into a bilevel program with one upper-level problem (the master problem) and several lower-level problems (the subproblems). Unfortunately, there is analytical and numerical evidence that some of these commonly used … Read more

A Local Convergence Analysis of Bilevel Decomposition Algorithms

Decomposition algorithms exploit the structure of large-scale optimization problems by breaking them into a set of smaller subproblems and a coordinating master problem. Cutting-plane methods have been extensively used to decompose convex problems. In this paper, however, we focus on certain nonconvex problems arising in engineering. Engineers have been using bilevel decomposition algorithms to tackle … Read more

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

Gradient Projection Methods for Quadratic Programs and Applications in Training Support Vector Machines

Gradient projection methods based on the Barzilai-Borwein spectral steplength choices are considered for quadratic programming problems with simple constraints. Well known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches the behavior of different combinations of the two spectral steplengths is investigated. A nw adaptive stplength alternating rule is proposed, … Read more

Self-scaled barrier functions on symmetric cones and their classification

Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains … Read more