Penalty for an objective function to encourage "pigeon-holing"?

30 Views Asked by At

I have an objective function $f(x_1, \ldots, x_n)$ that I'm trying to optimise. Simultaneously, I have $n$ given "target points" $y_1, \ldots, y_n$. Ultimately, I want each of the $x_i$'s to gravitate towards a different target point, so that each target point "has a single pigeon in its hole". What penalty can I add on to the function to encourage this? All I can think of is something like $$\text{penalty}=\sum_i \left(\text{softmin}_j \left|y_i - x_j\right|\right)^2$$ For the record, $$\text{softmin}_j ~ a_j = - \text{logsumexp}\left(-a_1, \ldots, -a_n\right)$$ but one could use anything similar. The absolute value is to encourage $\text{softmin}_j$ to prioritize a single $x_j$ corresponding to a $y_i$, and the squaring+sum is to encourage the each $y_i$ to do a good job of picking at least one $x_j$.