# American Institute of Mathematical Sciences

• Previous Article
A modification of the forward-backward splitting method for maximal monotone mappings
• NACO Home
• This Issue
• Next Article
Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in $\mathbb{R}^n$
2013, 3(2): 283-293. doi: 10.3934/naco.2013.3.283

## 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, China, China 2 School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046

Received  February 2012 Revised  January 2013 Published  April 2013

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.
Citation: Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
##### 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.

show all references

##### 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.
 [1] Jirui Ma, Jinyan Fan. On convergence properties of the modified trust region method under Hölderian error bound condition. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021222 [2] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [3] Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053 [4] 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 and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65 [5] Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 [6] Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 [7] Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309 [8] Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051 [9] Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 [10] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 [11] Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 [12] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [13] Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial and Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052 [14] Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893 [15] Gonglin Yuan, Zhan Wang, Pengyuan Li. Global convergence of a modified Broyden family method for nonconvex functions. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021164 [16] Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046 [17] Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651 [18] Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial and Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321 [19] Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223 [20] David Yang Gao. Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints. Journal of Industrial and Management Optimization, 2005, 1 (1) : 53-63. doi: 10.3934/jimo.2005.1.53

Impact Factor:

## Metrics

• PDF downloads (62)
• HTML views (0)
• Cited by (1)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]