How to maximize the infinity norm over a convex region?

Question

Consider the following optimization model

$$\begin{array}{ll} \text{maximize} & \displaystyle\max_{i \in S} |x_{i}|\\ \text{subject to} & Q(x)+ \displaystyle\sum_{i \in S}|x_{i}| \leq m\end{array}$$

where $x_{i} \in \mathbb R$, $Q(x)$ denotes a quadratic function of $x$, and $m$ is a known number.

Can we write this model as a quadratic and convex optimization model, which can be solved by optimization solvers such as Gurobi or CPLEX? In particular, how should we deal with a $\max \max$ type optimization problem?

Answer 1

Your problem can be equivalently stated as

\begin{equation} \begin{array}{rl} \max_{x\in\mathbb{R}^n}\ &\|x\|_\infty\\ \text{s.t.}\ & x^{T}Ax+b^{T}x+\|x\|_1\leqslant{c} \end{array} \end{equation} for some symmetric positive-definite matrix $A$. The constraint is convex, but since you are maximizing a convex function, this is a hard problem (NP hard, I believe). Consequently, to solve it, we will have to introduce some binary/integer variables.

Essentially, there are two things you need to be able to do:

1. Model the absolute values--i.e. introduce variables $y_i\geqslant0$ such that $y_i=|x_i|$ for all $i=1,\dots,n$. This is equivalent to enforcing that \begin{equation} |x_i|\leqslant{y_i}\Leftrightarrow -y_i\leqslant x_i\leqslant y_i\ \text{ for all }i=1,\dots,n, \end{equation} which is easy, and that $y_i\leqslant|x_i|$ for all $i=1,\dots,n$. This will require two things: (1) a value $u_i>0$ such that $|x_i|\leqslant u_i$ holds for all $x$ in which we are interested, and (2) introducing a binary variable $z_i\in\{0,1\}$ for each $i=1,\dots,n$ such that $z_i=1$ iff $x_i\geqslant0$. Using (1) and (2), we have that \begin{equation} y_i\leqslant |x_i| \Leftrightarrow y_i\leqslant x_i+2u_i(1-z_i)\text{ and }y_i\leqslant -x_i+2u_iz_i. \end{equation} In your case, assumption (1) is basically equivalent to having an upper bound on the optimal objective value. In principle, you could just "pick a huge number", but this is inadvisable--the larger the values $u_i$ are chosen, the weaker the continuous relaxation of this problem becomes, the harder it becomes to solve. Try to pick smart values of $u_i$.
2. Model the maximum. This is outlined in the Gurobi documentation, for example. From the link:

For example, the MAX constraint $r = \max\{x_1,\ldots,x_k,c\}$ can be modeled as follows: \begin{equation} \begin{array}{rcll} r &=& x_i+s_j &\text{ for all }j=1,\dots,k\\ r &=& c+s_{k+1} & \\ z_1+\dots+z_{k+1} &=& 1 & \\ SOS1(s_j,z_j) && & \text{ for all }j=1,\dots,k+1\\ s_j &\geqslant& 0 & \text{ for all }j=1,\dots,k+1\\ z_j &\in& \{0,1\} & \text{ for all }j=1,\dots,k+1 \end{array} \end{equation} The first two constraints state that $r \geq \max\{x_1,\ldots,x_k,c\}$, i.e., that the resultant variable $r$ has to be at least as large as each of the operand variables $x_j$ and the constant $c$. This can be modeled using inequalities, but we turned them into equations by introducing explicit continuous slack variables $s_j \geq 0$, which we will reuse below.

Those slack variables and the remaining constraints model $r \leq \max\{x_1,\ldots,x_k,c\}$, which is more complicated. In addition to the explicit slacks, this requires the introduction of binary auxiliary variables $z_j \in \{0,1\}$. The SOS1 constraints state that at most one of the two variables $s_j$ and $z_j$ can be non-zero, which models the implication $z_j = 1 \rightarrow s_j = 0$. Due to the third constraint, one $z_j$ will be equal to $1$ and thus at least one $s_j$ will be zero. Hence, $r = x_j$ for at least one $j$ due to the first constraint, or $r = c$ due to the second constraint.

This should be sufficient detail to figure this out for yourself.

Note on Gurobi

If you want to solve this with Gurobi, as you stated, then you should take advantage of Gurobi's general constraints. General constraints automatically handle both of the reformulations above, and hide all the messy details from you. In combination with their support for quadratic constraints, you should be well on your way to solving.