(Convergence of the Subgradient Method) Consider the subgradient methodand q∗ is the optimal dual cost (this stepsize requires knowledge of q∗, which is very restrictive, but the following Exercise 10.37 removes this restriction). Assume that there exists at least one optimal dual solution.

(a) Use Eq. (10.16) to show that {µk} is bounded.

(b) Use the fact that {gk} is bounded (since the dual function is piecewise linear), and Eq. (10.16) to show that