# Slightly change two vectors to satisfy a constraint

• $$\vec{a}\cdot\vec{b} \approx c$$
• $$\vec{\alpha} \cdot \vec{\beta} = c$$
• $$\vec{\alpha}$$ is close to $$\vec{a}$$ and $$\vec{\beta}$$ is close to $$\vec{b}$$

Given $$\vec{a}$$, $$\vec{b}$$ and c, how to find $$\vec{\alpha}$$, $$\vec{\beta}$$ quickly?

If necessary, I can assume distance between $$\vec{\alpha}$$ and $$\vec{a}$$ is usually much smaller than distance between $$\vec{b}$$ and $$\vec{\beta}$$.

Each vector has about 10 - 15 elements but I have to do this for about 10^4 vectors.

If probability should sum to 1 is the constraint, I can normalize the probabilty after each (or several) optimization step to control the numerical error. But I can't do the same thing for this constraint.

Lagrange multipliers and Linearization of the constraints give:

$$\vec{b} \cdot \vec{\alpha} + \vec{a} \cdot \vec{\beta} = \vec{\alpha} \cdot \vec{\beta} + \vec{a} \cdot \vec{b}$$

$$\vec {\alpha} + \lambda \vec{\beta} = \vec{a}$$

$$\vec {\beta} + \lambda \vec{\alpha} = \vec{b}$$

This is still not a linear system because of the $$\lambda \vec{\alpha}$$ terms.

How to do this faster?

• If I use lagrange multipliers, I get a non-linear (quadratic) system. – R zu Oct 24 '18 at 17:17
• Linearizing the constraint around $\vec a$ and $\vec b$ leads to 2N + 1 equations with 2N + 1 unknowns. – R zu Oct 24 '18 at 17:36
• Maybe I can do two Newton iterations. Fix beta and find alpha and lambda. Then fix alpha and find beta and lambda. Alternate till converge. – R zu Oct 24 '18 at 18:13
• This is an underdetermined problem so there are many many solutions. For example, just set $\alpha=a,\beta=bc/(a\cdot b)$. Since $a\cdot b\approx c$ you still get $\beta$ close to $b$. – Rahul Oct 24 '18 at 20:20
• If close means least square, then the problem becomes the last 3 equations I wrote. It is a non-linear system with n equations and n unknowns. hmm. I might try your normalization. Any one of the solutions would work. – R zu Oct 24 '18 at 20:31

There are of course infinitely many vectors $$\vec \alpha,\vec \beta$$ that satisfy $$\vec \alpha\cdot\vec \beta=c$$. So if you want to have a particular pair of vectors, you will have to be precise when stating what you mean that $$\vec \alpha,\vec \beta$$ should be "close" to $$\vec a,\vec b$$.
One pair that satisfies this is $$\vec \alpha = \vec a, \qquad \qquad \vec \beta = \frac{c}{\vec a \cdot \vec b}\;\vec b.$$