×

A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints. (English) Zbl 1122.90095

Summary: This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.

MSC:

90C55 Methods of successive quadratic programming type
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

OPECgen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Anitescu, “Degenerate nonlinear programming with a quadratic growth condition,” SIAM J. Optimization, vol. 10, pp. 1116-1135, 2000. · Zbl 0994.65073 · doi:10.1137/S1052623499359178
[2] J.V. Burke and S.P. Han, “A robust sequential quadratical programming method,” Mathematical Programming,” vol. 43, pp. 277-303, 1989. · Zbl 0683.90070 · doi:10.1007/BF01582294
[3] Y. Chen and M. Florian, “The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions,” Optimization, vol. 32, pp. 193-209, 1995. · Zbl 0812.00045 · doi:10.1080/02331939508844048
[4] R.W. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problems, Academic Press: Boston, 1992. · Zbl 0757.90078
[5] F. Facchinei, H. Jiang, and L. Qi, “A smoothing method for mathematical programs with equilibrium constraints,” Mathematical Programming, vol. 85, pp. 107-134, 1999. · Zbl 0959.65079 · doi:10.1007/s10107990015a
[6] A. Fischer, “A special Newton-type optimization method,” Optimization, vol. 24, pp. 269-284, 1992. · Zbl 0814.65063 · doi:10.1080/02331939208843795
[7] M. Fukushima, Z.-Q. Luo, and J.-S Pang, “A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints,” Computational Optimization and Applications, vol. 10, pp. 5-34, 1998. · Zbl 0904.90153 · doi:10.1023/A:1018359900133
[8] Fukushima, M.; Pamg, J.-S.; Théra, M. (ed.); Tichatschke, R. (ed.), Convergence of a smoothing continuation method for mathematical programs with complementarity constraints, 99-110 (2000), New York · Zbl 0944.65070
[9] M. Fukushima and P. Tseng, “An implementable active-set algorithm for computing a B-stationary of mathematical program with linear complementarity constraints,” SIAM J. Optimization, vol. 12, no. 3, pp.725-730, 2002. · Zbl 1005.65064 · doi:10.1137/S1052623499363232
[10] Z.Y. Gao, “A superlinearly convergent feasible method for nonlinear programming with nonlinear inequality constraints part I,” Journal of Northern Jiaotong University, vol. 20, no. 1, pp. 50-60, 1996.
[11] Z.Y. Gao and F. Wu, “Feasible method for nonlinear programming,” Acta Mathematicae Applicatae Sinica, vol. 18, no. 4, pp. 579-590, 1995. · Zbl 1108.35384 · doi:10.1007/s102550200060
[12] W.W. Hager, “Stablized sequential quadratic programming,” Computational Optimization and Applications, vol. 12, pp. 253-273, 1999. · Zbl 1040.90566 · doi:10.1023/A:1008640419184
[13] J.-B. Jian, “A generalized projection-succesive linear equations algorithm for nonlinearly equality and inequality constrainted optimization and its rate of convergence,” Applied Mathematics—-A J. of Chinese Universities, Series B, vol. 12, no. 3, pp. 343-354, 1997. · Zbl 0888.90133 · doi:10.1007/s11766-997-0035-6
[14] J.-B. Jian, “A generalized subfeasible directions method for optimization problems using generalized projection,” Guangxi Science (China), vol. 4, no. 4, pp. 246-250, 1997.
[15] J.-B. Jian, “Researches on superliearly and quadratically convergent algorithms for nonlinearly constrained optimization,” Ph.D. Thesis, School of Xi’a n Jiaotong University, Xi’a n, China, 2000.
[16] J.-B. Jian, “Two extension models of SQP and SSLE algorithms for optimization and their superlinear and quadratic convergence,” Appled Mathematics—-A Journal of Chinese Universities, Ser. A, vol. 16, pp. 435-444. · Zbl 1015.90088
[17] J.-B. Jian and S.-J Xue, “A class of superlinearly convergent feasible methods for nonlinearly constrained optimization,” J. of Mathematical Research and Exposition, vol. 19, no. 1, pp. 133-140, 1999. · Zbl 1054.90631
[18] H. Jiang and D. Ralph, “QPECgen, a MATHLAB generator for mathematical programs with quadratical objectives and affine variational inequality constraints, Computational Optimization and Applications, vol. 14, pp. 25-59, 1999. · Zbl 1040.90500 · doi:10.1023/A:1008696504163
[19] H. Jiang and D. Ralph, “Smooth SQP methods for mathematical programs with nonlinear complementarity constraints,” SIAM J. On Optimization, vol. 13, pp. 779-808, 2000. · Zbl 0955.90134 · doi:10.1137/S1052623497332329
[20] C. Kanzow, “Some noninterior continuation methods for linear complementarity problems,” SIAM J. on Matrix analysis and Applications, vol. 17, pp. 851-868. · Zbl 0868.90123 · doi:10.1137/S0895479894273134
[21] C. Kanzow and H. Kleninmichel, “A new class of semismooth Newton-type methods for nonlinear complementarity problems,” Numer. Funct. Anal. Optim. Appl., vol. 11, pp. 227-251, 1998. · Zbl 0913.90250
[22] Kocvara, M.; Outrata, J. V.; Du, D. Z. (ed.); Qi, L. (ed.); Womersley, R. S. (ed.), On the solution of optimun design problems withvariational inequalities, 172-192 (1995), Singapore · Zbl 0952.49034 · doi:10.1142/9789812812827_0011
[23] M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, “A unified approach to interior point algorithms for linear complementarity problems,” Springer-Verlag: Berlin, Heideberg, 1991. · Zbl 0766.90077 · doi:10.1007/3-540-54509-3
[24] M.B. Lignola and J. Morgan, “Existence and solution to generalized bilevel programming problems,” Preprint no. 18, Dipartimento di Mathematicae Applicazioni, Universita di Napoli “Federico II,” Italy, 1996.
[25] M.B. Lignola and J. Morgan, “Stability of regularized bilevel programming problems,” Journal of Optimization Theory and Applications, vol. 93, pp. 575-596, 1997. · Zbl 0872.90092 · doi:10.1023/A:1022695113803
[26] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical programs with equilibrium constraints, Cambridge University Press, 1996.
[27] Z.-Q. Luo, J.-S. Pang, and D. Ralph, “Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints,” in Multilevel Optimization: Algorithms, Complexity and Applications, A. Migdalas et al. (Eds.), Kluwer Academic Publishers, 1998. · Zbl 0897.90184
[28] Z.-Q. Luo, J.-S. Pang, D. Ralph, and S.-Q. Wu, “Exact penalization and stationaru condidtions of mathematical programs with equilibrium constraints,” Mathematical Programming, vol. 75, pp.19-76, 1996. · Zbl 0870.90092 · doi:10.1007/BF02592205
[29] Mangasarian, O. L.; Di Pillo, G. (ed.); Giannessi, F. (ed.), Mathematical programming in machine learning, 340-357 (1996), New York
[30] J.V. Outrata, “On optimization problems with varuational inequality constraints,” SIAM Journal on Optimization, vol. 4, pp. 340-357, 1994. · Zbl 0826.90114 · doi:10.1137/0804019
[31] J.V. Outrata and J. Zowe, “A numerical approach to optimization problems with variational inequality constraints,” Mathematical Programming, vol. 68, pp. 105-130, 1995. · Zbl 0835.90093
[32] E.R. Panier and A.L. Tits, “A superlinearly convergent feasible method for solution of inequality constrained optimization problems,” SIAM J. Control and Optimization, vol. 25, pp. 934-950, 1987. · Zbl 0634.90054 · doi:10.1137/0325051
[33] E.R. Panier, A.L. Tits, and J.N. Herskovits, “A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization,” SIAM J. Cotrol and Optimization, vol. 26, no. 4, pp. 788-811, 1988. · Zbl 0651.90072 · doi:10.1137/0326046
[34] D. Ralph, “Sequential quadratic programming for mathematical programs with linear complementarity constraints,” in CTAC95 Computational Techniques and Applications, R.L. May and Easton (Eds.), World Scientific, 1996. · Zbl 0910.90253
[35] H. Scheel and S. Scholtes, “Mathematical programs with equilibrium constraints: Stationarity, optimality, and sensityvity,” Repo 25, The Judge Institute of Management Studies, University of Cambridge, England, 1997. · Zbl 1073.90557
[36] S.J. Wright, “Superlinear convergence of a stabilized SQP method to a degenerate solution,” Computational Optimization and Applications, vol. 11, pp. 253-275, 1998. · Zbl 0917.90279 · doi:10.1023/A:1018665102534
[37] S.J. Wright, “Constraint identification and algorithm stabilization for degenerate nonlinera programs,” Mathematical Programming, vol. 95, pp. 137-160, 2003. · Zbl 1030.90126 · doi:10.1007/s10107-002-0344-8
[38] J.J. Ye, “Optimality conditions for optimization problems with complementarity constraints,” SIAM J. Optimization, vol. 9, pp. 374-387, 1999. · Zbl 0967.90092 · doi:10.1137/S1052623497321882
[39] J.J. Ye and D.L. Zhu, “Optimality constraints for bilevel programming problems,” Optimization, vol. 33, pp. 9-27, 1995. · Zbl 0820.65032 · doi:10.1080/02331939508844060
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.