Skip to main content
4 of 7
edited body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Projecting on a convex compact polytope with special form

Let $E$ be a sparse $l$-by-$n$ matrix with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and every other row contains exactly one entry equal $1$ (the other entries are thus equal to $0$ or $-1$). Also, let $e := (1,0,0,\ldots,0) \in \mathbb R^l$.

Now consider the convex compact polytope

$$Q := \{z \ge 0 | Ez = e\}.$$

Question: Given a point $x \in \mathbb R^n$, how to compute exactly (non-iteratively, etc.), a point of $Q$ which is closest to $x$. That is how to solve the problem

$$\text{minimize }\frac{1}{2}\|z-x\|^2\text{ subject to }z \in Q$$ exactly. There is a whole zoo of iterative algorithms for solving such problems in signal-processing, but I'd I'm looking for the "book solution". There are strong motivations for demanding this.

Special cases: If we take $l = 1$, then $Q$ is precisely the unit simplex in $\mathbb R^n$, and there are linear-time exact algorithms for projecting (for example, Condat's algorithm based on median-of-medians).

Applications: The set $Q$ defined above can be identified with the strategy profile of a player in the sequence-form representation of a sequential game with incomplete information and perfect recall (like Poker, etc.).

dohmatob
  • 6.9k
  • 1
  • 18
  • 76