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

Guodong Ma; Jinbao Jian

doi:10.3934/jimo.2015.11.307

Article Contents

2015, Volume 11, Issue 1: 307-328. Doi: 10.3934/jimo.2015.11.307

This issue Previous Article The warehouse-retailer network design game Next Article Second order sufficient optimality conditions for hybrid control problems with state jump

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

Guodong Ma^1, and
Jinbao Jian^2,

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

Received: November 2012

Revised: February 2014

Published: January 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Inequality constraints,
optimization,
QP-free algorithm,
method of quasi-strongly sub-feasible directions,
working set,
global and strong convergence.

Mathematics Subject Classification: Primary: 90C30, 49M37; Secondary: 65K05.

Citation:

Related Papers

Cited by

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.