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.

  • $\begingroup$ You could maybe do alternating steps solving - optimizing - solving - optimizing. $\endgroup$ – mathreadler Apr 19 '17 at 7:38
  • $\begingroup$ Looking more for the combined formulation $\endgroup$ – dacfer Apr 19 '17 at 7:52
  • $\begingroup$ You can reformulate the equation solving as an optimization instead of solving $f(x) = 0$ you try and minimize $\|f(x)\|_?$ with some ? norm. $\endgroup$ – mathreadler Apr 19 '17 at 7:54
  • $\begingroup$ 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. $\endgroup$ – dacfer Apr 19 '17 at 8:06
  • $\begingroup$ Just add another term $\min\{\|G\| + \sum \|F_i\|\}$ $\endgroup$ – 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.

Anyway, long story short, just formulate the equality constrained optimization problem. Then, focus on algorithms for that. Most good algorithms allow for error in the final solution of the equality constraint, so don't worry if there's a little shuffle. Opinions may vary, but a composite-step SQP method globalized with either a trust-region or line-search method is what you probably want.

  • $\begingroup$ Yes I was thinking of that last night. I hadn't done that to start with as the original problem did not involve optimization per se as it is just a square system of nonlinear equations which I was solving by minimization of the sum of the squares of the residuals. This problem can be large up to 500 variables while the optimization bit I want to add only involves less than 10 parameters. Is that an issue? $\endgroup$ – dacfer Apr 20 '17 at 9:37
  • $\begingroup$ 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. $\endgroup$ – wyer33 Apr 21 '17 at 7:28
  • $\begingroup$ You don't need the inexactness control for a problem of that size, but there's a tech report by Ridzal, Heinkenschloss, and Aguiló that spells out the algorithm with these modifications here called "Numerical study of a matrix-free trust-region method for equality constrained optimization" There's a SIAM paper that goes through the convergence proof, but that tech report has a much better description of the algorithm. That said, I think they make it more complicated than they need to, but all the information is there. $\endgroup$ – wyer33 Apr 21 '17 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.