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]

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]

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

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

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Laetitia Paoli. A proximal-like algorithm for vibro-impact problems with a non-smooth set of constraints. Conference Publications, 2011, 2011 (Special) : 1186-1195. doi: 10.3934/proc.2011.2011.1186

[18]

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

[19]

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

[20]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]