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


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.

  • 2
    $\begingroup$ Apply fmincon to the normal equations? $\endgroup$
    – user3883
    Feb 26, 2018 at 16:00
  • $\begingroup$ @Rahul, I doubt that is even possible. fmincon minimizes only a scalar function, see here uk.mathworks.com/help/optim/ug/fmincon.html . $\endgroup$ Feb 26, 2018 at 16:56
  • 4
    $\begingroup$ 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$. $\endgroup$ Feb 26, 2018 at 17:49
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 27, 2018 at 16:14
  • 1
    $\begingroup$ Correct if 0 denotes a zero vector. $\endgroup$ Feb 27, 2018 at 17:30

1 Answer 1


The problem was already solved in the comments section using linprog. Also CVX...

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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