Convex Optimization Task

A Convex Optimization Task is an optimization task that accepts a convex function (over convex sets).

• Context:
  • It can be solved by a Convex Optimization System (that implements a convex optimization algorithm).
• Example(s):
  • a Least Squares Optimization Task.
  • a Linear Programming Task.
  • a Convex Quadratic Programming Task (with linear constraint).
  • a Conic Optimization Task.
  • a Geometric Programming Task.
  • a Second Order Cone Programming Task.
  • a Semidefinite Programming Task.
  • an Entropy Maximization Task.
  • …
• Counter-Example(s):
  • Submodular Optimization.
  • Non-Convex Optimization.
• See: Convex Space, Unconstrained Optimization.

---

---

References

2015

• http://submodularity.org/
  • QUOTE: … Convex optimization has become a main workhorse for many machine learning algorithms during the past ten years. When minimizing a convex loss function for, e.g., training a Support Vector Machine, we can rest assured to efficiently find an optimal solution, even for large problems. …

2012

• http://en.wikipedia.org/wiki/Convex_optimization#Examples
  • The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:
    • Least squares.
    • Linear programming.
    • Convex quadratic minimization with linear constraints
    • Quadratically constrained Convex-quadratic minimization with convex quadratic constraints.
    • Conic optimization.
    • Geometric programming.
    • Second order cone programming.
    • Semidefinite programming.
    • Entropy maximization with appropriate constraints

2011

• http://en.wikipedia.org/wiki/Convex_optimization
  • Convex optimization, a subfield of mathematical optimization, studies the problem of minimizing convex functions over convex sets. Given a real vector space [math]\displaystyle{ X }[/math] together with a convex, real-valued function [math]\displaystyle{ f:\mathcal{X}\to \mathbb{R} }[/math] defined on a convex subset [math]\displaystyle{ \mathcal{X} }[/math] of [math]\displaystyle{ X }[/math], the problem is to find a point [math]\displaystyle{ x^* }[/math] in [math]\displaystyle{ \mathcal{X} }[/math] for which the number [math]\displaystyle{ f(x) }[/math] is smallest, i.e., a point [math]\displaystyle{ x^* }[/math] such that [math]\displaystyle{ f(x^*) \le f(x) }[/math] for all [math]\displaystyle{ x \in \mathcal{X} }[/math].

2007

• http://www.math.utk.edu/~vasili/refs/darpa07.MathChallenges.html
  • QUOTE: Mathematical Challenge Eight - Beyond Convex Optimization: Can linear algebra be replaced by algebraic geometry in a systematic way?

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.

---