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 and 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.

[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.

[3]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.

[4]

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

[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.

[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.

[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.

[8]

J. B. Jian, Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments, $1^{st}$ edition, Science Press, Beijing, 2010.

[9]

J. B. Jian, Strong combined Phase I-Phase II methods of sub-feasible directions, Math. Econ. (A Chinese Journal), 12 (1995), 64-70.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

G. D. Ma and J. B. Jian, An $\varepsilon$-generalized gradient projection method for nonlinear minimax problems, Nonlinear Dyn., 75 (2014), 693-700.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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.

[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.

[3]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.

[4]

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

[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.

[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.

[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.

[8]

J. B. Jian, Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments, $1^{st}$ edition, Science Press, Beijing, 2010.

[9]

J. B. Jian, Strong combined Phase I-Phase II methods of sub-feasible directions, Math. Econ. (A Chinese Journal), 12 (1995), 64-70.

[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.

[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.

[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.

[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.

[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.

[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.

[16]

G. D. Ma and J. B. Jian, An $\varepsilon$-generalized gradient projection method for nonlinear minimax problems, Nonlinear Dyn., 75 (2014), 693-700.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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 and 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 and 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 and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

[4]

Lei Guo, Gao-Xi Li, Xinmin Yang. Global convergence of augmented Lagrangian method applied to mathematical program with switching constraints. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022114

[5]

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 and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[6]

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 and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[7]

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

[8]

Yue Sun, Zhijian Yang, Yanxia Qu. Strong global and exponential attractors for a nonlinear strongly damped hyperbolic equation. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022116

[9]

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

[10]

Livia Betz. Strong stationarity for a highly nonsmooth optimization problem with control constraints. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022047

[11]

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

[12]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[13]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2022, 12 (4) : 679-692. doi: 10.3934/naco.2021028

[14]

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

[15]

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

[16]

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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[17]

He Huang, Zhen He. A global optimization method for multiple response optimization problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022016

[18]

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

[19]

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

[20]

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 and Optimization, 2012, 2 (3) : 571-599. doi: 10.3934/naco.2012.2.571

2021 Impact Factor: 1.411

Metrics

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

Other articles
by authors

[Back to Top]