Subgradient Methods
🛎️

Subgradient Methods

The subgradient method is a simple algorithm for minimizing a nondifferentiable convex function. The method looks much like the ordinary gradient method for differentiable functions but has several notable exceptions, i.e., it is not a descent method.
 

The subgradient method

Suppose is convex. To minimize , the subgradient method uses the following update equation
where is the -th iterate, is the -th step size, and is any subgradient of at , which is defined as follows:
Since the subgradient method is not a descent method, it is common to keep track of the best point found, i.e., the one with the smallest function value. At each step, we set
and set if , then we have

Step size rules

Several different types of step size rules are used.
  • Constant step size. is a constant, independent of
  • Constant step length. . This means that .
  • Square summable but not summable. The step sizes satisfy
One typical example is , where and .
  • Nonsummable diminishing. The step sizes satisfy
Step sizes that satisfy this condition are called diminishing step size rules. A typical example is , where .

Convergence results

There are many results on the convergence of the subgradient method. For constant step size and constant step length, the subgradient algorithm is guaranteed to converge within some range of the optimal value, i.e., we have
where denotes the optimal value of the problem, i.e., . This implies that the subgradient method finds an ε-suboptimal point within a finite number of steps. The number ε is a function of the step size parameter , and decreases with it.