Numerical Optimization: Difference between revisions
| Line 28: | Line 28: | ||
==Resources== | ==Resources== | ||
* [https://link.springer.com/book/10.1007%2F978-0-387-40065-5 Numerical Optimization by Nocedal and Wright (2006) | * [https://link.springer.com/book/10.1007%2F978-0-387-40065-5 Numerical Optimization by Nocedal and Wright (2006)] | ||
Revision as of 19:50, 31 October 2019
Numerical Optimization
Line Search Methods
Basic idea:
- For each iteration
- Find a direction \(\displaystyle p\).
- Then find a step length \(\displaystyle \alpha\) which decreases \(\displaystyle f\).
- Take a step \(\displaystyle \alpha p\).
Trust Region Methods
Basic idea:
- For each iteration
- Assume a quadratic model of your objective function near a point.
- Find a region where you trust your model accurately represents your objective function.
- Take a step.
Variables:
- \(\displaystyle f\) is your objective function.
- \(\displaystyle m_k\) is your quadratic model at iteration k.
- \(\displaystyle x_k\) is your point at iteration k.
Your model is \(\displaystyle m_k(p) = f_k + g_k^T p + \frac{1}{2}p^T B_k p\)
where \(\displaystyle g_k = \nabla f(x_k)\) and \(\displaystyle B_k\) is a symmetric matrix.
At each iteration, you solve a constrained optimization subproblem to find the best step \(\displaystyle p\).
\(\displaystyle \min_{p \in \mathbb{R}^n} m_k(p)\) such that \(\displaystyle \Vert p \Vert \lt \Delta_k \).