The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints

Liping Pang; Na Xu; Jian Lv

doi:10.3934/jimo.2018032

Article Contents

2019, Volume 15, Issue 1: 59-79. Doi: 10.3934/jimo.2018032

This issue Previous Article Delay characteristics in place-reservation queues with class-dependent service times Next Article Optimal stopping investment with non-smooth utility over an infinite time horizon

The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints

a, b.
School of Mathematical Sciences, Dalian University of Technology, Liaoning 116024, China
c.
School of Finance, Zhejiang University of Finance and Economics, Zhejiang 310018, China

* Corresponding author: Li-Ping Pang
* Corresponding author: Li-Ping Pang

Received: January 31, 2017

Revised: October 31, 2017

Early access: April 2018

Published: December 2018

The first author is supported by Huzhou science and technology plan on No.2016GY03

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We study the convergence of the log-exponential regularization method for mathematical programs with vertical complementarity constraints (MPVCC). The previous paper assume that the sequence of Lagrange multipliers are bounded and it can be found by software. However, the KKT points can not be computed via Matlab subroutines exactly in many cases. We note that it is realistic to compute inexact KKT points from a numerical point of view. We prove that, under the MPVCC-MFCQ assumption, the accumulation point of the inexact KKT points is Clarke (C-) stationary point. The idea of inexact KKT conditions can be used to define stopping criteria for many practical algorithms. Furthermore, we introduce a feasible strategy that guarantees inexact KKT conditions and provide some numerical examples to certify the reliability of the approach. It means that we can apply the inexact regularization method to solve MPVCC and show the advantages of the improvement.

Keywords:

Mathematical program with vertical complementarity constraints,
inexact KKT points,
C-/M-stationarity,
constraint qualification,
convergence,
inexact regularization method.

Mathematics Subject Classification: Primary: 90C30, 90C33; Secondary: 90C46.

Citation:

Full Text(HTML)

Table 1. The numerical results for Example 2

t	$(y^t_1, y^t_2, y^t_3, y^t_4, z^t_1, z^t_2)$	$ f^t $
0.2	(0.0592, -0.4868, 0.3863, 0.2741, 1.0058, 0.4937)	1.7496
0.01	(-0.0000, -0.4999, 0.4011, 0.1994, 1.0001, 0.4999)	1.6929
0.005	( 0.0000, -0.5000, 0.3997, 0.1998, 1.0000, 0.5000)	1.6901

| Show Table

DownLoad: CSV

Table 2. The numerical results for Example 4, 5

Example	Algorithm	$z$	$f$	$Gap$
4	Algorithm 2	(0.0000, 2.0000)	0.0000	100 %
	fmincon	(0.0004, 2.0000)	0.0000	99.98 %
	ADH	(0.0000, 1.9988)	0.0000	99.94 %
	AH	(-0.0000, 1.9999)	0.0000	100 %
	$Polak^1$	(0.0000, 1.8708)	0.0167	93.54 %
5	Algorithm 2	(0.7500, 0.0000)	0.0625	100 %
	fmincon	(0.7500, 0.0003)	0.0625	99.96 %
	ADH	(0.7500, 0.0000)	0.0625	100 %
	AH	(0.7500, 0.0000)	0.0625	100 %
	$Polak^1$	(0.7500, 0.0000)	0.0625	100 %

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	R. Andreani , J. M. Martínez , L. T. Santos and B. F. Svaiter , On the behaviour of constrained optimization methods when Lagrange multipliers do not exist, Optimization Methods and Software, 29 (2014) , 646-657. doi: 10.1080/10556788.2013.841692.
	R. Andreani , J. M. Martínez and B. F. Svaiter , A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM Journal on Optimization, 20 (2010) , 3533-3554. doi: 10.1137/090777189.
	M. S. Bazaraa and C. M. Shetty, Foundations of Optimization, 122 Springer-Verlag, Berlin/New York, 1976.
	B. Byrd , M. E. Hribar and J. Nocedal , An interior point algorithm for large-scale nonlinear programming, SIAM Journal on Optimization, 9 (1999) , 877-900. doi: 10.1137/S1052623497325107.
	R. Fletcher and S. Leyffer , Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002) , 239-269. doi: 10.1007/s101070100244.
	P. E. Gill , W. Murray and M. A. Saunders , SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Journal on Optimization, 12 (2002) , 979-1006. doi: 10.1137/S1052623499350013.
	M. S. Gowda and R. Sznajder , A generalization of the Nash equilibrium theorem on bimatrix games, International Journal of Game Theory, 25 (1996) , 1-12. doi: 10.1007/BF01254380.
	T. Hoheisel , C. Kanzow and A. Schwartz , Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Mathematical Programming Series A, 137 (2013) , 257-288. doi: 10.1007/s10107-011-0488-5.
	C. Kanzow , On the multiplier-penalty-approach for quasi-variational inequalities, Mathematical Programming Series A, 160 (2016) , 33-63. doi: 10.1007/s10107-015-0973-3.
	C. Kanzow and A. Schwartz , A new regularization method for mathematical programs with complementarity constraints with strong convergence properties, SIAM Journal on Optimization, 23 (2013) , 770-798. doi: 10.1137/100802487.
	C. Kanzow and A. Schwartz , Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with complementarity constraints, Computational Optimization and Applications, 59 (2014) , 249-262. doi: 10.1007/s10589-013-9575-2.
	C. Kanzow and A. Schwartz , The price of inexactness: Convergence properties of relaxation methods for mathematical programs with complementarity constraints revisited, Mathematical Programming Series A, 40 (2015) , 253-275. doi: 10.1287/moor.2014.0667.
	Y. Li , T. Tan and X. Li , A log-exponential smoothing method for mathematical programs with complementarity constraints, Applied Mathematics and Computation, 218 (2012) , 5900-5909. doi: 10.1016/j.amc.2011.11.046.
	Y. C. Liang, Some Studies on Optimization Problems with Equilibrium Constraints, Ph. D thesis, Dalian University of Technology in Dalian, 2006.
	Y. C. Liang and G. H. Lin , Stationaruty conditions and their reformulations for mathematical programs with vertical complementarity constraints, Journal of Optimization Theory and Applications, 154 (2012) , 54-70. doi: 10.1007/s10957-012-9992-x.
	G. H. Lin and M. Fukushima , A modified relaxation scheme for mathematical programs with complementarity constraints, Annals of Operations Research, 133 (2005) , 63-84. doi: 10.1007/s10479-004-5024-z.
	O. L. Mangasarian , Equivalence of the complementarity problem to a system of nonlinear equations, SIAM Journal on Applied Mathematics, 31 (1976) , 89-92. doi: 10.1137/0131009.
	J. M. Peng and Z. H. Lin , A non-interior continuation method for generalized linear complementarity problems, Mathematical Programming, 86 (1999) , 533-563. doi: 10.1007/s101070050104.
	H. D. Qi and L. Z. Liao , A smoothing Newton method for extended vertical linear complementarity problems, SIAM Journal on Matrix Analysis and Applications, 21 (1999) , 45-66. doi: 10.1137/S0895479897329837.
	L. Qi and Z. Wei , On the constant positive linear dependence condition and its application to SQP methods, SIAM Journal on Optimization, 10 (2000) , 963-981. doi: 10.1137/S1052623497326629.
	H. Scheel and S. Scholtes , Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Mathematics of Operations Ressearch, 25 (2000) , 1-22. doi: 10.1287/moor.25.1.1.15213.
	S. Scholtes , Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 11 (2001) , 918-936. doi: 10.1137/S1052623499361233.
	J. Stoer and C. Witzgall, Convexity and Optimization in Finite Dimensions, 1^nd edition, Springer-Verlag, New York, 1970.
	A. Wächter and L. T. Biegler , On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming, 106 (2006) , 25-57. doi: 10.1007/s10107-004-0559-y.
	H. J. Xiong and B. Yu , An aggergate deformation homotopy method for min-max-min problems with max-min constraints, Computational Optimization and Applications, 47 (2010) , 501-527. doi: 10.1007/s10589-008-9229-y.
	H. Yin and J. Zhang , Global convergence of a smooth approximation method for mathematical programs with complementarity constraints, Mathematical Methods of Operations Research, 64 (2006) , 255-269. doi: 10.1007/s00186-006-0076-2.
	J. Zhang , S. Lin and L. W. Zhang , A log-exponential regularization method for a mathematical program with general vertical complementarity constraints, Journal of Industrial and management Optimization, 9 (2013) , 561-577. doi: 10.3934/jimo.2013.9.561.