Minimizing quadratic object subject to max inequality constraints

78 Views Asked by At

Given $\delta > 0$, let $[n] := \{1,\dots,n\}$ and

$$\mathcal{M} := \left\{ \boldsymbol{\mu} : \max_{i \neq j \in [n]} | \mu_i - \mu_j | \geq \delta \right\}$$

I have the following optimisation problem

$$\min_{\boldsymbol{\mu}\in\mathcal{M}}\sum_{i<j}(\mu_i-\mu_j)^2$$

The solution, I suspect, is any permutation of $(-\delta/2, \delta/2, 0, \ldots, 0)$. I need help to prove this.

1

There are 1 best solutions below

2
On

Let $m := \binom{n}{2}$. Let $\rm C$ be the $m \times n$ signed incidence matrix of the complete graph on vertex set $[n]$. Hence,

$$\begin{array}{ll} \underset{\mathrm x \in \mathbb R^n}{\text{minimize}} & \| \mathrm C \mathrm x \|_2^2\\ \text{subject to} & \| \mathrm C \mathrm x \|_\infty \geq \delta\end{array}$$