1
$\begingroup$

I am trying to figure out if the following problem can be formulated using linear or quadratic programming: consider a set of $n$ normalized vectors $V = \{V_1,..,V_n\}$ with $V_i \in \mathbb{R}^d$. The goal is to find (sparse) pair(s) of linear combinations with $a_1V_i + .. + a_lV_l$ and $b_1V_j + .. + b_mV_m$ such that

  1. the linear combinations in each pair are linearly associated/correlated.
  2. the vectors in the first linear combination do not occur in the second linear combination (what I tried to indicate by using $i, l$ and $j, m$ when numbering the vectors in the aforementioned linear combinations. Sorry if this is weird use of notation.)
  3. $l + m < n$ (or $l < n$ and $m < n$), i.e. the linear combinations are sparse/not all vectors in $V$ participate

The values $a_1,..,a_l$ and $b_1,..,b_m$ are coefficients/weights with $a_i, b_i \in [-1,1]$.

My attempt at modeling this problem is to formulate it as an optimization problem and set $a_1V_1 + .. + a_nV_n + r_1 = b_1V_1 + .. + b_nV_n + r_2$, which can be encoded as $d$ linear equality constraints (one for each dimension). Here, $r_1, r_2 \in \mathbb{R}^d$ are vectors that serve as slack variables (i.e. error/residual terms for when the values in the linear combinations of the vectors do not match exactly).

The objective then becomes the minimization of $\sum_{i=1}^d (r_1 + r_2)$. Since the objective and constraints are linear in this case, I can formulate this as a linear programming problem. For obtaining sparse combinations, I can add a regularization term. However, modeling the fact that one vector cannot occur in both linear combinations requires me to introduce a binary variable that sets either $a_i = 0$ or $b_i = 0$. This turns the problem into a mixed-integer LP which works but makes it hard to scale to larger $n$.

I wonder if there's a way to reformulate it as an LP or QP? The problem seems to me close to regression (least absolute deviation for LP formulation, least squares for QP formulation) except that there is no obvious starting $y$.

$\endgroup$
5
  • 1
    $\begingroup$ It's unclear what you mean by requirement 1. What you have actually encoded using the slack variables and objective is that the two sums should be close to each other (in 1-norm), which is not the same as "linearly associated/correlated". (If 10 times the first sum minus 27 times the second sum is zero, the two sums can be called "linearly associated".) $\endgroup$
    – prubin
    Jan 5 '20 at 16:09
  • $\begingroup$ Thank you for your reply. You're right, I forgot to mention that the vectors are normalized beforehand. This should fix the case where the sums are not close (in 1-norm) but are linearly associated, right? Would it also be possible to formulate it using the $L_2$ norm (i.e. like a least squares regression, which would make it a QP problem)? I don't yet see how I could transform the constraints to achieve this without making the constraints quadratic (if that makes sense). Sorry for the immediate follow up question, just excited that I got a response to the question so quickly. $\endgroup$
    – Optimouse
    Jan 5 '20 at 21:23
  • 1
    $\begingroup$ I'm still uncertain what you mean in the first list item "the linear combinations in each pair are linearly associated/correlated", and whether this is a constraint or a goal (objective). $\endgroup$
    – prubin
    Jan 6 '20 at 22:25
  • $\begingroup$ The linear association of the linear combinations ($a_1V_1+..+a_nV_n+r_1$ and $b_1V_1+..+b_nV_n+r_2$) is the goal. But I try to achieve this by setting the optimization objective to minimize the sum of the residual terms $r_1, r_2$ of each linear combinations. My reasoning is then that by minimizing these two values, the linear combinations it finds should be "close" to each other so as to maximize their linear association/correlation. My reason for using the $L_1$ norm is so that I could express it as a linear program. But I want to prevent it to pick the same vector in both linear combi... $\endgroup$
    – Optimouse
    Jan 7 '20 at 12:44
  • $\begingroup$ ...nations. So I don't want it to pick say $V_1$ to end up in both linear combinations (I'm sorry for being unclear in my notation here). I can achieve this by introducing a binary variable that, for every coefficient $a_i, b_i$, sets $a_i = 0$ if $b_i > 0$ or vice-versa. But this turns it into a mixed-integer LP, which makes the optimization slow. So I am wondering if (1) my current way of setting up the optimization makes sense given the goal of making the linear combinations linearly associated/correlated and (2) if I can express this as an LP (or QP, with least squares) instead of an MILP. $\endgroup$
    – Optimouse
    Jan 7 '20 at 12:47
1
$\begingroup$

You cannot model this as an LP or QP with the mutual exclusion provision (item 2) as a hard constraint. Suppose, for instance, that one feasible solution has only a_1 and b_2 positive, and another has only a_2 and b_1 positive. Since the feasible region of an LP or QP is convex, the midpoint of those solutions would also be feasible, and it would have a_1, a_2, b_1 and b_2 all positive.

That leaves the question of whether you could add a term to the objective function to discourage violations of the mutual exclusion rule. I don't see any way to do that, but I don't have a ready proof that it is impossible.

$\endgroup$
6
  • $\begingroup$ Thank you for this explanation and for your patience with my initially unclear question. If I could ask one more thing about an LP proposal for this problem, what if the constraint $a_1V_1+..+a_nV_n + r_1 = b_1V_1+..+b_nV_n + r_2$ would change to just $a_1V_1+..+a_nV_n - r_1 = 0$ with $a_i \in [-1,1]$? Essentially, minimizing just $r_1$ and moving all $b_1V_1,..,b_nV_n$ to the lefthand side? Wouldn’t this achieve the goal in that the (linear combination of) vectors with negative coefficients would be close to the (linear combination of) vectors with positive coefficients while satisfying (2)? $\endgroup$
    – Optimouse
    Jan 8 '20 at 19:56
  • 1
    $\begingroup$ I don't see the b's having moved -- it looks like they disappeared entirely. In any case, changing that constraint will not eliminate the need for binary variables. That need stems from the requirement that not V show up in both sums. $\endgroup$
    – prubin
    Jan 9 '20 at 20:03
  • $\begingroup$ I meant that that original constraint $a_1V_1 + .. + a_nV_n + r_1 = b_1V_1 + .. + b_nV_n + r_2$ (of the form $LHS = RHS$) changes to $a_1V_1 + .. + a_nV_n - r = 0$ with $a_i \in [-1,1]$ and then whatever vectors have $a_i > 0$ will form the lefthand side (LHS) linear combination while the vectors with $a_i < 0$ will form the righthand side (RHS) linear combination. So basically the constraint changes from $LHS = RHS$ to $LHS - RHS = 0$ with a single residual vector $r$. Then any $V_i$ can also only occur once and the LHS lin.comb. and RHS lin.comb. will be linearly associated? $\endgroup$
    – Optimouse
    Jan 9 '20 at 22:09
  • 1
    $\begingroup$ If "linear association" means the two sums are approximately equal, then that seems as though it should work (give or take whether you get sparsity). $\endgroup$
    – prubin
    Jan 11 '20 at 0:52
  • 1
    $\begingroup$ The infeasibility result is perplexing. You might want to try fixing the $a$ and $b$ variables at some arbitrary values (leave the residuals unfixed) and then ask Gurobi to find an irreducible infeasible subset of constraints (i.e., tell you why it thinks the model is infeasible). $\endgroup$
    – prubin
    Jan 12 '20 at 15:39

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.