Complementarity and Variational Inequalities

Extending the Reach of First-Order Algorithms for Nonconvex Min-Max Problems with Cohypomonotonicity

  • Ahmet Alacaoglu
  • Donghwan Kim
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonlinear Optimization, Stochastic Programming

    We focus on constrained, \(L\)-smooth, nonconvex-nonconcave min-max problems either satisfying \(\rho\)-cohypomonotonicity or admitting a solution to the \(\rho\)-weakly Minty Variational Inequality (MVI), where larger values of the parameter \(\rho>0\) correspond to a greater degree of nonconvexity. These problem classes include examples in two player reinforcement learning, interaction dominant min-max problems, and certain synthetic test problems on … Read more

    Krasnoselskii-Mann Iterations: Inertia, Perturbations and Approximation

  • Daniel Cortild
  • Juan Peypouquet
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags , , ,

    This paper is concerned with the study of a family of fixed point iterations combining relaxation with different inertial (acceleration) principles. We provide a systematic, unified and insightful analysis of the hypotheses that ensure their weak, strong and linear convergence, either matching or improving previous results obtained by analysing particular cases separately. We also show … Read more

    Weak convexity and approximate subdifferentials

  • Felipe Atenas
  • Wim van Ackooij
  • Claudia Sagastizábal
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Nonsmooth Optimization

    We explore and construct an enlarged subdifferential for weakly convex functions. The resulting object turns out to be continuous with respect to both the function argument and the enlargement parameter. We carefully analyze connections with other constructs in the literature and particularize to the weakly convex setting well-known variational principles. By resorting to the new … Read more

    On a Tractable Single-Level Reformulation of a Multilevel Model of the European Entry-Exit Gas Market with Market Power

  • Veronika Grimm
  • Julia Grübel
  • Martin Schmidt
  • Alexandra Schwartz
  • Gregor Zöttl
  • Ann-Kathrin Wiertz
    • Categories Complementarity and Variational Inequalities, Energy Tags , , ,

    We propose a framework that allows to quantitatively analyze the interplay of the different agents involved in gas trade and transport in the context of the European entry-exit system. Previous contributions have focused on the case of perfectly competitive buyers and sellers of gas, which allows to replace the respective market equilibrium problem by a … Read more

    M-stationarity of Local Minimizers of MPCCs and Convergence of NCP-based Methods

  • Kexin Wang
  • Lorenz T. Biegler
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    This paper focuses on solving mathematical programs with complementarity constraints (MPCCs) without assuming MPCC-LICQ or lower level strict complementarity at a solution. We show that a local minimizer of an MPCC is “piecewise M-stationary” under MPCC-GCQ; furthermore, every weakly stationary point of an MPCC is B-stationary if MPCC-ACQ holds. For the Bounding Algorithm proposed in … Read more

    Continuous Selections of Solutions to Parametric Variational Inequalities

  • Shaoning Han
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities Tags , , ,

    This paper studies the existence of a (Lipschitz) continuous (single-valued) solution function of parametric variational inequalities under functional and constraint perturbations. At the most elementary level, this issue can be explained from classical parametric linear programming and its resolution by the parametric simplex method, which computes a solution trajectory of the problem when the objective … Read more

    Functions associated with the nonconvex second-order cone

  • Baha Alzalg
    • Categories Complementarity and Variational Inequalities, Cone Programming, Second-Order Cone Programming Tags , , ,

    The nonconvex second-order cone (nonconvex SOC for short) is a nonconvex extension to the convex second-order cone, in the sense that it consists of any vector divided into two sub-vectors for which the Euclidean norm of the first sub-vector is at least as large as the Euclidean norm of the second sub-vector. This cone can … Read more

    Bilevel Hyperparameter Optimization for Nonlinear Support Vector Machines

  • Alain Zemkoho
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization

    While the problem of tuning the hyperparameters of a support vector machine (SVM) via cross-validation is easily understood as a bilevel optimization problem, so far, the corresponding literature has mainly focused on the linear-kernel case. In this paper, we establish a theoretical framework for the development of bilevel optimization-based methods for tuning the hyperparameters of … Read more

    A Tutorial on Solving Single-Leader-Multi-Follower Problems using SOS1 Reformulations

  • Didier Aussel
  • Cecile Egea
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Game Theory Tags , , ,

    In this tutorial we consider single-leader-multi-follower games in which the models of the lower-level players have polyhedral feasible sets and convex objective functions. This situation allows for classic KKT reformulations of the separate lower-level problems, which lead to challenging single-level reformulations of MPCC type. The main contribution of this tutorial is to present a ready-to-use … Read more

    A new single-layer inverse-free fixed-time dynamical system for absolute value equations

  • Xin Han
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , ,

    In this technical note, a novel single-layer inverse-free fixed-time dynamical system (SIFDS) is proposed to address absolute value equations. The proposed SIFDS directly employs coefficient matrix and absolute value equation function that aims at circumventing matrix inverse operation and achieving fixed-time convergence. The equilibria of the proposed SIFDS is proved to be the unique solution … Read more