# Optimizers¶

Critical to using the insights generated from subspace-based dimension reduction is the ability to use these low-dimensional representations for optimization.

## Low-Level Optimization¶

### Gauss-Newton¶

psdr.gauss_newton(f, F, x0, tol=1e-10, tol_normdx=1e-12, maxiter=100, linesearch=None, verbose=0, trajectory=None, gnsolver=None)[source]

A Gauss-Newton solver for unconstrained nonlinear least squares problems.

Given a vector valued function $$\mathbf{f}:\mathbb{R}^m \to \mathbb{R}^M$$ and its Jacobian $$\mathbf{F}:\mathbb{R}^m\to \mathbb{R}^{M\times m}$$, solve the nonlinear least squares problem:

$\min_{\mathbf{x}\in \mathbb{R}^m} \| \mathbf{f}(\mathbf{x})\|_2^2.$

Normal Gauss-Newton computes a search direction $$\mathbf{p}\in \mathbb{R}^m$$ at each iterate by solving least squares problem

$\mathbf{p}_k \leftarrow \mathbf{F}(\mathbf{x}_k)^+ \mathbf{f}(\mathbf{x}_k)$

and then computes a new step by solving a line search problem for a step length $$\alpha$$ satisfying the Armijo conditions:

$\mathbf{x}_{k+1} \leftarrow \mathbf{x}_k + \alpha \mathbf{p}_k.$

This implementation offers several features that modify this basic outline.

First, the user can specify a nonlinear trajectory along which candidate points can move; i.e.,

$\mathbf{x}_{k+1} \leftarrow T(\mathbf{x}_k, \mathbf{p}_k, \alpha).$

Second, the user can specify a custom solver for computing the search direction $$\mathbf{p}_k$$.

Parameters: f (callable) – residual, $$\mathbf{f}: \mathbb{R}^m \to \mathbb{R}^M$$ F (callable) – Jacobian of residual $$\mathbf{f}$$; $$\mathbf{F}: \mathbb{R}^m \to \mathbb{R}^{M \times m}$$ tol (float [optional] default = 1e-8) – gradient norm stopping criterion tol_normdx (float [optional] default = 1e-12) – norm of control update stopping criterion maxiter (int [optional] default = 100) – maximum number of iterations of Gauss-Newton linesearch (callable, returns new x) – f : callable, residual, f: R^n -> R^m g : gradient, R^n p : descent direction, R^n x0 : current iterate, R^n gnsolver ([optional] callable, returns search direction p) – Parameters: F: current Jacobian f: current residual Returns: p: search step s: singular values of Jacobian verbose (int [optional] default = 0) – if >= print convergence history diagnostics numpy.array((dof,)) – returns x^* (optimizer) int – info = 0: converged with norm of gradient below tol info = 1: norm of gradient did not converge, but ||dx|| below tolerance info = 2: did not converge, max iterations exceeded

### Minimax¶

psdr.minimax(f, x0, domain=None, trajectory=<function trajectory_linear>, c_armijo=0.01, maxiter=100, trust_region=True, search_constraints=None, tol_dx=1e-10, tol_df=1e-10, verbose=False, bt_maxiter=30, **kwargs)[source]

Solves a minimax optimization problem via sequential linearization and line search

Given a vector-valued function $$f: \mathcal{D}\subset\mathbb{R}^m\to \mathbb{R}^q$$, solve the minimax optimization problem:

$\min_{\mathbf{x}\in \mathcal{D}} \max_{i=1,\ldots, q} f_i(\mathbf{x}).$

This implements a minor modification of the algorithm described by Osborne and Watson [OW69]. The basic premise is that we add in a slack variable $$t_k$$ representing the maximum value of $$f_i(\mathbf{x}_k)$$ at the current iterate $$\mathbf{x}_k$$. Then we linearize the functions $$f_i$$ about this point, yielding additional linear constraints:

(1)$\begin{split}\min_{\mathbf{p}_\mathbf{x} \in \mathbb{R}^m, p_t} & \ p_t \\ \text{such that} & \ t_k + p_t \ge f_i(\mathbf{x}_k) + \mathbf{p}_\mathbf{x}^\top \nabla f_i(\mathbf{x}_k) \quad \forall i=1,\ldots,q\end{split}$

This yields a search direction $$\mathbf{p}_\mathbf{x}$$, along which we preform a line search to find a point satisfying the constraint:

(2)$\min_{\alpha \ge 0} \max_{i=1,\ldots,q} f_i(T(\mathbf{x}_k, \mathbf{p}_\mathbf{x}, \alpha)) \le t_k + c\alpha p_t.$

Here $$T$$ represents the trajectory which defaults to a linear trajectory:

$T(\mathbf{x}, \mathbf{p}, \alpha) = \mathbf{x} + \alpha\mathbf{p}$

but, if provided can be more sophisticated. The substantial difference from [OW69] is using an inexact backtracking linesearch is used to find the $$\alpha$$ satisfying the Armijo like condition (2); as originally proposed, Osborne and Watson use an exact line search.

Parameters: f (BaseFuction-like) – Provides a callable interface f(x) that evalates the functions at x and access to the gradient by f.grad(x) x0 (array-like (m,)) – Starting point for optimization domain (Domain, optional) – Add constraints to each step enforcing that steps remain in the domain (assumes a linear trajectory for steps) trajectory (callable, optional) – Function taking current location x, direction p, and step length alpha and returning a new point x. c_armijo (float, optional) – Coefficient used in the Armijo backtracking linesearch maxiter (int, optional) – Maximum number of iterations trust_region (bool, optional) – If true, enforce a spherical trust region on each step search_constraints (callable) – Function taking the current iterate x and cvxpy.Variable representing the search direction and returning a list of cvxpy constraints. tol_dx (float) – convergence tolerance in terms of movement of x tol_df (float) – convergence tolerance in terms of the maximum verbose (bool) – If true, display convergence history bt_maxiter (int) – Number of backtracking line search steps to take **kwargs (dict) – Additional parameters to pass to cvxpy.Problem.solve() x – Solution to minimax problem. np.array (m,)

References

 [OW69] (1, 2) Osborne and Watson, “An algorithm for minimax approximation in the nonlinear case”, The Computer Journal, 12(1) 1969 pp. 63–68 https://doi.org/10.1093/comjnl/12.1.63