3
$\begingroup$

I have a matrix in the size of $S \in \mathbb{R}^{M\times N}$ with only binary values $0..1$.

I want to select $m<M$ rows from $S$ and sum the $m$ rows to get a new vector $v$.

I wish $v$ to be close to the uniform distribution. Currently, I am thinking of normalizing $v$ and maximize the entropy of the $v$.

For example, the matrix $S$ is like:

[[0,1,1,1,0],
[1,0,0,0,1],
[1,1,1,1,1],
[0,1,1,0,0]]

I want to select 2 rows from $S$. Say I selected first and second rows and the summation of the two rows is: [1,1,1,1,1]. And I normalize $v$ into [0.2,0.2,0.2,0.2,0.2], which is closest to the uniform distribution compared with other combinations.

But I don't know how to formulate this question into the standard mixed-integer linear program form. Thank you if anyone can give some insights.enter image description here

$\endgroup$
4
$\begingroup$

Let $x_1,\dots,x_M$ be binary variables, and let $y_1,\dots,y_N$, $z$ and $w$ be general (nonnegative) variables. (They will all turn out to be integers, but you do not need to declare them as integers.) Consider the following constraint set:\begin{align*} \sum_{i=1}^{M}x_{i} & =m\\ x^{\prime}S & =y\\ y_{i} & \ge z\quad\forall i\\ y_{i} & \le w\quad\forall i. \end{align*} $y$ is your row sum, and $w$ and $z$ will be the largest and smallest elements of that sum respectively. One way to achieve what I think you mean by uniformity is to minimize $w-z$, packing the row sum elements into the smallest range possible.

$\endgroup$
2
  • $\begingroup$ Thank you! This might be one heuristic. But say we have two vectors, [1,0,0,1,0] and [1,1,1,1,0]. These two have the same $w-z$ value but the first is closer to the uniform distribution. From a statistical view, we usually use entropy. For a normalized vector, [0.2,0.2,0.2,0.2,0.2]. The entropy is $\sum_{i=1}^M 0.2log(0.2)$. The larger the value is, the distribution is closer to the uniform distribution. Is there any way to set this objective function in the mixed integer programming solver? $\endgroup$
    – hidemyname
    Aug 25 '20 at 16:18
  • $\begingroup$ This looks similar to Shannon entropy, except that (as I understand it) that deals with probabilities. Assuming this is supposed to follow the Shannon formula, what do you do with $p\log_2(p)$ when $p=0$? $\endgroup$
    – prubin
    Aug 25 '20 at 20:08
4
$\begingroup$

Entropy maximization will not result in a MILP. The continuous relaxation is a convex (asymmetric cone) conic optimization problem.

Entropy can be maximized, subject to linear and integer constraints (unlike @prubin 's answer, I think you need to declare variables in this problem as binary (integer)) using a convex optimization tool such as CVX, YALMIP, CVXPY, or CVXR. Call and make use of Mosek's mized-integer native exponential cone capability. to solve the problem.

You can make use of CVX's entr function, and similar functions in the other convex optimization tools. If you do not have access to Mosek, but do have access to Gurobi, you can install CVXQUAD under CVX, including its exponential.m replacement, and call Gurobi to solve an MISOCP produced from CVXQUAD generating 2 by 2 LMIs which CVX converts to SOCP constraints before passing them on to the solver. See http://ask.cvxr.com/t/cvxquad-how-to-use-cvxquads-pade-approximant-instead-of-cvxs-unreliable-successive-approximation-for-gp-mode-log-exp-entr-rel-entr-kl-div-log-det-det-rootn-exponential-cone-cvxquads-quantum-matrix-entropy-matrix-log-related-functions/5598 .

$\endgroup$

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.