A mathematical program with complementarity constraints (MPCC) is an optimization problem with equality/inequality constraints in which a complementarity type constraint is considered in addition. This complementarity condition modifies the feasible region so as to remove many of those properties that are usually important to obtain the standard optimality conditions, e.g., convexity and constraint qualifications. In the literature, these problems have been tackled in many different ways: methods that introduce a parameter in order to relax the complementarity constraint, modified simplex methods that use an appropriate rule for choosing the non basic variable in order to preserve complementarity. We introduce a decomposition method of the given problem in a sequence of parameterized problems, that aim to force complementarity. Once we obtain a feasible solution, by means of duality results, we are able to eliminate a set of parameterized problems which are not worthwhile to be considered. Furthermore, we provide some bounds for the optimal value of the objective function and we present an application of the proposed technique in a non trivial example.

On linear problems with complementarity constraints

Letizia Pellegrini;Alberto Peretti
2019-01-01

Abstract

A mathematical program with complementarity constraints (MPCC) is an optimization problem with equality/inequality constraints in which a complementarity type constraint is considered in addition. This complementarity condition modifies the feasible region so as to remove many of those properties that are usually important to obtain the standard optimality conditions, e.g., convexity and constraint qualifications. In the literature, these problems have been tackled in many different ways: methods that introduce a parameter in order to relax the complementarity constraint, modified simplex methods that use an appropriate rule for choosing the non basic variable in order to preserve complementarity. We introduce a decomposition method of the given problem in a sequence of parameterized problems, that aim to force complementarity. Once we obtain a feasible solution, by means of duality results, we are able to eliminate a set of parameterized problems which are not worthwhile to be considered. Furthermore, we provide some bounds for the optimal value of the objective function and we present an application of the proposed technique in a non trivial example.
2019
Mathematical programs with complementarity constraints, duality, decomposition methods
File in questo prodotto:
File Dimensione Formato  
wp2019n21.pdf

accesso aperto

Descrizione: Articolo scientifico
Licenza: Dominio pubblico
Dimensione 395.62 kB
Formato Adobe PDF
395.62 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1005933
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact