Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\in\mathbb{R}^n$ to minimize: $$(y-\alpha)^\top (y-\alpha) + \tau \beta^\top \beta$$ subject to the constraints that: $$z=X\beta$$ $$\beta^\top 1_n = 1$$ $$\beta\ge 0$$ $$\forall i,j\in\{1,\dots,m\}, z_i\le z_j \rightarrow \alpha_i \le \alpha_j$$
(Here $1_n\in\mathbb{R}^n$ is a vector of ones.)
The final constraint is equivalent to:
$$\forall i,j\in\{1,\dots,m\}, (z_j-z_i,\alpha_j-\alpha_i)\in\left\{(c,d)\in\mathbb{R}^2\middle|c\le 0 \vee d\ge 0\right\},$$
which is clearly non-convex. While the problem can be given a mixed integer quadratic programming formulation, this is unlikely to be computationally feasible.
However, if we knew $z=\hat z$, Problem 1 reduces to:
Problem 2
Choose $\alpha\in\mathbb{R}^m$ to minimize: $$(y-\alpha)^\top (y-\alpha)$$ subject to the constraints that: $$\forall i,j\in\{1,\dots,m\}, \hat z_i\le \hat z_j \rightarrow \alpha_i \le \alpha_j$$
This is the isotonic regression problem, and may be solved very efficiently by the pooled adjacent violators algorithm.
Likewise, if we knew $\alpha=\hat\alpha$, then Problem 1 reduces to:
Problem 3
Choose $z\in\mathbb{R}^m,\beta\in\mathbb{R}^n$ to minimize: $$\beta^\top \beta$$ subject to the constraints that: $$z=X\beta$$ $$\beta^\top 1_n = 1$$ $$\beta\ge 0$$ $$\forall i,j\in\{1,\dots,m\}, \hat\alpha_i > \hat\alpha_j \rightarrow z_i > z_j$$
This is a simple quadratic programming problem (at least once the strict inequality on $z$ is replaced by a weak one with a small margin).
Question
My question is whether Problem 2 or Problem 3 can be exploited to give a computationally feasible (iterative?) algorithm for Problem 1. I would of course also be interested in any other approach to efficiently solving Problem 1.
Note that the naïve algorithm of alternating between solving Problem 2 and solving Problem 3 cannot possibly converge to a solution of Problem 1, as neither Problem 2 nor 3 depend on $\tau$.
