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.

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

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.