OLS/LAD on linear/quadratic programming type problem

Question

I have a list of equations that define halfspaces (3 equation list example below)

$x_1 + x_2 + x_3 + x_5 < x_4 + x_6 + x_7 \\ x_4 + x_6 + x_7 < x_8 + x_9 + x_{21} + x_{43} + x_1 \\ x_4 + x_6 + x_7 < x_1 + x_2 + x_3 + x_5$

As shown, sometimes this system will not be solvable (I've shown a simple case; in n-dim, it's obvious how this may happen in a more complex way). In this case, I want to find the values of all $x_n$ that has the lowest euclidean distance from being viable.

I'm not entirely sure if I want euclidean distance or squared euclidean distance., but my first thoughts jump to OLS, LAD, and linear programming. However, I've always seen OLS/LAD done with a bunch of real number valued points, not to solve a linear programming system.

I also got informed that this may be reformulateable as a classic nonlinear (specifically quadratic) programming problem, although I'm unfamiliar with the space as a whole.

Any ideas on how to best find the values of this system.?

Answer 1

If your problem is defined by $g_j(x) \le 0, j \in J$, you want to minimize $\sum_{j \in J} ||\max(0, g_j(x))||$ for a given norm.

If you take the 1-norm, you get
$\min_x \sum_{j \in J} \max(0, g_j(x))$
which is not differentiable. However you can reformulate it into a smooth problem by introducing the variables $s_j = \max(0, g_j(x))$:
$\min_{x, s} \sum_{j \in J} s_j$
s.t. $s_j \ge 0, s_j \ge g_j(x)$
which is a linear problem.