Convexity, Hessian, and quadratic programming

From second derivatives to positive semidefinite matrices, the mathematics behind convex QP.

Optimization & MetaheuristicsAdvanced

Explore more lessons View related project

Learning goal

Understand how Hessians characterize convexity, interpret positive semidefinite matrices, and connect these ideas to convex quadratic programming.

Prerequisites

Multivariable calculus
Basic linear algebra
Optimization fundamentals

What does convex mean?

A convex function has the property that the line segment between two points on its graph lies above the graph. Every local minimum of a convex function is also a global minimum.

Convexity definition

f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y),\qquad 0\le\theta\le1

Second derivatives and the Hessian

In one dimension, the second derivative describes curvature. In several variables, the Hessian plays the same role.

Hessian matrix

H_f(x)=\nabla^2 f(x)

Positive semidefinite condition

v^T H_f(x)v\ge0\qquad\forall v

Quadratic objectives

In convex QP, the quadratic objective contains x^T P x. When P is symmetric positive semidefinite, that quadratic term is convex.

Quadratic objective

f(x)=\frac12x^TPx+q^Tx

Role of P

P\succeq0\quad\Longrightarrow\quad f\;\text{convex}

A simple example

Two-variable function

f(x_1,x_2)=x_1^2+2x_2^2

Hessian

\nabla^2f=\begin{bmatrix}2&0\\0&4\end{bmatrix}

Both Hessian eigenvalues are positive, so the function is strictly convex.

Connection to the Convex QP Solver

In the Convex QP Solver project, positive semidefiniteness of P is part of the problem structure before the numerical method operates on the objective and constraints.

Convex QP

\min_x\;\frac12x^TPx+q^Tx\quad\text{s.t.}\quad Ax=b,\;Gx\le h

Exercises

Compute the Hessian of f(x,y)=x²+xy+y².
Determine whether the Hessian is positive definite or positive semidefinite.
Explain why convexity of the objective matters when analyzing a solver.

Related project

Convex Quadratic Programming Solver

From positive semidefinite P to numerical solution of a convex QP.

Open source

Working on a hard optimization problem?

Start with the mathematical structure before choosing the numerical method.

Start a conversation