Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from stats.stackexchange.com Jan 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 1

up vote 2 down vote accepted

(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.
share|improve this answer
    
@ 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
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. –  Willie Wong Jan 31 '12 at 8:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.