2
$\begingroup$

I have a system of equations with 4 variables and i'm trying to find the closest vector to the origin that satisfies both of the equations.

$x_1+0*x_2+2x_3-x_4 = 1$

$3x_1+x_2-2x_3+0*x_4=0$

I tried optimizing the 3D distance function for each one of those separately:

$f(x,y) = x^2 + y^2 + z^2$

But the answers I get for $x_1, x_2, x_3, x_4$ are different for each equation. I'm not sure how to proceed, any help would be much appreciated.

One suggestion I had was to put them in terms of matrices/vectors and optimize that way but i'm not sure how to do that.

EDIT: I tried a 4D distance function, but i still get different answers from each equation and I need one vector that satisfies both...

$\endgroup$
  • $\begingroup$ why are you using three dimensional distance? $\endgroup$ – qbert Sep 15 '16 at 14:55
  • $\begingroup$ Because in both equations 2 of the variables are zero'd out so i thought three dimensional would be the right one? $\endgroup$ – Ghazal Sep 15 '16 at 14:56
  • $\begingroup$ They may cancel in your constraint, but you still want to minimize the value of your fourth variable $\endgroup$ – qbert Sep 15 '16 at 14:58
  • $\begingroup$ I still get different answers from each equation but i need one vector that satisfies both $\endgroup$ – Ghazal Sep 15 '16 at 15:06
1
$\begingroup$

That would be a linear comb. of vectors $v$(1,0,2,-1) and $u$(3,1,-2,0) that satisfies both equations. $u$ and $v$ are the normal vectors of the given 3-dimensional planes, so they will be orthogonal to their intersection also. So you want the one that actually reaches that intersection and starts from the origin. Let $x=av+bu$ put it in your equations: $$(a+3b)+0(0a+b)+2(2a-2b)-(-a+0b)=1$$$$3(a+3b)+(0a+b)-2(2a-2b)+0(-a+0b)=0$$ So $a=14b$ and $14b+3b+2(28b-2b)+14b=1$ => $b=1/83$, $a=14/83$

Meaning your vector is (17/83, 1/83, 26/83, -14/83)

$\endgroup$
  • $\begingroup$ How do you know if this is the closest solution to the origin (0,0,0,0) ? $\endgroup$ – Ghazal Sep 15 '16 at 15:17
  • $\begingroup$ This answer doesn't seem to make sense, what are $v$ and $u$ meant to be here? $\endgroup$ – EHH Sep 15 '16 at 15:21
  • $\begingroup$ u and v are vectors normal to those 3-dimesnional planes you have given by those equations, so as for their intersection. $\endgroup$ – Djura Marinkov Sep 15 '16 at 15:22
  • $\begingroup$ So you actually mean $v=(1,0,2,-1)$? $\endgroup$ – EHH Sep 15 '16 at 15:23
  • $\begingroup$ Didn't I write so? $\endgroup$ – Djura Marinkov Sep 15 '16 at 15:26
1
$\begingroup$

Each of the given equations describes a three-dimensional hyperplane in $\mathbb R^4$. Their intersection is two-dimensional, i.e., a plane. Any vector in this plane can be decomposed into the sum of a vector parallel to the plane and one orthogonal to it. The orthogonal component is a constant vector whose length is the distance of the plane from the origin. Obviously, this minimum distance is attained when the parallel component is zero. This orthogonal vector can be found via projection onto the orthogonal complement of the plane.

First, we find a vector in the plane by solving the system of equations. Row-reduction produces $\mathbf v=(1,-3,0,0)^T$. Next, we need the orthogonal complement to the plane. The equations of the hyperplanes are of the form $\mathbf n\cdot\mathbf x=d$, where $\mathbf n$ is a vector normal to the hyperplane. The span of these two normals is orthogonal to the intersection of the hyperplanes. There are various ways to compute the orthogonal projection of $\mathbf v$ onto this space. If we let $A$ be the matrix with the two normals as columns, then $P=A(A^TA)^{-1}A^T$ is the matrix of this projection. Alternatively, finding an orthonormal basis $(\mathbf u_1,\mathbf u_2)$ via Gram-Schmidt isn’t too bad, after which you can use the projection formula $(\mathbf v\cdot\mathbf u_1)\mathbf u_1+(\mathbf v\cdot\mathbf u_2)\mathbf u_2$. The resulting vector is $\frac1{83}(17,1,26,-14)^T$.

$\endgroup$
0
$\begingroup$

Here's my solution:

If set the matrix A to be equal to the system of the equations:

$A = \begin{bmatrix} 1 & 0 & 2 & -1 \\ 3 & 1 & -2 & 0 \end{bmatrix}$

We can calculate the generalized inverse of A which is

$G = \begin{bmatrix} 0.2048 & 0.2289\\ 0.012 & 0.0723\\ 0.3 & -0.12\\ -.16 & -0.12 \end{bmatrix}$

We then have that the closest solution x to the origin of the equation $Ax=b$ is $x = Gb$

$\endgroup$
  • $\begingroup$ Hm interesting, seems OK $\endgroup$ – Djura Marinkov Sep 15 '16 at 16:43
0
$\begingroup$

Since intuition in 4D may be fallacious, I suggest the following approach.
Find the general set of solutions to the system:
it will be representable by a point (one specific solution), e.g. $ (0,0,0,-1)$, and the combination of two independent vectors (a basis of the null vectors of the coefficient matrix = the solutions to the homogeneous system). e.g. $(-2,8,1,0)$ and $(1,-3,0,1)$.
Take the square norm of such general solution vector (which is from the origin) and minimize with respect to the two "free" parameters, with the choices above you will get $\lambda = 26/83$ and $\mu = 69/83$.
Thus the vector you were looking for is $1/83 (17,1,26,-14)$ , and the distance is its modulus, i.e. $\sqrt{14/83}$.
You can check that it is a solution of the given system and that it is orthogonal to the null vectors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.