# Minimizing entropy plus a modular function

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?

• 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$?
– D.W.
Mar 6 '17 at 17:12
• 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. Mar 6 '17 at 17:55
• Re: Neal Young's answer below, I guess I was wrong. Mar 10 '17 at 15:50

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.