2
$\begingroup$

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).

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$ such that $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 the maximum 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 unique solution. 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 solution if and only if there is a critical path and a method of finding the exact 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.

$\endgroup$
8
  • 2
    $\begingroup$ "Find the critical path using convex optimization (if it exists)." sure sounds like an exercise from a book to me. $\endgroup$
    – user5810
    Oct 20, 2010 at 1:22
  • $\begingroup$ Try posting your question on math.stackexchange.com. $\endgroup$ Oct 20, 2010 at 2:58
  • $\begingroup$ or on cstheory.stackexchange.com $\endgroup$ Oct 20, 2010 at 4:48
  • $\begingroup$ @ricky ha, maybe i should write one then. I will try those others, not sure what they are. $\endgroup$ Oct 20, 2010 at 16:44
  • 1
    $\begingroup$ @Alejandro: This forum is dedicated to research-level questions in mathematics. I think you have an interesting question, but I'm not sure it's at research level. The other two sites mentioned are more appropriate for the level of your question. $\endgroup$ Oct 20, 2010 at 20:31

2 Answers 2

1
$\begingroup$

Hi, I'm a coauthor of the paper. This problem is just a bit out of our usual research topic. This indeed does not seem too hard, but we do not quite have the confidence to state outright that "this is trivial", and move along. If it is, then researchers more expert than we are in such questions might be able to tell us. If it is not, then this is the right place to ask...

$\endgroup$
0
$\begingroup$

After solving your first SOCP, you can solve another program which minimizes the sum of length of the edges. The second time the edge lengths are not constrained to be equal, but instead constrained to be less than of equal to the optimal $z$ of the first program.

$\endgroup$
1
  • $\begingroup$ ah yes, that is useful because we don't have to check uniqueness of the first solution. Suppose the result of the second program confirms that there is a critical path (by showing that the minimum sum is (m-1)z where m-1 is the number of edges, then I would like to show that the solutions to both programs (they should be the same) are unique. Are there some uniqueness results for SOCPs that would help me here? You implicitly agree that the program I wrote down is an SOCP then? $\endgroup$ Oct 21, 2010 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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