Complementarity and Variational Inequalities

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

    Variational Convergence of Bifunctions: Motivating Applications

  • Alejandro Jofré
  • Roger J.B. Wets
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Game Theory Tags , , , , , , , , ,

    It’s shown that a number of variational problems can be cast as finding the maxinf-points (or minsup-points) of bivariate functions, coveniently abbreviated to bifunctions. These variational problems include: linear and nonlinear complementarity problems, fixed points, variational inequalities, inclusions, non-cooperative games, Walras and Nash equilibrium problems. One can then appeal to the theory of lopsided convergence … Read more

    On the Dynamic Stability of Electricity Markets

  • Mihai Anitescu
  • Victor M. Zavala
    • Categories Complementarity and Variational Inequalities, Dynamic Programming, Game Theory Tags , , , ,

    In this work, we present new insights into the dynamic stability of electricity markets. In particular, we discuss how short forecast horizons, incomplete gaming, and physical ramping constraints can give rise to stability issues. Using basic concepts of market efficiency, Lyapunov stability, and predictive control, we construct a new stabilizing market design. A numerical case … Read more

    A Continuous Dynamical Newton-Like Approach to Solving Monotone Inclusions

  • Hédy Attouch
  • Benar Fux Svaiter
    • Categories Complementarity and Variational Inequalities, Infinite Dimensional Optimization, Systems governed by Differential Equations Optimization Tags , , , , , , , ,

    We introduce non-autonomous continuous dynamical systems which are linked to Newton and Levenberg-Marquardt methods. They aim at solving inclusions governed by maximal monotone operators in Hilbert spaces. Relying on Minty representation of maximal monotone operators as lipschitzian manifolds, we show that these dynamics can be formulated as first-order in time differential systems, which are relevant … Read more

    A Parallel Inertial Proximal Optimization Method

  • Jean-Christophe Pesquet
  • Nelly Pustelnik
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , , , ,

    The Douglas-Rachford algorithm is a popular iterative method for finding a zero of a sum of two maximal monotone operators defined on a Hilbert space. In this paper, we propose an extension of this algorithm including inertia parameters and develop parallel versions to deal with the case of a sum of an arbitrary number of … Read more

    First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints

  • Chao Ding
  • Defeng Sun
  • Jane J. Ye
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We derive explicit expressions for the strong-, Mordukhovich- and Clarke- (S-, M- and C-)stationary conditions and give constraint … Read more

    The Split Variational Inequality Problem

  • Yair Censor
  • Aviv Gibali
  • Simeon Reich
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , ,

    We propose a new variational problem which we call the Split Variational Inequality Problem (SVIP). It entails finding a solution of one Variational Inequality Problem (VIP), the image of which under a given bounded linear transformation is a solution of another VIP. We construct iterative algorithms that solve such problems, under reasonable conditions, in Hilbert … Read more