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-160. 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-429. 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-213. doi: 10.1007/s101070100263.  Google Scholar

[4]

D. Z. Du, A gradient projection algorithm for nonlinear constraints, Acta Mathematicae Applicatae Sinica, 8 (1985), 7-16.  Google Scholar

[5]

F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints, SIAM J. Optimiz., 9 (1999), 14-32. 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-397. 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, Springer-Verlag, 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, Science Press, Beijing, 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-70. 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-351.  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-1459. 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-618. 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-91,103.  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-976. 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-528. 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-700. 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-601. 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, Guangxi University in Nanning, China, 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-811. 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-132. 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-124. 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-471. 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-910. 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-160. 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-429. 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-213. doi: 10.1007/s101070100263.  Google Scholar

[4]

D. Z. Du, A gradient projection algorithm for nonlinear constraints, Acta Mathematicae Applicatae Sinica, 8 (1985), 7-16.  Google Scholar

[5]

F. Facchinei, A. Fischer and C. Kanzow, On the accurate identification of active constraints, SIAM J. Optimiz., 9 (1999), 14-32. 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-397. 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, Springer-Verlag, 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, Science Press, Beijing, 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-70. 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-351.  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-1459. 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-618. 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-91,103.  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-976. 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-528. 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-700. 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-601. 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, Guangxi University in Nanning, China, 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-811. 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-132. 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-124. 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-471. 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-910. doi: 10.3934/jimo.2010.6.895.  Google Scholar

[1]

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 & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[2]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[3]

Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

[4]

Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[5]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[6]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

[7]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003

[8]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123

[9]

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

[10]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021028

[11]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391

[12]

Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417

[13]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[14]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

[15]

Manuel Fernández-Martínez. A real attractor non admitting a connected feasible open set. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 723-725. doi: 10.3934/dcdss.2019046

[16]

Ryan Loxton, Qun Lin, Volker Rehbock, Kok Lay Teo. Control parameterization for optimal control problems with continuous inequality constraints: New convergence results. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 571-599. doi: 10.3934/naco.2012.2.571

[17]

Maria Laura Delle Monache, Paola Goatin. A front tracking method for a strongly coupled PDE-ODE system with moving density constraints in traffic flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 435-447. doi: 10.3934/dcdss.2014.7.435

[18]

Nithirat Sisarat, Rabian Wangkeeree, Gue Myung Lee. Some characterizations of robust solution sets for uncertain convex optimization problems with locally Lipschitz inequality constraints. Journal of Industrial & Management Optimization, 2020, 16 (1) : 469-493. doi: 10.3934/jimo.2018163

[19]

Rong Hu, Ya-Ping Fang, Nan-Jing Huang. Levitin-Polyak well-posedness for variational inequalities and for optimization problems with variational inequality constraints. Journal of Industrial & Management Optimization, 2010, 6 (3) : 465-481. doi: 10.3934/jimo.2010.6.465

[20]

Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005

2020 Impact Factor: 1.801

Metrics

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

Other articles
by authors

[Back to Top]