Convex Optimization Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - "]] *** " to "]]. *** ") |
m (Text replacement - "lems]]" to "lem]]s") |
||
| Line 33: | Line 33: | ||
=== 2004 === | === 2004 === | ||
* ([[2004_ConvexOptimization|Boyd & Vandenberghe, 2004]]) ⇒ Stephen P. Boyd, and Lieven Vandenberghe. ([[2004]]). “[http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization]." Cambridge University Press. ISBN:0521833787 | * ([[2004_ConvexOptimization|Boyd & Vandenberghe, 2004]]) ⇒ Stephen P. Boyd, and Lieven Vandenberghe. ([[2004]]). “[http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization]." Cambridge University Press. ISBN:0521833787 | ||
** QUOTE: [[Convex Optimization Task|Convex optimization problem]]s arise frequently in many different [[fields]]. [[2004_ConvexOptimization|This book]] provides a comprehensive introduction to [[the subject]], and shows in detail how such [[Convex Optimization Task|problem]]s can be solved [[numerically]] with great [[efficiency]]. [[2004_ConvexOptimization|The book]] begins with the basic elements of [[convex set]]s and [[Convex Function|functions]], and then describes various classes of [[Convex Optimization Task|convex optimization | ** QUOTE: [[Convex Optimization Task|Convex optimization problem]]s arise frequently in many different [[fields]]. [[2004_ConvexOptimization|This book]] provides a comprehensive introduction to [[the subject]], and shows in detail how such [[Convex Optimization Task|problem]]s can be solved [[numerically]] with great [[efficiency]]. [[2004_ConvexOptimization|The book]] begins with the basic elements of [[convex set]]s and [[Convex Function|functions]], and then describes various classes of [[Convex Optimization Task|convex optimization problem]]s. [[Duality]] and [[approximation technique]]s are then covered, as are [[statistical estimation technique]]s. Various [[geometrical problem]]s are then presented, and there is detailed discussion of [[unconstrained]] and [[constrained minimization problem]]s, and [[interior-point method]]s. The focus of [[2004_ConvexOptimization|the book]] is on recognizing [[Convex Optimization Task|convex optimization problem]]s and then finding the most appropriate [[technique]] for solving [[Convex Optimization Task|them]]. | ||
=== 2003 === | === 2003 === | ||
Latest revision as of 04:27, 28 November 2023
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):
- 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:[1]
- "Bundle methods" (Wolfe, Lemaréchal, Kiwiel), and
- Subgradient projection methods (Polyak),
- Interior-point methods (Nemirovskii and Nesterov).
- Other methods of interest:
- 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.
- Convex minimization problems can be solved by the following contemporary methods:[1]
- ↑ For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by Ruszczyński and Boyd and Vandenberghe (interior point).
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.