$$\DeclareMathOperator*{\argmin}{{arg\,min}} \DeclareMathOperator*{\argmax}{{arg\,max}} \DeclareMathOperator*{\minimize}{{minimize}}$$

# A unifying principle: surrogate optimization

We aim to solve an optimization problem of the form

$$\label{eq:fw_objective} \minimize_{\boldsymbol{x} \in \RR^p} f(\boldsymbol{x}) ~.$$

A key idea is to start at an initial estimate $\xx_0$ and successively minimize an approximating function $Q_t(\xx)$: $$\xx_{t+1} = \argmin_{\xx \in \RR^p} Q_t(\xx)~.$$

We will call $Q_t$ a surrogate function. It is also known as merit function.

How to find such surrogate function?

A good surrogate function should:

• Approximate the objective function.
• Easy to optimize.

### Linear surrogates

The simplest class of surrogates we can think of are linear surrogates, that is, functions of the form $$Q_t(\xx) = (\xx - \xx_t)^T \boldsymbol{b}_t + c_t~.$$

While simple, they are general unbounded, making thir minimization problematic -- although they do have some uses in constrained optimization

Slightly more complex are quadratic functions. These are of the form $$Q_t(\xx) = (\xx - \xx_t)^T \boldsymbol{A} (\xx - \xx_t) + \boldsymbol{b}_t^T (\xx - \xx_t) + c_t.$$

Yes! Many examples: Gradient descent, Newton, etc.