American Institute of Mathematical Sciences

January  2015, 11(1): 307-328. doi: 10.3934/jimo.2015.11.307

A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization

 1 Department of Mathematics, Shanghai University, Shanghai 200444, China 2 School of Mathematics and Information Science, Yulin Normal University, Yulin 537000, China

Received  November 2012 Revised  February 2014 Published  May 2014

In this paper, combining the method of quasi-strongly sub-feasible directions (MQSSFD) and the working set technique, a new QP-free algorithm with an arbitrary initial iteration point for solving inequality constrained optimization is proposed. At each iteration, the algorithm solves only two systems of linear equations with a same uniformly nonsingular coefficient matrix to obtain the search direction. Furthermore, the positive definiteness assumption on the Hessian estimate is relaxed. Under some necessary assumptions, the new algorithm not only possesses global and strong convergence, but also ensures that the iteration points can get into the feasible set after finite iterations. Finally, a series of preliminary numerical results are reported to show that the algorithm is promising.
Citation: Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial & Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307
References:
 [1] I. Bongartz, A. R. Conn, N. I. Gould and P. L. Toint, CUTE: Constrained and unconstrained testing environment,, Transactions on Mathematical Software (ACM), 21 (1995), 123.  doi: 10.1145/200979.201043.  Google Scholar [2] L. F. Chen, Y. L. Wang and G. P. Guo, A feasible active set QP-free method for nonlinear programming,, SIAM J. Optimiz., 17 (2006), 401.  doi: 10.1137/040605904.  Google Scholar [3] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Math. Program., 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar [4] D. Z. Du, A gradient projection algorithm for nonlinear constraints,, Acta Mathematicae Applicatae Sinica, 8 (1985), 7.   Google Scholar [5] F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints,, SIAM J. Optimiz., 9 (1999), 14.  doi: 10.1137/S1052623496305882.  Google Scholar [6] Z. Y. Gao, G. P. He and F. Wu, Sequential system of linear equations algorithm for nonlinear optimization problems with general constraints,, J. Optimiz. Theory App., 95 (1997), 371.  doi: 10.1023/A:1022639306130.  Google Scholar [7] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes,, Lecture Notes in Economics and Mathematical Systems, (1981).  doi: 10.1007/BF00934594.  Google Scholar [8] J. B. Jian, Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments,, $1^{st}$ edition, (2010).   Google Scholar [9] J. B. Jian, Strong combined Phase I-Phase II methods of sub-feasible directions,, Math. Econ. (A Chinese Journal), 12 (1995), 64.   Google Scholar [10] J. B. Jian, Y. H. Chen and C. H. Guo, A strongly convergent method of quasi-strongly sub-feasible directions for constrained optimization,, Pacific J. Optim., 7 (2011), 339.   Google Scholar [11] J. B. Jian, W. X. Cheng and X. Y. Ke, Finitely convergent $\varepsilon$-generalized projection algorithm for nonlinear systems,, J. Math. Anal. Appl., 332 (2007), 1446.  doi: 10.1016/j.jmaa.2006.11.020.  Google Scholar [12] J. B. Jian, G. D. Ma and C. H. Guo, A new $\varepsilon$-generalized projection method of strongly sub-feasible directions for inequality constrained optimization,, J. Systems Sci. Comp., 24 (2011), 604.  doi: 10.1007/s11424-011-8105-5.  Google Scholar [13] J. B. Jian and K. C. Zhang, Subfeasible direction method with strong convergence for inequality constrained optimization,, J. Xi'an Jiaotong Univ. (A Chinese Journal), 33 (1999), 88.   Google Scholar [14] J. B. Jian, H. Y. Zheng, C. M. Tang and Q. J. Hu, A new superlinearly convergent norm relaxed method of strongly sub-feasible direction for inequality constrained optimization,, Appl. Math. Compu., 182 (2006), 955.  doi: 10.1016/j.amc.2006.04.050.  Google Scholar [15] D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization,, Math. Program., 45 (1989), 503.  doi: 10.1007/BF01589116.  Google Scholar [16] G. D. Ma and J. B. Jian, An $\varepsilon$-generalized gradient projection method for nonlinear minimax problems,, Nonlinear Dyn., 75 (2014), 693.   Google Scholar [17] Z. Q. Meng, Q. Y. Hu and C. Y. Dang, A penalty function algorithm with objective parameters for nonlinear mathematical programming,, J. Ind. Manag. Optim., 5 (2009), 568.  doi: 10.3934/jimo.2009.5.585.  Google Scholar [18] H. Q. Pan, A Strong Sub-Feasible Primal-Dual Interior Point Algorithm for Nonlinear Inequality Constrained Optimization,, Master's thesis, (2007).   Google Scholar [19] 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. Control Optim., 26 (1988), 788.  doi: 10.1137/0326046.  Google Scholar [20] H. D. Qi and L. Q. Qi, A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization,, SIAM J. Control Optim., 11 (2000), 113.  doi: 10.1137/S1052623499353935.  Google Scholar [21] C. G. Shen, W. J. Xue and D. G. Pu, An infeasible nonmonotone SSLE algorithm for nonlinear programming,, Math. Method Oper. Res., 71 (2010), 103.  doi: 10.1007/s00186-009-0287-4.  Google Scholar [22] Y. L. Wang, L. F. Chen and G. P. He, Sequential system of linear equations method for general constrained optimization without strict complementarity,, J. Comput. Appl. Math., 182 (2005), 447.  doi: 10.1016/j.cam.2004.12.023.  Google Scholar [23] C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems,, J. Ind. Manag. Optim., 6 (2010), 895.  doi: 10.3934/jimo.2010.6.895.  Google Scholar

show all references

References:
 [1] I. Bongartz, A. R. Conn, N. I. Gould and P. L. Toint, CUTE: Constrained and unconstrained testing environment,, Transactions on Mathematical Software (ACM), 21 (1995), 123.  doi: 10.1145/200979.201043.  Google Scholar [2] L. F. Chen, Y. L. Wang and G. P. Guo, A feasible active set QP-free method for nonlinear programming,, SIAM J. Optimiz., 17 (2006), 401.  doi: 10.1137/040605904.  Google Scholar [3] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Math. Program., 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar [4] D. Z. Du, A gradient projection algorithm for nonlinear constraints,, Acta Mathematicae Applicatae Sinica, 8 (1985), 7.   Google Scholar [5] F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints,, SIAM J. Optimiz., 9 (1999), 14.  doi: 10.1137/S1052623496305882.  Google Scholar [6] Z. Y. Gao, G. P. He and F. Wu, Sequential system of linear equations algorithm for nonlinear optimization problems with general constraints,, J. Optimiz. Theory App., 95 (1997), 371.  doi: 10.1023/A:1022639306130.  Google Scholar [7] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes,, Lecture Notes in Economics and Mathematical Systems, (1981).  doi: 10.1007/BF00934594.  Google Scholar [8] J. B. Jian, Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments,, $1^{st}$ edition, (2010).   Google Scholar [9] J. B. Jian, Strong combined Phase I-Phase II methods of sub-feasible directions,, Math. Econ. (A Chinese Journal), 12 (1995), 64.   Google Scholar [10] J. B. Jian, Y. H. Chen and C. H. Guo, A strongly convergent method of quasi-strongly sub-feasible directions for constrained optimization,, Pacific J. Optim., 7 (2011), 339.   Google Scholar [11] J. B. Jian, W. X. Cheng and X. Y. Ke, Finitely convergent $\varepsilon$-generalized projection algorithm for nonlinear systems,, J. Math. Anal. Appl., 332 (2007), 1446.  doi: 10.1016/j.jmaa.2006.11.020.  Google Scholar [12] J. B. Jian, G. D. Ma and C. H. Guo, A new $\varepsilon$-generalized projection method of strongly sub-feasible directions for inequality constrained optimization,, J. Systems Sci. Comp., 24 (2011), 604.  doi: 10.1007/s11424-011-8105-5.  Google Scholar [13] J. B. Jian and K. C. Zhang, Subfeasible direction method with strong convergence for inequality constrained optimization,, J. Xi'an Jiaotong Univ. (A Chinese Journal), 33 (1999), 88.   Google Scholar [14] J. B. Jian, H. Y. Zheng, C. M. Tang and Q. J. Hu, A new superlinearly convergent norm relaxed method of strongly sub-feasible direction for inequality constrained optimization,, Appl. Math. Compu., 182 (2006), 955.  doi: 10.1016/j.amc.2006.04.050.  Google Scholar [15] D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization,, Math. Program., 45 (1989), 503.  doi: 10.1007/BF01589116.  Google Scholar [16] G. D. Ma and J. B. Jian, An $\varepsilon$-generalized gradient projection method for nonlinear minimax problems,, Nonlinear Dyn., 75 (2014), 693.   Google Scholar [17] Z. Q. Meng, Q. Y. Hu and C. Y. Dang, A penalty function algorithm with objective parameters for nonlinear mathematical programming,, J. Ind. Manag. Optim., 5 (2009), 568.  doi: 10.3934/jimo.2009.5.585.  Google Scholar [18] H. Q. Pan, A Strong Sub-Feasible Primal-Dual Interior Point Algorithm for Nonlinear Inequality Constrained Optimization,, Master's thesis, (2007).   Google Scholar [19] 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. Control Optim., 26 (1988), 788.  doi: 10.1137/0326046.  Google Scholar [20] H. D. Qi and L. Q. Qi, A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization,, SIAM J. Control Optim., 11 (2000), 113.  doi: 10.1137/S1052623499353935.  Google Scholar [21] C. G. Shen, W. J. Xue and D. G. Pu, An infeasible nonmonotone SSLE algorithm for nonlinear programming,, Math. Method Oper. Res., 71 (2010), 103.  doi: 10.1007/s00186-009-0287-4.  Google Scholar [22] Y. L. Wang, L. F. Chen and G. P. He, Sequential system of linear equations method for general constrained optimization without strict complementarity,, J. Comput. Appl. Math., 182 (2005), 447.  doi: 10.1016/j.cam.2004.12.023.  Google Scholar [23] C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems,, J. Ind. Manag. Optim., 6 (2010), 895.  doi: 10.3934/jimo.2010.6.895.  Google Scholar
 [1] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [2] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [3] Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149 [4] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [5] David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 [6] Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035 [7] Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817 [8] Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 [9] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [10] Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243 [11] Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094 [12] Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212 [13] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [14] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [15] Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109 [16] Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223 [17] Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053 [18] Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29 [19] Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 [20] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

2019 Impact Factor: 1.366