• Previous Article
    A two-warehouse probabilistic model with price discount on backorders under two levels of trade-credit policy
  • JIMO Home
  • This Issue
  • Next Article
    Coordination of VMI supply chain with a loss-averse manufacturer under quality-dependency and marketing-dependency
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, 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.

[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.

[3]

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

[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.

[5]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[23]

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

[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.

[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.

[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.

[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.

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.

[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.

[3]

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

[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.

[5]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[23]

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

[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.

[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.

[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.

[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.

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]

Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561

[2]

Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49

[3]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199

[4]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[5]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013

[6]

Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

[7]

Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223

[8]

Yi Zhang, Liwei Zhang, Jia Wu. On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints. Journal of Industrial & Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[9]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[10]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[11]

Lei Guo, Gui-Hua Lin. Globally convergent algorithm for solving stationary points for mathematical programs with complementarity constraints via nonsmooth reformulations. Journal of Industrial & Management Optimization, 2013, 9 (2) : 305-322. doi: 10.3934/jimo.2013.9.305

[12]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733

[13]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

[14]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153

[15]

Michal Kočvara, Jiří V. Outrata. Inverse truss design as a conic mathematical program with equilibrium constraints. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1329-1350. doi: 10.3934/dcdss.2017071

[16]

Nahid Banihashemi, C. Yalçın Kaya. Inexact restoration and adaptive mesh refinement for optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 521-542. doi: 10.3934/jimo.2014.10.521

[17]

Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial & Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99

[18]

Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial & Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563

[19]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[20]

Liping Pang, Fanyun Meng, Jinhe Wang. Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-23. doi: 10.3934/jimo.2018116

2017 Impact Factor: 0.994

Article outline

Figures and Tables

[Back to Top]