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


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

  • $\begingroup$ Originally posted on MO here: mathoverflow.net/questions/364943/… Posted here after a suggestion from a commentator there. $\endgroup$ – cfp Jul 8 '20 at 11:18
  • $\begingroup$ You speculated that a MIQP would not be computationally feasible. How large is your sample size? Also, are you open to heuristic solutions? $\endgroup$ – prubin Jul 13 '20 at 20:09
  • $\begingroup$ Problem size varies, m up to 1000 or so, n up to 400. The difficult is that you need O(m^2) binary variables I think. I'm definitely open to heuristic solutions. I'm currently smoothing the isotonic regression output, and then using a nonlinear optimisation routine re-solving the smoothed isotonic regression problem on each iteration. $\endgroup$ – cfp Jul 13 '20 at 20:20
  • $\begingroup$ @cfp I'm not familiar with your notation, what would your final constraint look like? $\endgroup$ – Nikos Kazazakis Jul 14 '20 at 17:49
  • $\begingroup$ What's unclear? The notation is standard. It means "for all i and j both between 1 and m, if z_i is less or equal to z_j, then alpha_i is less of equal to alpha_j" . $\endgroup$ – cfp Jul 14 '20 at 19:26

I'm shooting from the hip here (meaning none of the following ideas are tested), but a few different possibilities for heuristics come to mind.

  1. Fix the order of $\alpha$ based on the order of $y$ rather than $z$. Solve the resulting QP and check whether the $z\rightarrow \alpha$ ordering condition is violated. If so, solve your problem 2 using the $\hat{z}$ obtained from the first problem, and solve your problem 3 using the $\hat{\alpha}$ from the first problem. Go with the better of those two solutions.
  2. Using binary variables to enforce the order constraints, solve the MILQP on appropriate size subsets of the data (small enough that the MILQP solves "quickly"). Average the resulting $\beta$ vectors, use them to generate $z$, the solve problem 2 for $\alpha$ based on the "consensus" $z$.
  3. There is a "random key" variant of genetic algorithms suitable for sequencing problems. You could try it. Each member of the population would be a vector of $m$ random keys, used to dictate the sort order of both $\alpha$ and $z$. The fitness function would be the solution of the QP given a particular sort order. You could cache the fitness values, so that you would not have to repeat QPs, but it would still entail solving a boat-load of QPs.
  • $\begingroup$ Some neat ideas here! A few comments on each follow. $\endgroup$ – cfp Jul 15 '20 at 11:18
  • $\begingroup$ On 1) I'm not sure I understand this. With the order of alpha based on the order of y, alpha is given by the solution to Problem 2, and the optimal beta is a vector of repeated 1/n, as without the order condition, there's no constraint on z. $\endgroup$ – cfp Jul 15 '20 at 11:18
  • $\begingroup$ On 2) Could be promising! My worry is that with n not that much smaller than m, the smaller problems will all overfit (at least given tau optimal for the original problem), meaning that the betas will have high variance across subsets, and will not average to anything reasonable. $\endgroup$ – cfp Jul 15 '20 at 11:19
  • $\begingroup$ On 3) This sounds like a great approach to obtaining high quality solutions. But is probably on the wrong side of the time vs quality divide for my purposes. (This entire problem has to be solved many times.) $\endgroup$ – cfp Jul 15 '20 at 11:20
  • $\begingroup$ Regarding 1), sorry, I omitted something. The QP would contain an order condition on $z$, based on the contrapositive of the original requirement: $\alpha_i > \alpha_j \rightarrow z_i > z_j$. Since strict inequalities are taboo, you would have to settle for weak inequalities or change $a > b$ to $a \ge b + \epsilon$ for some positive $\epsilon$. $\endgroup$ – prubin Jul 16 '20 at 15:35

Although it might be possible to prove that you can obtain a convergent algorithm by alternating between the two problems, intuitively it seems unlikely to achieve constraint satisfaction with certainty. For guaranteed convergence, this is a problem that would typically be solved using continuous branch-and-bound. If you are a student/academic, you can test this with our Octeract Engine which is free for non-commercial use.

That being said, a way to exploit the formulations algorithmically would be to warm-start the solution of Problem 1 with a feasible solution to either Problem 2 or Problem 3. This would start the algorithm at a point where a subset of the constraints is already satisfied.

You can experiment with either, but I suspect that the best way to go about it would be to solve Problem 2 first, which would give you a feasible point to the non-convex sub-problem. It should then be much easier to obtain a solution that satisfies the remaining constraints.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.