# # Lagrange Multiplier

A technique for constrained optimisation.

## # 2 Examples

Notation: using capitals for vectors, lower case for scalars, and subscripts for vector components.

### # 2.1 Nearest Point On Perpendicular Bisector

Find the distance $$d$$ from a given point $$X$$ to the nearest point $$Y$$ on the perpendicular bisector of two other given points $$A$$ and $$B$$.

(Practical use: drawing Voronoi tesselation using distance estimate, when $$A$$ and $$B$$ are the two nearest centers to $$X$$.)

Let the function to be minimized be $f(Y) = d^2 = \sum (x_i - y_i)^2$ then $(\operatorname{grad} f)_i = -2 (x_i - y_i).$

Let the midpoint of $$A,B$$ be $$M = (A + B)/2$$ and the normal of the bisector be $$N = (A - B)/2$$. Then let the constraint on $$Y$$ be $g(Y) = (Y - M) \cdot N = \sum (y_i - m_i) n_i$ with $(\operatorname{grad} g)_i = n_i.$

By the method of Lagrange multiplier, solve simultaneously $\operatorname{grad} f = \lambda \operatorname{grad} g \quad\quad g = 0$ that is $-2(x_i - y_i) = \lambda n_i\quad\quad\sum(y_i-m_i)n_i = 0.$

In matrix form using 4D with $$\mu = \lambda / 2$$, that gives

$\begin{pmatrix} 1 & & & & -n_1 \\ & 1 & & & -n_2 \\ & & 1 & & -n_3 \\ & & & 1 & -n_4 \\ n_1 & n_2 & n_3 & n_4 & 0 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ \mu \end{pmatrix} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ N \cdot M \end{pmatrix}$

Subtracting from the bottom row, $$n_1$$ times the top row, $$n_2$$ times the second row, and so on (Gaussian elimination by elementary row operations), gives the equivalent triangular system:

$\begin{pmatrix} 1 & & & & -n_1 \\ & 1 & & & -n_2 \\ & & 1 & & -n_3 \\ & & & 1 & -n_4 \\ & & & & N \cdot N \\ \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \\ \mu \end{pmatrix} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ N \cdot (M - X) \end{pmatrix}$

Solving by back substitution, $\mu = \frac{N \cdot (M - X)}{N \cdot N}\quad\quad Y = X + \mu N$

Therefore $d^2 = |Y - X|^2 = |\mu N|^2 = \mu^2 (N \cdot N) = \frac{(N \cdot (M - X))^2}{N \cdot N}$

Checking the result, geometric considerations indicate the line $$XY$$ should be perpendicular to the perpendicular bisector, so vector projection can be used: $Y = X + \frac{(M - X) \cdot N}{N \cdot N} N$ This is the same answer, which is good. The dance with Lagrange multipliers may be more useful in other circumstances.