(迭代式?)具有非凸約束的二次方程的解


8

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

我想有效地解決以下問題:


問題1

選擇 $ \ alpha,z \ in \ mathbb {R} ^ m,\ beta \ in \ mathbb {R} ^ n $ 以最小化: $$(y- \ alpha)^ \ top(y- \ alpha)+ \ tau \ beta ^ \ top \ beta $$ 受到以下約束: $$ 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 $$


(這裡 $ 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 \},$$

這顯然是非凸的。儘管可以為問題提供混合整數二次規劃公式,但這在計算上不太可行。

但是,如果我們知道 $ z = \ hat z $ ,問題1就會減少為:


問題2

選擇 $ \ alpha \ in \ mathbb {R} ^ m $ 以最小化: $$(y- \ alpha)^ \ top(y- \ alpha)$$ 受到以下約束: $$ \ forall i,j \ in \ {1,\ dots,m \},​​\ hat z_i \ le \ hat z_j \ rightarrow \ alpha_i \ le \ alpha_j $$


這是等滲回歸問題,可以通過合併的相鄰違規者算法非常有效地解決。

同樣,如果我們知道 $ \ alpha = \ hat \ alpha $ ,那麼問題1會簡化為:


問題3

選擇 $ z \ in \ mathbb {R} ^ m,\ beta \ in \ mathbb {R} ^ n $ 以最小化: $$ \ beta ^ \ top \ beta $$ 受到以下約束: $$ 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 $$


這是一個簡單的二次編程問題(至少將 $ z $ 上的嚴格不等式替換為一個具有較小邊際的弱不等式)。

問題

我的問題是,是否可以利用問題2或問題3為問題1提供計算上可行的(迭代?)算法。我當然也對有效解決問題1的任何其他方法感興趣。

請注意,解決問題2和解決問題3之間交替的樸素算法不可能收斂到問題1的解決方案,因為問題2和3都不依賴於 $ \ tau $

2

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.

2

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.