January  2019, 15(1): 59-79. doi: 10.3934/jimo.2018032

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

Received  February 2017 Revised  November 2017 Published  April 2018

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

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.

Citation: Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial & Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
References:
[1]

R. AndreaniJ. M. MartínezL. 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.  Google Scholar

[2]

R. AndreaniJ. 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.  Google Scholar

[3]

M. S. Bazaraa and C. M. Shetty, Foundations of Optimization, 122 Springer-Verlag, Berlin/New York, 1976.  Google Scholar

[4]

B. ByrdM. 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.  Google Scholar

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.  doi: 10.1007/s101070100244.  Google Scholar

[6]

P. E. GillW. 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.  Google Scholar

[7]

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.  Google Scholar

[8]

T. HoheiselC. 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.  Google Scholar

[9]

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.  Google Scholar

[10]

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.  Google Scholar

[11]

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.  Google Scholar

[12]

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.  Google Scholar

[13]

Y. LiT. 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.  Google Scholar

[14]

Y. C. Liang, Some Studies on Optimization Problems with Equilibrium Constraints, Ph. D thesis, Dalian University of Technology in Dalian, 2006. Google Scholar

[15]

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.  Google Scholar

[16]

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.  Google Scholar

[17]

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.  Google Scholar

[18]

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.  Google Scholar

[19]

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.  Google Scholar

[20]

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.  Google Scholar

[21]

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.  Google Scholar

[22]

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.  Google Scholar

[23]

J. Stoer and C. Witzgall, Convexity and Optimization in Finite Dimensions, 1nd edition, Springer-Verlag, New York, 1970.  Google Scholar

[24]

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.  Google Scholar

[25]

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.  Google Scholar

[26]

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.  Google Scholar

[27]

J. ZhangS. 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.  Google Scholar

show all references

References:
[1]

R. AndreaniJ. M. MartínezL. 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.  Google Scholar

[2]

R. AndreaniJ. 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.  Google Scholar

[3]

M. S. Bazaraa and C. M. Shetty, Foundations of Optimization, 122 Springer-Verlag, Berlin/New York, 1976.  Google Scholar

[4]

B. ByrdM. 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.  Google Scholar

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.  doi: 10.1007/s101070100244.  Google Scholar

[6]

P. E. GillW. 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.  Google Scholar

[7]

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.  Google Scholar

[8]

T. HoheiselC. 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.  Google Scholar

[9]

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.  Google Scholar

[10]

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.  Google Scholar

[11]

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.  Google Scholar

[12]

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.  Google Scholar

[13]

Y. LiT. 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.  Google Scholar

[14]

Y. C. Liang, Some Studies on Optimization Problems with Equilibrium Constraints, Ph. D thesis, Dalian University of Technology in Dalian, 2006. Google Scholar

[15]

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.  Google Scholar

[16]

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.  Google Scholar

[17]

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.  Google Scholar

[18]

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.  Google Scholar

[19]

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.  Google Scholar

[20]

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.  Google Scholar

[21]

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.  Google Scholar

[22]

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.  Google Scholar

[23]

J. Stoer and C. Witzgall, Convexity and Optimization in Finite Dimensions, 1nd edition, Springer-Verlag, New York, 1970.  Google Scholar

[24]

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.  Google Scholar

[25]

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.  Google Scholar

[26]

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.  Google Scholar

[27]

J. ZhangS. 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.  Google Scholar

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
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
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 %
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 %
[1]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[2]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[3]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[4]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[5]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[6]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[7]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[8]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[9]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[10]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[12]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013

[13]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[15]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[16]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[17]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[18]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[19]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[20]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (179)
  • HTML views (1210)
  • Cited by (0)

Other articles
by authors

[Back to Top]