July  2013, 9(3): 561-577. doi: 10.3934/jimo.2013.9.561

A log-exponential regularization method for a mathematical program with general vertical complementarity constraints

1. 

School of Mathematics, Liaoning Normal University, Dalian, 116029, China

2. 

School of information Science and Engineering, Dalian Polytechnic University, Dalian, 116029, China, China

Received  March 2012 Revised  March 2013 Published  April 2013

Based on the log-exponential function, a regularization method is proposed for solving a mathematical program with general vertical complementarity constraints (MPVCC) considered by Scheel and Scholtes (Math. Oper. Res. 25: 1-22, 2000). With some known smoothing properties of the log-exponential function, a difficult MPVCC is reformulated as a smooth nonlinear programming problem, which becomes solvable by using available nonlinear optimization software. Detailed convergence analysis of this method is investigated and the results obtained generalize conclusions in Yin and Zhang (Math. Meth. Oper. Res. 64: 255-269, 2006). An example of Stackelberg game is illustrated to show the application of this method.
Citation: Jie Zhang, Shuang Lin, Li-Wei Zhang. A log-exponential regularization method for a mathematical program with general vertical complementarity constraints. Journal of Industrial and Management Optimization, 2013, 9 (3) : 561-577. doi: 10.3934/jimo.2013.9.561
References:
[1]

S. I. Birbil, G. Gürkan and O. Listes, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res., 31 (2006), 739-760. doi: 10.1287/moor.1060.0215.

[2]

R. W. Cottle and G. B. Dantzig, A generalization of the linear complementarity problem, J. Combinatorial Theory, 8 (1970), 79-90. doi: 10.1016/S0021-9800(70)80010-2.

[3]

F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley and Sons, New York, 1983.

[4]

M. Fukushima and J. S. Pang, Convergence of a smoothing continuation method for mathematical programs with complementarity constraints, in "Ill-Posed Variational Problems and Regularization Techniques" (eds. M. Thera and R. Tichatschke), Springer-Verlag, Berlin/Heidelberg, (1999), 99-110. doi: 10.1007/978-3-642-45780-7_7.

[5]

A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992), 269-284. doi: 10.1080/02331939208843795.

[6]

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.

[7]

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

[8]

X. Liu and J. Sun, Generalized stationary points and an interior point method for mathematical programs with equilibrium constraints, Mathematical Programming, 101 (2004), 231-261. doi: 10.1007/s10107-004-0543-6.

[9]

X. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Computational Optimization and Applications, 34 (2006), 5-33. doi: 10.1007/s10589-005-3075-y.

[10]

Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, UK, 1996. doi: 10.1017/CBO9780511983658.

[11]

M. Kočvara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Math. Program., 101 (2004), 119-149. doi: 10.1007/s10107-004-0539-2.

[12]

J. Peng and Z. Lin, A non-interior continuation method for generalized linear complementarity problems, Mathematical Programming, 86 (1999), 533-563. doi: 10.1007/s101070050104.

[13]

H. Qi and L. Liao, A smoothing Newton method for extended vertical linear complementarity problems, SIAM Joural of Matrix Analysis and Applications, 21 (1999), 45-66. doi: 10.1137/S0895479897329837.

[14]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Berlin Heidelberg, 1998. doi: 10.1007/978-3-642-02431-3.

[15]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.

[16]

H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stability, optimality, and sensitivity, Math. Oper. Res., 25 (2000), 1-22. doi: 10.1287/moor.25.1.1.15213.

[17]

H. V. Stackelberg, "The Theory of Market Economy," Oxford University Press, London, 1952.

[18]

H. Yin and J. Zhang, Global convergence of a smooth approximation method for mathematical programs with complementarity constraints, Math. Meth. Oper. Res., 64 (2006), 255-269. doi: 10.1007/s00186-006-0076-2.

[19]

N. D. Yen, Stability of the solution set of perturbed nonsmooth inequality systems and application, Journal of Optimization Theory and Applications, 93 (1997), 199-225. doi: 10.1023/A:1022662120550.

[20]

J. Zhang, L. Zhang and S. Lin, A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints, J. Math. Anal. Appl., 387 (2012), 201-220. doi: 10.1016/j.jmaa.2011.08.073.

[21]

J. Zhang, L. Zhang and W. Wang, On constraint qualifications in terms of approximate Jacobians for nonsmooth continuous optimization problems, Nonlinear Analysis, 75 (2012), 2566-2580. doi: 10.1016/j.na.2011.11.003.

show all references

References:
[1]

S. I. Birbil, G. Gürkan and O. Listes, Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res., 31 (2006), 739-760. doi: 10.1287/moor.1060.0215.

[2]

R. W. Cottle and G. B. Dantzig, A generalization of the linear complementarity problem, J. Combinatorial Theory, 8 (1970), 79-90. doi: 10.1016/S0021-9800(70)80010-2.

[3]

F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley and Sons, New York, 1983.

[4]

M. Fukushima and J. S. Pang, Convergence of a smoothing continuation method for mathematical programs with complementarity constraints, in "Ill-Posed Variational Problems and Regularization Techniques" (eds. M. Thera and R. Tichatschke), Springer-Verlag, Berlin/Heidelberg, (1999), 99-110. doi: 10.1007/978-3-642-45780-7_7.

[5]

A. Fischer, A special Newton-type optimization method, Optimization, 24 (1992), 269-284. doi: 10.1080/02331939208843795.

[6]

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.

[7]

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

[8]

X. Liu and J. Sun, Generalized stationary points and an interior point method for mathematical programs with equilibrium constraints, Mathematical Programming, 101 (2004), 231-261. doi: 10.1007/s10107-004-0543-6.

[9]

X. Liu, G. Perakis and J. Sun, A robust SQP method for mathematical programs with linear complementarity constraints, Computational Optimization and Applications, 34 (2006), 5-33. doi: 10.1007/s10589-005-3075-y.

[10]

Z. Q. Luo, J. S. Pang and D. Ralph, "Mathematical Programs with Equilibrium Constraints," Cambridge University Press, Cambridge, UK, 1996. doi: 10.1017/CBO9780511983658.

[11]

M. Kočvara and J. V. Outrata, Optimization problems with equilibrium constraints and their numerical solution, Math. Program., 101 (2004), 119-149. doi: 10.1007/s10107-004-0539-2.

[12]

J. Peng and Z. Lin, A non-interior continuation method for generalized linear complementarity problems, Mathematical Programming, 86 (1999), 533-563. doi: 10.1007/s101070050104.

[13]

H. Qi and L. Liao, A smoothing Newton method for extended vertical linear complementarity problems, SIAM Joural of Matrix Analysis and Applications, 21 (1999), 45-66. doi: 10.1137/S0895479897329837.

[14]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Berlin Heidelberg, 1998. doi: 10.1007/978-3-642-02431-3.

[15]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.

[16]

H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stability, optimality, and sensitivity, Math. Oper. Res., 25 (2000), 1-22. doi: 10.1287/moor.25.1.1.15213.

[17]

H. V. Stackelberg, "The Theory of Market Economy," Oxford University Press, London, 1952.

[18]

H. Yin and J. Zhang, Global convergence of a smooth approximation method for mathematical programs with complementarity constraints, Math. Meth. Oper. Res., 64 (2006), 255-269. doi: 10.1007/s00186-006-0076-2.

[19]

N. D. Yen, Stability of the solution set of perturbed nonsmooth inequality systems and application, Journal of Optimization Theory and Applications, 93 (1997), 199-225. doi: 10.1023/A:1022662120550.

[20]

J. Zhang, L. Zhang and S. Lin, A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints, J. Math. Anal. Appl., 387 (2012), 201-220. doi: 10.1016/j.jmaa.2011.08.073.

[21]

J. Zhang, L. Zhang and W. Wang, On constraint qualifications in terms of approximate Jacobians for nonsmooth continuous optimization problems, Nonlinear Analysis, 75 (2012), 2566-2580. doi: 10.1016/j.na.2011.11.003.

[1]

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

[2]

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

[3]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050

[4]

Kobamelo Mashaba, Jianxing Li, Honglei Xu, Xinhua Jiang. Optimal control of hybrid manufacturing systems by log-exponential smoothing aggregation. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1711-1719. doi: 10.3934/dcdss.2020100

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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 and Management Optimization, 2018, 14 (3) : 981-1005. doi: 10.3934/jimo.2017086

[10]

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

[11]

Yu Li, Kok Lay Teo, Shuhua Zhang. A new feedback form of open-loop Stackelberg strategy in a general linear-quadratic differential game. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022105

[12]

Tao Li, Suresh P. Sethi. A review of dynamic Stackelberg game models. Discrete and Continuous Dynamical Systems - B, 2017, 22 (1) : 125-159. doi: 10.3934/dcdsb.2017007

[13]

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

[14]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[15]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[16]

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

[17]

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

[18]

Lianju Sun, Ziyou Gao, Yiju Wang. A Stackelberg game management model of the urban public transport. Journal of Industrial and Management Optimization, 2012, 8 (2) : 507-520. doi: 10.3934/jimo.2012.8.507

[19]

Weijun Meng, Jingtao Shi. A linear quadratic stochastic Stackelberg differential game with time delay. Mathematical Control and Related Fields, 2021  doi: 10.3934/mcrf.2021035

[20]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control and Related Fields, 2021, 11 (4) : 797-828. doi: 10.3934/mcrf.2020047

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (66)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]