# Using Coordinate Descent on Projected Space

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.

• 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. – user3257842 Mar 21 at 22:03
• @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}$? – user52932 Mar 22 at 21:15
• 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}}$ . – user3257842 Mar 23 at 8:02