Suppose I am given a linear function $F:\mathbb{R}^n\to\mathbb{R}^k$ and a non-empty convex set $K$ which is given as the intersection of half planes. Is there any standard easy method for finding a solution to $F(x)=0$ with $x\in K$?
What I am looking for is a fast and as simple as possible algorithm. Some possibilities that I see would be
- Some kind of gradient descent with $\|F(x)\|^2$ as loss function, but this is probably overkill.
- Finding the subspace $\ker F$, starting with a point in there, and then iteratively move to the correct side of each of the hyperplanes delimiting $K$.
- Start with a point in $X:=K\cap\{F(x)_i\ge0\ \forall i\}$ (need to find one first!), and then do gradient descent in $X$ with loss function $L:=\sum_iF(x)_i$, noticing that the gradient of L is constant, so when we meet one of the hyperplanes delimiting $X$ we simply project the gradient and follow the resulting vector.
Does any of these methods work well? Is there another, even better method? Any help or ideas are appreciated.
This is essentially "phase 1" of linear programming (finding a basic feasible solution). The half-planes to intersect correspond to inequality constraints, the function $F$ to equality constraints.