# 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^Tx-1|=\max(a^Tx-1,1-a^Tx)$. So you just need to maximize those two affine functions and take the maximum of them.
– user856
Commented May 31, 2019 at 19:58
• Numerically that makes sense, but I'm after an analytical solution. That is why I was mentioning the KKT conditions. Commented May 31, 2019 at 20:12
• Why don't you think maximizing $a^Tx-1$ or $1-a^Tx$ over the quadratic constraint can be done analytically?
– user856
Commented Jun 1, 2019 at 5:54
• Commented Jun 24, 2019 at 20:14

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}

• And $max\{ a^T\bar{x} -1 ,1 -a^T\bar{x}\}$ can be written as $|a^T\bar{x} -1 |$ , right? Commented Jun 26, 2019 at 11:47
• @noob013 That is correct. Thank you for the suggestion. I edited my answer. Commented Jun 26, 2019 at 22:21

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.