3
$\begingroup$

What is the best way to handle a constraint of the type $ax_1^2+x_2^2+...+x_n^2=c$ in a gradient descent algorithm?

I would like to solve an optimization problem of the type: $$ \min J(x_1,..,x_n)$$ with this constraint using gradient descent. I tried to think of a way to alter the gradient so that it doesn't affect the constraint, but I didn't manage to do something useful.

What I did was that after each gradient descent, I projected (in a more or less correct way...) the result onto the constraint. I got the results I wanted, but I don't think my approach was 100% valid...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes, that's a valid way of incorporating constraints into nonlinear programming problems. These types of algorithms are called reduced gradient or gradient projection methods. The method of that type I'm most familiar with is the generalized reduced gradient (GRG) method, and there are other methods out there as well.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there a rule which indicates how should the projection be made? For example, in my case I have 21 variables. I should modify all variables in "the same way" to reach the constraint. I modified only the first variable to reach the desired constraint (in my case, the variables were related to the geometry of a shape, and the first variable had only a sort of homothetical effect...), but I encountered problems where I unsuccessfully tried all sorts of projections but the "good one". $\endgroup$
    – Beni Bogosel
    Sep 4, 2013 at 21:59
  • $\begingroup$ You normally project onto constraints that are active. It's been a while since I've read up on that, but the literature should specify what types of projection work better. $\endgroup$
    – Geoff Oxberry
    Sep 4, 2013 at 22:24
  • $\begingroup$ Your constraint is an ellipsoid. It shouldn't be very difficult to just find the closest point on the surface from $x_k+\delta x_k$. $\endgroup$
    – Wolfgang Bangerth
    Sep 5, 2013 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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