6
$\begingroup$

I have a question about whether there are faster algorithms for specific submodular minimization problems.

In particular, I am trying to find a fast algorithm for minimizing the following set function

$$f(S) = - [\sum_{i \in S} \alpha_i \log(\alpha_i) + (1-\sum_{i \in S} \alpha_i) \log(1-\sum_{i \in S} \alpha_i)] + \sum_{i \in S} w_i$$

where $S \subset \{1,...,n\}$, $\{\alpha_i\}_{i=1}^N$ is a vector of positive numbers that add up to 1, and $w_i$ is a set of (possibly negative) weights.

The first term in the function is a submodular function of $S$. The second term is a modular function of $S$. I know there exist algorithms (Fujishige-Wolfe) to minimize a general submodular function. Are there known algorithms to quickly minimize the sum of the entropy of a set and a modular function?

$\endgroup$
  • 1
    $\begingroup$ That isn't the expression for the entropy of a set. Are you sure you've got the right expression? Did you perhaps mean $-p\log p -(1-p)\log(1-p)$ where $p = \sum_{i \in S} \alpha_i$? $\endgroup$ – D.W. Mar 6 '17 at 17:12
  • $\begingroup$ Thanks for your comment. The expression I got comes from the problem I am trying to solve, but if it is not a common way of measuring the entropy of a set, it is likely there is no better algorithm than the generic Fujishige-Wolfe to solve this problem. $\endgroup$ – Asterix Mar 6 '17 at 17:55
  • $\begingroup$ Re: Neal Young's answer below, I guess I was wrong. $\endgroup$ – Asterix Mar 10 '17 at 15:50
4
$\begingroup$

Unless I'm mistaken, you can solve your problem in $O(n\log n)$ time using a greedy algorithm.

Minimizing $f(S)$ is equivalent to maximizing $$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in S'} \alpha_i\big) \log \sum_{j \in S'} \alpha_j$$ for $b_i=w_i + \alpha_i\log(\alpha_i)$. Here $S'$ is the complement of your $S$.

Assume WLOG that $\alpha_i>0$ (otherwise $i\in S'$ iff $b_i>0$).

Introduce indicator variable $x_i$ for the event that $i\in S'$, then relax the problem by allowing $x_i\in[0,1]$. The relaxed problem is to choose $x\in[0,1]^n$ maximizing $$\textstyle G(x) = \sum_{i} x_i b_i + \big(\sum_i x_i \alpha_i\big) \log \sum_{j} x_j \alpha_j.$$ The partial derivative of $G(x)$ with respect to $x_i$ is $$\textstyle b_i + \alpha_i\, \lambda(x),$$ where $\lambda(x) = 1 + \log\sum_j x_j \alpha_j$. So at any optimal $x$, you have $$x_i = \begin{cases} 0 & \text{if}~ b_i/\alpha_i < -\lambda(x) \\ 1 & \text{if}~ b_i/\alpha_i > -\lambda(x) \\ ? & \text{if}~ b_i/\alpha_i = -\lambda(x). \end{cases} $$

WLOG, the ratios $b_i/\alpha_i$ are distinct for each $i$ (otherwise an insignificant perturbation of the $b_i$'s makes them so). So only a single $x_i$ is undetermined by the above condition. Since $G(x)$ is convex, one of the two neighboring solutions $x'$ (obtained by changing that $x_i$ to zero or one) has $G(x') \ge G(x)$. Hence, defining $S_j = \{i : b_i/\alpha_i \le b_j/\alpha_j\}$ and $S_0=\emptyset$, the optimal set is $S_j$ for some $j\in\{0,\ldots,n\}$.

So, here is the algorithm. Assume that $\alpha_i > 0$ for each $i$, and (by sorting first in $O(n\log n)$ time), that $b_1/\alpha_1 > b_2/\alpha_2 > \cdots > b_n/\alpha_n$. Enumerate all sets $S_j$ (and compute $G(S_j)$ for each) in $O(n)$ time, then take the best.

$\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.