How to find if this minimization problem is solvable

Question

Given $x_i,y_i,z_i \in \mathbb{R}$, I want to find $a_0, a_1, a_2$ that minimize the following

$$\sum_{i=1}^n(a_0\times\text{max}[a_1x_i-1,a_2y_i-1]-z_i)^2$$

Is this convex optimization problem and can it be solved efficiently using numerical methods?

Answer 1

Considering the gradient calculated as follows

$$ \nabla \max\left(a_0a_1x_k-a_0-z_k,a_0a_2y_k-a_0-z_k\right)=\left( \begin{array}{l} \begin{array}{cc} \left\{ \begin{array}{cc} a_1 x_k-1 & a_0 a_1 x_k-a_0 a_2 y_k\geq 0 \\ a_2 y_k-1 & \text{else} \\ \end{array}\right. \\ \end{array} \\ \begin{array}{cc} \left\{ \begin{array}{cc} a_0 x_k & a_0 a_1 x_k-a_0 a_2 y_k\geq 0 \\ 0 & \text{else} \\ \end{array} \right. \\ \end{array} \\ \begin{array}{cc} \left\{ \begin{array}{cc} 0 & a_0 a_1 x_k-a_0 a_2 y_k\geq 0 \\ a_0 y_k & \text{else} \\ \end{array} \right. \\ \end{array} \\ \end{array} \right) $$ the minimization problem can be handled successfully with an algorithm as basic as the steepest descent, when considering $\rho > 0$ small enough we proceed with a sequence

$$ A_k = A_{k-1}-\rho_k\nabla f(A_{k-1}) $$

with $A_k = (a_0^k, a_1^k, a_2^k)$

Follows a very basic MATHEMATICA script which tackles that.

n = 10;
X = Table[Subscript[x, k] -> RandomReal[-10, 10][[1]], {k, 1, n}];
Y = Table[Subscript[y, k] -> RandomReal[-10, 10][[1]], {k, 1, n}];
Z = Table[Subscript[z, k] -> RandomReal[-10, 10][[1]], {k, 1, n}];
P = Join[X, Join[Y, Z]];

rho = 0.001;
aant = {0, 0, 0};
as = {Subscript[a, 0], Subscript[a, 1], Subscript[a, 2]};
kmax = 30;

f = Sum[Max[Subscript[a, 0] Subscript[a, 1] Subscript[x, k] - Subscript[a, 0] - Subscript[z, k], Subscript[a, 0] Subscript[a, 2] Subscript[y, k] - Subscript[a, 0] - Subscript[z, k]]^2, {k, 1, n}] /. P;
grad = Grad[f, {Subscript[a, 0], Subscript[a, 1], Subscript[a, 2]}];

For[k = 1, k <= kmax, k++,
   f0 = f /. Thread[as -> aant];
   Print[{k, f0, aant}];
   grad0 = grad /. Thread[as -> aant];
   aatu = aant - rho grad0;
   aant = aatu
]