[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Second-Derivative SQP Methods
Vyacheslav Kungurtsev
UCSD
Abstract:
Sequential Quadratic Programming (SQP) methods are a popular and successful class of methods for minimizing a generally nonlinear function subject to nonlinear constraints. Under a standard set of assumptions, conventional SQP methods exhibit a fast local convergence rate. However, in practice, a conventional SQP method involves solving an indefinite quadratic program (QP), which is NP hard. As a result, approximations to the second-derivatives are often used, slowing the local convergence rate and reducing the chance that the algorithm will converge to a local minimizer instead of a saddle point. In addition, the standard assumptions required for convergence often do not hold in practice. For such problems, regularized SQP methods, which also require second-derivatives, have been shown to have good local convergence properties; however, there are few regularized SQP methods that exhibit convergence to a minimizer from an arbitrary initial starting point. My thesis considers the formulation, analysis and implementation of: (i) practical methods that use exact second-derivative information but do not require the solution of an indefinite QP, (i) a regularized SQP method with global convergence and (iii) a rigorously defined version of a conventional SQP method with features that have been observed to work in practice for degenerate problems.
Tuesday, April 17, 2012
11:00AM AP&M 2402
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Vyacheslav Kungurtsev
UCSD
Abstract:
Sequential Quadratic Programming (SQP) methods are a popular and successful class of methods for minimizing a generally nonlinear function subject to nonlinear constraints. Under a standard set of assumptions, conventional SQP methods exhibit a fast local convergence rate. However, in practice, a conventional SQP method involves solving an indefinite quadratic program (QP), which is NP hard. As a result, approximations to the second-derivatives are often used, slowing the local convergence rate and reducing the chance that the algorithm will converge to a local minimizer instead of a saddle point. In addition, the standard assumptions required for convergence often do not hold in practice. For such problems, regularized SQP methods, which also require second-derivatives, have been shown to have good local convergence properties; however, there are few regularized SQP methods that exhibit convergence to a minimizer from an arbitrary initial starting point. My thesis considers the formulation, analysis and implementation of: (i) practical methods that use exact second-derivative information but do not require the solution of an indefinite QP, (i) a regularized SQP method with global convergence and (iii) a rigorously defined version of a conventional SQP method with features that have been observed to work in practice for degenerate problems.
Tuesday, April 17, 2012
11:00AM AP&M 2402