Minimize the maximum magnitude of several quadratic functions

Question

I have a collection of quadratic functions

\begin{align} f_i(x) = \frac{1}{2}x^T Q_i x, \qquad i = 1,\dots,m, \end{align}

where each $Q_i$ is an indefinite $n \times n$ matrix and $x \in \{-1,1\}^n$. I wish to solve the following optimization problem

\begin{align} \text{minimize} &&\max \limits_i |f_i(x)| \end{align}

which has a nonlinear objective function.

What approaches exist for attacking this kind of optimization program? Is there a more powerful approach than using a general purpose global optimizer?

Note: In response to a comment, I've realized that I need to change the condition on $x$ to generate the desired problem. In particular, I need $x \in \{-1,1\}^n$ instead of $x \in [-1,1]^n$.

Answer 1

The problem is nonconvex both from the indefinite quadratics, and from the combinatoric $x$. The way I would approach it is by first writing the absolute values as $-t \leq x^TQ_ix \leq t$ with objective $t$, and then exactly linearize the quadratic terms.

Since I am lazy, I will write the linearization for binary $x$ (scale and shift accordingly for your case). Terms $x_ix_j$ are replaced with $w_{ij}$ which satisfies $w_{ij}\leq x_i$, $w_{ij}\leq x_j$ and $w_{ij} \geq x_i + x_j-1$. At this point you have a standard mixed-integer linear program in $x$, $w$ and $t$.

Answer 2

Introducing optimization variable $t \in \mathbb R$, the optimization problem can be written as follows

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & -t \leq \mathrm x^\top \mathrm Q_1 \mathrm x \leq t\\ & -t \leq \mathrm x^\top \mathrm Q_2 \mathrm x \leq t\\ &\qquad\quad\vdots\\ & -t \leq \mathrm x^\top \mathrm Q_m \mathrm x \leq t\\ & -1_n \leq \mathrm x \leq 1_n\end{array}$$