Projected Gradient for Bounded constraint Problem

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?

-

migrated from stats.stackexchange.comJan 26 '12 at 14:31

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

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. – Willie Wong Jan 26 '12 at 14:37

1 Answer

(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.
-
@ Willie Wong: sorry, i have deleted my previous comment thinking that it would be inappropriate to ask you for the materials. Im still trying to get the feel of this constraint projected gradient. – Learner Jan 27 '12 at 11:28
Thanks for your answer. However have some issues in understanding this Projected Gradient for a simple example. Please let me know where im making mistake. (We know that Projected Gradient = 0 at optimality). Let $f = x + 2y$ s.t $x+y=1$ & $x,y \geq 0$. We can see that the optimal point is $[1 \ 0]^T$. Lets calculate the Gradient and modified gradient, $\nabla f = [1\ 2]^T$ and $\tilde{\nabla} f = [ -0.5 \ 0.5 ]^T$. Now if i apply the projected gradient as defined to this case, i end up with $\nabla^p f= [ -0.5 \ 0]^T$ which is not expected. – Learner Jan 28 '12 at 4:58
@Learner: ah. oops. You are correct. It needs to be amended. – Willie Wong Jan 30 '12 at 11:33
Im confused with your answer. Is it the answer for any other question. – Learner Jan 30 '12 at 16:05
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. – Willie Wong Jan 31 '12 at 8:53