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

<p>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$.</p>

<p>Assume WLOG that $\alpha_i&gt;0$ (otherwise $i\in S'$ iff $b_i&gt;0$).</p>

<p>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 &amp; \text{if}~ b_i/\alpha_i &lt; -\lambda(x) \\
1 &amp; \text{if}~ b_i/\alpha_i &gt; -\lambda(x) \\
? &amp; \text{if}~ b_i/\alpha_i = -\lambda(x).
\end{cases}
$$</p>

<p>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\}$.</p>

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

CC BY-SA 3.0
2017-03-08T13:33:29.100Z
2017-03-08T13:33:29.100Z
Neal Young
<p>I have a question about whether there are faster algorithms for specific submodular minimization problems.</p>

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

<p>$$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$$</p>

<p>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. </p>

<p>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? </p>

CC BY-SA 3.0
2017-03-06T17:12:55.860Z
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.
CC BY-SA 3.0
2017-03-06T17:55:57.960Z
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.
Asterix
CC BY-SA 3.0
2017-03-10T15:50:34.723Z
Re: Neal Young's answer below, I guess I was wrong.
Asterix
<submodularity>
Minimizing entropy plus a modular function
Asterix
# Minimizing entropy plus a modular function

(Asked by: username_0 on 2017-03-06)

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?

**Tags:** submodularity
> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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.  
> **username_0**: Re: Neal Young's answer below, I guess I was wrong.  

---

## 1 answers

### Answer by username_2 on 2017-03-08. Score: 4 | Accepted answer

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.


---

