• 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 & 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). Google Scholar

[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. Google Scholar

[3]

J. T. Betts, An accelerated multiplier method for nonlinear programming,, Journal of Optimization Theory and Applications, 21 (1977), 137. doi: 10.1007/BF00932517. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[9]

A. R. Conn, N. I. M. Gould and P. L. Toint, "Trust Region Methods,", MPS-SIAM, (2000). Google Scholar

[10]

J. Eckstein, "Splitting Methods for Monotone Operators with Applications to Parallel Optimization,", Ph.D. Thesis, (1989). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems,", North-Holland, (1983). Google Scholar

[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. Google Scholar

[16]

A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions,, in, (1982), 301. Google Scholar

[17]

P. C. Hansen, J. G. Nagy and D. P. O'Leary, "Deblurring Images: Matrices, Spectra, and Filtering,", SIAM, (2006). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

J. J. Moré, Trust regions and projected gradients,, in, (1988), 1. Google Scholar

[24]

B. A. Murthagh and R. W. Sargent, A constrained minimization method with quadratic convergence,, in, (1970), 215. Google Scholar

[25]

J. Nocedal, "Theory of Algorithms for Unconstrained Optimization,", Cambridge: Cambridge University Press, (1992). Google Scholar

[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. Google Scholar

[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. Google Scholar

[28]

W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

show all references

References:
[1]

D. P. Bertsekas and J. N. Tsitsiklis, "Parallel and Distributed Computation: Numerical Methods,", Prentice Hall, (1989). Google Scholar

[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. Google Scholar

[3]

J. T. Betts, An accelerated multiplier method for nonlinear programming,, Journal of Optimization Theory and Applications, 21 (1977), 137. doi: 10.1007/BF00932517. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[9]

A. R. Conn, N. I. M. Gould and P. L. Toint, "Trust Region Methods,", MPS-SIAM, (2000). Google Scholar

[10]

J. Eckstein, "Splitting Methods for Monotone Operators with Applications to Parallel Optimization,", Ph.D. Thesis, (1989). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[14]

M. Fortin and R. Glowinski, "Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems,", North-Holland, (1983). Google Scholar

[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. Google Scholar

[16]

A. Griewank and P. L. Toint, On the unconstrained optimization of partially separable functions,, in, (1982), 301. Google Scholar

[17]

P. C. Hansen, J. G. Nagy and D. P. O'Leary, "Deblurring Images: Matrices, Spectra, and Filtering,", SIAM, (2006). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

J. J. Moré, Trust regions and projected gradients,, in, (1988), 1. Google Scholar

[24]

B. A. Murthagh and R. W. Sargent, A constrained minimization method with quadratic convergence,, in, (1970), 215. Google Scholar

[25]

J. Nocedal, "Theory of Algorithms for Unconstrained Optimization,", Cambridge: Cambridge University Press, (1992). Google Scholar

[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. Google Scholar

[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. Google Scholar

[28]

W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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, 2019, 15 (4) : 1677-1699. 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: 

Metrics

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

Other articles
by authors

[Back to Top]