5
$\begingroup$

Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product

$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$

where $P$ is a point on the circle and $d$ are distances between points.

Now, every point $D$ in the interior of the circle can be written as a convex combination of points $D_i$ on the circle:

$$D = d_1 D_1 + d_2 D_2 + d_3 D_3$$ where each $d_i > 0$ and $d_1+d_2+d_3=1$. Then we define $F$ as

$$F(D) = d_1 f(D_1) + d_2 f(D_2) + d_3 f(D_3).$$

A simple visualization of the problem.

The problem I am interested in is: find the choice of points $\{D_1,D_2,D_3\}$ which minimizes $F$ for a given $D$.

However, since the optimization is performed over all possible choices of $\{D_1,D_2,D_3\}$, it is in general very difficult. Could this perhaps correspond to a more manageable optimization problem that can be computed?

Note that if one was to remove the restriction that points $D_i$ lie on the circle and define $f$ in the same way for every point in the interior, the minimization problem would correspond exactly to finding the convex hull (convex envelope) of the function $f$. This would provide a lower bound for the original problem, but I am not sure if the computation of this quantity is in any way easier.

I would appreciate any pointers with regards to computing the minimum.

$\endgroup$
  • $\begingroup$ I take it you don't want $D_2=D_3$? I'm asking because you don't need the triangle to describe every point in the interior. $\endgroup$ – Raphael Nov 7 '16 at 12:08
  • $\begingroup$ @Raphael I believe you actually need three points in general because the function $F$ is defined on the whole interior of the circle and has a higher dimension. $\endgroup$ – Drew Nov 7 '16 at 12:16
  • $\begingroup$ $F$ seems to be well-defined if two of the points (or even all of the points) are equal. Since every point can be described as a linear combination of two points on the circle, I don't get why you'd need three here. $\endgroup$ – Raphael Nov 7 '16 at 12:23
  • 1
    $\begingroup$ @Raphael It is well defined, but in general you might need three points to obtain the minimal value of F. This definitely holds for problem of finding the convex hull of F, where you need $n+1$ points in $n$ dimensions (following standard definitions), and this problem is related. $\endgroup$ – Drew Nov 7 '16 at 12:32
4
$\begingroup$

A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms.

In particular, define parameters $\theta_1,\theta_2,\theta_3$, representing the angle from the horizontal of $D_1,D_2,D_3$, respectively. Here each $\theta_i$ is in the range $[0,2\pi)$. The locations of $D_1,D_2,D_3$ are completely determined by the value of $\theta_1,\theta_2,\theta_3$. Therefore, we can express the value of $F$ as a function of $\theta_1,\theta_2,\theta_3$: let's write this as $F^*(\theta_1,\theta_2,\theta_3)$. It's tedious but not too hard to write down an explicit expression for $F^*$.

The problem becomes: given an expression for $F^*$, find $\theta_1,\theta_2,\theta_3$ that maximize $F^*(\theta_1,\theta_2,\theta_3)$, subject to $0 \le \theta_1,\theta_2,\theta_3 < 2\pi$. This is a mathematical optimization problem on a three-dimensional objective function $F^* : [0,2\pi)^3 \to \mathbb{R}_{\ge 0}$. There are standard algorithms for maximizing such a function, e.g., using gradient descent or any number of other methods. You can try applying any of them.

In practice, I suggest you run gradient descent, starting from an initial point (an initial assignment to $\theta_1,\theta_2,\theta_3$) chosen at random. Run gradient descent until convergence. This will give you a local maximum. Repeat this 1000 times, with 1000 different randomly chosen starting values, and take the best solution found in any of these iterations. While there are no guarantees, I expect this to work well. Generally speaking, these methods tend to work very well when the number of dimensions is small, and in this case, you have only 3 variables and 3 dimensions, so I expect they'll work well. In particular, I expect the function $F^*$ to be piecewise smooth, with only a small finite number of pieces, so this procedure will probably ensure that you have at least one starting point in each piece and thus that gradient descent finds the maximum within each piece, ensuring that you find the global maximum with high probability.

If you wanted to do a more careful analysis, you could probably work out analytically the boundaries of each piece (i.e., decompose the three-dimensional space $[0,2\pi)^3$ into a finite union of regions within which $F^*$ is continuous and differentiable) and then run one iteration of gradient descent per piece. However, that sounds tedious, and it's probably easier to just slam the thing into an off-the-shelf optimization tool and let the computer do the grunt work for you. Doing the delicate analysis might be important if you want a procedure that is guaranteed correct in all cases (e.g., long and skinny triangles, etc.), but if you just want something that'll probably work without working too hard, I suggest you spare yourself the headache and let the computer do the crunching.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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