This paper considers the problem of optimizing a Schur-convex objective under a linearly shifted, or skewed, majorization constraint. Similar to the case with a regular majorization constraint, the solution is found to be the same for the entire class of cost functions. Furthermore, it is shown that the problem is equivalent to identifying the convex hull under a simple polygon defined by the constraint parameters. This leads to an algorithm that produces the exact optimum with linear computational complexity. As an application, we present a novel precoder design for a multi-input multi-output communication system with heterogeneous signal constellations utilizing decision feedback detection at the receiver.