I saw subgradient optimization of a function $f$ described as the following algorithm:

  1. start with any $\lambda^{(0)} \ge 0$ then repeat the following for $i = 1, 2, \dots$
  2. compute a subgradient $g$ for $f$ at $f(\lambda^{(i)})$
  3. set $\lambda^{(i+1)} = \max\{0, \lambda^{(i)} - t_ig\}$

What happens if $f(\lambda^{(i)})$ is undefined at any point? Can we project $\lambda^{(i)}$ to the domain of $f$? Will this maintain the theoretical guarantees of the algorithm?

Example: If we use subgradient optimization to find the minimum of $f=\{\lambda \mapsto -\lambda : 0 \le \lambda \le 1\}$ and pick $\lambda^{(0)} := 3$ this happens immediately. If we pick $\lambda^{(0)}$ to have a defined value, say $\lambda^{(0)} := 0.5$, we could still have a subgradient of $g=-1$ and a step size of $t:=2.5$. The next value would then also be $\lambda^{(1)} = \lambda^{(0)} - tg = 3$ with the same problem.

  • $\begingroup$ This is a projected subgradient algorithm for a problem with the constraint $\lambda \geq 0$. It's designed to work with functions that have subgradients at every point where $\lambda \geq 0$ and avoids points that don't satisfy that constraint. As stated in the algorithm, you need to start with a feasible $\lambda$. $\endgroup$ – Brian Borchers Aug 10 '18 at 15:02
  • $\begingroup$ Thanks. The problem I see is that even if you start with feasible point, the update with the gradient might move the point outside of the feasible region. In my second example, I started with 0.5 which is feasible and ended up with 3 which is not feasible. You mentioned people.brunel.ac.uk/~mastjjb/jeb/natcor_ip_rest.pdf to me in another question, but the description of the algorithm there also does not have a special case for this. All descriptions of the method I saw so far seem incomplete in that regard, i.e., they would fail on the example above. $\endgroup$ – Flogo Aug 10 '18 at 15:30
  • $\begingroup$ Is there a book that describes projected subgradient algorithms? In particular, do they come with the same guarantees as the normal subgradient algorithm about the limit of the value for appropriate step sizes? $\endgroup$ – Flogo Aug 10 '18 at 15:32
  • $\begingroup$ Amir Beck's recent SIAM textbook on convex optimization would be a good place to start. $\endgroup$ – Brian Borchers Aug 10 '18 at 16:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.