On Equilibrium Problems Involving Strongly Pseudomonotone Bifunctions

  • Le Dung Muu
  • V. Quy Nguyen
    • Categories Generalized Convexity/Monoticity Tags , ,

    We study equilibrium problems with strongly pseudomonotone bifunctions in real Hilbert spaces. We show the existence of a unique solution. We then propose a generalized strongly convergent projection method for equilibrium problems with strongly pseudomonotone bifunctions. The proposed method uses only one projection without requiring Lipschitz continuity. Application to variational inequalities is discussed. CitationInstitute of … Read more

    A polynomial projection algorithm for linear programming

  • Sergei Chubanov
    • Categories Linear Programming

    We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either fi nds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the … Read more

    A Generalized Proximal Point Algorithm and its Convergence Rate

  • Etienne Corman
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , ,

    We propose a generalized proximal point algorithm (PPA), in the generic setting of finding a zero point of a maximal monotone operator. In addition to the classical PPA, a number of benchmark operator splitting methods in PDE and optimization literatures such as the Douglas-Rachford splitting method, Peaceman-Rachford splitting method, alternating direction method of multipliers, generalized … Read more

    A branch and cut algorithm for minimum spanning trees under conflict constraints

  • Phillippe Samer
  • Sebastián Urrutia
    • Categories 0-1 Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , ,

    We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more

    A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions

  • Frank Fischer
  • Christoph Helmberg
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , ,

    An algorithmic framework is presented for optimising general convex functions by non synchronised parallel processes. Each process greedily picks a suitable adaptive subset of coordinates and runs a bundle method on a corresponding restricted problem stopping whenever a descent step is encountered or predicted decrease is reduced sufficiently. No prior knowledge on the dependencies between … Read more

    New Analysis and Results for the Conditional Gradient Method

  • Robert M. Freund
  • Paul Grigas
    • Categories Convex Optimization Tags , , , ,

    We present new results for the conditional gradient method (also known as the Frank-Wolfe method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial … Read more

    An approximation scheme for a class of risk-averse stochastic equilibrium problems

  • Juan Pablo Luna
  • Claudia Sagastizábal
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Stochastic Programming Tags , , , , ,

    We consider two models for stochastic equilibrium: one based on the variational equilibrium of a generalized Nash game, and the other on the mixed complementarity formulation. Each agent in the market solves a one-stage risk-averse optimization problem with both here-and-now (investment) variables and (production) wait-and-see variables. A shared constraint couples almost surely the wait-and-see decisions … Read more

    Extended Linear Formulation for Binary Quadratic Problems

  • Fabio Furini
  • Emiliano Traversi
    • Categories 0-1 Programming, Quadratic Programming

    In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more

    Sample Average Approximation Method for Compound Stochastic Optimization Problems

  • Yuri M. Ermoliev
  • Vladimir I. Norkin
    • Categories Statistics, Stochastic Programming

    The paper studies stochastic optimization (programming) problems with compound functions containing expectations and extreme values of other random functions as arguments. Compound functions arise in various applications. A typical example is a variance function of nonlinear outcomes. Other examples include stochastic minimax problems, econometric models with latent variables, and multilevel and multicriteria stochastic optimization problems. … Read more

    On Minimal Valid Inequalities for Mixed Integer Conic Programs

  • Fatma Kılınç-Karzan
    • Categories (Mixed) Integer Nonlinear Programming

    We study mixed integer conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient … Read more