×

Superlinearly convergent norm-relaxed SQP method based on active set identification and new line search for constrained minimax problems. (English) Zbl 1309.90122

Summary: In this paper, the minimax problems with inequality constraints are discussed, and an alternative fast convergent method for the discussed problems is proposed. Compared with the previous work, the proposed method has the following main characteristics. First, the active set identification which can reduce the scale and the computational cost is adopted to construct the direction finding subproblems. Second, the master direction and high-order correction direction are computed by solving a new type of norm-relaxed quadratic programming subproblem and a system of linear equations, respectively. Third, the step size is yielded by a new line search which combines the method of strongly sub-feasible direction with the penalty method. Fourth, under mild assumptions without any strict complementarity, both the global convergence and rate of superlinear convergence can be obtained. Finally, some numerical results are reported.

MSC:

90C47 Minimax problems in mathematical programming
90C55 Methods of successive quadratic programming type
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhou, J.L., Tits, A.L.: Nonmonotone line search for minimax problems. J. Optim. Theory Appl. 76, 455-476 (1993) · Zbl 0792.90079 · doi:10.1007/BF00939377
[2] Rustem, B., Nguyen, Q.: An algorithm for the inequality-constrained discrete minimax problem. SIAM J. Optim. 8, 265-283 (1998) · Zbl 0911.90310 · doi:10.1137/S1056263493260386
[3] Yu, Y.H., Gao, L.: Nonmonotone line search algorithm for constrained minimax problems. J. Optim. Theory Appl. 115, 419-446 (2002) · Zbl 1039.90089 · doi:10.1023/A:1020896407415
[4] Jian, J.B., Quan, R., Zhang, X.L.: Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints. J. Comput. Appl. Math. 205, 406-429 (2007) · Zbl 1149.90148 · doi:10.1016/j.cam.2006.05.034
[5] Reemtsen, R.: A cutting plane method for solving minimax problems in the complex plane. Numer. Algorithms 2, 409-436 (1992) · Zbl 0756.65092 · doi:10.1007/BF02139477
[6] Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20, 267-279 (2001) · Zbl 1054.90087 · doi:10.1023/A:1011211101714
[7] Polak, E., Womersley, R.S., Yin, H.X.: An algorithm based on active sets and smoothing for discretized semi-infinite minimax problems. J. Math. Anal. Appl. 138, 311-328 (2008) · Zbl 1211.90283
[8] Zhu, Z.B., Cai, X., Jian, J.B.: An improved SQP algorithm for solving minimax problems. Appl. Math. Lett. 22, 464-469 (2009) · Zbl 1189.90193 · doi:10.1016/j.aml.2008.06.017
[9] Jian, J.B., Zhang, X.L., Quan, R., Ma, Q.: Generalized monotone line search SQP algorithm for constrained minimax problems. Optimization 58, 101-131 (2009) · Zbl 1158.90404 · doi:10.1080/02331930801951140
[10] Han, D.L., Jian, J.B., Li, J.: On the accurate identification of active set for constrained minimax problems. Nonlinear Anal., Real World Appl. 74, 3022-3032 (2011) · Zbl 1235.90150 · doi:10.1016/j.na.2011.01.024
[11] Royset, J.O., Pee, E.Y.: Rate of convergence analysis of discretization and smoothing algorithms for semi-infinite minimax problems. J. Optim. Theory Appl. 155, 855-882 (2012) · Zbl 1257.90109 · doi:10.1007/s10957-012-0109-3
[12] Bagirov, A.M., Al Nuaimat, A., Sultanova, N.: Hyperbolic smoothing function method for minimax problems. Optimization 62, 759-782 (2013) · Zbl 1282.65065 · doi:10.1080/02331934.2012.675335
[13] Hare, W., Macklem, M.: Derivative-free optimization methods for finite minimax problems. Optim. Methods Softw. 28, 300-312 (2013) · Zbl 1270.90099 · doi:10.1080/10556788.2011.638923
[14] Hare, W., Nutini, J.: A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput. Optim. Appl. 56, 1-38 (2013) · Zbl 1300.90064 · doi:10.1007/s10589-013-9547-6
[15] Wang, F.S.: A hybrid algorithm for linearly constrained minimax problems. Ann. Oper. Res. 206, 501-525 (2013) · Zbl 1297.90176 · doi:10.1007/s10479-012-1274-3
[16] Jian, J.B., Mo, X.D., Qiu, L.J., Yang, S.M., Wang, F.S.: Simple sequential quadratically constrained quadratic programming feasible algorithm with active identification sets for constrained minimax problems. J. Optim. Theory Appl. (2013, in press). doi:10.1007/s10957-013-0339-z · Zbl 1316.90061
[17] Zoutendijk, G.: Methods of Feasible Directions. Elsevier, Amsterdam (1960) · Zbl 0097.35408
[18] Topkis, D.M., Veinott, A.F.: On the convergence of some feasible direction algorithms for nonlinear programming. SIAM J. Control 5, 268-279 (1967) · Zbl 0158.18805 · doi:10.1137/0305018
[19] Pironneau, O., Polak, E.: Rate of convergence of a class of methods of feasible directions. SIAM J. Numer. Anal. 10, 161-173 (1973) · Zbl 0283.65032 · doi:10.1137/0710017
[20] Cawood, M.E., Kostreva, M.M.: Norm-relaxed method of feasible direction for solving the nonlinear programming problems. J. Optim. Theory Appl. 83, 311-320 (1994) · Zbl 0828.90117 · doi:10.1007/BF02190059
[21] Chen, X., Kostreva, M.M.: A generalization of the norm-relaxed method of feasible directions. Appl. Math. Comput. 102, 257-273 (1999) · Zbl 0935.65064 · doi:10.1016/S0096-3003(98)10025-5
[22] Kostreva, M.M., Chen, X.: A superlinearly convergent method of feasible directions. Appl. Math. Comput. 116, 231-244 (2000) · Zbl 1112.90380 · doi:10.1016/S0096-3003(99)00176-9
[23] Lawrence, C.T., Tits, A.L.: A computationally efficient feasible sequential quadratic programming algorithm. SIAM J. Optim. 11, 1092-1118 (2001) · Zbl 1035.90105 · doi:10.1137/S1052623498344562
[24] Chen, X., Kostreva, M.M.: Global convergence analysis of algorithm for finding feasible points in norm-relaxed method of feasible directions. J. Optim. Theory Appl. 100, 287-309 (1999) · Zbl 0915.90234 · doi:10.1023/A:1021778002066
[25] Jian, J.B.: Strong combined Phase I-Phase II methods of sub-feasible directions. Math. Econ. 12, 64-70 (1995) (in Chinese)
[26] Jian, J.B., Zheng, H.Y., Hu, Q.J., Tang, C.M.: A new norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization. Appl. Math. Comput. 168, 1-28 (2005) · Zbl 1087.65062 · doi:10.1016/j.amc.2004.08.009
[27] Jian, J.B., Zheng, H.Y., Hu, Q.J., Tang, C.M.: A new superlinearly convergent norm-relaxed method of strongly sub-feasible direction for inequality constrained optimization. Appl. Math. Comput. 182, 955-976 (2006) · Zbl 1108.65064 · doi:10.1016/j.amc.2006.04.050
[28] Jian, J.B.: Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments. Science Press, Beijing (2010)
[29] Solodov, M.V.: Global convergence of an SQP method without boundedness assumptions on any of iterative sequences. Math. Program. 118, 1-12 (2009) · Zbl 1176.90579 · doi:10.1007/s10107-007-0180-y
[30] Zheng, H.Y., Jian, J.B., Tang, C.M., Quan, R.: A new norm-relaxed SQP algorithm with global convergence. Appl. Math. Lett. 23, 670-675 (2010) · Zbl 1186.90088 · doi:10.1016/j.aml.2010.02.005
[31] Burke, J.V., More, J.J.: On the identification of active constraints. SIAM J. Numer. Anal. 25, 1197-1211 (1998) · Zbl 0662.65052 · doi:10.1137/0725068
[32] Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints. SIAM J. Optim. 9, 14-32 (1998) · Zbl 0960.90080 · doi:10.1137/S1052623496305882
[33] Hare, W.L., Lewis, A.S.: Identifying active constraints via partial smoothness and prox-regularity. J. Convex Anal. 11, 251-266 (2004) · Zbl 1178.90314
[34] Jian, J.B., Liu, Y.: A superlinearly convergent method of quasi-strongly sub-feasible direction with active set identifying for constrained optimization. Nonlinear Anal., Real World Appl. 12, 2717-2729 (2011) · Zbl 1223.49034 · doi:10.1016/j.nonrwa.2011.03.017
[35] Chao, M.T., Wang, Z.X., Liang, Y.M., Hu, Q.J.: Quadratically constraint quadratical algorithm model for nonlinear minimax problems. Appl. Math. Comput. 205, 247-262 (2008) · Zbl 1163.65036 · doi:10.1016/j.amc.2008.08.033
[36] Karmitsa, N.: Test problems for large-scale nonsmooth minimization. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing, No. B.4 (2007) · Zbl 1035.90105
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.