Optimization-like question

Question

Let's say I have a formula like $ax + by + cz = N$. $a, b, c$, and $N$ are known and cannot be changed. $x, y$, and $z$ are known and can be changed.

The problem is that the equation is not true! My problem (for a program I'm writing) is: how can $x, y$, and $z$ be changed enough that they equal $N$ while differing from their previous values as little as possible?

Answer 1

The solution space of the equation $ax+by+cz=N$ is a plane in three dimensions, thus for any given point, say, $(x_0,y_0,z_0)$, you may easily calculate the distance between this point and the plane of actual solutions (this is equivalent to the possibly-familiar "least-squares method", which I think is the answer you're after?)

Answer 2

IN CASE YOU WANT THE VARIABLES TO BE INTEGERS:

This is called the "closest vector problem". Also the "nearest lattice point." Given one solution $X_0 = (x_0, y_0,z_0)$ to $ax+by+cz = N,$ you get a "lattice" by taking $X-X_0$ for every solution $X.$

You have a nonsolution, call it $Y = (x_1, y_1,z_1).$ You want the closest lattice point $X-X_0$ to $Y-X_0,$ so that $X-Y$ is shortest.

There is plenty of research on this, and probably some textbooks have good methods in dimensions 2 and 3 for the shortest vector problem and the related closest vector problem. https://en.wikipedia.org/wiki/Lattice_problem

EDIT: the lattice given is two dimensional. This means that finding a reduced basis is just Gauss reduction for (positive) a binary quadratic form. Once you have a reduced basis, it becomes straightforward to produce a finite list of lattice vectors that must contain the best solution, then check them.

Answer 3

Let $x_0, y_0, z_0$ be the current values of $x, y, z$.

An equation of the form $ax + by + cz = N$ specifies a plane in space. Let your plane be $P$. So your problem is equivalent to the following one: in space, given a point $(x_0, y_0, z_0)$ and a plane $P$, find the point on $P$ that is closest to $(x_0, y_0, z_0)$.

The closest point will be the point you get by dropping a perpendicular line from $(x_0, y_0, z_0)$ to $P$ and seeing where it lands. (This must be the closest because a straight line is the shortest distance between any two points!)

What I just described is also called the orthogonal projection of a point onto a plane. It's solved e.g. here.

As charlestoncrabb mentions, this is equivalent to the method of least squares because we measure distance in space by $\sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2 + (z_1 - z_0)^2}$. So that's the "default" meaning of "close to" in this context, oddly enough. If want to measure "close to" some other way, you can use more general optimization methods (like Lagrange multipliers).

Answer 4

Define $A = [a,b,c]$ and $X=[x, y, z]^T$, so your equation is $A*X = N$. Assume your known point to be $ \bar X = [x_0, y_0,z_0]^T$. Define the residual to be $R = N - A*\bar X$, since the equation is not true. The question becomes $$\min|| X- \bar X ||,s.t. A*X = N$$

The solution $X^*$ that minimize the distance is $X^* = \bar X + A^+R$ where $A^+$ is the Moore_Penrose pseudo inverse of $A$ and is this case since $A$ has linearly independent rows, $A^+ = A^T(AA^T)^{-1}$. The distance is $||X^* - \bar X || = || A^+R||$, you can pick whatever norm you like.

This is also true if $A$ is a matrix instead of a row vector suppose you have a linear equation system.