3
$\begingroup$

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would be that the gradient of function is close to zero.

But for a constrained problem the gradient at the optimal point is not necessarily (close to) zero. Now what stopping condition should we use for a projected gradient descent algorithm?

$\endgroup$
3
  • $\begingroup$ I thought your question was about projected gradient descent. But the answer you accepted says nothing about projected gradient descent. $\endgroup$
    – user856
    Nov 13, 2012 at 0:20
  • $\begingroup$ @RahulNarain Could you complete the answer? $\endgroup$
    – user25004
    Nov 13, 2012 at 0:43
  • $\begingroup$ I don't know the answer, or I would have posted it. I just didn't understand your acceptance criteria. Usually when one accepts an answer, it means that one has found out what they wanted to know and are not looking for any more answers. $\endgroup$
    – user856
    Nov 13, 2012 at 17:21

2 Answers 2

Reset to default
6
$\begingroup$

Just like in the gradient descent method, you want to stop when the norm of the gradient is sufficiently small, in the projected gradient method, you want to stop when the norm of the projected gradient is sufficiently small. Suppose the projected gradient is zero. Geometrically, that means that the negative gradient lies in the normal cone to the feasible set. If you had linear equality constraints only, it would mean that the gradient vector is orthogonal to the feasible set. In other words, it's locally impossible to find a descent direction, and you have first-order optimality.

$\endgroup$
4
  • $\begingroup$ Thanks. Do you have a formal proof for this? (Do you know where I can find it?) $\endgroup$
    – user25004
    May 9, 2014 at 2:22
  • 1
    $\begingroup$ Look for example in Numerical Optimization (Nocedal & Wright, Springer), Section 12.3 "First-Order Optimality Conditions". For any optimization problem, the first-order conditions are that the negative gradient lie in the normal cone. $\endgroup$
    – Dominique
    May 9, 2014 at 8:16
  • 1
    $\begingroup$ @ Dominique, what do you mean projected gradient in "projected gradient is sufficiently small"? Can you explain it more clearly? $\endgroup$
    – Richkent
    Jan 19, 2016 at 15:55
  • $\begingroup$ @Richkent the concept of projected gradient depends on the type of constraints. If you have equality constraints, the projected gradient is the orthogonal projection of the usual gradient into the subspace tangent to the constraints. If you have inequality constraints, the projection is into the tangent cone to the active inequalities. That's what the Kuhn-Tucker conditions express when your objective and constraints are smooth and the Slater qualification holds. The section of Nocedal & Wright that I recommended above has all the details. I hope this helps. $\endgroup$
    – Dominique
    Jan 27, 2016 at 23:39
-1
$\begingroup$

there are actually several methods for dealing with constraint optimization problems. See Penalty Method or Augmented Lagrangian Method as two examples.

To solve the problem \begin{align} \min f( x) \\ \text{ subject to: } c_i( x) \ge 0 ~\forall i \in I \end{align} We reformulate the problem for the Penalty Method as follows \begin{align} \min F(x)_k = f(x) + {\sigma_k}_i p(c_i(x)) \end{align} With $p(c) = \min(0,c)^2$.

Then inside each of your optimization iteration, you iterate over k, increasing the penalty coefficients ${\sigma_k}_i$.Thus you hope to obtain a solution to your minimization problem $F$ which also minimizes $f$, while fullfilling the constraints.

Edit:

Note that also the constraints have to be smooth as you evaluate the gradient.

$\endgroup$
1
  • $\begingroup$ How is this related to the question??? $\endgroup$
    – Dominique
    May 8, 2014 at 22:35

You must log in to answer this question.

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