Parametric constrained optimization

Question

I'd like to find a way of determining if the distance from the origin of a parametric parabolic path falls below a certain value within a given range of the parameter. The parabola is expressed as:

$$x = a_xt^2+b_xt+c_x$$ $$y = a_yt^2+b_yt+c_y$$

So I'm looking for $x^2+y^2=d^2$ for $t_1 \leq t \leq t_2$.

Obviously I can plug in the first $2$ equations into the third, solve the quartic and test if any of the four solutions for $t$ lies within the range, but I would like to see if there is a faster test for this. My idea is to formulate it as a constrained optimization problem with constraints $x^2+y^2-d^2=0$, $-t \leq t_1$ and $t \leq t_2$ but I'm not sure how to proceed. I don't need the to know the exact minimum point, just whether the distance falls below $d$ with the range.

Am I on the wrong path?

Thanks.

Answer 1

I don't know whether this is faster, but here is a way to solve it as an "optimization" problem.

I first show how to formulate an optimization problem to determine the minimum distance. I then show how to instead formulate it as a feasibility problem, which may execute faster. In all cases, global optimization is used.

Minimize $x^2+y^2$ with respect to $t$ subject to $t_1 \le t \le t_2$

However, if you, only care whether the minimum distance falls below a threshold $d$, but not by how much, you can formulate the feasibility problem:

Minimize $0$ with respect to $t$, subject to $x^2+y^2 - d^2 \le 0, t_1 \le t \le t_2$. The problem will either be reported feasible or infeasible.

Here is sample YALMIP code (running under MATLAB) using the BARON global solver (free demo mode of BARON is sufficient given the small size of the problem):

t = sdpvar;
x = t^2 + t + 1;
y = 2*t^2 + t + 2;
% Minimum distance determination version
optimize(1<=t<=2,x^2+y^2,sdpsettings('solver','baron'))

which reports optimal objective value of 34, which is the minimum distance

% Feasibility version. [] is used instead of 0 for the objective, which accomplishes the same thing
optimize([1<=t<=2,x^2+y^2-33<=0],[],sdpsettings('solver','baron'))

with the result that the problem is reported infeasible. If 35 is used instead of 33, a solution is reported, i.e., the problem is feasible.