Subgradient method (General, Constrained optimization Convex Optimization (Non-linear))

Time Complexity

$O(n^{2} )$

Space Complexity

$O(n+L)$? words

(keep track of current guess x^{(k)}, and needs to compute subgradient g^{(k)})

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word/Real RAM

Year

1981

Reference

https://www.springer.com/gp/book/9783642821202