11.4 Convex optimization

Convex optimization is a powerful tool in data science and statistics, enabling efficient solutions to complex problems. It focuses on minimizing convex functions over convex sets, which guarantees a global optimum.

Key concepts include convex sets, functions, and optimization problems. Understanding these fundamentals allows data scientists to formulate and solve a wide range of practical problems, from machine learning to portfolio management.

Convex sets

• Convex sets play a crucial role in convex optimization as they define the feasible region of optimization problems
• Understanding the properties and characteristics of convex sets is essential for formulating and solving convex optimization problems in data science and statistics
• Convex sets exhibit favorable properties that make optimization problems more tractable and efficient to solve

Definition of convex sets

Top images from around the web for Definition of convex sets

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  Konvexní – Wikipedie View original

  Is this image relevant?

• 

  economics - Problem relating convex sets and optimization - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  Konvexní – Wikipedie View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition of convex sets

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  Konvexní – Wikipedie View original

  Is this image relevant?

• 

  economics - Problem relating convex sets and optimization - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  Konvexní – Wikipedie View original

  Is this image relevant?

1 of 3

• A set $C$ is convex if for any two points $x, y \in C$, the line segment connecting $x$ and $y$ is entirely contained within $C$
• Mathematically, $C$ is convex if for all $x, y \in C$ and $\theta \in [0, 1]$, $\theta x + (1-\theta)y \in C$
• Intuitively, a convex set has no indentations or holes and can be visualized as a solid, connected region

Examples of convex sets

• Euclidean balls: The set $\{x \in \mathbb{R}^n : \|x - x_0\| \leq r\}$ is a convex set for any $x_0 \in \mathbb{R}^n$ and $r > 0$
• Hyperplanes and half-spaces: The set $\{x \in \mathbb{R}^n : a^Tx = b\}$ (hyperplane) and $\{x \in \mathbb{R}^n : a^Tx \leq b\}$ (half-space) are convex sets for any $a \in \mathbb{R}^n$ and $b \in \mathbb{R}$
• Polyhedra: The set $\{x \in \mathbb{R}^n : Ax \leq b\}$ is a convex set for any matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$

Properties of convex sets

• Intersection of convex sets is convex: If $C_1$ and $C_2$ are convex sets, then $C_1 \cap C_2$ is also a convex set
• Convex combination of points in a convex set remains in the set: If $x_1, \ldots, x_k \in C$ and $\theta_1, \ldots, \theta_k \geq 0$ with $\sum_{i=1}^k \theta_i = 1$, then $\sum_{i=1}^k \theta_i x_i \in C$
• Projection onto a convex set is unique: For any point $x \in \mathbb{R}^n$ and a closed convex set $C$, there exists a unique point $y \in C$ that minimizes the Euclidean distance $\|x - y\|$

Convex functions

• Convex functions are a fundamental concept in convex optimization and play a central role in formulating and solving optimization problems in data science and statistics
• Many common loss functions and regularization terms used in machine learning are convex, making convex optimization techniques widely applicable

Definition of convex functions

• A function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is convex if its domain is a convex set and for all $x, y$ in the domain and $\theta \in [0, 1]$, $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$
• Geometrically, a function is convex if its epigraph (the set of points above the graph) is a convex set

Examples of convex functions

• Affine functions: $f(x) = a^Tx + b$ for any $a \in \mathbb{R}^n$ and $b \in \mathbb{R}$
• Quadratic functions: $f(x) = x^TQx + b^Tx + c$ for any positive semidefinite matrix $Q \in \mathbb{R}^{n \times n}$, $b \in \mathbb{R}^n$, and $c \in \mathbb{R}$
• Norms: $f(x) = \|x\|_p$ for any $p \geq 1$, including the Euclidean norm ($p=2$) and the Manhattan norm ($p=1$)

Properties of convex functions

• First-order condition: A differentiable function $f$ is convex if and only if $f(y) \geq f(x) + \nabla f(x)^T(y-x)$ for all $x, y$ in the domain
• Second-order condition: A twice differentiable function $f$ is convex if and only if its Hessian matrix $\nabla^2 f(x)$ is positive semidefinite for all $x$ in the domain
• Jensen's inequality: If $f$ is convex, then for any $x_1, \ldots, x_k$ in the domain and $\theta_1, \ldots, \theta_k \geq 0$ with $\sum_{i=1}^k \theta_i = 1$, $f(\sum_{i=1}^k \theta_i x_i) \leq \sum_{i=1}^k \theta_i f(x_i)$

Convex vs non-convex functions

• Convex functions have a single global minimum, while non-convex functions may have multiple local minima
• Optimizing convex functions is generally easier and more efficient than optimizing non-convex functions due to the absence of local minima that are not global minima
• Many optimization algorithms are guaranteed to converge to the global optimum for convex functions, while they may get stuck in local minima for non-convex functions

Convex optimization problems

• Convex optimization problems are a class of optimization problems where the objective function is convex and the feasible region is a convex set
• These problems arise frequently in various fields, including data science, statistics, machine learning, and signal processing
• Convex optimization problems have desirable properties that make them more tractable and efficient to solve compared to general non-convex optimization problems

Standard form of convex optimization

• The standard form of a convex optimization problem is: minimize $f(x)$ subject to $g_i(x) \leq 0$, $i = 1, \ldots, m$, and $h_j(x) = 0$, $j = 1, \ldots, p$
• Here, $f$ is a convex function (objective function), $g_i$ are convex functions (inequality constraints), and $h_j$ are affine functions (equality constraints)
• The feasible region, defined by the constraints, is a convex set

Types of convex optimization problems

• Linear programming (LP): The objective function and constraints are all linear
• Quadratic programming (QP): The objective function is quadratic, and the constraints are linear
• Second-order cone programming (SOCP): The objective function is linear, and the constraints are second-order cone constraints
• Semidefinite programming (SDP): The objective function is linear, and the constraints involve positive semidefinite matrix variables

Applications of convex optimization

• Portfolio optimization: Maximizing expected return while minimizing risk
• Least squares and regularized regression (Ridge, Lasso): Fitting linear models to data with different regularization techniques
• Support vector machines (SVM): Finding optimal hyperplanes for classification tasks
• Logistic regression: Modeling the probability of binary outcomes

Optimality conditions

• Optimality conditions are criteria that characterize the solutions of optimization problems
• These conditions provide necessary and sufficient conditions for a point to be an optimal solution
• Understanding optimality conditions is crucial for developing and analyzing optimization algorithms

First-order optimality conditions

• For unconstrained optimization problems, a necessary condition for $x^*$ to be a local minimum is $\nabla f(x^*) = 0$ (stationary point)
• For constrained optimization problems, the first-order necessary condition is the Karush-Kuhn-Tucker (KKT) conditions

Second-order optimality conditions

• For unconstrained optimization problems, a sufficient condition for $x^*$ to be a local minimum is $\nabla f(x^*) = 0$ and $\nabla^2 f(x^*) \succeq 0$ (positive semidefinite Hessian)
• For constrained optimization problems, second-order sufficient conditions involve the Hessian of the Lagrangian function

Karush-Kuhn-Tucker (KKT) conditions

• The KKT conditions are first-order necessary conditions for a point $x^*$ to be an optimal solution of a constrained optimization problem
• The KKT conditions involve the gradients of the objective function and constraints, as well as the Lagrange multipliers
• For convex optimization problems, the KKT conditions are also sufficient for optimality

Algorithms for convex optimization

• Various algorithms have been developed to solve convex optimization problems efficiently
• These algorithms exploit the properties of convex functions and sets to iteratively converge to the optimal solution
• The choice of algorithm depends on the specific structure of the problem, the size of the problem, and the desired accuracy

Gradient descent

• Gradient descent is a first-order iterative optimization algorithm that moves in the direction of the negative gradient of the objective function
• The update rule is $x^{k+1} = x^k - \alpha_k \nabla f(x^k)$, where $\alpha_k$ is the step size at iteration $k$
• Gradient descent converges to the optimal solution for convex functions with a properly chosen step size

Newton's method

• Newton's method is a second-order iterative optimization algorithm that uses both the gradient and the Hessian of the objective function
• The update rule is $x^{k+1} = x^k - [\nabla^2 f(x^k)]^{-1} \nabla f(x^k)$
• Newton's method converges faster than gradient descent near the optimal solution but requires computing the Hessian matrix

Interior-point methods

• Interior-point methods solve constrained optimization problems by converting them into a sequence of unconstrained or equality-constrained problems
• These methods maintain the iterates within the feasible region and gradually approach the boundary of the constraints
• Examples include the barrier method and the primal-dual interior-point method

Dual ascent methods

• Dual ascent methods solve the dual problem of a constrained optimization problem
• These methods iteratively update the dual variables to maximize the dual objective function
• Examples include the dual gradient ascent method and the dual coordinate ascent method

Duality in convex optimization

• Duality is a fundamental concept in optimization that relates an optimization problem (the primal problem) to another optimization problem (the dual problem)
• The dual problem provides a lower bound on the optimal value of the primal problem
• Duality is particularly useful in convex optimization, as it allows for the development of efficient algorithms and provides optimality conditions

Lagrangian duality

• The Lagrangian function $L(x, \lambda, \nu)$ is formed by adding the constraints to the objective function, weighted by the Lagrange multipliers $\lambda$ and $\nu$
• The dual function $g(\lambda, \nu)$ is defined as the infimum of the Lagrangian function over the primal variables $x$
• The dual problem is to maximize the dual function subject to $\lambda \geq 0$

Strong duality

• Strong duality holds when the optimal values of the primal and dual problems are equal
• For convex optimization problems that satisfy certain constraint qualifications (e.g., Slater's condition), strong duality holds
• Under strong duality, the optimal solutions of the primal and dual problems are related by the KKT conditions

Weak duality

• Weak duality states that the dual objective function value at any feasible point is always less than or equal to the primal objective function value at any feasible point
• This implies that the dual problem provides a lower bound on the optimal value of the primal problem
• Weak duality always holds, even for non-convex problems

Duality gap

• The duality gap is the difference between the primal and dual objective function values at a given pair of primal and dual feasible points
• For convex optimization problems that satisfy strong duality, the duality gap is zero at the optimal solutions
• The duality gap can be used as a measure of the suboptimality of a given primal-dual pair and is often used as a stopping criterion in optimization algorithms

Constrained convex optimization

• Constrained convex optimization problems involve minimizing a convex objective function subject to convex constraints
• The presence of constraints adds complexity to the optimization problem but also provides a way to incorporate domain knowledge and enforce feasibility
• Several methods have been developed to handle constraints in convex optimization problems

Equality constraints

• Equality constraints are of the form $h_j(x) = 0$, where $h_j$ is an affine function
• Equality constraints can be handled using the method of Lagrange multipliers, which introduces dual variables for each constraint
• The KKT conditions for problems with only equality constraints do not involve complementary slackness

Inequality constraints

• Inequality constraints are of the form $g_i(x) \leq 0$, where $g_i$ is a convex function
• Inequality constraints can be handled using the KKT conditions, which introduce non-negative dual variables for each constraint
• The complementary slackness condition in the KKT conditions ensures that the dual variables are zero when the corresponding constraint is inactive

Barrier methods

• Barrier methods convert a constrained optimization problem into a sequence of unconstrained problems by adding a barrier term to the objective function
• The barrier term is a function that approaches infinity as the iterates approach the boundary of the feasible region
• Examples of barrier functions include the logarithmic barrier and the inverse barrier

Penalty methods

• Penalty methods convert a constrained optimization problem into a sequence of unconstrained problems by adding a penalty term to the objective function
• The penalty term is a function that increases the objective function value when the constraints are violated
• Examples of penalty functions include the quadratic penalty and the $\ell_1$ penalty

Subgradient methods

• Subgradient methods are iterative optimization algorithms that can be used to minimize non-differentiable convex functions
• These methods are particularly useful when the objective function is not differentiable everywhere, such as in $\ell_1$-regularized problems
• Subgradient methods are simple to implement but may have slower convergence compared to other methods

Definition of subgradients

• A vector $g \in \mathbb{R}^n$ is a subgradient of a convex function $f$ at a point $x$ if $f(y) \geq f(x) + g^T(y-x)$ for all $y$ in the domain of $f$
• The set of all subgradients of $f$ at $x$ is called the subdifferential, denoted as $\partial f(x)$
• If $f$ is differentiable at $x$, then the subdifferential contains only the gradient, i.e., $\partial f(x) = \{\nabla f(x)\}$

Subgradient optimization algorithms

• The subgradient method is an iterative algorithm that updates the iterates using a subgradient of the objective function
• The update rule is $x^{k+1} = x^k - \alpha_k g^k$, where $g^k \in \partial f(x^k)$ and $\alpha_k$ is the step size
• The step size can be chosen in various ways, such as a constant step size, a diminishing step size, or a dynamic step size based on the subgradient norm

Convergence of subgradient methods

• Subgradient methods converge to the optimal solution under certain conditions on the step sizes, such as $\sum_{k=0}^{\infty} \alpha_k = \infty$ and $\sum_{k=0}^{\infty} \alpha_k^2 < \infty$
• The convergence rate of subgradient methods is typically slower than that of gradient-based methods, often $O(1/\sqrt{k})$ for the best iterate after $k$ iterations
• Variants of the subgradient method, such as the averaged subgradient method and the stochastic subgradient method, can improve the convergence properties

Proximal algorithms

• Proximal algorithms are a class of optimization algorithms that can handle non-smooth and constrained convex optimization problems
• These algorithms use the concept of proximal operators to handle the non-smooth terms in the objective function or the constraints
• Proximal algorithms have become popular in recent years due to their effectiveness in solving large-scale problems arising in machine learning and signal processing

Proximal operators

• The proximal operator of a convex function $f$ with parameter $\lambda > 0$ is defined as $\text{prox}_{\lambda f}(x) = \arg\min_y \left(f(y) + \frac