Complementarity and Variational Inequalities

Algorithms for Bilevel Pseudomonotone Variational Inequality Problems

  • Bui Van Dinh
  • Le Dung Muu
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags , , , ,

    We propose easily implementable algorithms for minimizing the norm with pseudomonotone variational inequality constraints. This bilevel problem arises in the Tikhonov regularization method for pseudomonone variational inequalities. Since the solution set of the lower variational inequality is not given explicitly, the available methods of mathematical programming and variational inequality can not be applied directly. With … Read more

    A lifting method for generalized semi-infinite programs based on lower level Wolfe duality

  • Moritz Diehl
  • Oliver Stein
  • Boris Houska
  • Paul Steuermann
    • Categories Complementarity and Variational Inequalities, Robust Optimization, Semi-infinite Programming Tags , , , ,

    This paper introduces novel numerical solution strategies for generalized semi-infinite optimization problems (GSIP), a class of mathematical optimization problems which occur naturally in the context of design centering problems, robust optimization problems, and many fields of engineering science. GSIPs can be regarded as bilevel optimization problems, where a parametric lower-level maximization problem has to be … Read more

    A Family of Newton Methods for Nonsmooth Constrained Systems with Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We propose a new family of Newton-type methods for the solution of constrained systems of equations. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, local, quadratic convergence to a solution of the system of equations can be established. We show that as particular instances of the method we obtain inexact … Read more

    A Class of Dantzig-Wolfe Type Decomposition Methods for Variational Inequality Problems

  • Juan Pablo Luna
  • Claudia Sagastizábal
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags ,

    We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with set-valued or nonmonotone operators, as well as various kinds of approximations in the subproblems of the functions and derivatives in the single-valued … Read more

    An LP-Newton Method: Nonsmooth Equations, KKT Systems, and Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We define a new Newton-type method for the solution of constrained systems of equations and analyze in detail its properties. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, the method converges locally quadratically to a solution of the system of equations, thus filling an important gap in the existing theory. … Read more

    Weak and Strong Convergence of Algorithms for the Split Common Null Point Problem

  • Charles Byrne
  • Yair Censor
  • Aviv Gibali
  • Simeon Reich
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonlinear Optimization

    We introduce and study the Split Common Null Point Problem (SCNPP) for set-valued maximal monotone mappings in Hilbert space. This problem generalizes our Split Variational Inequality Problem (SVIP) [Y. Censor, A. Gibali and S. Reich, Algorithms for the split variational inequality problem, Numerical Algorithms, accepted for publication, DOI 10.1007/s11075-011-9490-5]. The SCNPP with only two set-valued … Read more

    On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators

  • Bingsheng He
    • Categories Complementarity and Variational Inequalities, Convex Optimization Tags , ,

    Recently, Nemirovski’s analysis indicates that the extragradient method has the $O(1/t)$ convergence rate for variational inequalities with Lipschitz continuous monotone operators. For the same problems, in the last decades, we have developed a class of Fej\’er monotone projection and contraction methods. Until now, only convergence results are available to these projection and contraction methods, though … Read more

    Iteration-Complexity of a Newton Proximal Extragradient Method for Monotone Variational Inequalities and Inclusion Problems

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

    In a recent paper by Monteiro and Svaiter, a hybrid proximal extragradient framework has been used to study the iteration-complexity of a first-order (or, in the context of optimization, second-order) method for solving monotone nonlinear equations. The purpose of this paper is to extend this analysis to study a prox-type first-order method for monotone smooth … Read more

    The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD

  • Ilan Adler
  • Sushil Verma
    • Categories Complementarity and Variational Inequalities Tags , , , ,

    We present a single sufficient condition for the processability of the Lemke algorithm for semimonotone Linear Complementarity problems (LCP) which unifies several sufficient conditions for a number of well known subclasses of semimonotone LCPs. In particular, we study the close relationship of these problems to the complexity class PPAD. Next, we show that these classes … Read more

    Stochastic Variational Inequalities:Residual Minimization Smoothing/Sample Average approximations

  • Xiaojun Chen
  • Roger J.B. Wets
  • Yanfang Zhang
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    The stochastic variational inequality (SVI) has been used widely, in engineering and economics, as an effective mathematical model for a number of equilibrium problems involving uncertain data. This paper presents a new expected residual minimization (ERM) formulation for a class of SVI. The objective of the ERM-formulation is Lipschitz continuous and semismooth which helps us … Read more