Complementarity and Variational Inequalities

On the Relation Between Affinely Adjustable Robust Linear Complementarity and Mixed-Integer Linear Feasibility Problems

  • Martin Schmidt
  • Christian Biefel
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , ,

    We consider adjustable robust linear complementarity problems and extend the results of Biefel et al.~(2022) towards convex and compact uncertainty sets. Moreover, for the case of polyhedral uncertainty sets, we prove that computing an adjustable robust solution of a given linear complementarity problem is equivalent to solving a properly chosen mixed-integer linear feasibility problem. Article … Read more

    A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

  • Horländer Andreas
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities Tags , , ,

    We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more

    A Ramsey-Type Equilibrium Model with Spatially Dispersed Agents

  • Leonhard Frerick
  • Georg Müller-Fürstenberger
  • Martin Schmidt
  • Max Späth
    • Categories Complementarity and Variational Inequalities, Finance and Economics Tags , , ,

    We present a spatial and time-continuous Ramsey-type equilibrium model for households and firms that interact on a spatial domain to model labor mobility in the presence of commuting costs. After discretization in space and time, we obtain a mixed complementarity problem that represents the spatial equilibrium model. We prove existence of equilibria using the theory … Read more

    Monotonicity and Complexity of Multistage Stochastic Variational Inequalities

  • Jie Jiang
  • Hailin Sun
    • Categories Complementarity and Variational Inequalities, Stochastic Programming Tags , , ,

    In this paper, we consider multistage stochastic variational inequalities (MSVIs). First, we give multistage stochastic programs and multistage multi-player noncooperative game problems as source problems. After that, we derive the monotonicity properties of MSVIs under less restrictive conditions. Finally, the polynomial rate of convergence with respect to sample sizes between the original problem and its … Read more

    BilevelJuMP.jl: Modeling and Solving Bilevel Optimization in Julia

  • Joaquim Dias Garcia
  • Guilherme Bodin
  • Alexandre Street
    • Categories Complementarity and Variational Inequalities, Modeling Languages and Systems, Optimization Software and Modeling Systems Tags , , , ,

    In this paper we present BilevelJuMP, a new Julia package to support bilevel optimization within the JuMP framework. The package is a Julia library that enables the user to describe both upper and lower-level optimization problems using the JuMP algebraic syntax. Due to the generality and flexibility our library inherits from JuMP’s syntax, our package … Read more

    Global Convergence of Augmented Lagrangian Method Applied to Mathematical Program with Switching Constraints

  • Lei Guo
  • Gao-Xi Li
  • Xinmin Yang
    • Categories Complementarity and Variational Inequalities Tags , ,

    The mathematical program with switching constraints (MPSC) is a kind of problems with disjunctive constraints. The existing convergence results cannot directly be applied to this kind of problem since the required constraint qualifications for ensuring the convergence are very likely to fail. In this paper, we apply the augmented Lagrangian method (ALM) to solve the … Read more

    Global convergence and acceleration of fixed point iterations of union upper semicontinuous operators: proximal algorithms, alternating and averaged nonconvex projections, and linear complementarity problems

  • Jan Harold Alcantara
  • Ching-pei Lee
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose a unified framework to analyze fixed point iterations of a set-valued operator that is the union of a finite number of upper semicontinuous maps, each with a nonempty closed domain and compact values. We discuss global convergence, local linear convergence under a calmness condition, and component identification, and further propose acceleration strategies that … Read more

    A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods

  • Felipe Atenas
  • Claudia Sagastizábal
  • Paulo J. S. Silva
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , , , , ,

    We present a framework for analyzing convergence and local rates of convergence of a class of descent algorithms, assuming the objective function is weakly convex. The framework is general, in the sense that it combines the possibility of explicit iterations (based on the gradient or a subgradient at the current iterate), implicit iterations (using a … Read more

    Mirror-prox sliding methods for solving a class of monotone variational inequalities

  • George Lan
  • Yuyuan Ouyang
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Stochastic Programming

    In this paper we propose new algorithms for solving a class of structured monotone variational inequality (VI) problems over compact feasible sets. By identifying the gradient components existing in the operator of VI, we show that it is possible to skip computations of the gradients from time to time, while still maintaining the optimal iteration … Read more

    Exact computation of an error bound for a generalized linear complementarity problem with unique solution

  • Jean-Pierre Dussault
  • Jean-Charles Gilbert
    • Categories Complementarity and Variational Inequalities Tags , , , , , , , , ,

    This paper considers a generalized form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a … Read more