Maximisation of a piecewise affine function over an ellipsoid Given vectors $\mathrm a, \bar{\mathrm x} \in \mathbb R^n$ and matrix $\mathrm P \in \mathbb S^n_{++}$, how to deal with the absolute value in the objective function of this optimization  problem in $\mathrm x \in \mathbb R^n$?
$$\begin{array}{ll} 
    \text{maximize} & | \mathrm a^{\top} \mathrm x - 1 |\\
    \text{subject to} &  (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x})  \leq 1 
\end{array}$$
I can not write it in epigraph form because it is a maximisation of a convex function right?
Trying the KKT conditions for nonconvex problems will give me trouble since the absolute value is not differentiable everywhere. Geometrically, I think that the solution is at the boundary of the constraint set.
 A: By using the big-M method for linearizing logical constraints, you can also rewrite this problem as a mixed-integer second order cone program (assuming $P \succeq 0$). This is because the absolute value objective is equivalent to maximizing $\theta$, where:
$$
\theta \leq a^\top x-1+M z_1\\
\theta \leq 1-a^\top x+M z_2\\
z_1+z_2=1\\
z_1, z_2 \in \{0,1\}
$$
Note that in the above formulation if $a^\top x >1$ then the optimal choice of $z$ is $z_1=0, z_2=1$ so the logical constraint is enforced at optimality.
All told, we can formulate the problem as the following MISOCP whenever $P \succeq 0$:
$$
\max \theta\\
\text{s.t.} \theta \leq a^\top x-1+M z_1\\
\theta \leq 1-a^\top x+M z_2\\
z_1+z_2=1\\
\Vert P^{-\frac{1}{2}}(x-\bar{x}\Vert_2 \leq 1\\
z_1, z_2 \in \{0,1\}
$$
and this problem can easily be solved by MISOCP solvers such as Gurobi or CPLEX.
N.b. as mentioned in the comments it would be faster to consider the two absolute value cases separately, but this is not a good option if there are a number of different absolute value constraints.
A: We have the following optimization  problem in $\mathrm x \in \mathbb R^n$
$$\begin{array}{ll} 
    \text{maximize} & \left| \mathrm a^{\top} \mathrm x - 1 \right|\\
    \text{subject to} &  (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x})  \leq 1 
\end{array}$$
where
$$\left| \mathrm a^{\top} \mathrm x - 1 \right| = \begin{cases} \mathrm a^{\top} \mathrm x - 1 & \text{if } \mathrm a^{\top} \mathrm x \geq 1\\ 1 - \mathrm a^{\top} \mathrm x & \text{if } \mathrm a^{\top} \mathrm x \leq 1\end{cases}$$
Since the objective function is piecewise affine, the maximum should be attained at the boundary of the ellipsoid. Hence, let us consider the following quadratically-constrained linear program (QCLP)
$$\begin{array}{ll} 
    \text{extremize} & \mathrm a^{\top} \mathrm x \\
    \text{subject to} &  (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x}) = 1 
\end{array}$$
We define the Lagrangian
$$\mathcal L (\mathrm x, \mu) := \mathrm a^{\top} \mathrm x - \frac{\mu}{2} \left( (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x}) - 1 \right)$$
Taking the gradient with respect to $\rm x$ and the derivative with respect to $\mu$, we obtain
$$\begin{aligned} \mathrm a - \mu \, \mathrm P^{-1}(\mathrm x - \bar{\mathrm x}) &= 0_n\\ (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x}) &= 1\end{aligned}$$
Left-multiplying the first equation by $\rm P$ and re-arranging,
$$\begin{aligned} \mu (\mathrm x - \bar{\mathrm x}) &= \mathrm P \mathrm a  \\ (\mathrm x- \bar{\mathrm x})^{\top} \mathrm P^{-1}(\mathrm x - \bar{\mathrm x}) &= 1\end{aligned}$$
If $\mathrm P \mathrm a \neq 0_n$, then $\mu \neq 0$ and, thus,
$$\mathrm x - \bar{\mathrm x} = \frac{1}{\mu} \mathrm P \mathrm a$$
Using the equation of the ellipsoid, we obtain
$$\mu^2 = \mathrm a^\top \mathrm P^\top \mathrm P^{-1} \,\mathrm P \,\mathrm a = \mathrm a^\top \mathrm P \,\mathrm a$$
where $\mathrm a^\top \mathrm P \,\mathrm a \geq 0$ because $\rm P$ is positive definite. Hence,
$$\mathrm x - \bar{\mathrm x} = \pm \frac{1}{\sqrt{\mathrm a^\top \mathrm P \,\mathrm a}} \mathrm P \mathrm a$$
and, thus, the minimizer and maximizer of the QCLP are
$$\begin{aligned} \mathrm x_{\min} &:= \bar{\mathrm x} - \frac{1}{\sqrt{\mathrm a^\top \mathrm P \,\mathrm a}} \mathrm P \mathrm a \\\\ \mathrm x_{\max} &:= \bar{\mathrm x} + \frac{1}{\sqrt{\mathrm a^\top \mathrm P \,\mathrm a}} \mathrm P \mathrm a\end{aligned}$$
and the maximum of the original optimization problem is
$$\begin{aligned} \max \left\{ \mathrm a^\top \mathrm x_{\max} - 1, 1 - \mathrm a^\top \mathrm x_{\min} \right\} &= \max \left\{ \mathrm a^\top \bar{\mathrm x} + \sqrt{\mathrm a^\top \mathrm P \,\mathrm a} - 1, 1 - \mathrm a^\top \bar{\mathrm x} + \sqrt{\mathrm a^\top \mathrm P \,\mathrm a} \right\}\\ &= \max \left\{ \mathrm a^\top \bar{\mathrm x} - 1, 1 - \mathrm a^\top \bar{\mathrm x} \right\} + \sqrt{\mathrm a^\top \mathrm P \,\mathrm a}\\ &= \color{blue}{\left| \mathrm a^\top \bar{\mathrm x} - 1 \right| + \sqrt{\mathrm a^\top \mathrm P \,\mathrm a}}\end{aligned}$$
