3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Apply fmincon to the normal equations? $\endgroup$ – Rahul Feb 26 '18 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$ – Krishna Feb 26 '18 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$ – Tyler Olsen Feb 26 '18 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$ – Rodrigo de Azevedo Feb 27 '18 at 16:14
  • 1
    $\begingroup$ Correct if 0 denotes a zero vector. $\endgroup$ – Rodrigo de Azevedo Feb 27 '18 at 17:30
2
$\begingroup$

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

$\endgroup$

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.