Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

A Quadratic Program with Two Variables

Consider the problem

displaystylemin_x : x_1^2 - x_1x_2 + 2x_2^2 -3x_1 - 1.5 x_2 ~:~ -1 le x_1 le 2, ;; 0 le x_2 le 3 .

The problem is a quadratic program:

  • the constraints are affine inequalities in the decision vector x;

  • the objective function can be expressed as

f_0(x) = c^Tx + x^TQx

where

c = left( begin{array}{c} -3 -1.5 end{array}right), ;; Q = left( begin{array}{cc} 1 & -1/2 -1/2 & 2 end{array}right).

We check that Q is positive semi-definite by computing its eigenvalue decomposition:

Q = U Lambda U^T, ;; U = left( begin{array}{cc} -0.3827 & 0.9239 0.9239 & 0.3827 end{array}right), ;; Lambda = left( begin{array}{cc} 2.2071 & 0 0 & 0.7929 end{array}right),

and checking that the eigenvalues (appearing on the diagonal of Lambda) are non-negative.

alt text 

Geometric view of the quadratic program above. The problem is a QP since the objective function is quadratic convex, and the constraints are affine inequalities.