Minimizing a single-variable quadratic function with quadratic constraint on the same variable

21 Views Asked by At

I am reading a paper (see Algorithm 3.1) that contains the sub-problem:

Find $\tilde{\tau}$ so that $\tilde{s} = \tilde{s}_j + \tilde{\tau} \tilde{p}_j$ minimizes

$$ \tilde{\phi}(\tilde{s}) = \tilde{g}^T\tilde{s} + \frac{1}{2}\tilde{s}^T\tilde{B} \; \tilde{s} $$

and $\|\tilde{s}\| = \Delta$, where $\tilde{\phi}(\tilde{s})$ is defined in equation (3.4), $\tilde{B}$ is a matrix, $\Delta$ is a constant and $\tilde{g}$, $\tilde{p}$ and $\tilde{s}$ are vectors.

Here's my current thinking (I am not at all certain it is correct)

Expanding $\tilde{\phi}(\tilde{s})$ and dropping the constants results in the quadratic

$$ \tilde{\phi}(\tilde{s}) = \tilde{\tau}\left( \tilde{g}^T\tilde{p}_j + \tilde{s}^T_j\tilde{B} \; \tilde{p}_j \right) + \frac{1}{2} \tilde{\tau}^2\left(\tilde{p}^T_j\tilde{B} \; \tilde{p}_j \right) $$

but expanding and squaring $\|\tilde{s}\|$ also yields the quadratic

$$ \tilde{s}^T_j\tilde{s}_j + 2 \,\tilde{\tau} \left(\tilde{s}^T_j\tilde{p}_j \right) + \tilde{\tau}^2\left(\tilde{p}^T_j \tilde{p}_j \right) = \Delta^2 $$

This suggests that I can proceed by considering the two solutions to the latter quadratic, selecting the one that minimizes $\tilde{\phi}(\tilde{s})$. This seems a bit too simplistic tho.