# Algorithms for non-square rootfinding

**URL:** <https://discourse.julialang.org/t/algorithms-for-non-square-rootfinding/119370>\
**Category:** Optimization (Mathematical)\
**Tags:** question\
**Created:** [September 13, 2024, 12:11pm UTC](https://discourse.julialang.org/t/algorithms-for-non-square-rootfinding/119370 "2024-09-13T12:11:05Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 13, 2024, 12:11pm UTC](https://discourse.julialang.org/t/algorithms-for-non-square-rootfinding/119370/1 "2024-09-13T12:11:05Z")

</div>

Consider a rootfinding problem

f(x) = 0

in x \in \mathbb{R}^ n, where f is differentiable.

Most texts I am familiar with assume that f: \mathbb{R}^n \to \mathbb{R}^n, so implicitly the Jacobian J is square.

But in economics, it is common to have f: \mathbb{R}^n \to \mathbb{R}^m, with m \ge n. A simple example is an excess demand system, because of [Walras’s law](https://en.wikipedia.org/wiki/Walras%27s_law), if all but one markets clear then the last one clears too. For the purposes of this discussion, **a root can be assumed** , it is not a nonlinear least squares problem.

Of course one can just drop one of the equations/residuals, but I found that is not always well-behaved in f's with a lot of non-uniform curvature: sometimes rootfinding converges much quicker when I retain the whole system. Taking this further, when I have equivalent equilibrium conditions that have different scales, throwing them all in is usually much more stable than pre-selecting. Sometimes I end up systems where m \approx 2n, and they work much better.

Algorithms that require non-singular J, J^{-1}, or similar cannot handle this, but quasi-Newton and trust region algorithms that use merit functions can be trivially extended, sometimes without a change in code.

Now the **questions** :

1. is there textbook you would recommend on nonlinear rootfinding that discusses this case (ie m \ge n), from a practical perspective?

2. any algorithms you would recommend for this problem class? (I have implemented trust-region with simple dogleg, and it works OK, but I wonder if I could do better).

3. is there a Julia package that handles these kind of problems?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 13, 2024, 12:56pm UTC](https://discourse.julialang.org/t/algorithms-for-non-square-rootfinding/119370/2 "2024-09-13T12:56:27Z")

</div>

NonlinearSolve.jl supports this (primarily via QR factorization)

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [September 13, 2024, 6:33pm UTC](https://discourse.julialang.org/t/algorithms-for-non-square-rootfinding/119370/3 "2024-09-13T18:33:13Z")

</div>

You could simply apply an optimization solver to the feasibility problem

Min 0 subject to f(x) = 0.

For instance, IPOPT will boil down to a method for nonlinear equations, with robust globalization features.