Implement ellipsoid.intersectTightIa method that builds a series of tight internal approximations based on Andrew Vazhentsev's thesis

[pgagarinov]

Deadline is the end of this semester

Here is the thesis: https://drive.google.com/open?id=0B5OqL4IVOIC8SnlFeGVPVjNfdzA

1. Read the thesis first
2. Suggest a sensible way of parameterization
3. Implement the method
4. Cover this method with tests in 2d and 3d space
5. Write a demo that demonstrates this method at work in 2d and 3d space products\elltoolboxcore\demo subfolder.
6. Write a few tests for higher-dimensional ellipsoids.

More details will follow.

[talking-quant]

But there's https://drive.google.com/open?id=0B5OqL4IVOIC8LVFzLVRzNGZHbHc no Vazhentsev's thesis.

[pgagarinov]

Fixed, please use the updated link.

[talking-quant]

Hello,

I have to implement method from Ch.1 or Ch.3?

[pgagarinov]

Ch2 and ch3 for an arbitrary pair of ellipsoids.

[talking-quant]

Hello.

I have some problems with a parametrization. I don't really understand how to sort out matrices G, L and T for method in Th. 3.3 (page 104). G have n by n, L have (n-m-p) by m, T have m by p numbers to sort out.

And moreover, for method in Th. 3.4 I have to sort out matrices G, L, T and 3-dim vector. And for any 3-dim vector I have to generate new matrices.

[talking-quant]

I realized that matrice G fixed, but still I have to sort out L and T. I have constraint for T, but no constraints for L and every element of L can take values from -infty to +infty.

[pgagarinov]

I contacted Andrew Vazhentsev and asked him to help you with your question directly on GitHub (he has the link to this issue so no worries). He is on a business trip right now but promised to take a look on Saturday this week. If he doesn't help - I'll do it by myself but let us hope he does because if the thesis doesn't explain this stuff he is the only one who can read between the lines. Meanwhile please try to figure out the answer all by yourself - there is always a chance you missed something and L and T are not that arbitrary as you think. Just keep trying. Thanks.

[pgagarinov]

We need to start with a polar transformation and making matrices of both ellipsoids diagonal. Then I suggest we parameterize matrices T_T'<E from section 3.2 as T= D_O, where O is orthogonal and D is diagonal with elements from [0,1). Then we need to see if it is empirically sufficient to consider only such matrices O(v) that transfrom e_1 into an arbitray v via function gras.la.orthtransl. Thus, in R^n fixing T will require fixing diagonal elements of D and vector v, 2*m numbers in total, m<=n-1.

[talking-quant]

Hello.

I have a problem with minimizing and maximizing this function: dot(x, Q1 * x) / dot(x, Q2 * x) with constraint dot(x, z) = 0, where Q1 = Q1' > 0, Q2 = Q2' > 0 and z = const.

Cvx can't minimize such things, I tried gradient descent method with penalty function, but it doesn't work.

Could you give an advice how to find extremums of this finction?

[pgagarinov]

We can assume that Q2=I which makes this a problem of maximizing a quadratic form on a unit sphere under an orthogonality constraint. This problem is well known - see section 2.2 in

http://people.hss.caltech.edu/~kcb/Notes/QuadraticForms.pdf