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.?


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.

  • $\begingroup$ What is $g_j$ here? $\endgroup$ – user760900 Dec 10 '20 at 22:55
  • $\begingroup$ The inequalities that you described in your first post. $\endgroup$ – cvanaret Dec 11 '20 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.