Complementarity and Variational Inequalities

Monotonicity of L”{o}wner Operators and Its Applications to Symmetric Cone Complementarity Problems

  • Lingchen Kong
  • Levent Tunçel
  • Naihua Xiu
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Semi-definite Programming Tags , , , ,

    This paper focuses on monotone L\”{o}wner operators in Euclidean Jordan algebras and their applications to the symmetric cone complementarity problem (SCCP). We prove necessary and sufficient conditions for locally Lipschitz L\”{o}wner operators to be monotone, strictly monotone and strongly monotone. We also study the relationship between monotonicity and operator-monotonicity of L\”{o}wner operators. As a by-product … 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

    On the Global Solution of Linear Programs with Linear Complementarity Constraints

  • Kristin P. Bennett
  • Jing Hu
  • John E. Mitchell
  • Gautam Kunapuli
  • Jong-Shi Pang
    • Categories Complementarity and Variational Inequalities

    This paper presents a parameter-free integer-programming based algorithm for the global resolution of a linear program with linear complementarity constraints (LPEC). The cornerstone of the algorithm is a minimax integer program formulation that characterizes and provides certificates for the three outcomes—infeasibility, unboundedness, or solvability—of an LPEC. An extreme point/ray generation scheme in the spirit of … Read more

    CONVERGENCE OF A CLASS OF SEMI-IMPLICIT TIME-STEPPING SCHEMES FOR NONSMOOTH RIGID MULTIBODY DYNAMICS

  • Mihai Anitescu
  • Florian A. Potra
  • Bogdan Gavrea
    • Categories Complementarity and Variational Inequalities, Mechanical Engineering, Other Topics Tags , , , ,

    In this work we present a framework for the convergence analysis in a measure differential inclusion sense of a class of time-stepping schemes for multibody dynamics with contacts, joints, and friction. This class of methods solves one linear complementarity problem per step and contains the semi-implicit Euler method, as well as trapezoidallike methods for which … Read more

    Primal-dual affine scaling interior point methods for linear complementarity problems

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , , ,

    A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more

    Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

  • Giovanni Giallombardo
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary … Read more

    A Path to the Arrow-Debreu Competitive Market Equilibrium

  • Yinyu Ye
    • Categories Complementarity and Variational Inequalities, Game Theory, Linear Programming Tags , ,

    We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more

    A Note on Exchange Market Equilibria with Leontief’s Utility: Freedom of Pricing Leads to Rationality

  • Yinyu Ye
    • Categories Complementarity and Variational Inequalities, Game Theory Tags , ,

    We extend the analysis of [27] to handling more general utility functions: piece-wise linear functions, which include Leontief’s utility. We show that the problem reduces to the general analytic center model discussed in [27]. Thus, the same linear programming complexity bound applies to approximating the Fisher equilibrium problem with these utilities. More importantly, we show … Read more

    An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version

  • Christina Oberlin
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares Tags , ,

    We discuss local convergence of Newton’s method to a singular solution $x^*$ of the nonlinear equations $F(x) = 0$, for $F:\R^n \rightarrow \R^n$. It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution $x^*$ from a starlike domain around $x^*$ for $F$ twice Lipschitz continuously differentiable and $x^*$ satisfying … Read more