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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.