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

## This question had a bounty worth +50 reputation from user52932 that ended 8 hours ago. Grace period ends in 15 hours

This question has not received enough attention.

• 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 16 hours ago