Optimizing an expression containing sum of square roots of squared terms

Question

For optimization problems involving square root, it is common to optimize the squared expression instead of that containing the square root. What if we have sum of squared expressions ?

Consider the following figure which shows distances from two fixed points $H,Q$ to a variable point $X$;$O$ is the origin:

The objective is to find $x$ which minimizes the distance $\alpha HX +\beta XQ$ , i.e. minimize

$S(x) = \alpha \sqrt{h^2+x^2} + \beta \sqrt{(p-x)^2 + q^2}$

The usual method of finding the optimal x by setting the derivative to $0$ results in a hideous fourth-order quartic.

It feels like this can be solved for a unique $x$ but I am at a loss trying to solve this. Any suggestions ?

Answer 1

I do not see an "hideous fourth-order quartic" anywhere. If $$S(x) = \sqrt{h^2+x^2} + \sqrt{(p-x)^2 + q^2}$$ $$S'(x)=\frac{x}{\sqrt{h^2+x^2}}-\frac{p-x}{\sqrt{(p-x)^2+q^2}}$$ So, for $S'(x)=0$,$$\frac{x}{p-x}=\frac{\sqrt{h^2+x^2}}{\sqrt{(p-x)^2+q^2}}$$ Square both sides, reduce to same denominator, expand and simplify; you should arrive to $$-h^2 p^2+2 h^2 p x+x^2 \left(q^2-h^2\right)=0$$

Added after the introduction of the weights.

Since now $$S(x) = \alpha \sqrt{h^2+x^2} + \beta \sqrt{(p-x)^2 + q^2}$$ I should try to find any analytical solution and use numerical methods instead. You then look for the zero of $$S'(x)=\frac{\alpha x}{\sqrt{h^2+x^2}}-\frac{\beta (p-x)}{\sqrt{(p-x)^2+q^2}}$$ in the range $0 \leq x \leq p$. For that I would suggest a combination of Newton and bisection steps (see for example subroutine RTSAFE in "Numerical recipes"). You have $$S''(x)=\frac{\alpha h^2}{\left(h^2+x^2\right)^{3/2}}+\frac{\beta q^2}{\left((p-x)^2+q^2\right)^{3/2}}$$

If you want to simply use Newton, you should notice that $$S'(0)= -\frac{\beta p}{\sqrt{p^2+q^2}} <0$$ $$S''(0)=\frac{\alpha }{\sqrt{h^2}}+\frac{\beta q^2}{\left(p^2+q^2\right)^{3/2}}>0$$ $$S'(p)=\frac{\alpha p}{\sqrt{h^2+p^2}}>0$$ $$S''(p)=\frac{\alpha h^2}{\left(h^2+p^2\right)^{3/2}}+\frac{\beta }{\sqrt{q^2}}>0$$ So, starting iterating at $x_0=p$ should lead to solution without any overshoot of it.

Answer 2

In this case it's probably easier to just minimize $ S $ by differentiation rather than the squared expression. Differentiating, we get

$$ S'(x) = \frac{x}{\sqrt{h^2 + x^2}} - \frac{p-x}{\sqrt{(p-x)^2 + q^2}} $$

Setting the derivative equal to $ 0 $, we get

$$ \frac{p-x}{\sqrt{(p-x)^2 + q^2}} = \frac{x}{\sqrt{h^2 + x^2}} $$

The most elegant solution at this point is probably recognizing this equation as a statement about angles. As such we see that the solution is the solution to

$$ \frac{p-x}{q} = \frac{x}{h} $$ $$ \implies x = \frac{p}{1 + \frac{q}{h}} $$

Answer 3

Regarding your general question: it's entirely reasonable to minimize convex functions involving the sum of the root of the sum of squares :-) It is convex, but as you rightly point out, it's often not differentiable.

Don't get hung up on the need for an analytic solution. Within the set of useful, practical optimization problems, the subset that admit analytic solutions is truly miniscule. There's nothing wrong with applying an iterative, numerical method to solve this problem.

For your particular problem, a variety of numerical approaches will work, in part because your problem is univariate and differentiable over the domain of potential solutions ($0\leq x\leq p$). I recommended bisection in the comment; Claude recommended a combination of Newton and bisection steps. I argue that bisection alone is superior simply for reasons of personal convenience: it's easier to compute one derivative than two :-) The fastest approach for the computer might be the slowest for you if it takes longer to code up.

If you're using MATLAB, and you happened to already have a convex optimization modeling framework like YALMIP or my software CVX installed, you could simply type the model in as follows (for CVX):

cvx_begin
    variable x
    minimize( alpha * norm([h,x]) + beta * norm([p-x,q]) )
cvx_end

What's funny though is that CVX & YALMIP will transform your problem into a constrained optimization problem---specifically, a second-order cone program like this:

\begin{array}{ll} \text{minimize} & \alpha t_1 + \beta t_2 \\ \text{subject to} & \| \begin{bmatrix} h & x \end{bmatrix} \|_2 \leq t_1 \\ & \| \begin{bmatrix} p - x & q \end{bmatrix} \|_2 \leq t_2 \end{array}

These systems will then apply an interior-point method to this transformed problem. Now, is that overkill? I suppose; it will certainly take more floating-point operations to arrive at a good result than a custom coded unconstrained algorithm. And yet, from your human perspective, it would be done in no time at all, so who cares?

Answer 4

This is the famous refraction problem for the minimum-time path followed by light in refraction.

The governing equation is known as Snell's law.

In the notation used above, the solution is

$$ \frac {\sin(\theta_1)}{\sin\left(\theta_2\right)} = \frac{\beta}{\alpha} $$

where $ \theta_1 = OHX$ and $\theta_2 = PQX$; and $1/\alpha$, $1/\beta$ can be thought of as corresponding velocities above and below the line $OP$.