0
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ You could maybe do alternating steps solving - optimizing - solving - optimizing. $\endgroup$ Apr 19, 2017 at 7:38
  • $\begingroup$ Looking more for the combined formulation $\endgroup$
    – Adrian
    Apr 19, 2017 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$ Apr 19, 2017 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$
    – Adrian
    Apr 19, 2017 at 8:06
  • $\begingroup$ Just add another term $\min\{\|G\| + \sum \|F_i\|\}$ $\endgroup$ Apr 19, 2017 at 8:10

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\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$
    – Adrian
    Apr 20, 2017 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, 2017 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, 2017 at 7:32
  • $\begingroup$ revisiting this- let's say I have implemented this in the manner you have suggested (optimizer with a square system of equality constraints = 0). I would still like to use this method in an unoptimized case. So basically just use the solver to solve the nonlinear constraints and not optimize anything. What should the objective function of the optimizer be in this case? $\endgroup$
    – Adrian
    Dec 29, 2023 at 6:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .