3 added clarification and a step in the right direction; added 25 characters in body

I have a formulation of the above as what appears to be a second-order cone problem (as far as I understand).

The segment $E_i$ can be described as $E_i = {(x,a_ix+b_i): x_{l,i} \le x \le x_{r,i}}$ and the length of the edge $e_i$ is the distance between points $p_i$and $p_{i+1}$. Here $p_i = (x_i, a_ix_i+b_i)$ for some choice of $x_i$ suchthat $x_{l,i} \le x_i \le x_{r,i}$, so $|e_i|_2^2 = (x_i-x_{i+1})^2 + (a_ix_i+b_i - a_{i+1}x_{i+1}-b_{i+1})^2$

We can use the following second-order cone problem (or is that what it is?) to minimize themaximum length edge among all paths with points on the sequence $E$,

$\min z$

such that

$|e_i|_2 \le z, 1\le i \le m-1$

$x_{l,i} \le x \le x_{r,k}, 1 \le i \le m$

If there is a critical path on $E$, this problem has a uniquesolution. Otherwise it does not have a unique solution. But how do we prove this?

What we would like is a problem which has a provably unique solutionif and only if there is a critical path and a method of finding theexact solution.

Please understand that this problem was misinterpreted in the comments below, that it is a research problem, and any useful answers posted here will be properly cited.

2 added 5 characters in body

I want to us convex optimization to describe a problem in computational geometry.

Let $E = (E_1, E_2,\ldots , E_m)$ be a sequence of line segments in the plane, where $E_1$ and $E_m$ may be points and the rest are non-degenerate segments. A critical path on $E$ is a selection of points $(p_1,p_2,\cdots ,p_m)$ with $p_i\in E_i$ with edges $e_i=(p_i,p_{i+1})$ such that (1) all $e_i$ has the same length $l$ and (2) no other selection of points results in a path with edges that are not longer than $l$ and some that are shorter.

Find the critical path using convex optimization (if it exists). Can you use the convex optimization problem to show that the solution is unique (in certain cases)? Can you find exact locations for the points $p_i$ in polynomial time?

I have the impression that this is an elementary convex optimization problem, where points are restricted to segments, edge lengths must be minimized, and then check that the lengths are all the same (for existence).

1

# formulate edge length problem as convex optimization problem

I want to us convex optimization to describe a problem in computational geometry.

Let $E = (E_1, E_2,\ldots , E_m)$ be a sequence of segments in the plane, where $E_1$ and $E_m$ may be points and the rest are non-degenerate segments. A critical path on $E$ is a selection of points $(p_1,p_2,\cdots ,p_m)$ with $p_i\in E_i$ with edges $e_i=(p_i,p_{i+1})$ such that (1) all $e_i$ has the same length $l$ and (2) no other selection of points results in a path with edges that are not longer than $l$ and some that are shorter.

Find the critical path using convex optimization (if it exists). Can you use the convex optimization problem to show that the solution is unique (in certain cases)? Can you find exact locations for the points $p_i$ in polynomial time?

I have the impression that this is an elementary convex optimization problem, where points are restricted to segments, edge lengths must be minimized, and then check that the lengths are all the same (for existence).