Complementarity and Variational Inequalities

Mathematical programs with complementarity constraints and application to hyperparameter tuning for nonlinear support vector machines

  • Samuel Ward
  • Alain Zemkoho
  • Selin Damla Ahipasaoglu
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Optimization in Data Science Tags , , , , ,

    We consider the Mathematical Program with Complementarity Constraints (MPCC). One of the main challenges in solving this problem is the systematic failure of standard Constraint Qualifications (CQs). Carefully accounting for the combinatorial nature of the complementarity constraints, tractable versions of the Mangasarian Fromovitz Constraint Qualification (MFCQ) have been designed and widely studied in the literature. … Read more

    Facial approach for constructing stationary points for mathematical programs with cone complementarity constraints

  • Javier I. Madariaga
  • Héctor Ramírez
    • Categories Complementarity and Variational Inequalities, Cone Programming Tags , , ,

    This paper studies stationary points in mathematical programs with cone complementarity constraints (CMPCC). We begin by reviewing various formulations of CMPCC and revisiting definitions for Bouligand, proximal strong, regular strong, Wachsmuth’s strong, L-strong, weak, as well as Mordukhovich and Clarke stationary points, establishing a comprehensive framework for CMPCC. Building on key principles related to cone … Read more

    New Sufficient and Necessary Conditions for Constrained and Unconstrained Lipschitzian Error Bounds

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mario Jelitte
    • Categories Complementarity and Variational Inequalities, Global Optimization Theory, Nonsmooth Optimization Tags , , , , , , ,

    Local error bounds play a fundamental role in mathematical programming and variational analysis. They are used e.g. as constraint qualifications in optimization, in developing calculus rules for generalized derivatives in nonsmooth and set-valued analysis, and they serve as a key ingredient in the design and convergence analysis of Newton-type methods for solving systems of possibly … Read more

    A new problem qualification based on approximate KKT conditions for Lipschitzian optimization with application to bilevel programming

  • Isabella Käming
  • Andreas Fischer
  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization

    When dealing with general Lipschitzian optimization problems, there are many problem classes where even weak constraint qualications fail at local minimizers. In contrast to a constraint qualification, a problem qualification does not only rely on the constraints but also on the objective function to guarantee that a local minimizer is a Karush-Kuhn-Tucker (KKT) point. For … Read more

    Relaxation methods for pessimistic bilevel optimization

  • Alain Zemkoho
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , ,

    We consider a smooth pessimistic bilevel optimization problem, where the lower-level problem is convex and satisfies the Slater constraint qualification. These assumptions ensure that the Karush-Kuhn-Tucker (KKT) reformulation of our problem is well-defined. We then introduce and study the (i) Scholtes, (ii) Lin and Fukushima, (iii) Kadrani, Dussault and Benchakroun, (iv) Steffensen and Ulbrich, and … Read more

    Descent Scheme for a Class of Bilevel Programming Problems

  • Bhuvnesh Khatana
    • Categories Approximation Algorithms, Combinatorial Optimization, Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    In this paper, a class of bilevel programming problems is studied, in which the lower level is a quadratic programming problem, and the upper level problem consists of a nonlinear objective function with coupling constraints. An iterative process is developed to generate a sequence of points, which converges to the solution of this problem. In … Read more

    Double-proximal augmented Lagrangian methods with improved convergence condition

  • Jianchao Bai
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    In this paper, we propose a novel double-proximal augmented Lagrangian method(DP-ALM) for solving a family of linearly constrained convex minimization problems whose objective function is not necessarily smooth. This DP-ALM not only enjoys a flexible dual stepsize, but also contains a proximal subproblem with relatively smaller proximal parameter. By a new prediction-correction reformulation for this … Read more

    An novel adaptive inertial algorithm for solving bilevel variational inequalities with pseudomonotone multivalued operators

  • Zhongbao Wang
    • Categories Complementarity and Variational Inequalities

    This paper aims to develop an adaptive inertial algorithm for solving bilevel variational inequalities with multivalued pseudomonotone operators in real Hilbert spaces and establish its strong convergence property. The algorithm does not need to know the prior information of the Lipschitz constants and strong monotonicity coefficients of the associated mappings, incorporates inertial techniques and involves … Read more

    On Coupling Constraints in Linear Bilevel Optimization

  • Dorothee Henke
  • Henri Lefebvre
  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Other Topics Tags ,

    It is well-known that coupling constraints in linear bilevel optimization can lead to disconnected feasible sets, which is not possible without coupling constraints. However, there is no difference between linear bilevel problems with and without coupling constraints w.r.t. their complexity-theoretical hardness. In this note, we prove that, although there is a clear difference between these … Read more

    A new proximal gradient algorithm for solving mixed variational inequality problems with a novel explicit stepsize and applications

  • Pham Thi Hoai
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Nonlinear Optimization Tags , , , ,

    In this paper, we propose a new algorithm for solving monotone mixed variational inequality problems in real Hilbert spaces based on proximal gradient method. Our new algorithm uses a novel explicit stepsize which is proved to be increasing to a positive value. This property plays an important role in improving the speed of the algorithm. … Read more