• PDF
• Cite
• Share
Article Contents  Article Contents

# A superlinearly convergent hybrid algorithm for solving nonlinear programming

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.

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

 Citation: • • 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)$ 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

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-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
• Figures(3)

Tables(2)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint