Convex Optimization Algorithm

A Convex Optimization Algorithm is an optimization algorithm that can be implemented by a convex optimization system to solve a convex optimization task.

• Context:
  • It can range from being a Centralized Convex Optimization Algorithm to being a Distributed Convex Optimization Algorithm.
  • …
• Example(s):
  • an Interior Point Algorithm.
  • a Subgradient Algorithm.
  • a Cutting-Plane Algorithm.
  • …
• Counter-Example(s):
  • …
• See: Expectation Maximization Algorithm, Improved Iterative Scaling Algorithm.

---

---

References

2014

• http://en.wikipedia.org/wiki/Convex_optimization#Methods
  • Convex minimization problems can be solved by the following contemporary methods:
    • "Bundle methods" (Wolfe, Lemaréchal, Kiwiel), and
    • Subgradient projection methods (Polyak),
    • Interior-point methods (Nemirovskii and Nesterov).
  • Other methods of interest:
    • Cutting-plane methods.
    • Ellipsoid method.
    • Subgradient method.
    • Dual subgradients and the drift-plus-penalty method.
  • Subgradient methods can be implemented simply and so are widely used. Dual subgradient methods are subgradient methods applied to a dual problem. The drift-plus-penalty method is similar to the dual subgradient method, but takes a time average of the primal variables.

2004

• (Boyd & Vandenberghe, 2004) ⇒ Stephen P. Boyd, and Lieven Vandenberghe. (2004). “Convex Optimization." Cambridge University Press. ISBN:0521833787
  • QUOTE: Convex optimization problems arise frequently in many different fields. This book provides a comprehensive introduction to the subject, and shows in detail how such problems can be solved numerically with great efficiency. The book begins with the basic elements of convex sets and functions, and then describes various classes of convex optimization problems. Duality and approximation techniques are then covered, as are statistical estimation techniques. Various geometrical problems are then presented, and there is detailed discussion of unconstrained and constrained minimization problems, and interior-point methods. The focus of the book is on recognizing convex optimization problems and then finding the most appropriate technique for solving them.

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.

---