Computational complexity analysis of large-scale mathematical optimization algorithms in engineering applications

Abstract

The mathematical optimization algorithms represent an essential tool in solving complicated engineering problems with high-dimensional space of parameters and nonlinear constraints. However, the increase of problem dimension leads to specific difficulties related to execution time, convergence rate, memory and scalability. This research proposes the framework for the complexity analysis of the optimization algorithms for the engineering application. The complexity of the gradient descent, accelerated gradient, quasi-Newton, Newton optimization, interior point and alternating direction method of multipliers is estimated using such criteria as iteration number, computational costs, memory requirements and impact of the sparsity structure. The numerical tests are performed for synthetic problems of strongly convex quadratic optimization with dimensions from 50 to 1600 and condition number from 5 to 400. It is shown that for increasing dimensions and fixed κ = 50, gradient descent requires 807–945 iterations for convergence, while Newton optimization converges after one iteration but with higher computation cost. Accelerated gradient optimization decreases iteration number from 7356 to 420 for increasing κ = 400 (17.5 times less iterations than conventional gradient descent). BFGS optimization converges with a stable number of iterations (from 60 to 98) for dimensions from 50 to 800. Sparsity structure analysis shows that sparse solver achieves 0.0196 seconds execution time at n = 51,200 while dense factorization execution time is more than 30 seconds beyond n ≈ 5000.