Python trust region optimization code that allows ellipsoid-shaped trust regions

Question

Are there any high quality trust region optimization implementations that

1. allow nonspherical ellipsoid trust regions, and
2. are written in Python, or are easy to call from python?

By nonspherical ellipsoid trust regions, I mean that each Newton step solves (or approximately solves) a problem of the following form: \begin{align}\min_x \quad& \frac{1}{2}x^T H x + g^T p \\ \text{such that} \quad & x^T C x \le \Delta^2, \end{align}

for some symmetric positive definite matrix $C$. The matrix $C$ acts like a Hessian preconditioner and may vary from Newton iteration to Newton iteration - for example, see the classic paper by Steihaug.

I've looked around a little and haven't found much yet.

• scipy.optimize only allows spherical trust regions. That is, it can only solve the case $C=I$
• Tao in PETSc allows you to choose from a fixed set of premade preconditioners for the CG-Steihaug step, but not use your own custom preconditioner (as far as I can tell).

Answer 1

Optizelle should be able to handle this. It's open-source and BSD licensed. Specifically, it will solve a trust-region subproblem of the form $$\begin{array}{rcl} \min\limits_{\delta x \in X} && \frac{1}{2}\langle H\delta x,\delta x\rangle + \langle \nabla f(x),\delta x\rangle\\ \textrm{st} && \langle \delta x,\delta x\rangle \leq \Delta^2 \end{array}$$ where the user can define an arbitrary preconditioner $P$ and inner product $\langle \cdot,\cdot\rangle$. As such, if you want a nonspherical shaped trust-region, redefine the inner product into something more oblique. Be careful, because the this also affects the definition of the gradient. If you want a preconditioner that changes optimization iteration to optimization iteration, that's fine. The CG system solved will be $$ PH \delta x = -P\nabla f(x). $$ Technically, if want to change the inner product every iteration, that's also possible, but needs to be done very carefully. There's a mechanism called the state manipulator that can inject arbitrary code. At the end of the optimization iteration, you could inject some code to update your inner product, but you'd also need to update the cached gradient since this would also be affected.