I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of projected gradient descent? What does that projection contribute?


2 Answers 2


At a basic level, projected gradient descent is just a more general method for solving a more general problem.

Gradient descent minimizes a function by moving in the negative gradient direction at each step. There is no constraint on the variable. $$ \text{Problem 1:} \min_x f(x) $$ $$ x_{k+1} = x_k - t_k \nabla f(x_k) $$

On the other hand, projected gradient descent minimizes a function subject to a constraint. At each step we move in the direction of the negative gradient, and then "project" onto the feasible set.

$$ \text{Problem 2:} \min_x f(x) \text{ subject to } x \in C $$

$$ y_{k+1} = x_k - t_k \nabla f(x_k)\\ x_{k+1} = \text{arg} \min_{x \in C} \|y_{k+1}-x\| $$

  • 4
    $\begingroup$ pretty good answer thanks $\endgroup$
    – erogol
    Nov 19, 2013 at 19:43

I've found two approaches to the algorithm.

Approach 1:

  1. $d_k = Pr(x_k-\nabla f(x_k)) - x_k$ : search direction projected onto feasible set
  2. $x_{k+1} = x_k + t_k d_k$

Approach 2: (Same as answer from p.s.)

  1. $y_k = x_k - t_k \nabla f(x_k)$
  2. $x_{k+1} = Pr(y_k)$ : Project $y_k$ onto feasible set

where $Pr$ is the projection operator.

I've found Approach 1 to work more reliably. Approach 2 fails to converge if the minimizer is on the edge of the feasible set and that edge is perpendicular to the objective gradient. For example, the search directions bounce around the minimizer in algorithm 2.

See here for matlab implementation https://github.com/wwehner/projgrad

  • $\begingroup$ For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$
    – KReiser
    Aug 11, 2020 at 19:24
  • $\begingroup$ got it. Thanks. $\endgroup$
    – wwehner
    Aug 11, 2020 at 19:50
  • 1
    $\begingroup$ A note: approach 2 is an exterior point method whereas approach 1 is an interior point method, meaning that it relies on $x_k$ being feasible. $\endgroup$
    – Brannon
    Sep 16, 2022 at 14:03
  • $\begingroup$ How does Approach 1 guarantee that $x_{k+1}$ is feasible? Is there a formal name for this approach? $\endgroup$
    – xadu
    Oct 19, 2022 at 10:58
  • $\begingroup$ @Brannon Do you know some references on the subject? People seem to be referring to something different with interior point methods, but maybe I am misunderstanding something. $\endgroup$
    – lightxbulb
    Dec 10, 2022 at 10:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .