I am using an optimization method that requires a starting point within the feasible domain:
$$\min f(x)$$
$$Ax=b$$
$$Cx>r$$
where
$$x \in R^l$$
$$b \in R^n$$
$$r \in R^m$$
and
$$ (m+n) > l $$
In other words, the amount of equality/inequality constraint equations is greater that the amount of unknowns. Also, note that $l>n$ so in general there should be a feasible solution in existence.
What is the best approach to generate any feasible point to start the program? Thanks.
On
Most LP solvers have pretty clever ways to generate the initial iterate. If you want to do it yourself, consider following auxiliary LP: $ \max y $ for $Ax=b$, $Cx - ye \ge r$, $y\le 1$, where $e$ is the vector with ones.
Solve that auxiliary LP with what method you like, if the optimal $y^*$ is positive, you obtain your feasible $x$. If $y^* \le 0$, there is no feasible point. However due to rounding error, you need to check this with some tolerance.
To obtain a feasible point for the auxiliary LP: Compute a solution of $Ax=b$ (for example by factorization). Then set $y$ to some value less than (or equal) the least component of $Cx - r$. If $y>0$ you are done, otherwise solve the auxiliary LP. You could stop, if you reach some iterate with $y>0$.
Knowing nothing about $A, C, b, y$ except dimensions a bit, this is a pretty hopeless task.
We can write $$ C x > r \quad (*) $$ as $$ C x \ge r + \epsilon \quad (**) \\ \epsilon > 0 $$ where $\epsilon \in \mathbb{R}^m$ is some vector with positive components. I have no idea how to pick this in a smart way. This way one can model it as LP problem. A solution $x$ fulfilling $(**)$ should fulfill $(*)$: