# American Institute of Mathematical Sciences

• 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:

show all references

##### References:
under Case Ⅰ and Case Ⅱ, respectively.">Figure 1.  The performance of ALGO 1 for solving problems in Table 1 under Case Ⅰ and Case Ⅱ, respectively.
under Case Ⅰ and Case Ⅱ, respectively.">Figure 2.  The performance of ALGO 1 for solving problems in Table 2 under Case Ⅰ and Case Ⅱ, respectively.
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.
The corresponding parameters for the test problems (1)
 Prob $n/m$ $x^0$ $\Upsilon(x^0)$ Prob $n/m$ $x^0$ $\Upsilon(x^0)$ 013 2/3 $(-5,-5)^T$ 5.00 098 6/16 $(20,0,\ldots,0)^T$ 19.69 018 2/6 $(1,5)^T$ 20.00 100 7/4 $(3,\ldots,3)^T$ 188.00 023 2/9 $(-5,-5)^T$ 11.00 108 9/14 $\begin{array}{ll}(0.1,5,0.5,\ 1,0,1,\ 0.5,5,0.1)^T\end{array}$ 23.26 030 3/7 $(5,10,15)^T$ 124.00 224 2/8 $(-2,-1)^T$ 5.00 033 3/6 $(1,4,7)^T$ 2.00 225 2/5 $(1,4)^T$ 3.00 038 4/8 $(0,3,1,2)^T$ 3.00 234 2/5 $(1,3)^T$ 9.00 043 4/3 $(-10,2,-8,5)^T$ 236.00 250 3/8 $(-3,-3,-3)^T$ 15.00 044 4/10 $(-20,\ldots,-20)^T$ 20.00 #38; 264 4/3 $(0,0,0,3)^T$ 6.00 066 3/8 $(0,0,100)^T$ 90.00 337 3/3 $(1,1,0)^T$ 1.00 076 4/7 $(1,2,3,4)^T$ 7.00 354 4/5 $(1,-1,1,-1)^T$ 1.00
 Prob $n/m$ $x^0$ $\Upsilon(x^0)$ Prob $n/m$ $x^0$ $\Upsilon(x^0)$ 013 2/3 $(-5,-5)^T$ 5.00 098 6/16 $(20,0,\ldots,0)^T$ 19.69 018 2/6 $(1,5)^T$ 20.00 100 7/4 $(3,\ldots,3)^T$ 188.00 023 2/9 $(-5,-5)^T$ 11.00 108 9/14 $\begin{array}{ll}(0.1,5,0.5,\ 1,0,1,\ 0.5,5,0.1)^T\end{array}$ 23.26 030 3/7 $(5,10,15)^T$ 124.00 224 2/8 $(-2,-1)^T$ 5.00 033 3/6 $(1,4,7)^T$ 2.00 225 2/5 $(1,4)^T$ 3.00 038 4/8 $(0,3,1,2)^T$ 3.00 234 2/5 $(1,3)^T$ 9.00 043 4/3 $(-10,2,-8,5)^T$ 236.00 250 3/8 $(-3,-3,-3)^T$ 15.00 044 4/10 $(-20,\ldots,-20)^T$ 20.00 #38; 264 4/3 $(0,0,0,3)^T$ 6.00 066 3/8 $(0,0,100)^T$ 90.00 337 3/3 $(1,1,0)^T$ 1.00 076 4/7 $(1,2,3,4)^T$ 7.00 354 4/5 $(1,-1,1,-1)^T$ 1.00
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-20 20/60 $(5,\ldots,5)^T$ 4.20 S394-40 40/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-30 30/90 $(5,\ldots,5)^T$ 4.20 S394-70 70/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-40 40/120 $(5,\ldots,5)^T$ 4.20 S394-100 100/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-50 50/150 $(5,\ldots,5)^T$ 4.20 S394-150 150/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-200 200/600 $(5,\ldots,5)^T$ 4.20 S394-200 200/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-300 300/900 $(5,\ldots,5)^T$ 4.20 S394-300 300/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-20 20/60 $(5,\ldots,5)^T$ 4.20 S394-40 40/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-30 30/90 $(5,\ldots,5)^T$ 4.20 S394-70 70/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-40 40/120 $(5,\ldots,5)^T$ 4.20 S394-100 100/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-50 50/150 $(5,\ldots,5)^T$ 4.20 S394-150 150/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-200 200/600 $(5,\ldots,5)^T$ 4.20 S394-200 200/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-300 300/900 $(5,\ldots,5)^T$ 4.20 S394-300 300/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] Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055 [2] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [3] Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102 [4] Wided Kechiche. Global attractor for a nonlinear Schrödinger equation with a nonlinearity concentrated in one point. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021031 [5] Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 [6] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [7] Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 [8] Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206 [9] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 [10] Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074 [11] Amira Khelifa, Yacine Halim. Global behavior of P-dimensional difference equations system. Electronic Research Archive, , () : -. doi: 10.3934/era.2021029 [12] Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228 [13] Brahim Alouini. Finite dimensional global attractor for a class of two-coupled nonlinear fractional Schrödinger equations. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021013 [14] Kazuhiro Kurata, Yuki Osada. Variational problems associated with a system of nonlinear Schrödinger equations with three wave interaction. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021100 [15] Flank D. M. Bezerra, Jacson Simsen, Mariza Stefanello Simsen. Convergence of quasilinear parabolic equations to semilinear equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3823-3834. doi: 10.3934/dcdsb.2020258 [16] Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021026 [17] Thomas Y. Hou, Ruo Li. Nonexistence of locally self-similar blow-up for the 3D incompressible Navier-Stokes equations. Discrete & Continuous Dynamical Systems, 2007, 18 (4) : 637-642. doi: 10.3934/dcds.2007.18.637 [18] Lianbing She, Nan Liu, Xin Li, Renhai Wang. Three types of weak pullback attractors for lattice pseudo-parabolic equations driven by locally Lipschitz noise. Electronic Research Archive, , () : -. doi: 10.3934/era.2021028 [19] Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209 [20] Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675

2019 Impact Factor: 1.366