variational inequality

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

    Alternating proximal algorithms for constrained variational inequalities. Application to domain decomposition for PDE’s

  • Hédy Attouch
  • A Cabot
  • Pierre Frankel
  • Juan Peypouquet
    • Categories Convex Optimization Tags , , , , ,

    Let $\cX,\cY,\cZ$ be real Hilbert spaces, let $f : \cX \rightarrow \R\cup\{+\infty\}$, $g : \cY \rightarrow \R\cup\{+\infty\}$ be closed convex functions and let $A : \cX \rightarrow \cZ$, $B : \cY \rightarrow \cZ$ be linear continuous operators. Let us consider the constrained minimization problem $$ \min\{f(x)+g(y):\quad Ax=By\}.\leqno (\cP)$$ Given a sequence $(\gamma_n)$ which tends toward … Read more

    The unified framework of some proximal-based decomposition methods for monotone variational inequalities with separable structure

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Complementarity and Variational Inequalities Tags , , , ,

    Some existing decomposition methods for solving a class of variational inequalities (VI) with separable structures are closely related to the classical proximal point algorithm, as their decomposed sub-VIs are regularized by proximal terms. Differing in whether the generated sub-VIs are suitable for parallel computation, these proximal-based methods can be categorized into the parallel decomposition methods … Read more

    On approximate KKT condition and its extension to continuous variational inequalities

  • Gabriel Haeser
  • María Laura Schuverdt
    • Categories Nonlinear Optimization Tags , ,

    In this work we introduce a necessary natural sequential Approximate-Karush-Kuhn-Tucker (AKKT) condition for a point to be a solution of a continuous variational inequality problem without constraint quali cations, and we prove its relation with the Approximate Gradient Projection condition (AGP) of Garciga-Otero and Svaiter. We also prove that a slight variation of the AKKT condition … Read more

    On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean

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

    In this paper we analyze the iteration-complexity of the hybrid proximal extragradient (HPE) method for finding a zero of a maximal monotone operator recently proposed by Solodov and Svaiter. One of the key points of our analysis is the use of new termination criteria based on the $\varepsilon$-enlargement of a maximal monotone operator. The advantage … Read more

    Proximal-like contraction methods for monotone variational inequalities in a unified framework

  • Bingsheng He
  • Lizhi Liao
  • Xiang Wang
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Convex Optimization Tags , ,

    Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. To solve the subproblems of these algorithms, the projection method takes the iteration in form of $u^{k+1} = P_{\Omega}[u^k-\alpha_k d^k]$. Interestingly, many of them can be paired such that $%\exists \tilde{u}^k, \tilde{u}^k = P_{\Omega}[u^k – \beta_kF(v^k)] = … Read more

    Impulsive Optimal Control of Hybrid Finite-Dimensional Lagrangian Systems

  • Kerim Yunt
    • Categories Complementarity and Variational Inequalities, Control Applications, Nonsmooth Optimization Tags , ,

    The scope of this dissertation addresses numerical and theoretical issues in the impulsive control of hybrid finite-dimensional Lagrangian systems. In order to treat these aspects, a modeling framework is presented based on the measure-differential inclusion representation of the Lagrangian dynamics. The main advantage of this representation is that it enables the incorporation of set-valued force … Read more

    The Variational Inequality Approach for Solving Spatial Auction Problems with Joint Constraints

  • Igor V. Konnov
    • Categories Complementarity and Variational Inequalities, Finance and Economics Tags , , ,

    We consider a problem of managing a system of spatially distributed markets under capacity and balance constraints and show that solutions of a variational inequality enjoy auction principle properties implicitly. This enables us to develop efficient tools both for derivation of existence and uniqueness results and for creation of solution methods. Citation Kazan University, Kazan, … Read more

    Using exact penalties to derive a new equation reformulation of KKT systems associated to variational inequalities

  • Thiago A. de André
  • Paulo J. S. Silva
    • Categories Complementarity and Variational Inequalities Tags , , ,

    In this paper, we present a new reformulation of the KKT system associated to a variational inequality as a semismooth equation. The reformulation is derived from the concept of differentiable exact penalties for nonlinear programming. The best results are presented for nonlinear complementarity problems, where simple, verifiable, conditions ensure that the penalty is exact. We … Read more

    Stochastic Mathematical Programs with Equilibrium Constraints, Modeling and Sample Average Approximation

  • Alexander Shapiro
  • Huifu Xu
    • Categories Complementarity and Variational Inequalities, Stochastic Programming Tags , , , , , ,

    In this paper, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate piecewise structure and directional differentiability of both — the lower level equilibrium solution and objective integrant. We show almost sure convergence of optimal values, optimal solutions … Read more