4
$\begingroup$

Consider the following constrained minimization problem:
$ min_{x \in X} \ f(x) $
where $ X \subset \Bbb{R}^{n} $ is a nonempty closed convex set and f is continuously diferentiable.

I'm currently studying to solve this problem with the Gradient Projection Method, a fixed-point method:
$ x_{k+1} = Proj_{X}[x_{k}-\alpha_{k}\nabla f(x_{k})] $

($ Proj_{X}(y) $ denotes the point in X with shortest distance to $ y \in \Bbb{R}^{n} $, $ \alpha_{k} $ some appropriate stepsizes - for my case, i just start with some $\gamma \in (0,1)$ and halve this $\gamma$ until it satisfies some kind of Armijo-Rule $f \left( x^{k}(\gamma) \right) \ \le \ f(x_{k}) - 10^{-4} \nabla f(x_{k})^{T}\left( x_{k} - x^{k}(\gamma)]\right) $ with $ x^{k}(\alpha) = Proj_{X}[x_{k}-\alpha \nabla f(x_{k})]$ and declare this $\gamma$ as $\alpha_{k}$)

Now i would like to know more about the quality of this method. All i could gather is a theorem saying that all limit points of the sequence obtained by the algorithm are stationary points of the minimization problem $\small(P.H. \ Calamai \ and \ J.J. \ Moré,\ “Projected \ gradient \ methods \ for \ linearly \ constrained \ problems,” \ Math. \ Programming, vol. 39, pp. 93–116, 1987.)$ .
In my ears this sounds pretty bad. The sequence doesn't need to converge, it could jump between two different limit points, everything could happen. On top of that you somehow have to calculate the projection $Proj_{X}$() - for some simple contraints you can actually determine it, but for most cases you turn in circles have to solve another minimization problem. And nevertheless i hear people saying that this method is globaly "good".
But why? Is there something i missed?

I would be glad for some help, Thanks!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.