(Iterative?) Solutions to a certain quadratic program with non-convex constraints

Question

Let $yinmathbb{R}^m$, $tauinmathbb{R}$ and $Xinmathbb{R}^{mtimes n}$, with $tau>0$
I would like to efficiently solve the following problem:

Problem 1
Choose $alpha,zinmathbb{R}^m,betainmathbb{R}^n$ to minimize:
$$(y-alpha)^top (y-alpha) + tau beta^top beta$$
subject to the constraints that:
$$z=Xbeta$$
$$beta^top 1_n = 1$$
$$betage 0$$
$$forall i,jin{1,dots,m}, z_ile z_j rightarrow alpha_i le alpha_j$$

(Here $1_ninmathbb{R}^n$ is a vector of ones.)
The final constraint is equivalent to:
$$forall i,jin{1,dots,m}, (z_j-z_i,alpha_j-alpha_i)inleft{(c,d)inmathbb{R}^2middle|cle 0 vee dge 0right},$$
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 $alphainmathbb{R}^m$ to minimize:
$$(y-alpha)^top (y-alpha)$$
subject to the constraints that:
$$forall i,jin{1,dots,m}, hat z_ile 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=hatalpha$, then Problem 1 reduces to:

Problem 3
Choose $zinmathbb{R}^m,betainmathbb{R}^n$ to minimize:
$$beta^top beta$$
subject to the constraints that:
$$z=Xbeta$$
$$beta^top 1_n = 1$$
$$betage 0$$
$$forall i,jin{1,dots,m}, hatalpha_i > hatalpha_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$.

Nikos Kazazakis · Answer

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.

prubin · Answer

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.

Fix the order of $alpha$ based on the order of $y$ rather than $z$. Solve the resulting QP and check whether the $zrightarrow 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.
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$.
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.

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

Problem 1

Problem 2

Problem 3

Question

2 Answers

Add your own answers!

Ask a Question