# American Institute of Mathematical Sciences

• Previous Article
Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in $\mathbb{R}^n$
• NACO Home
• This Issue
• Next Article
A modification of the forward-backward splitting method for maximal monotone mappings
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 & 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, (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. doi: 10.1561/2200000016. [3] J. T. Betts, An accelerated multiplier method for nonlinear programming,, Journal of Optimization Theory and Applications, 21 (1977), 137. 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. 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. 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. 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. 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, (1992). [9] A. R. Conn, N. I. M. Gould and P. L. Toint, "Trust Region Methods,", MPS-SIAM, (2000). [10] J. Eckstein, "Splitting Methods for Monotone Operators with Applications to Parallel Optimization,", Ph.D. Thesis, (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. 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. 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. doi: 10.1137/S1052623499357258. [14] M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems,", North-Holland, (1983). [15] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems,, Computational Optimization and Applications, 1 (1992), 93. doi: 10.1007/BF00247655. [16] A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions,, in, (1982), 301. [17] P. C. Hansen, J. G. Nagy and D. P. O'Leary, "Deblurring Images: Matrices, Spectra, and Filtering,", SIAM, (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. [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. 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. 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. 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. doi: 10.1007/BF00927947. [23] J. J. Moré, Trust regions and projected gradients,, in, (1988), 1. [24] B. A. Murthagh and R. W. Sargent, A constrained minimization method with quadratic convergence,, in, (1970), 215. [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. 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. doi: 10.1137/S1064827595286955. [28] W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006). [29] J. Takaki and N. Yamashita, A derivative-free trust region algorithm for unconstrained optimization with controlled error,, Numerical Algebra, 1 (2011), 117. 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. 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. 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. doi: 10.1137/0722035.

show all references

##### References:
 [1] D. P. Bertsekas and J. N. Tsitsiklis, "Parallel and Distributed Computation: Numerical Methods,", Prentice Hall, (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. doi: 10.1561/2200000016. [3] J. T. Betts, An accelerated multiplier method for nonlinear programming,, Journal of Optimization Theory and Applications, 21 (1977), 137. 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. 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. 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. 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. 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, (1992). [9] A. R. Conn, N. I. M. Gould and P. L. Toint, "Trust Region Methods,", MPS-SIAM, (2000). [10] J. Eckstein, "Splitting Methods for Monotone Operators with Applications to Parallel Optimization,", Ph.D. Thesis, (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. 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. 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. doi: 10.1137/S1052623499357258. [14] M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems,", North-Holland, (1983). [15] M. Fukushima, Application of the alternating direction method of multipliers to separable convex programming problems,, Computational Optimization and Applications, 1 (1992), 93. doi: 10.1007/BF00247655. [16] A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions,, in, (1982), 301. [17] P. C. Hansen, J. G. Nagy and D. P. O'Leary, "Deblurring Images: Matrices, Spectra, and Filtering,", SIAM, (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. [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. 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. 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. 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. doi: 10.1007/BF00927947. [23] J. J. Moré, Trust regions and projected gradients,, in, (1988), 1. [24] B. A. Murthagh and R. W. Sargent, A constrained minimization method with quadratic convergence,, in, (1970), 215. [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. 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. doi: 10.1137/S1064827595286955. [28] W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006). [29] J. Takaki and N. Yamashita, A derivative-free trust region algorithm for unconstrained optimization with controlled error,, Numerical Algebra, 1 (2011), 117. 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. 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. 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. doi: 10.1137/0722035.
 [1] Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171 [2] 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 & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65 [3] Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237 [4] Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 [5] Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309 [6] 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 & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169 [7] Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041 [8] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [9] Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052 [10] Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893 [11] Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651 [12] Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial & Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321 [13] Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223 [14] Rong Liu, Feng-Qin Zhang, Yuming Chen. Optimal contraception control for a nonlinear population model with size structure and a separable mortality. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3603-3618. doi: 10.3934/dcdsb.2016112 [15] David Yang Gao. Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints. Journal of Industrial & Management Optimization, 2005, 1 (1) : 53-63. doi: 10.3934/jimo.2005.1.53 [16] Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319 [17] Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070 [18] Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117 [19] Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-23. doi: 10.3934/jimo.2018117 [20] Julián López-Gómez. On the structure of the permanence region for competing species models with general diffusivities and transport effects. Discrete & Continuous Dynamical Systems - A, 1996, 2 (4) : 525-542. doi: 10.3934/dcds.1996.2.525

Impact Factor: