Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for generalized variational inequalities with applications to saddle point and convex optimization problems

  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization Tags , , , , ,

    In this paper, we consider both a variant of Tseng’s modified forward-backward splitting method and an extension of Korpelevich’s method for solving generalized variational inequalities with Lipschitz continuous operators. By showing that these methods are special cases of the hybrid proximal extragradient (HPE) method introduced by Solodov and Svaiter, we derive iteration-complexity bounds for them … Read more

    Local Search Approximation Algorithms for the Complement of the Min-hBcCut Problems

  • Wenxing Zhu
    • Categories Approximation Algorithms Tags , ,

    Min-$k$-cut is the problem of partitioning vertices of a given graph or hypergraph into $k$ subsets such that the total weight of edges or hyperedges crossing different subsets is minimized. For the capacitated min-$k$-cut problem, each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on … Read more

    Cutting Stock with Bounded Open Stacks: a New Integer Linear Programming Model

  • Claudio Arbib
  • Fabrizio Marinelli
  • Paolo Ventura
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags ,

    We address a 1-dimensional cutting stock problem where, in addition to trim-loss minimization, we require that the set of cutting patterns forming the solution can be sequenced so that the number of stacks of parts maintained open throughout the process never exceeds a given $s$. For this problem, we propose a new integer linear programming … Read more

    Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: a Generic Algorithmic Framework

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Data-Mining, Stochastic Programming Tags , , , , ,

    In this paper we present a generic algorithmic framework, namely, the accelerated stochastic approximation (AC-SA) algorithm, for solving strongly convex stochastic composite optimization (SCO) problems. While the classical stochastic approximation (SA) algorithms are asymptotically optimal for solving differentiable and strongly convex problems, the AC-SA algorithm, when employed with proper stepsize policies, can achieve optimal or … Read more

    Feasible and accurate algorithms for covering semidefinite programs

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we describe an algorithm to approximately solve a class of semidefinite programs called covering semidefinite programs. This class includes many semidefinite programs that arise in the context of developing algorithms for important optimization problems such as sparsest cut, wireless multicasting, and pattern classification. We give algorithms for covering SDPs whose dependence on … Read more

    Optimality Conditions and Duality for Nonsmooth Multiobjective Optimization Problems with Cone Constraints and Applications

  • Jiawei Chen
  • Zhong-Ping Wan
  • Zheng Yue
    • Categories Nonsmooth Optimization, Other Topics Tags , , , , , ,

    In this work, a nonsmooth multiobjective optimization problem involving generalized invexity with cone constraints and Applications (for short, (MOP)) is considered. The Kuhn-Tucker necessary and sufficient conditions for (MOP) are established by using a generalized alternative theorem of Craven and Yang. The relationship between weakly efficient solutions of (MOP) and vector valued saddle points of … Read more

    New concave penalty functions for improving the Feasibility Pump

  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Linear Programming, Nonlinear Optimization Tags , , ,

    Mixed-Integer optimization represents a powerful tool for modeling many optimization problems arising from real-world applications. The Feasibility pump is a heuristic for finding feasible solutions to mixed integer linear problems. In this work, we propose a new feasibility pump approach using concave non-differentiable penalty functions for measuring solution integrality. We present computational results on binary … Read more

    Coverings and Matchings in r-Partite Hypergraphs

  • Douglas S. Altner
  • J. Paul Brooks
    • Categories 0-1 Programming, Graphs and Matroids Tags , , , ,

    Ryser’s conjecture postulates that, for $r$-partite hypergraphs, $\tau \leq (r-1) \nu$ where $\tau$ is the covering number of the hypergraph and $\nu$ is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where $r \leq 5$. In this paper, we … Read more

    A splitting method for separate convex programming with linking linear constraints

  • Bingsheng He
  • Min Tao
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    We consider the separate convex programming problem with linking linear constraints, where the objective function is in the form of the sum of m individual functions without crossed variables. The special case with m=2 has been well studied in the literature and some algorithms are very influential, e.g. the alternating direction method. The research for … Read more

    A Faster Algorithm for Quasi-convex Integer Polynomial Optimization

  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    We present a faster exponential-time algorithm for integer optimization over quasi-convex polynomials. We study the minimization of a quasi-convex polynomial subject to s quasi-convex polynomial constraints and integrality constraints for all variables. The new algorithm is an improvement upon the best known algorithm due to Heinz (Journal of Complexity, 2005). A lower time complexity is … Read more