A structured trust region method   for nonconvex programming    with  separable structure

Dan Xue; Wenyu Sun; Hongjin He

doi:10.3934/naco.2013.3.283

Article Contents

2013, Volume 3, Issue 2: 283-293. Doi: 10.3934/naco.2013.3.283

This issue Previous Article Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in $\mathbb{R}^n $ Next Article A modification of the forward-backward splitting method for maximal monotone mappings

A structured trust region method for nonconvex programming with separable structure

1.
School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023
2.
School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046

Received: February 2012

Revised: January 2013

Published: April 2013

Abstract / Introduction Related Papers Cited by

Abstract

In this paper, we present a structured trust region algorithm for nonconvex programming with separable structure. We obtain the trial step by decomposing the step into its normal and tangential components. The structure of the problem is dealt with in the framework of the trust region. The global convergence is proved for the proposed algorithm. The preliminary numerical results show that the proposed algorithm is potentially efficient.

Keywords:

Mathematics Subject Classification: Primary: 65K05; Secondary: 90C26; 90C30.

Citation:

Related Papers

Cited by

References

[1]	D. P. Bertsekas and J. N. Tsitsiklis, "Parallel and Distributed Computation: Numerical Methods," Prentice Hall, Englewood Cliffs, NJ, 1989.
[2]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends of Machine Learning, 3 (2011), 1-122.doi: 10.1561/2200000016.
[3]	J. T. Betts, An accelerated multiplier method for nonlinear programming, Journal of Optimization Theory and Applications, 21 (1977), 137-174.doi: 10.1007/BF00932517.
[4]	J. V. Burke and J. J. Moré, On the identification of active constraints, SIAM Journal on Numerical Analysis, 25 (1988), 1197-1211.doi: 10.1137/0725068.
[5]	R. H. Byrd, R. B. Schnabel and G. A. Schultz, A trust region algorithm for nonlinearly constrained optimization, SIAM Journal on Numerical Analysis, 24 (1987), 1152-1170.doi: 10.1137/0724076.
[6]	A. R. Conn, N. I. M. Gould, A. Sartenaer and P. L. Toint, Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints, SIAM Journal on Optimization, 3 (1993), 164-221.doi: 10.1137/0803009.
[7]	A. R. Conn, N. I. M. Gould, A. Sartenaer and P. L. Toint, Convergence properties of minimization algorithms for convex constraints using a structured trust region, SIAM Journal on Optimization, 6 (1996), 1059-1086.doi: 10.1137/S1052623492236481.
[8]	A. R. Conn, N. I. M. Gould and P. L. Toint, "LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A)," Number 17 in Springer Series in Computational Mathematics, Springer-Verlag, New York, 1992.
[9]	A. R. Conn, N. I. M. Gould and P. L. Toint, "Trust Region Methods," MPS-SIAM, Philadelphia, 2000.
[10]	J. Eckstein, "Splitting Methods for Monotone Operators with Applications to Parallel Optimization," Ph.D. Thesis, Massachusetts Institute of Technology, Department of Civil Engineering, Technical Report LIDS-TH-1877, MIT, 1989.
[11]	J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318.doi: 10.1007/BF01581204.
[12]	M. Elalem, A global convergence theory for the Celis-Dennis-Tapia trust-region algorithm for constrained optimization, SIAM Journal on Numerical Analysis, 28 (1991), 266-290.doi: 10.1137/0728015.
[13]	R. Fletcher, N. I. M. Gould, S. Leyffer, P. L. Toint and A. Wächter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM Journal on Optimization, 13 (2002), 635-659.doi: 10.1137/S1052623499357258.
[14]	M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems," North-Holland, Amsterdam, 1983.
[15]	M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems, Computational Optimization and Applications, 1 (1992), 93-111.doi: 10.1007/BF00247655.
[16]	A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions, in "Nonlinear Optimization" (eds. M.J.D. Powell), Academic Press, London, (1982), 301-312.
[17]	P. C. Hansen, J. G. Nagy and D. P. O'Leary, "Deblurring Images: Matrices, Spectra, and Filtering," SIAM, Philadelphia, 2006.
[18]	P. T. Harker and J. S. Pang, Finite dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Mathematical Programming, 48 (1990), 161-220.
[19]	B. S. He, L. Z. Liao, D. R. Han and H. Yang, A new inexact alternating direction method for monotone variational inequalities, Mathematical Programming, 92 (2002), 103-118.doi: 10.1007/s101070100280.
[20]	H. Y. Huang and A. K. Aggerwal, A class of quadratically convergent algorithms for constrained function minimization, Journal of Optimization Theory and Applications, 16 (1975), 447-485.doi: 10.1007/BF00933853.
[21]	S. Kontogiorgis and R. R. Meyer, A variable-penalty alternating directions method for convex optimization, Mathematical Programming, 83 (1998), 29-53.doi: 10.1007/BF02680549.
[22]	A. Miele, H. Y. Huang and J. C. Heideman, Sequential gradient-restoration algorithm for the minimization of constrained functions, ordinary and conjugate gradient versions, Journal of Optimization Theory and Applications, 4 (1969), 213-243.doi: 10.1007/BF00927947.
[23]	J. J. Moré, Trust regions and projected gradients, in "System Modelling and Optimization," Lecture Notes in Control nd Information Sciences, Berlin, (1988), 1-13.
[24]	B. A. Murthagh and R. W. Sargent, A constrained minimization method with quadratic convergence, in " Optimization" (eds. R. Fletcher), Academic Press, London, (1970), 215-245.
[25]	J. Nocedal, "Theory of Algorithms for Unconstrained Optimization," Cambridge: Cambridge University Press, 1992.
[26]	M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1990), 189-211.doi: 10.1007/BF01588787.
[27]	A. Sartenaer, Automatic determination of an initial trust region in nonlinear programming, SIAM Journal on Scientific Computing, 18 (1997), 1788-1803.doi: 10.1137/S1064827595286955.
[28]	W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer, New York, 2006.
[29]	J. Takaki and N. Yamashita, A derivative-free trust region algorithm for unconstrained optimization with controlled error, Numerical Algebra, Control and Optimization, 1 (2011), 117-145.doi: 10.3934/naco.2011.1.117.
[30]	P. L. Toint, On large scale nonlinear least squares calculations, SIAM Journal on Scientific and Statistical Computing, 8 (1987), 416-435.doi: 10.1137/0908042.
[31]	P. L. Toint, Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space, IMA Journal of Numerical Analysis, 8 (1988), 231-252.doi: 10.1093/imanum/8.2.231.
[32]	A. Vardi, A trust region algorithm for equality constrained minimization: Convergence properties and implementation, SIAM Journal on Numerical Analysis, 22 (1985), 575-591.doi: 10.1137/0722035.