I have the following problem: given a vector $v\in\mathbb{R}^n$ (if it matters, its values are only from $\pm1$) I need to find a vector that maximizes some function, and follows the two constraints:
-
the vector is positive (for every i, proj(u)i≥0)
-
the vector is orthogonal to v.
Im using a version of the gradient descent algorithm with a "projection" step to find the solution, and the "projection" step takes any vector and converts it into a "valid" vector.
I want to find an algorithm for this "projection" step, but I dont understand how to satisfy both constaints together and not only one of them.
I would be glad to get some help!
Best Answer
I think the 'algorithm' shall consist of the following 2 steps:
Step 1: Project $u$ onto $v^{\perp}$. From the problem statement I believe you already know the most efficient way to do this.
For step 2 you must realize that the intersection of $v^{\perp}$ with the non-negative orthant (this is what you call the vector being non-negative) is a (possibly trivial as I showed in the comment) convex cone.
Therefore step 2 is to project the projected vector $u'$ onto this convex cone. I have a reference which goes into detail on how to do this even in the case of a Hilbert space. This will hopefully be strong enough to handle your case as well. Actually when proceeding algorithmically for large n you will likely employ these approximation methods.
Projections onto convex cones in Hilbert space, John M. Ingram, M.M. Marsh ,Journal of Approximation Theory, Volume 64, Issue 3, March 1991, Pages 343-350
https://www.sciencedirect.com/science/article/pii/002190459190067K
Hopefully it was helpful. Sorry for outsourcing the crux of the problem to a reference. It is just that the statement is a bit too generic to fully resolve it in a small post here.