Method to solve nonlinear system of inequalities

Question

I have a system of inequalities of the form

$x_i + y_i \cos(p_{ik}-a_i)-z_iq_{ik} > x_j + y_j \cos(p_{jk}-a_j)-z_jq_{jk}$

$x_i + y_i \cos(p_{in}-a_i)-z_iq_{in} < x_m + y_m \cos(p_{mn}-a_m)-z_mq_{mn}$

All $p$ and $q$ are parameters, I need to solve for $x_i$, $y_i$, $z_i$, $a_i$ for all $i$.

There are many inequalities for each $i$ (several hundred) so I expect this to be an overdetermined system whose set of exact solutions might be empty - if that is the case, I am looking for a "well-fitting" solution; an approximation is OK if it is not too unstable.

I am unable to linearize the problem so I fear I cannot use linear optimization for this, and I am unaware of any regression-like method using inequalities.

Is there a computationally feasible method to achieve this?

Answer 1

For purposes of this exposition, let's presume you have a system of $k$ inequalities in $n$ variables, which has been put into the form (trivial to do) $$f_i(x) \ge 0, i = 1..k$$ where $x$ is the $n$ by $1$ vector of variables.

Solve (using an optimizer which can handle the nonlinear inequalities) the following nonlinearly-constrained optimization problem: (but see the generalization below).

minimize $\Sigma_{i=1}^k M_i$ with respect to x,M subject to $$f_i(x) + M_i \ge 0, i = 1..k$$ $$M_i \ge 0, i=1..k$$

If the optimal objective of this problem is zero, then you have found a feasible solution to the original system of nonlinear inequalities. If it is positive, then the original system of nonlinear inequalities is infeasible (does not have an exact solution), but you will have found a solution which is close as possible to feasible, as measured per the objective function of the optimization problem.

You can use a different objective function in order to prioritize different levels of errors and relative importance of compliance among the various constraints. For instance, more generally consider an objective function such as $$\Sigma_{i=1}^k w_iM_i^q$$ where $w_i \ge 0$, which allows a nonlinear "non-compliance" penalty and allows different weights for the different inequalities. The simple version presented above corresponds to all $w_i = 1$ and $q = 1$. If you want to get really fancy, $q$ need not be the same for all $k$ inequalities.

Answer 2

It is also possible to linearize the inequalities using substitutions $b_i = y_i \cos a_i$, $c_i = y_i \sin a_i$:

$x_i - x_j + b_i \cos p_{ik} - b_j \cos p_{jk} + c_i \sin p_{ik} - c_j \sin p_{jk} - z_iq_{ik} + z_jq_{jk} \ge 0$