1
$\begingroup$

For the one-side bounded constraint problem, $\min_x f(x)$ s.t $x\geq0$, I know the projected gradient is given as
$\nabla^p f(x) = \nabla f(x)$ if $x>0$
$\nabla^p f(x) = min(0,\nabla f(x))$ if $x=0$

I wanted to know the projected gradient for
$\min_X f(X)$ s.t $x_i \geq 0$ and $\sum_i x_i = 1$ where $X = [x_1 \cdots x_n]$.

With my understanding of projected gradient, i deduced as
$\nabla^p f(x)_i = \nabla f(x)_i$ if $x_i>0$ and $x_i <1$
$\nabla^p f(x)_i = min(0,\nabla f(x)_i)$ if $x=0$
$\nabla^p f(x)_i = max(0,\nabla f(x)_i)$ if $x=1$

Am i right? If not, what is the projected gradient for the problem?

  • 0
    I don't think that's quite right. The way you wrote the conditions looks like it is capturing the constraint $0 \leq x_i \leq 1$, rather than $0 \leq x_i$, $\sum x_i = 1$. Also, I am pretty sure the projected gradient should be tangent to the simplex in the interior.2012-01-26

1 Answers 1

2

(There was a mistake in the previous version of the answer.)

Given a vector field $\omega$ depending on the position $x$, and given a set of linear constraints

$ \langle v_1, x\rangle = a_1, \ldots, \langle v_k,x\rangle = a_k $

and a set of linear inequalities

$ \langle w_1, x\rangle \geq b_1, \ldots, \langle w_j, x\rangle \geq b_j $

the projected version of $\omega$, which we write $\omega^p$ is defined as follows:

At a point $x$ which solves the systems of linear equations and linear inequalities, let $V := \{ v_1, \ldots, v_k\}$ and let $W(x) := \{ w_i ~~|~~ \langle w_i, x\rangle = b_i \} $

At a point $x$, let $C(x)$ be the set of all vectors such that $ C(x) := \{ \eta ~~|~~ \langle v,\eta\rangle = 0 \forall v\in V\quad \langle w,\eta\rangle \leq 0 \forall w\in W\}$ which is by definition a convex cone, and a closed convex set.

The projection $\omega^p$ that you are looking for is given by the "convex projection" of $\omega$ onto $C(x)$. I am not sure of an algorithm to compute $\omega^p$ in all cases. But there are a few cases of interest:

  • If $\omega \in C(x)$, then $\omega^p = \omega$.
  • If $W = \emptyset$, then $\omega^p$ is given by projecting $\omega$ to the orthogonal complement of $V$. (So in the "interior" of the allowed set, that's how the projections are done.)
  • Let W'\subset W be given by the set of all $w_i$ such that $\langle w_i,\omega\rangle \geq 0$. If W'\cup V span the entire space, then $\omega^p = 0$.
  • If for every $w$ in $W$ we have that $\langle w,\omega\rangle \geq 0$, then $\omega^p$ is the projection of $\omega$ to the orthogonal complement of $V\cup W$.
  • If all of $v_i$ and $w_i$ are pairwise either orthogonal or parallel, then we can use the one-dimensional algorithm relative to each of the $v_i$ and $w_i$. But in general we cannot do it coordinate-wise.
  • 1
    The algorithm in the previous version only works for the final one of the special cases. In the example you gave the constraints are not orthogonal, so it didn't work as expected.2012-01-31