• Previous Article
    Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects
  • JIMO Home
  • This Issue
  • Next Article
    Infinite-time ruin probability of a renewal risk model with exponential Levy process investment and dependent claims and inter-arrival times
April  2017, 13(2): 1009-1024. doi: 10.3934/jimo.2016059

A superlinearly convergent hybrid algorithm for solving nonlinear programming

1. 

School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China

2. 

School of Management, Shanghai University, Shanghai 200444, China

3. 

School of Mathematics and Physics, Huaiyin Institute of Technology, Huaian, Jiangsu 223003, China

Received  April 2015 Revised  June 2016 Published  August 2016

Fund Project: The research is supported by the National Natural Science Foundation of China (No. 11501350)

In this paper, a superlinearly convergent hybrid algorithm is proposed for solving nonlinear programming. First of all, an improved direction is obtained by a convex combination of the solution of an always feasible quadratic programming (QP) subproblem and a mere feasible direction, which is generated by a reduced system of linear equations (SLE). The coefficient matrix of SLE only consists of the constraints and their gradients corresponding to the working set. Then, the second-order correction direction is obtained by solving another reduced SLE to overcome the Maratos effect and obtain the superlinear convergence. In particular, the convergence rate is proved to be locally one-step superlinear under a condition weaker than the strong second-order sufficient condition and without the strict complementarity. Moreover, the line search in our algorithm can effectively combine the initialization processes with the optimization processes, and the line search conditions are weaker than the previous work. Finally, some numerical results are reported.

Citation: Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059
References:
[1]

R. H. ByrdF. E. Curtis and J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM Journal on Optimizaion, 20 (2010), 2281-2299. doi: 10.1137/080738222. Google Scholar

[2]

J. F. BonnansE. R. PanierA. L. Tits and J. L. Zhou, Avoiding the Maratos effect by means of a nonmonotone line search. Ⅱ. Inequality constrained problems-feasible iterates, SIAM Journal on Numerical Analysis, 29 (1992), 1187-1202. doi: 10.1137/0729072. Google Scholar

[3]

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

[4]

F. FacchineiA. Fischer and C. Kanzow, On the accurate identification of active constraints, SIAM Journal of Optimization, 9 (1998), 14-32. doi: 10.1137/S1052623496305882. Google Scholar

[5]

C. H. GuoY. Q. Bai and J. B. Jian, An improved sequential quadratic programming algorithm for solving general nonlinear programming problems, Journal of Mathematical Analysis and Applications, 409 (2014), 777-789. doi: 10.1016/j.jmaa.2013.06.052. Google Scholar

[6]

N. I. M. Gould and D. P. Robinson, A second derivative SQP method: Local convergence and practical issues, SIAM Journal on Optimizaion, 20 (2010), 2049-2079. doi: 10.1137/080744554. Google Scholar

[7]

N. I. M. GouldD. Orban and Ph. L. Toint, A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 353-372. doi: 10.1145/962437.962438. Google Scholar

[8]

M. Heinkenschloss and D. Ridzal, A matrix-free trust-region SQP method for equality constrained optimization, SIAM Journal on Optimization, 24 (2014), 1507-1541. doi: 10.1137/130921738. Google Scholar

[9]

W. Hock and K. Schittkowski, Test examples for nonlinear programming codes, Journal of Optimization Theory and Applications, 30 (1980), 127-129. doi: 10.1007/BF00934594. Google Scholar

[10]

J. B. JianC. H. GuoC. M. Tang and Y. Q. Bai, A new superlinearly convergent algorithm of combining QP subproblem with system of linear equations for nonlinear optimization, Journal of Computational and Applied Mathematics, 273 (2015), 88-102. doi: 10.1016/j.cam.2014.06.009. Google Scholar

[11] J. B. Jian, Fast algorithms for smooth constrained optimization---theoretical analysis and numerical experiments, Science Press, Beijing, 2010. Google Scholar
[12]

J. B. Jian, A strong subfeasible direction algorithm with superlinear convergence, Journal of Systems Science and Systems Engineering, 5 (1996), 287-295. Google Scholar

[13]

J. B. JianC. M. TangQ. J. Hu and H. Y. Zheng, A new superlinearly convergent strongly subfeasible sequential quadratic programming algorithm for inequality-constrained optimization, Numerical Functional Analysis and Optimization, 29 (2008), 376-409. doi: 10.1080/01630560802000918. Google Scholar

[14]

J. B. JianY. H. Chen and C. H. Guo, A strongly convergent method of quasi-strongly sub-feasible directions for constrained optimization, Pacific Journal of Optimization, 7 (2011), 339-351. Google Scholar

[15]

J. B. JianX. Y. KeH. Y. Zheng and C. M. Tang, A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization, Journal of Computational and Applied Mathematics, 223 (2009), 1013-1027. doi: 10.1016/j.cam.2008.03.048. Google Scholar

[16]

P. MorinR. H. NochettoM. S. Pauletti and M. Verani, Adaptive SQP Method for Shape Optimization, Numerical Mathematics and Advanced Applications 2009, (2010), 663-673. doi: 10.1007/978-3-642-11795-4_71. Google Scholar

[17]

J. L. MoralesJ. Nocedal and Y. Wu, A sequential quadratic programming algorithm with an additional equality constrained phase, IMA Journal of Numerical Analysis, 32 (2012), 553-579. doi: 10.1093/imanum/drq037. Google Scholar

[18]

D. Q. Mayne and E. Polak, A surperlinearly convergent algorithm for constrained optimization problems, Algorithms for Constrained Minimization of Smooth Nonlinear Functions, (1982), 45-61. Google Scholar

[19]

E. R. Panier and A. L. Tits, On combining feasibility, descent and superlinear convergence in inequality constrained optimization, Mathematical Programming, 59 (1993), 261-276. doi: 10.1007/BF01581247. Google Scholar

[20]

J. F. A. Pantoja and D. Q. Mayne, Exact penalty function algorithm with simple updating of the penalty parameter, Journal of Optimization Theory and Applications, 69 (1991), 441-467. doi: 10.1007/BF00940684. Google Scholar

[21]

K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., 1987. doi: 10.1007/978-3-642-61582-5. Google Scholar

[22]

P. Spellucci, A new technique for inconsistent QP problems in the SQP methods, Mathematical Methods of Operations Research, 47 (1998), 355-400. doi: 10.1007/BF01198402. Google Scholar

[23]

Y. L. WangL. F. Chen and G. P. He, Sequential systems of linear equations method for general constrained optimization without strict complementarity, Journal of Computational and Applied Mathematics, 182 (2005), 447-471. doi: 10.1016/j.cam.2004.12.023. Google Scholar

show all references

References:
[1]

R. H. ByrdF. E. Curtis and J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM Journal on Optimizaion, 20 (2010), 2281-2299. doi: 10.1137/080738222. Google Scholar

[2]

J. F. BonnansE. R. PanierA. L. Tits and J. L. Zhou, Avoiding the Maratos effect by means of a nonmonotone line search. Ⅱ. Inequality constrained problems-feasible iterates, SIAM Journal on Numerical Analysis, 29 (1992), 1187-1202. doi: 10.1137/0729072. Google Scholar

[3]

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

[4]

F. FacchineiA. Fischer and C. Kanzow, On the accurate identification of active constraints, SIAM Journal of Optimization, 9 (1998), 14-32. doi: 10.1137/S1052623496305882. Google Scholar

[5]

C. H. GuoY. Q. Bai and J. B. Jian, An improved sequential quadratic programming algorithm for solving general nonlinear programming problems, Journal of Mathematical Analysis and Applications, 409 (2014), 777-789. doi: 10.1016/j.jmaa.2013.06.052. Google Scholar

[6]

N. I. M. Gould and D. P. Robinson, A second derivative SQP method: Local convergence and practical issues, SIAM Journal on Optimizaion, 20 (2010), 2049-2079. doi: 10.1137/080744554. Google Scholar

[7]

N. I. M. GouldD. Orban and Ph. L. Toint, A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 353-372. doi: 10.1145/962437.962438. Google Scholar

[8]

M. Heinkenschloss and D. Ridzal, A matrix-free trust-region SQP method for equality constrained optimization, SIAM Journal on Optimization, 24 (2014), 1507-1541. doi: 10.1137/130921738. Google Scholar

[9]

W. Hock and K. Schittkowski, Test examples for nonlinear programming codes, Journal of Optimization Theory and Applications, 30 (1980), 127-129. doi: 10.1007/BF00934594. Google Scholar

[10]

J. B. JianC. H. GuoC. M. Tang and Y. Q. Bai, A new superlinearly convergent algorithm of combining QP subproblem with system of linear equations for nonlinear optimization, Journal of Computational and Applied Mathematics, 273 (2015), 88-102. doi: 10.1016/j.cam.2014.06.009. Google Scholar

[11] J. B. Jian, Fast algorithms for smooth constrained optimization---theoretical analysis and numerical experiments, Science Press, Beijing, 2010. Google Scholar
[12]

J. B. Jian, A strong subfeasible direction algorithm with superlinear convergence, Journal of Systems Science and Systems Engineering, 5 (1996), 287-295. Google Scholar

[13]

J. B. JianC. M. TangQ. J. Hu and H. Y. Zheng, A new superlinearly convergent strongly subfeasible sequential quadratic programming algorithm for inequality-constrained optimization, Numerical Functional Analysis and Optimization, 29 (2008), 376-409. doi: 10.1080/01630560802000918. Google Scholar

[14]

J. B. JianY. H. Chen and C. H. Guo, A strongly convergent method of quasi-strongly sub-feasible directions for constrained optimization, Pacific Journal of Optimization, 7 (2011), 339-351. Google Scholar

[15]

J. B. JianX. Y. KeH. Y. Zheng and C. M. Tang, A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization, Journal of Computational and Applied Mathematics, 223 (2009), 1013-1027. doi: 10.1016/j.cam.2008.03.048. Google Scholar

[16]

P. MorinR. H. NochettoM. S. Pauletti and M. Verani, Adaptive SQP Method for Shape Optimization, Numerical Mathematics and Advanced Applications 2009, (2010), 663-673. doi: 10.1007/978-3-642-11795-4_71. Google Scholar

[17]

J. L. MoralesJ. Nocedal and Y. Wu, A sequential quadratic programming algorithm with an additional equality constrained phase, IMA Journal of Numerical Analysis, 32 (2012), 553-579. doi: 10.1093/imanum/drq037. Google Scholar

[18]

D. Q. Mayne and E. Polak, A surperlinearly convergent algorithm for constrained optimization problems, Algorithms for Constrained Minimization of Smooth Nonlinear Functions, (1982), 45-61. Google Scholar

[19]

E. R. Panier and A. L. Tits, On combining feasibility, descent and superlinear convergence in inequality constrained optimization, Mathematical Programming, 59 (1993), 261-276. doi: 10.1007/BF01581247. Google Scholar

[20]

J. F. A. Pantoja and D. Q. Mayne, Exact penalty function algorithm with simple updating of the penalty parameter, Journal of Optimization Theory and Applications, 69 (1991), 441-467. doi: 10.1007/BF00940684. Google Scholar

[21]

K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., 1987. doi: 10.1007/978-3-642-61582-5. Google Scholar

[22]

P. Spellucci, A new technique for inconsistent QP problems in the SQP methods, Mathematical Methods of Operations Research, 47 (1998), 355-400. doi: 10.1007/BF01198402. Google Scholar

[23]

Y. L. WangL. F. Chen and G. P. He, Sequential systems of linear equations method for general constrained optimization without strict complementarity, Journal of Computational and Applied Mathematics, 182 (2005), 447-471. doi: 10.1016/j.cam.2004.12.023. Google Scholar

Figure 1.  The performance of ALGO 1 for solving problems in Table 1 under Case Ⅰ and Case Ⅱ, respectively.
Figure 2.  The performance of ALGO 1 for solving problems in Table 2 under Case Ⅰ and Case Ⅱ, respectively.
Figure 3.  The left figure shows the performance of ALGO 1-Ⅱ and ALGO-WCH, the right figure shows the performance of ALGO 1-Ⅱ and ALGO 2.1.
Table 1.  The corresponding parameters for the test problems (1)
Prob$n/m$$x^0$$\Upsilon(x^0)$Prob$n/m$$x^0$$\Upsilon(x^0)$
0132/3$(-5,-5)^T$5.000986/16$(20,0,\ldots,0)^T$19.69
0182/6$(1,5)^T$20.001007/4$(3,\ldots,3)^T$188.00
0232/9$(-5,-5)^T$11.001089/14$\begin{array}{ll}(0.1,5,0.5,\ 1,0,1,\ 0.5,5,0.1)^T\end{array}$23.26
0303/7$(5,10,15)^T$124.002242/8$(-2,-1)^T$5.00
0333/6$(1,4,7)^T$2.002252/5$(1,4)^T$3.00
0384/8$(0,3,1,2)^T$3.002342/5$(1,3)^T$9.00
0434/3$(-10,2,-8,5)^T$236.002503/8$(-3,-3,-3)^T$15.00
0444/10$(-20,\ldots,-20)^T$20.00#38; 2644/3$(0,0,0,3)^T$6.00
0663/8$(0,0,100)^T$90.003373/3$(1,1,0)^T$1.00
0764/7$(1,2,3,4)^T$7.003544/5$(1,-1,1,-1)^T$1.00
Prob$n/m$$x^0$$\Upsilon(x^0)$Prob$n/m$$x^0$$\Upsilon(x^0)$
0132/3$(-5,-5)^T$5.000986/16$(20,0,\ldots,0)^T$19.69
0182/6$(1,5)^T$20.001007/4$(3,\ldots,3)^T$188.00
0232/9$(-5,-5)^T$11.001089/14$\begin{array}{ll}(0.1,5,0.5,\ 1,0,1,\ 0.5,5,0.1)^T\end{array}$23.26
0303/7$(5,10,15)^T$124.002242/8$(-2,-1)^T$5.00
0333/6$(1,4,7)^T$2.002252/5$(1,4)^T$3.00
0384/8$(0,3,1,2)^T$3.002342/5$(1,3)^T$9.00
0434/3$(-10,2,-8,5)^T$236.002503/8$(-3,-3,-3)^T$15.00
0444/10$(-20,\ldots,-20)^T$20.00#38; 2644/3$(0,0,0,3)^T$6.00
0663/8$(0,0,100)^T$90.003373/3$(1,1,0)^T$1.00
0764/7$(1,2,3,4)^T$7.003544/5$(1,-1,1,-1)^T$1.00
Table 2.  The corresponding parameters for the test problems (2)
Prob$n/m$$x^0$$\Upsilon(x^0)$Prob$n/m$$x^0$$\Upsilon(x^0)$
Svanberg-2020/60$(5,\ldots,5)^T$4.20S394-4040/1$(0.4,\ldots,0.4)^T$5.40
$(0.5,\ldots,0.5)^T$2.42$(0.3,\ldots,0.3)^T$5.30
Svanberg-3030/90$(5,\ldots,5)^T$4.20S394-7070/1$(0.4,\ldots,0.4)^T$10.20
$(0.5,\ldots,0.5)^T$2.50$(0.3,\ldots,0.3)^T$5.30
Svanberg-4040/120$(5,\ldots,5)^T$4.20S394-100100/1$(0.4,\ldots,0.4)^T$15.00
$(0.5,\ldots,0.5)^T$2.54$(0.3,\ldots,0.3)^T$8.00
Svanberg-5050/150$(5,\ldots,5)^T$4.20S394-150150/1$(0.4,\ldots,0.4)^T$23.00
$(0.5,\ldots,0.5)^T$2.57$(0.3,\ldots,0.3)^T$12.50
Svanberg-200200/600$(5,\ldots,5)^T$4.20S394-200200/1$(0.4,\ldots,0.4)^T$31.00
$(0.5,\ldots,0.5)^T$2.64$(0.3,\ldots,0.3)^T$17.00
Svanberg-300300/900$(5,\ldots,5)^T$4.20S394-300300/1$(0.4,\ldots,0.4)^T$31.00
$(0.5,\ldots,0.5)^T$2.65$(0.3,\ldots,0.3)^T$17.00
Prob$n/m$$x^0$$\Upsilon(x^0)$Prob$n/m$$x^0$$\Upsilon(x^0)$
Svanberg-2020/60$(5,\ldots,5)^T$4.20S394-4040/1$(0.4,\ldots,0.4)^T$5.40
$(0.5,\ldots,0.5)^T$2.42$(0.3,\ldots,0.3)^T$5.30
Svanberg-3030/90$(5,\ldots,5)^T$4.20S394-7070/1$(0.4,\ldots,0.4)^T$10.20
$(0.5,\ldots,0.5)^T$2.50$(0.3,\ldots,0.3)^T$5.30
Svanberg-4040/120$(5,\ldots,5)^T$4.20S394-100100/1$(0.4,\ldots,0.4)^T$15.00
$(0.5,\ldots,0.5)^T$2.54$(0.3,\ldots,0.3)^T$8.00
Svanberg-5050/150$(5,\ldots,5)^T$4.20S394-150150/1$(0.4,\ldots,0.4)^T$23.00
$(0.5,\ldots,0.5)^T$2.57$(0.3,\ldots,0.3)^T$12.50
Svanberg-200200/600$(5,\ldots,5)^T$4.20S394-200200/1$(0.4,\ldots,0.4)^T$31.00
$(0.5,\ldots,0.5)^T$2.64$(0.3,\ldots,0.3)^T$17.00
Svanberg-300300/900$(5,\ldots,5)^T$4.20S394-300300/1$(0.4,\ldots,0.4)^T$31.00
$(0.5,\ldots,0.5)^T$2.65$(0.3,\ldots,0.3)^T$17.00
[1]

Andrew J. Steyer, Erik S. Van Vleck. Underlying one-step methods and nonautonomous stability of general linear methods. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2859-2877. doi: 10.3934/dcdsb.2018108

[2]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075

[3]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[4]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[5]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[6]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[7]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[8]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[9]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323

[10]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[11]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[12]

Jin Feng He, Wei Xu, Zhi Guo Feng, Xinsong Yang. On the global optimal solution for linear quadratic problems of switched system. Journal of Industrial & Management Optimization, 2019, 15 (2) : 817-832. doi: 10.3934/jimo.2018072

[13]

Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-26. doi: 10.3934/jimo.2018188

[14]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[15]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[16]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041

[17]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020024

[18]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[19]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019102

[20]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779

2018 Impact Factor: 1.025

Article outline

Figures and Tables

[Back to Top]