Sequential Optimization, Quadratic Approximations, and Trust Regions
Summary
The discussion asks whether it is useful to solve a second optimization problem near the solution of a nonconvex problem, particularly when the two problems use different solvers. The response connects this idea to several established numerical optimization concepts. Gradient descent and Newton’s method can be understood as repeatedly optimizing quadratic approximations to an objective, while the broader practice of updating a solution through successive steps is called an iterative method.
Restricting a candidate solution to a ball around a current point is related to trust region methods, which control the region over which a local approximation is used. The answer offers these connections and points to a standard numerical optimization reference, but it does not establish that the proposed second problem improves the original solution. In particular, the result depends on the objectives and constraints, and proximity alone does not guarantee global optimality or better performance.
Key ideas
- Successive quadratic approximations underlie methods such as gradient descent and Newton’s method.
- Repeatedly updating a candidate solution is generally described as an iterative method.
- A constraint limiting steps to a neighborhood of a point is related to trust region methods.
- A nearby solution to a second problem does not by itself guarantee improvement to the original objective.
Tags
Full text
# Sequential Optimization
# Sequential Optimization
I am looking for the name of a sequential optimization, if that technique makes indeed any sense and exists.
Given the solution $x^*$ to a non-linear non-convex problem \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & \mathbf{f(x)}\\ & \text{subject to} & A_1\mathbf {x} \leq \mathbf {b}_1 \end{aligned} \end{equation*} with $f(x)$ non-linear and non-convex, is it reasonable to look at the quadratic problem \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & \frac{1}{2}\mathbf {x} ^{\mathrm{T} }Q\mathbf{x} +\mathbf{c}^{\mathrm {T} }\mathbf {x} \\ & \text{subject to} & A_2\mathbf {x} \leq \mathbf {b}_2 \\ & &\lVert \mathbf{x-x^*} \rVert_2 \leq \epsilon \end{aligned} \end{equation*} and if so, is there a name for looking for the solution of one optimization problem that is in some sense (not necessarily in the sense of the Euclidean norm) close to the solution of another. The practical background is that I would like to use different solvers for each problem. I understand that the solution $\overline{x}$ of the quadratic problem is not a global solution. Is there a name under which this has been studied?
## Answer by Matthew Gunn (score 2, accepted)
https://quant.stackexchange.com/a/41082
I'm not sure what you're exactly looking for? Perhaps of use:
- Gradient descent ($Q = \frac{1}{\alpha} I$) or Newton's method ($Q = \nabla^2 f$) can both be interpreted as minimizing successive quadratic approximations of a function.
- A method where you repeatedly update your answer is called an iterative method.
- Constraining the feasible set to some ball around a point (not necessarily the solution) is related to trust region methods.
- A comprehensive reference on numerical optimization is Nocedal and Wright.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.