1
$\begingroup$

Can I use Mathematica to find a value for $\alpha$ that satisfies the below linear combination inequality? If so, how?

$$ \begin{bmatrix} -1 \\ -1 \\ -1 \end{bmatrix} < \begin{bmatrix} g_1 \\ \vdots \\ g_n \end{bmatrix} + \alpha \begin{bmatrix} m_1 \\ \vdots \\ m_n \end{bmatrix} < \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} $$

I do not care as much about finding an algebraic expression as I do about finding a numerical solution for $\alpha$ given a set of values $g_1, \dots, g_n$ and $m_1, \dots, m_n$.

Furthermore, an important point is that I would be happy as long as the value of $\alpha$ is such that the above inequality is almost true. In other words, if an exact solution does not exist (which is rather likely) I would like to find a value for $\alpha$ that minimizes the error in the inequality (Currently, I cannot find a more precise way to express what I mean by the "error" in the inequality.)

Update 1: Perhaps one could think of minimizing the "error" in the above inequality in a "least squares sense". After all, if we omit one of the outer vectors, say $[-1 \ -1 \ -1]$, and replace $<$ by $=$, we would have an overdetermined system of equations and could attempt to find a value for $\alpha$ by the Method of Least Squares.

For example, the system $$ \begin{bmatrix} g_1 \\ \vdots \\ g_n \end{bmatrix} + \alpha \begin{bmatrix} m_1 \\ \vdots \\ m_n \end{bmatrix} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} $$ could be rewritten on the form $A\vec{x} = \vec{b}$ as follows: $$ \begin{bmatrix} g_1 & m_1 \\ \vdots & \vdots \\ g_n & m_n \end{bmatrix} \begin{bmatrix} 1 \\ \alpha \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}. $$

Update 2: Since I want all of the entries in my resulting vector to lie between $-1$ and $1$, I believe that I could find a good value for $\alpha$ by solving the subsequent system of $n$ equations in one unknown:

$$ \begin{bmatrix} g_1 \\ \vdots \\ g_n \end{bmatrix} + \alpha \begin{bmatrix} m_1 \\ \vdots \\ m_n \end{bmatrix} = \begin{bmatrix} 0 \\ \vdots \\ 0 \end{bmatrix} $$

I believe that the problem proposed at the very start of my post can be reduced to finding a solution to the above system using the Method of Least Squares. I believe this because $0$ lies precisely in the middle between $-1$ and $1$, and the least squares solution to the above system finds the value of $\alpha$ that will result in all entries of the linear combination being as close to 0 as possible in the "least squares sense". Intuitively, getting all entires as close to zero as possible (or, in other words, as close to precisely in the middle between $-1$ and $1$ as possible) appears to be a very similar problem as the problem of getting all entires to lie within the interval $[-1, 1]$.

Ultimately, I think that solving the overdetermined system

$$ \begin{bmatrix} m_1 \\ \vdots \\ m_n \end{bmatrix} \begin{bmatrix} \alpha \end{bmatrix} = \begin{bmatrix} -g_1 \\ \vdots \\ -g_n \end{bmatrix} $$ using the Method of Least Squares should also be a solution to the original problem. Can you find any holes in this approach?

Update 3: My proposed approach seems to work fairly well. A test on vectors with 48000 randomly generated entries between $-1$ and $1$ resulted in $7$ entires (~0.15%) that violate the inequality in the resulting linear combination. If I just add together the vectors without using my approach to prepare them, 12 064 entires (~25%) violate the inequality.

$\endgroup$
  • $\begingroup$ Probably better to ask another question, rather than changing a question, particularly once it has been answered. $\endgroup$ – mikado Feb 25 at 6:08
  • $\begingroup$ @mikado In my question, I say "if an exact solution does not exist (which is rather likely) I would like to find a value for 𝛼 that minimizes the error in the inequality". The provided answer only works if an exact solution exist, and thus it does not fully answer my original question. Furthermore, I have not changed my question in updating it, only provided a possible to it answer and asked for confirmation that it is correct. Please point out to me what you think should be a separate question; maybe I am overlooking it. $\endgroup$ – K. Claesson Feb 25 at 10:56
4
$\begingroup$

As an example, you could write this quite literally

eqn = {-1, -1, -1} < {3, 4, 5} + α {5, 6, 7} < {1, 1,  1}
(* {-1, -1, -1} < {3 + 5 α, 4 + 6 α, 5 + 7 α} < {1, 1, 1} *)

Reduce[Thread[eqn], α]
(* -(4/5) < α < -(4/7) *)

If your inequalities are infeasible, you will need to decide how you would define a "best" solution.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you elaborate on what Reduce[Thread[eqn], α] does? $\endgroup$ – K. Claesson Feb 24 at 21:30
  • 1
    $\begingroup$ @K.Claesson Reduce is a general function for solving equations. Thread turns expressions involving lists into lists of expressions. Try evaluating Thread[eqn] to see the effect. $\endgroup$ – mikado Feb 24 at 21:32

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