Calculating the distance function and projection

169 Views Asked by At

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$.

We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ $$\pi(x;\Omega)=\{\omega\in\Omega\mid||x-\omega||=d(x;\Omega)\}$$ Suppose we want to find $d(x;\Omega)$, that is $$d(x;\Omega)=\inf\{||x-\omega||\mid\langle a,\omega\rangle=b\}$$ I used the method of Lagrange coefficients $$f(\omega)=||x-\omega||,\quad g(\omega)=\langle a,\omega\rangle,\quad\nabla f=\lambda\nabla g$$ and obtained that $$\lambda=\sum_{i=1}^n\frac{\omega_i(x_i-\omega_i)}{b||x-\omega||}$$ I replaced $\lambda$ for example to $$\frac{\omega_1-x_1}{||x-\omega||}+\lambda a_1=0$$ to find $\omega_1$ $$\omega_1-x_1+\frac{a_1x_1\omega_1^2}b+\frac{a_1}{b}\sum_{i=2}^n\omega_i(x_i-\omega_i)=0$$

So I couldn't arrive to any thing fun to use it for calculating the projection. This is an elementary exercise in first chapter of mordukhovich's book about convex analysis, so I can't use the advanced methods about it if exists!

1

There are 1 best solutions below

1
On BEST ANSWER

If you're going to apply multivariable calculus tools to the distance function, it's best to use the squared distance function: $$f(\omega)=\|x-\omega\|^2,\quad g(\omega)=\langle a,\omega\rangle$$ The minimum is attained in the same place, but this $f$ expands as inner product, allowing for simpler computations: $\nabla f(\omega) = 2(\omega-x)$. So, the equation $\nabla f=\lambda\nabla g$ becomes $$ 2(\omega - x) = \lambda a $$ From here you should solve for $\omega$, not for $\lambda$ (because this uses the full vector equation, rather than the 1st component as in your attempt): $$\omega = x+\frac{\lambda}{2}a$$ Plug this into $g(\omega)=b$ to find $\lambda$: $$\left \langle a, x+\frac{\lambda}{2}a \right\rangle = b$$ hence $ \langle a,x\rangle+\frac{\lambda}{2} |a|^2=b$, and the rest is routine.