I'm studying for an exam and came across a practice problem that I've been unable to solve.
Let $a_i \in \mathbb{R}^n$, then answer the questions pertaining to the following optimization problem
\begin{align} & \underset{x}{\text{minimize}} & & f_0(x) = \sum_{i=1}^m{(|a_i^T x| - 1)^2} \end{align}
a) Is this a convex optimization problem?
b) Formulate this problem as one of the standard problems from class; that is, as a linear program (LP), quadratic program (QP), quadratically constrained quadratic program (QCQP), second order cone program (SOCP), geometric program (GP) or semidefinite program (SDP).
I can answer part a. This clearly isn't convex in general.
Proof: If we consider the case where $m=1$ then consider the values $x_1$ and $x_2$ such that $a_1^T x_1 = -1$ and $x_2 = -x_1$ so $a_1^T x_2 = 1 \Rightarrow f_0(x_1)=0$ and $f_0(x_2)=0$. We find that $f_0(1/2 x_1 + 1/2 x_2) = f_0(0) = 1 > 0 = 1/2 f_0(x_1) + 1/2 f_0(x_2)$ which contradicts the claim that $f_0$ is convex. Also, the objective is not concave (fairly clear using similar argument).
I'm stuck at part b. I can formulate this problem as a set of quadratic programs by considering the fact that we want $a_i^T x$ to be near $1$ or $-1$. So we can solve this by considering the $2^m$ different quadratic programs
\begin{align} & \underset{x}{\text{minimize}} & & f_0(x) = \sum_{i=1}^m{(s_{i,k} a_i^T x - 1)^2} \end{align}
where $k = 1,\ldots,2^m$ defines $2^m$ different optimization problems where where $s_{i,k} \in \{-1,1\}$ is every permutation of $-1$ and $1$.
An optimal point for the original problem is an optimal point of the above problem for the $k$ which gives the lowest optimal value.
I'm fairly certain this is not the answer the problem writer had in mind but I'm struggling to come up with a single convex optimization problem which can solve this problem. Can anybody help me come up with such a solution?
The best I can come up with is $2^m$ sub problems.
The idea is straightforward, similar to your idea, except with the addition of constraints which essentially partition the feasible space so that the objective is convex on each partition.
The idea is illustrated with the function $x \mapsto (|x|-1)^2$. Split into the two QPs $\min \{ ((x-1)^2 | x \ge 0 \}$ and $\min \{ (-x-1)^2 | x \le 0 \}$.
Formally, if $\sigma \in \{\pm 1\}^m$, define the subproblem $P_\sigma: \ \min \{ \sum_m (\sigma_i a_i^T x-1)^2 | \sigma_i a_i^T x \ge 0 \}$.