# Adding an optimizer to a nonlinear set of equations

I have a set of N nonlinear equations, $F_i(x_i,p_i) = 0$ in N unknowns, $x_i, i=1,N$. These equations also depend on a set of parameters, $p_i, i=1,P$. Currently I am solving the equations for a fixed set of parameter values, $p_i = p_i^*$ using a Newton scheme. This scheme minimizes the sum of the squares of the residuals, $R = \frac{1}{2} (F_i)^2$

Clearly the minimum found here needs to be as close to zero as possible so that all the equations are satisfied. Now I want to add an optimization level on to this solution, where I have an objective function $G(x_i,p_i)$ which I want to minimize for varying some of the $p_i, i=1,Q$ where $Q\le P$.

Obviously I can just treat the first solution as a function evaluation for the optimizer, however this is not efficient, being an iteration loop within an iteration loop. What I would like to do is solve the entire system using one combined Newton scheme. My question is how do I do this?

I could just add the objective function G to R and minimize the sum, however this may minimize the sum, but not each individually, specifically R which must minimize to zero.

• You could maybe do alternating steps solving - optimizing - solving - optimizing. – mathreadler Apr 19 '17 at 7:38
• Looking more for the combined formulation – dacfer Apr 19 '17 at 7:52
• You can reformulate the equation solving as an optimization instead of solving $f(x) = 0$ you try and minimize $\|f(x)\|_?$ with some ? norm. – mathreadler Apr 19 '17 at 7:54
• Yes that's exactly what I doing at the moment to solve the equation system- I am minimizing the sum of squares of $F_i$. I need to add the minimization of G to this formulation somehow. – dacfer Apr 19 '17 at 8:06
• Just add another term $\min\{\|G\| + \sum \|F_i\|\}$ – mathreadler Apr 19 '17 at 8:10

I may be missing something, but it just sounds like you have an equality constrained optimization problem. It's easiest to write this in vectorized form, so let $p=(\hat{p},\tilde{p})$ where $\hat{p}$ are now the parameters you want to optimize for (new variables) and $\tilde{p}$ are the remaining true parameters. Then, we can solve $$\min\limits_{x,\hat{p}}\{G(x,p) : F(x,p) = 0\}$$ Algorithms like SQP methods do not care if $F$ is nonlinear or not, so just let the algorithm solve the equality constraint for you and focus on the objective.
Now, that said, if you have a nonconvex, nonlinear optimization problem, then a basic SQP method won't work and you'll have to globalize, which means using a line-search or trust-region method. Personally, I like what are called composite step SQP methods. In affect, the algorithm will take a single step of something that looks like a Gauss-Newton method to solve the feasibility problem and then a Newton step to find optimality. However, this is done in a very principled way in order to guarantee convergence of the method. Likely, the work that you put into designing a Newton solver for $F$ will pay off in this algorithm. I don't really like their write-up, but Conn, Gould, and Toint do summarize this algorithm starting on page 657 of their book Trust-Region Methods. If you strip out all of the interior point stuff, Byrd, Hribar, and Nocedal use this algorithm in their 1999 paper "An Interior Point Algorithm for Large-Scale Nonlinear Programming". I am certain there's a better reference than these two, but I can't think of it off the top of my head.
• Not really. I've scaled out the algorithms I mentioned above to thousands of variables. The trick is to carefully solve the linear systems involved. In short, there are two. The composite step algorithm requires null space projections. These can be found either by solving something called an augmented system or by an SVD. Going the augmented system route, if the equality constraint is $g(x)=0$, the preconditioner involves factorizing $g'(x)g'(x)^T$, which is nconstraints by nconstraints. The other system is the optimality system. This can be solved with Steihaug-Toint truncated CG. – wyer33 Apr 21 '17 at 7:28