Arc search methods for linearly constrained optimization
Abstract/Contents
- Abstract
- We present a general arc search algorithm for linearly constrained optimization. The method constructs and searches along smooth arcs that satisfy a small and practical set of properties. An active-set strategy is used to manage linear inequality constraints. When second derivatives are used, the method is shown to converge to a second-order critical point and have a quadratic rate of convergence under standard conditions. The theory is applied to the methods of line search, curvilinear search, and modified gradient flow that have previously been proposed for unconstrained problems. A key issue when generalizing unconstrained methods to linearly constrained problems using an active-set strategy is the complexity of how the arc intersects hyperplanes. We introduce a new arc that is derived from the regularized Newton equation. Computing the intersection between this arc and a linear constraint reduces to finding the roots of a quadratic polynomial. The new arc scales to large problems, does not require modification to the Hessian, and is rarely dependent on the scaling of directions of negative curvature. Numerical experiments show the effectiveness of this arc search method on problems from the CUTEr test set and on a specific class of problems for which identifying negative curvature is critical. A second set of experiments demonstrates that when using SR1 quasi-Newton updates, this arc search method is competitive with a line search method using BFGS updates.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Henderson, Nicholas Wayne |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Murray, Walter |
| Thesis advisor | Murray, Walter |
| Thesis advisor | Saunders, Michael |
| Thesis advisor | Ye, Yinyu |
| Advisor | Saunders, Michael |
| Advisor | Ye, Yinyu |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Nicholas Wayne Henderson. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Nicholas Wayne Henderson
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...