Complementarity and Variational Inequalities

Optimization Reformulations of Complementarity Equilibrium Models

  • Laura Bahiense
  • Marcelo Cordova
  • Juan Pablo Luna
  • Claudia Sagastizábal
    • Categories Applications - Science and Engineering, Complementarity and Variational Inequalities, Energy Tags , ,

    We propose a new mathematical model to describe equilibria in competitive markets. Our approach transforms the well-known complementary formulation into a numerically more efficient optimization framework. In complementarity models, the actions of all elastic consumers in the market are implicitly represented by their aggregate demand. Instead, we introduce demand-induced utilities, which can be explicitly constructed individually for each consumer. … Read more

    Covering for Set-Valued Mappings in the Absence of Metric Regularity

  • Mario Jelitte
  • Alexey F. Izmailov
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    Covering properties build the foundation of stability and sensitivity analysis of solutions to a generalized equation and more specific optimization-related stationarity and equilibrium problems. It has been well-understood that metric regularity of the mapping defining the generalized equation is a key to furnish Lipschitzian stability of the solution of interest. With this work, we want … Read more

    A path-following framework on fiber bundle for variational inequalities

  • Hongbo Sun
    • Categories Complementarity and Variational Inequalities Tags , , ,

    Variational inequality (VI) is a fundamental mathematical framework for many classical problems. We present a path-following framework for finite-dimensional VIs with arbitrary continuous functions and compact convex domains. The approach first approximately reduces a general VI to a smooth VI on simplex. Its key innovation is to formulate the smooth VI on simplex on a … Read more

    Second-Order Optimality Conditions for Bilevel Optimization Problems Using Parabolic Directional Derivatives

  • Bhuvnesh Khatana
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization

    This paper studies the second-order properties of a class of inequality-constrained bilevel programming problems. First-order optimality conditions for the existence of solutions to bilevel optimization problems are derived using the first-order directional derivative of the optimal solution function of the lower-level problem in the seminal paper by Dempe (1992). In this work, we prove that … Read more

    Convergence of the Frank-Wolfe Algorithm for Monotone Variational Inequalities

  • Matthew Hough
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We consider the Frank-Wolfe algorithm for solving variational inequalities over compact, convex sets under a monotone \(C^1\) operator and vanishing, nonsummable step sizes. We introduce a continuous-time interpolation of the discrete iteration and use tools from dynamical systems theory to analyze its asymptotic behavior. This allows us to derive convergence results for the original discrete … Read more

    Chance-Constrained Linear Complementarity Problems

  • René Henrion
  • Martin Schmidt
    • Categories Complementarity and Variational Inequalities, Energy, Stochastic Programming Tags , , , , ,

    We study linear complementarity problems (LCPs) under uncertainty, which we model using chance constraints. Since the complementarity condition of the LCP is an equality constraint, it is required to consider relaxations, which naturally leads to optimization problems in which the relaxation parameters are minimized for given probability levels. We focus on these optimization problems and … Read more

    Efficient Warm-Start Strategies for Nash-based Linear Complementarity Problems via Bilinear Approximation

  • Dominic C. Flocco
  • Steven A. Gabriel
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Global Optimization Applications Tags , , ,

    We present an effective warm-starting scheme for solving large linear complementarity problems (LCPs) arising from Nash equilibrium problems. The approach generates high-quality starting points that, when passed to the PATH solver, yield substantial reductions in computational time and variance. Our warm-start routine reformulates each agent’s LP using strong duality, leading to a master problem with … Read more

    A General Penalty-Method and a General Regularization-Method for Cardinality-Constrained Optimization Problems

  • Felix P. Broesamle
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    We consider cardinality-constrained optimization problems (CCOPs), which are general nonlinear programs with an additional constraint limiting the number of nonzero continuous variables. The continuous reformulation of CCOPs involves complementarity constraints, which pose significant theoretical and computational challenges. To address these difficulties, we propose and analyze two numerical solution approaches: a general penalty method and a … Read more

    Stability analysis of parameterized models relative to nonconvex constraints

  • Zijian Shi
  • Miantao Chao
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags , , , , ,

    For solution mappings of parameterized models (such as optimization problems, variational inequalities, and generalized equations), standard stability inevitably fails as the parameter approaches the boundary of the feasible domain. One remedy is relative stability restricted to a constraint set (e.g., the feasible domain), which is our focus in this paper. We establish generalized differentiation criteria … Read more

    A Heuristic for Complementarity Problems Using Difference of Convex Functions

  • Steven A. Gabriel
  • Dominic C. Flocco
  • Trine Krogh Boomsma
  • Miguel A. Lejeune
  • Martin Schmidt
    • Categories Complementarity and Variational Inequalities Tags , , , ,

    We present a new difference of convex functions algorithm (DCA) for solving linear and nonlinear mixed complementarity problems (MCPs). The approach is based on the reformulation of bilinear complementarity constraints as difference of convex (DC) functions, more specifically, the difference of scalar, convex quadratic terms. This reformulation gives rise to a DC program, which is … Read more