Complementarity and Variational Inequalities

Interior-Point Methods for Nonconvex Nonlinear Programming: Complementarity Constraints

  • Hande Benson
  • David F. Shanno
  • Robert J. Vanderbei
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , ,

    In this paper, we present the formulation and solution of optimization problems with complementarity constraints using an interior-point method for nonconvex nonlinear programming. We identify possible difficulties that could arise, such as unbounded faces of dual variables, linear dependence of constraint gradients and initialization issues. We suggest remedies. We include encouraging numerical results on the … Read more

    Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

  • Lídia Montero
  • Dulce Rosas
  • Jordi Castro
    • Categories Complementarity and Variational Inequalities, Transportation Tags , , ,

    The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient … Read more

    Local convergence of SQP methods for Mathematical Programs with Equilibrium Constraints

  • Roger Fletcher
  • Sven Leyffer
  • Daniel Ralph
  • Stefan Scholtes
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , ,

    Recently, it has been shown that Nonlinear Programming solvers can successfully solve a range of Mathematical Programs with Equilibrium Constraints (MPECs). In particular, Sequential Quadratic Programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. It is shown that SQP converges superlinearly under reasonable assumptions … Read more

    The Penalty Interior Point Method fails to converge for Mathematical Programs with Equilibrium Constraints

  • Sven Leyffer
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , ,

    This paper presents a small example for which the Penalty Interior Point Method converges to a non-stationary point. The reasons for this adverse behaviour are discussed. CitationNumerical Analysis Report NA/208, Department of Mathematics, University of Dundee, February 2002.ArticleDownload View PDF

    A new class of merit functions for the semidefinite complementarity problem

  • Rosely M. B. Goes
  • Paulo Roberto Oliveira
    • Categories Complementarity and Variational Inequalities, Semi-definite Programming Tags , ,

    Recently,Tseng extended a class of merit functions for the nonlinear complementarity problem to semidefinite complementarity problem (SDCP), showing some properties under suitable assumptions. Yamashita and Fukushima also presented other properties. In this paper, we propose a new class of merit functions for the SDCP, and prove some of those properties, under weaker hypothesis. Particularly, we … Read more

    A new class of proximal algorithms for the nonlinear complementarity problem

  • Paulo Roberto Oliveira
  • Geci Silva
    • Categories Complementarity and Variational Inequalities Tags , ,

    In this paper, we consider a variable proximal regularization method for solving the nonlinear complementarity problem for P0 functions. CitationApplied Optimization Series, 96, Optimization and Control With Applications, L. Qi, K. Teo and X. Yang (Eds.), pp 549-561, Springer, 2005.

    Global Newton-type methods and semismooth reformulations for NCP

  • Maria Grazia Gasparo
  • Sandra Pieraccini
  • Aldo Pasquali
    • Categories Complementarity and Variational Inequalities Tags , , ,

    It is known that a nonlinear complementarity problem (NCP) can be reformulated as a semismooth system of nonlinear equations by using a so called NCP-function. Global Newton-type methods for solving NCP via semismooth reformulation need to use a merit function, which is usually required to be continuously differentiable. In this paper we present a global … Read more

    A Bundle Method to Solve Multivalued Variational Inequalities

  • Van Hien Nguyen
  • Genevieve Salmon
  • Jean-Jacques Strodiot
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags , ,

    In this paper we present a bundle method for solving a generalized variational inequality problem. This problem consists in finding a zero of the sum of two multivalued operators defined on a real Hilbert space. The first one is monotone and the second one is the subdifferential of a lower semicontinuous proper convex function. The … Read more

    Semismooth Support Vector Machines

  • Michael C. Ferris
  • Todd S. Munson
    • Categories Complementarity and Variational Inequalities, Data-Mining Tags , ,

    The linear support vector machine can be posed as a quadratic program in a variety of ways. In this paper, we look at a formulation using the two-norm for the misclassification error that leads to a positive definite quadratic program with a single equality constraint when the Wolfe dual is taken. The quadratic term is … Read more

    On reduced QP formulations of monotone LCP problems

  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Quadratic Programming Tags , ,

    Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice versa are well known. We describe a class of LCPs for which a reduced QP formulation—one that has fewer constraints than the “standard” QP formulation—is available. We mention several instances of this class, including the known case in which the … Read more