# Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints

I would like to obtain a feasible solution for an under-determined system of linear equations,

$$Ax=b$$

where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^{7\times1}$.

Clearly, there is no unique solution, but I would like to obtain a solution that satisfies some non-linear inequality conditions for a few components in $x$,

\begin{align} f_1(x_1,x_2,x_3) &\le c_1 \\ f_2(x_7,x_8,x_9) &\le c_2 \\ \end{align}

To be specific, the inequalities are $|x_1 + x_2 + x_3 - k| \le c_1$ and $|x_7 + x_8 + x_9 - k| \le c_2$ , i.e. the only non-linearity here is the abs() function.

I am happy with any solution $x^*$ that satisfies the underdetermined system exactly whilst also satisfying the two constraints above.

I am currently using MATLAB as my programming environment, but pseudo-code/links to useful resources etc shall be more than enough to get started. An example MATLAB code for a dummy problem shall also be very helpful.

• Apply fmincon to the normal equations? – Rahul Feb 26 '18 at 16:00
• @Rahul, I doubt that is even possible. fmincon minimizes only a scalar function, see here uk.mathworks.com/help/optim/ug/fmincon.html . – Krishna Feb 26 '18 at 16:56
• Well, I think you have answered your own question. $g(x) = \|Ax-b\|_2$ is a scalar function, and fmincon can certainly handle problems of the form $\min_x g(x) \;\; s.t \;\; f_1(x)\le c_1, \;\; f_2(x) \le c_2$. – Tyler Olsen Feb 26 '18 at 17:49
• Why not write $-c_1 \leq x_1 + x_2 + x_3 - k \leq c_1$? It is the conjunction of two linear inequalities. Also, you don't have an objective function. There is nothing to minimize. You have linear equality and inequality constraints. Deciding whether there exists a feasible solution can be done via linear programming. – Rodrigo de Azevedo Feb 27 '18 at 16:14
• Correct if 0 denotes a zero vector. – Rodrigo de Azevedo Feb 27 '18 at 17:30

I wanted just to point out that fmincon can also be used: just set the linear equality constraints Ax=b and construct a nonlinear constraint function after the model [c,ceq,G,Geq] = nonlcon(x), where the constraints will be of the form c <= 0, ceq =0 and G and Geq are the respective gradients. This works for more general non-linear functions $f_1,f_2$ than the ones mentioned in the question. For the objective function just put a fictious one, like @(x) 0