A Finitely Convergent Cutting Plane, and a Bender’s Decomposition Algorithm for Mixed-Integer Convex and Two-Stage Convex Programs using Cutting Planes

We consider a general mixed-integer convex program. We first develop an algorithm for solving this problem, and show its nite convergence. We then develop a finitely convergent decomposition algorithm that separates binary variables from integer and continuous variables. The integer and continuous variables are treated as second stage variables. An oracle for generating a parametric … Read more


We consider variational inequalities governed by strongly pseudomonotone vec- tor fields on Hadamard manifolds. The existence and uniqueness results of the solution, linear convergence, error estimates and finite convergence for sequences generated by a mod- ified projection method for solving variational inequalities are investigated. Some examples and numerical experiments are also given to illustrate our … Read more

Finite convergence of sum-of-squares hierarchies for the stability number of a graph

We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G) -1$ steps. Even the weaker conjecture claiming finite convergence is still open. … Read more

First-order methods for the impatient: support identification in finite time with convergent Frank-Wolfe variants

In this paper, we focus on the problem of minimizing a non-convex function over the unit simplex. We analyze two well-known and widely used variants of the Frank-Wolfe algorithm and first prove global convergence of the iterates to stationary points both when using exact and Armijo line search. Then we show that the algorithms identify … Read more

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence

The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first … Read more

Decomposition Algorithms with Parametric Gomory Cuts for Two-Stage Stochastic Integer Programs

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the L-shaped or Benders methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology … Read more

Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs

In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard … Read more