finite convergence

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

  • Fengqiao Luo
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    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

    VARIATIONAL INEQUALITIES GOVERNED BY STRONGLY PSEUDOMONOTONE VECTOR FIELDS ON HADAMARD MANIFOLDS

  • Nguyen Thai An
  • Luong Nguyen
  • Nguyen Thu
    • Categories Complementarity and Variational Inequalities Tags , , , , ,

    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

  • Monique Laurent
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    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

  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Samuel Rota Bulo
    • Categories Constrained Nonlinear Optimization Tags , , ,

    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

  • Xiaojun Chen
  • Zhaosong Lu
    • Categories Convex Optimization, Nonsmooth Optimization, Quadratic Programming Tags , , , ,

    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

  • Dinakar Gade
  • Simge Küçükyavuz
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags , , , , ,

    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

  • Binyuan Chen
  • Simge Küçükyavuz
  • Suvrajeet Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    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