Newton projection method as applied to assembly simulation. (English) Zbl 1508.90050
This article suggests improvements for the Newton projection method, such as the method for solving systems of linear equations emerging in the algorithm and constraint recalculation method to improve convergence. Several techniques for step-size selection are discussed and compared. Duality theory is used to consider other forms of the problem, namely a dual and relative formulation, which can be solved alternatively. This allows the significant reduction of the solving time for large-scale computations of quadratic programming problems. A projection method is used for the minimization of the nonsmooth function arising in the assembly simulation. Convergence of the proposed method is proved. Finally, the Newton projection method is compared with the quadratic programming techniques mentioned above.
Reviewer: Yisheng Song (Hong Kong)
MSC:
| 90C20 | Quadratic programming |
Keywords:
Newton projection method; quadratic programming; duality; nonsmooth objective function; subgradientSoftware:
ZQPCVXReferences:
| [1] | Andrew, G. and Gao, J., Scalable training of L1-regularized log-linear models, in Proceedings of the 24th International Conference on Machine Learning, Association for Computing Machinery, New York, 2007, pp. 33-40. |
| [2] | Bertsekas, D. P., On the goldstein-levitin-polyak gradient projection method, IEEE. Trans. Automat. Contr., 21, 174-184 (1976) · Zbl 0326.49025 · doi:10.1109/TAC.1976.1101194 |
| [3] | Bertsekas, D. P., Projected newton methods for optimization problems with simple constraints, SIAM J. Control Optim., 20, 221-246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018 |
| [4] | Bertsekas, D. P., Convex Analysis and Optimization (2003), Athena Scientific, Belmont · Zbl 1140.90001 |
| [5] | Birge, J. R.; Qi, L.; Wei, Z., A general approach to convergence properties of some methods for nonsmooth convex optimization, Appl. Math. Optim., 38, 141-158 (1998) · Zbl 0910.90228 · doi:10.1007/s002459900086 |
| [6] | Birgin, E. G.; Martínez, J. M.; Raydan, M., Spectral projected gradient methods: review and perspectives, J. Stat. Softw., 60, 1-21 (2014) · doi:10.18637/jss.v060.i03 |
| [7] | Boyd, S., Xiao, L., and Mutapcic, A., Subgradient methods (2003), lecture notes of EE392o, Stanford University, Autumn Quarter 2003-2004. |
| [8] | Calamai, P. H.; More, J. J., Projected gradient methods for linearly constrained problems, Math. Program., 39, 93-116 (1987) · Zbl 0634.90064 · doi:10.1007/BF02592073 |
| [9] | Crisci, S.; Ruggiero, V.; Zanni, L., Steplength selection in gradient projection methods for box-constrained quadratic programs, Appl. Math. Comput., 356, 312-327 (2019) · Zbl 1428.90110 |
| [10] | Ferry, M.W., Projected-search methods for box-constrained optimization, Ph.D. diss., University of California, 2011. |
| [11] | Goldfarb, D.; Idnani, A., A numerically stable dual method for solving strictly convex quadratic programs, Math. Program., 27, 1-33 (1983) · Zbl 0537.90081 · doi:10.1007/BF02591962 |
| [12] | Goldstein, A. A., Convex programming in hilbert space, Bull. Am. Math. Soc., 70, 709-710 (1964) · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2 |
| [13] | Gondzio, J., Interior point methods 25 years later, Eur. J. Oper. Res., 218, 587-601 (2012) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017 |
| [14] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press, Cambridge · Zbl 0576.15001 |
| [15] | Khapaev, M. and Kupriyanov, M., Sparse approximation of FEM matrix for sheet current integro-differential equation, in 2nd International Conference On Matrix Methods And Operator Equations, World Scientific, Singapore, 2007, p. 38. · Zbl 1215.65198 |
| [16] | Kim, D.; Sra, S.; Dhillon, I. S., Fast projection-based methods for the least squares nonnegative matrix approximation problem, Stat. Anal. Data. Min., 1, 38-51 (2008) · Zbl 07260181 · doi:10.1002/sam.104 |
| [17] | Levitin, E. S.; Polyak, B. T., Constrained minimization problems, USSR Comput. Math. Math. Phys., 6, 1-50 (1966) · Zbl 0184.38902 · doi:10.1016/0041-5553(66)90114-5 |
| [18] | Lin, C. J.; Saigal, R., An incomplete cholesky factorization for dense symmetric positive definite matrices, BIT, 40, 1-25 (2000) |
| [19] | Lupuleac, S.; Kovtun, M.; Rodionova, O.; Marguet, B., Assembly simulation of riveting process, SAE Int. J. Aerosp., 2, 193-198 (2010) · doi:10.4271/2009-01-3215 |
| [20] | Lupuleac, S.; Petukhova, M.; Shinder, Y.; Bretagnol, B., Methodology for solving contact problem during riveting process, SAE Int. J. Aeros., 4, 952-957 (2011) · doi:10.4271/2011-01-2582 |
| [21] | Lupuleac, S.; Petukhova, M.; Yakunin, S.; Smirnov, A.; Bondarenko, D., Development of numerical methods for simulation of airframe assembly process, SAE Int. J. Aeros., 6, 101-105 (2013) · doi:10.4271/2013-01-2093 |
| [22] | Lupuleac, S., Petukhova, M., Shinder, J., Smirnov, A., Stefanova, M., Zaitseva, N., Pogarskaia, T., and Bonhomme, E., Software complex for simulation of riveting process: concept and applications, in SAE 2016 Aerospace Manufacturing and Automated Fastening Conference & Exhibition, SAE International, Bremen, 2016, p. 4. |
| [23] | Lupuleac, S., Zaitseva, N., Stefanova, M., Berezin, S., Shinder, J., Petukhova, M., and Bonhomme, E., Simulation and optimization of airframe assembly process, in International Mechanical Engineering Congress and Exposition, American Society of Mechanical Engineers, Pittsburgh, 2018. |
| [24] | Lupuleac, S., Shinder, J., Churilova, M., Zaitseva, N., Khashba, V., Bonhomme, E., and Montero-Sanjuan, P., Optimization of automated airframe assembly process on example of a350 s19 splice joint, Tech. Rep., SAE Technical Paper, 2019. |
| [25] | Lupuleac, S., Smirnov, A., Churilova, M., Shinder, J., Zaitseva, N., and Bonhomme, E., Simulation of body force impact on the assembly process of aircraft parts, in ASME 2019 International Mechanical Engineering Congress and Exposition, 2019. |
| [26] | Lupuleac, S.; Zaitseva, N.; Stefanova, M.; Berezin, S.; Shinder, J.; Petukhova, M.; Bonhomme, E., Simulation of the wing-to-fuselage assembly process, ASME. J. Manuf. Sci. Eng., 141, 1-15 (2019) · doi:10.1115/1.4043365 |
| [27] | McCormick, G. P.; Tapia, R. A., The gradient projection method under mild differentiability conditions, SIAM J. Contr., 10, 93-98 (1972) · Zbl 0237.49019 · doi:10.1137/0310009 |
| [28] | Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM. J. Optim., 2, 575-601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028 |
| [29] | Moré, J. J.; Toraldo, G., On the solution of large quadratic programming problems with bound constraints, SIAM. J. Optim., 55, 377-400 (1991) · Zbl 0675.65061 |
| [30] | Nesterov, Y., Introductory Lectures on Convex Optimization (2004), Springer, Boston · Zbl 1086.90045 |
| [31] | Nesterov, Y.; Nemirovski, A., Interior Point Polynomial Algorithms in Convex Programming (1994), SIAM: SIAM, Philadelphia · Zbl 0824.90112 |
| [32] | Ogita, T.; Oishi, S., Accurate and robust inverse cholesky factorization, Nonlinear Theory Appl., IEICE, 3, 103-111 (2012) · doi:10.1587/nolta.3.103 |
| [33] | Ogita, T.; Rump, S. M.; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput. (SISC), 26, 1955-1988 (2005) · Zbl 1084.65041 · doi:10.1137/030601818 |
| [34] | Osborne, M.A., Bayesian gaussian processes for sequential prediction, optimisation and quadrature, Ph.D. diss., Oxford University New College, 2010. |
| [35] | Petukhova, M.; Lupuleac, S.; Shinder, Y.; Smirnov, A.; Yakunin, S.; Bretagnol, B., Numerical approach for airframe assembly simulation, J. Math. Ind., 4 (2014) |
| [36] | Pogarskaia, T., Churilova, M., Petukhova, M., and Petukhov, E., Simulation and optimization of aircraft assembly process using supercomputer technologies, in Communications in Computer and Information Science, Vol. 965, Springer, Cham, 2018. |
| [37] | Powell, M. J.D., On the quadratic programming algorithm of goldfarb and idnani, Math. Program. Studies, 25, 46-61 (1985) · Zbl 0584.90069 · doi:10.1007/BFb0121074 |
| [38] | Pytlak, R.; Tarnawski, T., Preconditioned conjugate gradient algorithms for nonconvex problems, Computing, 2, 81-104 (2006) · Zbl 1143.90031 |
| [39] | Rosen, J. B., The gradient projection method for nonlinear programming. part i. linear constraints, SIAM. J. Appl. Math., 8, 181-217 (1961) · Zbl 0099.36405 · doi:10.1137/0108011 |
| [40] | Rump, S. M., Inversion of extremely ill-conditioned matrices in floating-point, Japan J. Indust. Appl. Math, 26, 249-277 (2009) · Zbl 1185.65050 · doi:10.1007/BF03186534 |
| [41] | Santin, O.; Jarošová, M.; Havlena, V.; Dostal, Z., Proportioning with second-order information for model predictive control, Optim. Methods Soft., 32, 1-19 (2016) |
| [42] | Schöberl, J., Solving the signorini problem on the basis of domain decomposition techniques, Computing, 60, 323-344 (1998) · Zbl 0915.73077 · doi:10.1007/BF02684379 |
| [43] | Schmidt, M., Kim, D., and Sra, S., Projected Newton-type methods in machine learning, in Optimization for Machine Learning, MIT Press, Cambridge, MA, USA, 2011, pp. 305-330. |
| [44] | Serafino, D. D.; Ruggiero, V.; Toraldo, G.; Zanni, L., On the steplength selection in gradient methods for unconstrained optimization, Appl. Math. Comput., 318, 176-195 (2018) · Zbl 1426.65082 |
| [45] | Stefanova, M.; Yakunin, S.; Petukhova, M.; Lupuleac, S.; Kokkolaras, M., An interior-point method-based solver for simulation of aircraft parts riveting, Eng. Optim., 50, 781-796 (2018) · doi:10.1080/0305215X.2017.1355367 |
| [46] | Stefanova, M.; Minevich, O.; Baklanov, S.; Petukhova, M.; Lupuleac, S.; Grigor’ev, B.; Kokkolaras, M., Convex optimization techniques in compliant assembly simulation, Optim. Eng., 1-26 (2020) · Zbl 1455.74072 |
| [47] | Stewart, G. W., Basic Decompositions (1998), Soc. for Industrial and Applied Mathematics: Soc. for Industrial and Applied Mathematics, Philadelphia · Zbl 0910.65012 |
| [48] | Vallejos, M., Mgopt with gradient projection method for solving bilinear elliptic optimal control problems, Computing, 87, 21-33 (2010) · Zbl 1184.49034 · doi:10.1007/s00607-009-0073-4 |
| [49] | van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press, Cambridge · Zbl 1023.65027 |
| [50] | Vuong, P. T.; Strodiot, J. J.; Nguyen, V. H., A gradient projection method for solving split equality and split feasibility problems in hilbert spaces, Optimization, 64, 2321-2341 (2014) · Zbl 1329.65129 · doi:10.1080/02331934.2014.967237 |
| [51] | Yao, Y.; Kang, S. M.; Jigang, W.; Yang, P. X., A regularized gradient projection method for the minimization problem, J. Appl. Math., 2012, 9 (2012) · Zbl 1242.49031 |
| [52] | Zaitseva, N., Pogarskaia, T., Minevich, O., Shinder, J., and Bonhomme, E., Simulation of aircraft assembly via asrp software, Tech. Rep., SAE Technical Paper, 2019. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
