A canonical duality approach for the solution of affine quasi-variational inequalities.

*(English)*Zbl 1354.90148The authors consider quasi-variational inequality problems where both the cost and constraint mappings are affine. This property allows them to write the optimality conditions involving the usual complementarity problem. Using the Fischer-Burmeister gap function, they rewrite the optimality conditions as an unconstrained optimization problem and propose its several reformulations by using the so-called canonical duality approach. The authors give some relationships among stationary points of these problems and conditions for recognizing the global solutions. A heuristic algorithm based on these properties is suggested. Its performance is illustrated by computational experiments.

Reviewer: Igor V. Konnov (Kazan)

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C46 | Optimality conditions and duality in mathematical programming |

90C26 | Nonconvex programming, global optimization |

##### Keywords:

quasi-variational inequality; affine mappings; optimality conditions; complementarity problems; gap functions; canonical duality; stationary points
PDF
BibTeX
XML
Cite

\textit{V. Latorre} and \textit{S. Sagratella}, J. Glob. Optim. 64, No. 3, 433--449 (2016; Zbl 1354.90148)

Full Text:
DOI

##### References:

[1] | Aussel, D; Correa, R; Marechal, M, Gap functions for quasivariational inequalities and generalized Nash equilibrium problems, J. Optim. Theory Appl., 3, 474-488, (2011) · Zbl 1250.90095 |

[2] | Baiocchi, C., Capelo, A.: Variational and Quasivariational Inequalities: Applications to Free Boundary Problems. Wiley, New York (1984) · Zbl 0551.49007 |

[3] | Chan, D; Pang, J-S, The generalized quasi-variational inequality problem, Math. Oper. Res., 7, 211-222, (1982) · Zbl 0502.90080 |

[4] | Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, New York (1992) · Zbl 0757.90078 |

[5] | Dirkse, SP; Ferris, MC, The PATH solver: A non-monotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 123-156, (1995) |

[6] | Dreves, A; Facchinei, F; Kanzow, C; Sagratella, S, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21, 1082-1108, (2011) · Zbl 1230.90176 |

[7] | Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. Siam, Philadelphia (1976) · Zbl 0322.90046 |

[8] | Facchinei, F., Kanzow, C., Sagratella, S.: Solving quasi-variational inequalities via their KKT conditions. Math. Prog. Ser. A (2013). doi:10.1007/s10107-013-0637-0 · Zbl 1293.65100 |

[9] | Facchinei, F; Kanzow, C; Sagratella, S, QVILIB: a library of quasi-variational inequality test problems, Pac. J. Optim., 9, 225-250, (2013) · Zbl 1267.65078 |

[10] | Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II. Springer, New York (2003) · Zbl 1062.90002 |

[11] | Fukushima, M, A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim., 3, 165-171, (2007) · Zbl 1170.90487 |

[12] | Fukushima, M, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Prog., 53, 99110, (1992) · Zbl 0756.90081 |

[13] | Gao, D.Y.: Duality Principles in Nonconvex Systems: Theory, Methods and Applications. Kluwer, Dordrecht (2000) · Zbl 0940.49001 |

[14] | Gao, DY, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization, J. Glob. Optim., 17, 127-160, (2000) · Zbl 0983.74053 |

[15] | Gao, DY, Canonical duality theory: theory, method, and applications in global optimization, Comput. Chem., 33, 1964-1972, (2009) |

[16] | Gao, DY; Ruan, N; Pardalos, PM; Pardalos, PM (ed.); Ye, YY (ed.); Boginski, V (ed.); Commander, C (ed.), Canonical dual solutions to sum of fourth-order polynomials minimization problems with applications to sensor network localization, (2010), . |

[17] | Harms, N., Hoheisel T., Kanzow, C.: On a smooth dual gap function for a class of quasi-variational inequalities. Preprint 318, Institute of Mathematics, University of Würzburg, Würzburg, March 2013 · Zbl 1304.49018 |

[18] | Harms, N., Kanzow, C., Stein, O.: Smoothness Properties of a Regularized Gap Function for Quasi-Variational Inequalities. Preprint 313, Institute of Mathematics, University of Würzburg, Würzburg, March (2013) · Zbl 1330.90114 |

[19] | Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17, 851-868 (1996) · Zbl 0868.90123 |

[20] | Latorre, V., Gao, D.Y.: Canonical dual solution to nonconvex radial basis neural network optimization problem. Neurocomputing (2013, to appear) · Zbl 0502.90080 |

[21] | Latorre, V., Gao, D.Y.: Canonical duality for solving general nonconvex constrained problems. Optim. Lett. (2013, Submitted) preprint available at http://arxiv.org/pdf/1310.2014 · Zbl 1362.90315 |

[22] | Mosco, U.: Implicit variational problems and quasi variational inequalities. In: Gossez, J., Lami Dozo, E. (eds.) Nonlinear Operators and the Calculus of Variations. Lecture Notes in Mathematics, vol. 543, pp. 83-156. Springer, Berlin (1976) |

[23] | Nesterov, Y., Scrimali, L.: Solving strongly monotone variational and quasi-variational inequalities. CORE Discussion Paper 2006/107, Catholic University of Louvain, Center for Operations Research and Econometrics (2006) · Zbl 1238.49019 |

[24] | Noor, MA, On general quasi-variational inequalities, J. King Saud Univ., 24, 81-88, (2012) |

[25] | Outrata, J; Kocvara, M, On a class of quasi-variational inequalities, Optim. Methods Softw., 5, 275-295, (1995) |

[26] | Outrata, J., Kocvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer Academic Publishers, Dordrecht and Boston (1998) · Zbl 0947.90093 |

[27] | Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21-56 (2005) (Erratum: ibid 6, 373-375 (2009)) · Zbl 1115.90059 |

[28] | Ruan, N., Gao, D.Y.: Global optimal solutions to a general sensor network localization problem. Perform. Eval. (2013, to appear) published online at http://arxiv.org/submit/654731 |

[29] | Ryazantseva, IP, First-order methods for certain quasi-variational inequalities in Hilbert space, Comput. Math. Math. Phys., 47, 183-190, (2007) · Zbl 1210.39028 |

[30] | Scrimali, L.: Quasi-variational inequality formulation of the mixed equilibrium in mixed multiclass routing games. CORE Discussion Paper 2007/7, Catholic University of Louvain, Center for Operations Research and Econometrics, January 2007 |

[31] | Wang, ZB; Fang, SC; Gao, DY; Xing, WX, Canonical dual approach to solving the maximum cut problem, J. Glob. Optim., 54, 341-352, (2012) · Zbl 1259.90154 |

[32] | Zhang, J; Gao, DY; Yearwood, J, A novel canonical dual computational approach for prion AGAAAAGA amyloid fibril molecular modeling, J. Theor. Biol., 284, 149-157, (2011) · Zbl 1397.92548 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.