575. Complexity of trust-region methods in the presence of unbounded Hessian approximations
Invited abstract in session TA-35: Nonlinear Optimization Algorithms and Applications: 4, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Tuesday, 8:30-10:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | Youssef Diouane
|
| Mathematics and Industrial Engineering, Polytechnique Montréal | |
| 2. | Mohamed Laghdaf Habiboullah
|
| Polytechnique Montréal | |
| 3. | Dominique Orban
|
| Polytechnique Montréal |
Abstract
We extend traditional complexity analyses of trust-region methods for unconstrained, possibly nonconvex, optimization. Whereas most complexity analyses assume uniform boundedness of the model Hessians, we work with potentially unbounded model Hessians. Boundedness is not guaranteed in practical implementations, in particular ones based on quasi-Newton updates such as PSB, BFGS and SR1. Our analysis is conducted for a family of trust-region methods that includes most known methods as special cases. We examine two regimes of Hessian growth: one bounded by a power of the number of successful iterations, and one bounded by a power of the number of iterations.
When the model Hessians grow as $\mathcal{O}(k^p)$, where $k$ is the iteration counter and $0 \le p \le 1$, we derived a sharp $\mathcal{O}(\epsilon^{−2/(1−p)})$ worst-case evaluation complexity bound to reach an $\epsilon$-stationary point. Additionally, for the case where $p = 1$, we established a new $\mathcal{O}(\exp(c\epsilon^{−2}))$ worst-case evaluation complexity bound, for some constant $c > 0$. We derived similar sharp bounds when the model Hessians grow linearly with the number of successful iterations. Among others, our results confirmed the profound intuition of Powell on complexity for multiple quasi-Newton approximations.
Keywords
- Continuous Optimization
- Programming, Nonlinear
- Algorithms
Status: accepted
Back to the list of papers