4
$\begingroup$

Problem

Solving a non-linear system of equations.

The number of variables is the same as the number of equations.

When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{x}$), the system becomes an under-determined, dense, and linear system of the subset of variables $$A(\vec{y})\vec{x} = \vec{b}(\vec{y})\tag{1}\label{system1}$$

where $A(\vec{y})$ is a dense matrix, and $\vec{b}(\vec{y})$ is a dense vector). Let's call this sub-system $\eqref{system1}$ as system 1.

When I fix $\vec{x}$ and keep $\vec{y}$ free, the system becomes an over-determined, sparse, and non-linear system of the subset of variables $$F(\vec{x}, \vec{y}) = 0\tag{2}\label{system2}$$

The Jacobian $J(\vec{x}, \vec{y})$ is available in a closed form. Let's call this sub-system $\eqref{system2}$ as system 2.

About half of the equations in $\eqref{system2}$ are equality constraints that are linear in terms of $\vec{y}$. Each of the constraints is quite sparse and involves only about 5% of all variables.

Can I solve it with the following?

Algorithm 1

  1. Initialize $\vec{x} = \vec{x}_0$, and $\vec{y} = \vec{y}_0$
  2. Fix $\vec{y}_{n - 1}$, solve $A(\vec{y}_{n-1})\vec{x}_{n} = \vec{b}(\vec{y}_{n-1})$ for one of all the possible $\vec{x}_{n}$ because this system is under-determined.
  3. Fix $\vec{x}_{n - 1}$. Perform one iteration of Newton's method for solving $F(\vec{x}_{n-1}, \vec{y}_{n}) = 0$ for $\vec{y}_{n}$.
  4. If not converged, go to step 2.

Algorithm 2

If I replace step 2 in Algorithm 1 by a Newton's method iteration for solving system 1 $\eqref{system1}$, then I guess the steps become a block Newton's method.

Question

But I don't know if these two algorithms can work because system 1 $\eqref{system1}$ is under-determined and system 2 $\eqref{system2}$ is over-determined.

Can this work?

Related

Guess

It is similar to a coordinated descent over two groups of variables. So I hope algorithm 2 should be generally fine. Algorithm 2 would keep the approximate solution in each iteration close to each other. Algorithm 1 might make the variables jump around in some cases (might. but I am not sure). I assume the trajectory of approximate solutions don't form a stable cycle or orbit. But Newton's method in general has the same assumption.

$\endgroup$
  • $\begingroup$ I think any reasonable answer will be fine, including geometrical or linear algebra arguments or explanation based on existing algorithms or analysis. Really looking for any kind of pointers. Thanks. $\endgroup$ – R zu Oct 7 '18 at 14:56
  • $\begingroup$ Your question is better suited for Computational Science SE and I’m sure you’ll recieve answers pretty soon there. $\endgroup$ – Sandro Lovnički Oct 7 '18 at 15:52
  • $\begingroup$ Try editing your question slightly (maybe include these thoughts you commented) and it will be pushed to the top by activity, so more people will see it. Also do that on Computational Science channel. $\endgroup$ – Sandro Lovnički Oct 9 '18 at 15:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.