2
$\begingroup$

Hi: I'm trying to understand the concept of projection and I created a toy example that might help me to do that.

Suppose that I have a non-linear optimization with 3 parameters theta_1, theta_2 and theta_3. The actual problem requires that theta_1, theta_2 and theta_3 be between 0 and 1 and that their sum is equal 1.0.

So, now suppose I optimize without any of the constraints and get back the optimal unconstrained parameters theta_1 = 1.992, theta_2 = 0.575 and theta_3 = 0.487.

So, now suppose that I want to project those optimal parameters into the feasible region so the projected parameters are as close to the original ones as possible.

I think understand the concept of projections when I read about it in textbooks, both in the vector case and matrix case.

1) vector case: To project a vector $b$ on to the subspace spanned by another vector $a$, it can be shown that the point through the origin and along the point a, where the distance between from b to a is minimized is $\frac{a^{T}b}{a^{T}a} \times a$. The derivation made sense to me but I won't show it here. ( It's pretty standard result obviously ).

2) matrix case: if $X$ is $n \times k$ and $\beta$ is $k \times 1$, and we have $y = X \beta$ where $\beta$ is unknown, then $\hat{\beta} = (X^{\prime}X)^{-1}X^{\prime}y$ and $\hat{y} = X \hat{\beta} = X (X^{\prime}X)^{-1}X^{\prime}y$ is the projection of y onto the spaced spanned by the column space of $X$. The derivation of that made sense and the derivation is pretty much the same as 1) where $b = y$ and $a = X\beta$.

But I don't know how to apply the results of 1) or 2) to the toy optimization problem that I described. Someone told me that the answer is that the projected coefficients are the original coefficients divided by their sum but I don't see how to obtain that.

I think if I can understand how one solves the toy problem, then I'll understand the application of projections rather than just the formulae.

Thank you very much for any explanations using either 1 or 2. Also, if anyone could tell me if the coefficients divided by their sum has any meaning in terms of a projection, that would be appreciated also.

$\endgroup$
0
$\begingroup$

Your problem is essentially: given a point $x \in \mathbb{R}^n$ and a convex set $C \subset \mathbb{R}^n$, how do I project $x$ onto $C$? There's lots of work on this; you want a projection operator. The definition of the projection of $x$ onto $C$ is the point $y \in C$ that minimizes the Euclidean distance $\|x-y\|$.

In your case, the convex set $C$ has a special form: it is a box. In particular, in your example, it is a unit box: $C=[0,1]^n$. For this special case, projection is especially easy. In particular, the projection of $x$ onto $C$ is the vector $y$ defined as

$$y_i = \max(0, \min(x_i, 1)).$$

In other words, you clamp each coordinate to be within the range $[0,1]$: if it is already in $[0,1]$, you do nothing; if it is larger than $1$, you clamp it to $1$; if it is smaller than $0$, you clamp it to $0$.

The same works with any box: you clamp each entry, separately, to the interval it is supposed to be within.

Once you know about this, look up projected gradient descent.

$\endgroup$
  • $\begingroup$ thanks D.W. I'll print out but it makes sense. I'll also check out the link and check it as the answer. thanks again. $\endgroup$ – mark leeds Jul 13 '16 at 2:00
  • $\begingroup$ D.W.: It sort of makes sense but is it obvious to you that if one of the points is at 1.1, then putting it at 1.0 is the best thing to do. How do we know that 0.5 is not better than 1.0 ? Thanks and if it's in the reference, I'll go over that. $\endgroup$ – mark leeds Jul 13 '16 at 2:26
  • $\begingroup$ @markleeds, I think your first step should be to see if you can be precise about what you mean by "best thing to do". Best, in terms of minimizing the Euclidean distance to the nearest point of $C$? Best, in terms of maximizing the objective function of the optimization problem you're trying to solve? That will lead to different answers. Your question was about how to project to a feasible region, and that's what this is addressing. Whether projecting to a feasible region leads to the optimal solution to a constrained optimization problem is a different question. $\endgroup$ – D.W. Jul 13 '16 at 2:35
  • $\begingroup$ Hi D.W: Yes. I probably wasn't clear in my original question. ( it's been a while so I had to re-read it ). I understand how your formula gets one into a feasible region. But does it necessarily follow that that that the feasible set of points not only is feasible but also optimal ? I don't think that follows but I could be wrong. thanks for any references on that. note that the examples in my original question do minimiize distances but I still probably wasn't all that clear. Thanks again. $\endgroup$ – mark leeds Jul 14 '16 at 5:50
  • $\begingroup$ @markleeds, again, it's necessary to be clear about what you mean by optimal. There are two possible meanings. See my prior comment (and replace "best" with "optimal"). I show how to project to the nearest point in $C$, i.e., to the point that is nearest (and yes it is totally "optimal" if your metric is that it has to be the nearest of all the points in $C$). As mentioned in my prior comment, that doesn't necessarily mean it'll be optimal for the original optimization problem (e.g., for the original objective function). Projection is just a substep in projected gradient descent. $\endgroup$ – D.W. Jul 14 '16 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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