Combination of trust region method and simplicial decomposition for convex constrained nonlinear problems

GUOSHENG FENG, ZAIQIN CUI

Department of Applied Mathematics, Tongji University 200092 Shanghai, P.R.China

Abstract

J.A.Ventura et al(1993) prsented a simplicial decomposition algorithm (RS-DCC) for nonlinear pseudoconvex programming with convex constraints.

min f(x)
s.t. g_{j}(x) ≤ 0, j ∈ N_{q}
Ax ≤ b

Because the objective function of the master problem in RSDCC is nonlinear, it cannot be solved in finite times of iteration for an exact solution. But the convergence of the RSDCC is based on the exact solutin. Therefore the tradeoff between precision of the solution and CPU time consumption must be made for solving the master problem. In this paper a combined algorithm(RSDCC-TR) of the trust region method(TR) and RSDCC is given, which incorportes TR into RSDCC to solve the master problem. The global convergence of the combined algorithm is proved. The advantage of the RSDCC-TR over the RSDCC is that the former is exact and finite in every iteration. The 11 nonlinear problems with nonlinear constraints are selected from H.W.Schittkowski(1981,1987). They are solved by the RSDCC and the RSDCC-TR. The computatioal results showed that the latter is much better than the former.

References

J.A. Ventura(1993), “Restricted simplicial decomposition for convex constrained problems”,

Mathematical Programming 59(1993) 71-85. H.W. Schittkowski(1981),“Test Examples for Nonlinear Programming Codes”,

Lecture Notes in Economics and Mathematical Systems 187,Springer-Verlag, Berlin-Heidellerg. H.W.Schittkowski(1987),“klaus ”More test examples for nonlinear programming codes”,

Lecture notes in economics and mathematical systems 282,Spring-Verlag,Berlin Heidelberg.