Modified projected Newton scheme for non-convex function with simple constraints
DOI:
https://doi.org/10.2298/YJOR200515002CKeywords:
Projected Newton Scheme, Non-convex Function, Simple Constraints, Saddle Point, Local Minimum PointAbstract
In this paper, a descent line search scheme is proposed to find a local minimum point of a non-convex optimization problem with simple constraints. The idea ensures that the scheme escapes the saddle points and finally settles for a local minimum point of the non-convex optimization problem. A positive definite scaling matrix for the proposed scheme is formed through symmetric indefinite matrix factorization of the Hessian matrix of the objective function at each iteration. A numerical illustration is provided, and the global convergence of the scheme is also justified.References
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. “Identifying and attacking the saddle point problem in high-dimensional non-convex optimization”, Advances in Neural Information Processing Systems, 27 (2014) 2933–2941.
Jayswal, A., Ahmad, I., and Banerjee, J. “Nonsmooth interval-valued optimization and saddle-point optimality criteria”, Bulletin of the Malaysian Mathematical Sciences Society, 39 (4) (2016) 1391–1411.
Bertsekas, D. P. “Projected Newton methods for optimization problems with simple constraints”, SIAM Journal on Control and Optimization, 20 (2) (1982) 221–246.
Bardsley, J. M., and Vogel, C. R. “A nonnegatively constrained convex programming method for image reconstruction”, SIAM Journal on Scientific Computing, 25 (4) (2004) 1326–1343.
Chi, E. C., Zhou, H., and Lange, K. “Distance majorization and its applications”, Mathematical Programming, 146 (1-2) (2014) 409–436.
Kuang, D., Park, H., and Ding, C. HQ. “Symmetric nonnegative matrix factorization for graph clustering”, SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, California, USA, 106-117, 2012.
Schmidt, M., Kim, D., and Sra, S. “Projected Newton-type methods in machine learning”, Optimization for Machine Learning, MIT Press, Cambridge, MA, USA, 2011.
Golub, G. H., and Van Loan, C. F. “Matrix Computations”, Johns Hopkins University Press, Baltimore, USA, 2012.
Cheng, S. H., and Higham, N. J. “A modified Cholesky algorithm based on a symmetric indefinite factorization”, SIAM Journal on Matrix Analysis and Applications, 19 (4) (1998) 1097–1110.
Nocedal, J., and Wright, S. J. “Numerical Optimization”, Springer Series in Operations Research and Financial Engineering, Springer, New York, USA, 2006.
Chakraborty, S. K., and Panda, G. “Newton like line search method using q-calculus”, Mathematics and Computing, ICMC 2017, Communications in Computer and Information Science, vol. 655, Springer, Singapore, 196-208, 2017.
Downloads
Published
Issue
Section
License
Copyright (c) 2021 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
