Convex Optimization Algorithm

A Convex Optimization Algorithm is an optimization algorithm that can solve a convex optimization task.

• Example(s):
  • an Interior Point Algorithm.
• See: Expectation Maximization Algorithm, Improved Iterative Scaling Algorithm.

---

---

References

2009

• http://en.wikipedia.org/wiki/Convex_optimization#Methods
  • QUOTE: Convex minimization problems can be solved by the following contemporary methods:
    • "Bundle methods" (Wolfe, Lemaréchal), and
    • Subgradient projection methods (Polyak),
    • Interior-point methods (Nemirovskii and Nesterov).
  • Other methods of interest:
    • Cutting-plane methods
    • Ellipsoid method
    • Subgradient method
  • Subgradient methods can be implemented simply and so are widely used.

2003

• (Sha & Pereira, 2003a) ⇒ Fei Sha, and Fernando Pereira. (2003). "Shallow Parsing with Conditional Random Fields." In: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (HLT-NAACL 2003). doi:10.3115/1073445.1073473
  • QUOTE: To obtain these results, we had to abandon the original iterative scaling CRF training algorithm for convex optimization algorithms with better convergence properties.

---