2
$\begingroup$

My goal is to maximize an objective function using coordinate descent over a 3-dimensional vector. In the simple case the domain over which I am maximizing is defined as follows:

$X \in \mathcal{X}$ where $\mathcal{X} = \{X | X\in \mathbb{R}^3,X_{lb} < X < X_{ub}\}$, where $X_{lb}$ and $X_{ub}$ are known quantities. This is geometrically a cuboid. Here, I am able to fix a coordinate at a time, optimize and then move to the other coordinate and repeat the process till convergence (i.e. use coordinate descent).

In the more complicated case, I am projecting the space $\mathcal{X}$, using a projection matrix $Q$. The matrix $Q$ has two eigenvalues that equal 1 and one eigenvalue that equals 0. In other words, it reduces the cube to a 2-dimensional object in $\mathbb{R}^3$. This object typically has 6 corners and looks like a tilted imperfect hexagon in 3-d space. In other words, I want to optimize over the following domain:

$X \in \mathcal{\hat{X}}$ where $\mathcal{\hat{X}} = \{QX | X\in \mathbb{R}^3,X_{lb} < X < X_{ub}\}$

We know that the 2-d object can be represented by a linear combination of the eigenvectors, where the $v$ denotes the vectors and $c$ denotes the coefficients:

$c_1$ $v_1$ + $c_2$ $v_2$

Since I know $Q$, I know $v_1$ and $v_2$. I want to apply coordinate descent on this space, which should be equivalent to treating $c_1$ and $c_2$ as the new coordinates and optimizing over them, one by one.

The problem is that given that the shape is irregular and looks like a hexagon, as I vary $c_2$, the range for $c_1$ varies and vice versa. In other words, the upper and lower bound for $c_1$ is a function of $c_2$ and vice versa. To employ coordinate descent, I will have to account for the changing bounds.

How do I compute the function that maps $c_2$ to the upper and lower bounds on $c_1$ and the function that maps $c_1$ to the upper and lower bounds on $c_2$? Further, how do I find the overall range for $c_1$ and $c_2$, which must exist, since the original object is a cuboid?

Edit: Something that I am trying to do is rotating this tilted hexagon onto a flat surface in $\mathbb{R}^3$ and then using a linear program to try and figure out the bounds. But, I am having a hard time finding the correct transformation to do the rotation. I need the flat surface to figure out the correct bounds and implement coordinate descent, I think.

$\endgroup$
  • $\begingroup$ You know the domain is the projection of a cuboid. Why not use three "virtual" coordinates representing the original unflat cuboid $Y=(y_1,y_2,y_3)$, and maximize for $ f(QY) $ Then your answer is $QY$. You have more coordinates to go over (3 instead of 2), but the advantage is you already understand the boundary geometry. You don't have to work in the projected co-domain if you can pullback the problem into a nice cuboid domain. $\endgroup$ – user3257842 Mar 21 at 22:03
  • 1
    $\begingroup$ @user3257842 Sorry, I am confused. How can I pull it back to the cuboid domain? What is the object Y in my notation? Is it $\mathcal{X}$? $\endgroup$ – user52932 Mar 22 at 21:15
  • $\begingroup$ Sorry for being obscure. I've re-read your post. You've said the problem appears when you use $\mathcal{\hat{X}} = Q[\mathcal{X}]$ . So why not work with coordinates in $\mathcal{X}$ ? You need to define $f^{*}(a) = f(Qa)$, where $f$ is your original function. Then do descent for $f^{*}$ over $\mathcal{X}$. Then apply $Q$ to the result. Since you maximize $f^{*} = f \circ Q$ for $X\in \mathcal{X}$, you also maximize $f$ for $Q(X)\in Q[\mathcal{X}] = \mathcal{\hat{X}}$ . $\endgroup$ – user3257842 Mar 23 at 8:02

Your Answer

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

Browse other questions tagged or ask your own question.