Isotonic regression with a linear constraint I'm trying to find a direct approach to solving (for some fixed vector $y$):
$$
\begin{aligned}
    \min & \; \|x - y \|^2 \\
    \mbox{s.t. } & \alpha^\top x \leq 0 \\
         & x_i \geq x_j, \; \forall i \geq j \\ & x \geq 0.
\end{aligned}
$$
Had we dropped the $ \alpha^\top x \leq 0$ constraint, we would have a standard isotonic regression problem for which an $O(n)$ algorithm exists. Is there a way to solve the problem with the added linear constraint using a direct method (i.e. without resorting to some gradient scheme)?
 A: Not a reference, but I believe it is an answer. I will elaborate on the comment by @gerw, since I believe there are some delicate details which are not immediately seen.
Introducing a Lagrange multiplier $\lambda \geq 0$, and using the square completion trick, we obtain
$$
L(x, \lambda) = \|x - y\|^2 + (\lambda a)^T x
 = \|x - (y - 0.5 \lambda a) \|^2 + \lambda a^T y - 0.25 \lambda^2 \|a\|^2
$$
The dual function is
$$
q(\lambda) = \underbrace{\min_{x} \{ \|x - (y - 0.5 \lambda a) \|^2 : x \geq 0 ,~ \forall i\geq j ~ x_i\geq x_{j}\}}_{(*)} + \lambda a^T y - 0.25 \lambda^2 \|a\|^2
$$
The minimization problem $(*)$ is an isotonic regression problem. So we can easily evaluate $q(\lambda)$ given $\lambda$, and recover the the corresponding optimal $x^*(\lambda)$. However finding a maximizer of $q$ (or, alternatively, $\lambda$ which ensures that $a^T x^*(\lambda) \leq 0$) requires some work. We know from convex analysis theory that $q(\lambda)$ is concave, the strong duality theorem ensures that it attains its maximum.
First, observe that $(*)$ is a Moreau envelope. It is known that Moreau envelopes are continuously differentiable, and there is an explicit formula for computing their gradient (it includes solving the minimization problem. In your case - the isotonic regression problem $(*)$).  In other words, $q$ is continuously differentiable, and you can compute the derivative $q'$, whose computation requires solving an isotonic regression problem. See the excellent paper titled 'Epigraphical Analysis' by Attouch and Wets.
Since $q$ is concave, we know that the derivative $q'$ is monotone decreasing. Since the domain of $q$ is $[0, \infty)$, its maximum is either attained at $\lambda = 0$, or is a positive number satisfying $q'(\lambda) = 0$. Thus, we obtain the following simple algorithm for solving the problem you described:


*

*Check if $a^T x^*(0) \leq 0$. If so, then $\lambda = 0$ must be the optimal dual, and $x^*(0)$ must be the optimal primal.

*Otherwise, find the smallest $k \in \mathbb{N}$ such that $q'(2^k)$ is negative. Perform a bisection search for solving the equation $q'(\lambda) = 0$ over the interval $(0, 2^k)$. 


Note, that the optimal positive $\lambda$ will indeed satisfy $a^T x^*(\lambda) = 0$, and you can use it as a certificate of optimality. But I do not see a direct method of finding such $\lambda$, except for a bisection search on $q'(\lambda)$.
