Solving a nonlinear least-square problem with a nonlinear equality constraint

Question

Given three points $P_k \in \mathbb{R}^2$, $k \in \{0,1,2\}$, and two edges $P_0 P_1$ and $P_1 P_2$ connecting them, I'm trying to get my head around the following (representing a very much simplified version of a more involved problem):

• $P_1$ is moved to a new position $P_1'$
• $P_0$ and $P_2$ should be updated to $P_0'$ and $P_2'$ such that we have $\|P_1' - P_0'\| = \|P_1 - P_0\|$ and $\|P_2' - P_1'\| = \|P_2 - P_1\|$. In other words, the lengths of the edges connecting the three points should not change. This means that $P_0'$ and $P_2'$ can move on circles with respective radii $\|P_1 - P_0\|$ and $\|P_2 - P_1\|$ centred at $P_1'$
• At the same time, $P_0$ and $P_2$ should move as little as possible, i.e. $\|P_0 - P_0'\|$ and $\|P_2 - P_2'\|$ should be minimal

A visualisation of the above might look as follows:

Now, this problem can be easily solved by hand: $P_0'$ and $P_2'$ must lie on the intersections of the edges $P_0 P_1'$ and $P_1' P_2$ with the circles mentioned above.

However, as the actual setting is more involved (e.g. there might be many more points and connected edges, or even a 2D network of them), I'd like to consider the problem in a (nonlinear) optimisation setting. As such, the first condition can be formulated as a (single) nonlinear equality constraint, i.e. $$g(P_0', P_1', P_2') = (\|P_1 - P_0\| - \|P_1' - P_0'\|)^2 + (\|P_2 - P_1\| - \|P_2' - P_1'\|)^2 = 0.$$

In other words, the nonlinear equality constraint gives us a subset of $\mathbb{R}^4$ as feasible domain (though we only have two scalar degrees of freedom, the angles of the two edges). Furthermore, the second condition can be formulated as a nonlinear least-squares problem, i.e. $$\min_{P_0', P_2'} f(P_0', P_2') = \frac12 \Big( \|P_0 - P_0'\|^2 + \|P_2 - P_2'\|^2 \Big).$$

For a general nonlinear least-squares problem without (nonlinear) equality constraint, I'd use a Gauss-Newton method to solve it numerically. With the constraint present, I'm not certain how to proceed.

[Edit] One option might be to introduce a Lagrangian multiplier $\lambda$ and solve for $\nabla f - \lambda \nabla g = 0$, e.g. using a Newton-Lagrange or constrained Gauss-Newton approach as described in these lecture notes (Chapter 12). However, I have some doubts about the nonlinear equality constraint $g$ — we actually have an equality constraint for each individual edge (so two of them following the example), which results in multiple (two) Lagrangian multipliers. At the same time, summing these to form a single equality constraint as I did above looks valid (the individual terms are squared, so the only way for the constraint to vanish is for each term to vanish).

Answer 1

Really, the applied approach can be modified.

Let

• $r_0 = \|P_0P_1\|,\; r_2=\|P_1P_2\|\tag1$
• $P_k\rightarrow b_k\in\mathbb C^3,\;P'_k\rightarrow z_k \in\mathbb C^3,\tag2$ then
• $z_0(\varphi_0) = z_1 + r_0e^{i\varphi_0},\quad z_2(\varphi_2) = z_1 + r_2e^{i\varphi_2},\tag3$
• $f(\varphi_0,\varphi_2) = \dfrac12(|z_0(\varphi_0)-b_0|^2+|z_2(\varphi_2)-b_2|^2).\tag4$ $ $

Proposed $2$-parametric model allows to avoid Lagrange multipliers method and looks the easiest for the given problem.