# （迭代式？）具有非凸約束的二次方程的解

$$y \ in \ mathbb {R} ^ m$$$$\ tau \ in \ mathbb {R}$$$$X \ in \ mathbb {R} ^ {m \ times n}$$，帶有$$\ tau> 0$$

### 問題1

（這裡$$1_n \ in \ mathbb {R} ^ n$$是1的向量。）

$$\ 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 \}，$$

### 問題

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.

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.