Quadratic programming

Authors: Kayleigh Calder (kjc263), Colton Jacobucci (cdj59), Carolyn Johnson (cj456), Caleb McKinney (cdm235), Olivia Thomas (oat9) (5800 Fall 2024)
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

A quadratic program is an optimization problem that comprises a quadratic objective function bound to linear constraints.¹ Quadratic Programming (QP) is a common type of non-linear programming (NLP) used to optimize such problems.

One of the earliest known theories for QP was documented in 1943 by Columbia University’s H.B. Mann^2,3, but many are given credit for their early contributions to the field such as E. W. Barankin and R. Dorfman in their naval research throughout the 1950s⁴ and Princeton University’s Wolfe and Frank for their research in 1956.⁵ The field has since made other prominent strides, such as when Harry Markowitz famously received the Nobel Prize in Economics in 1990 for his application of QP in optimizing his portfolio’s financial risk and reward.⁶

QP is essential to the field of optimization for multiple reasons. Firstly, quadratic problems can often be applied to real world applications due to the quadratic nature of variance, the sum of squares deviation used to represent uncertainty.⁶ QP can also be applied to a wide variety of real-world problems such as scheduling, planning, flow computations, engineering modeling, design and control, game theory, and economics.⁷ Secondly, QP is commonly used as a steppingstone for more general optimization problems such as sequential quadratic programming and augmented Lagrangian methods.¹

Algorithm Discussion

General Problem Fomulation

Quadratic programming problems are typically formatted as minimization problems, and the general mathematical formulation is:

minimize $q(x)={\frac {1}{2}}x^{T}Qx+c^{T}x$

subject to:

$Ax\geq b$

$x\geq 0$

Where:

• $x\in R^{n}$ is the decision variable vector.
• $Q\in R^{n\times n}$ is a symmetric, positive semi-definite $n\times n$ matrix representing the quadratic coefficients.
• $A\in R^{m\times n}$ is the inequality constraint matrix.
• $b\in R^{m}$ is an $m$ dimensional vector representing a constraint boundary.
• $c\in R^{n}$ is a linear coefficient vector.

Dual Formulation

The general mathematical formulation for the QP dual is:

maximize $q(x,y)=b^{T}y-{\frac {1}{2}}x^{T}Qx$

subject to:

$A^{T}y-Qx+s=c$

$y,s\geq 0$

Where:

• $y\in R^{m}$ is an m-dimensional vector dual variable.
• $x\in R^{n}$ is the prime decision variable.
• $s\in R^{n}$ is the slack variable.
• $Q\in R^{n\times n}$ is a symmetric, positive semi-definite $n\times n$ matrix representing the quadratic coefficients.
• $A\in R^{m\times n}$ is the inequality constraint matrix.
• $b\in R^{m}$ is an $m$ dimensional vector representing a constraint boundary.
• $c\in R^{n}$ is a linear coefficient for the dual target.

The general conditions for using QP for an optimization problem begin with having a quadratic objective function accompanied by linear constraints. For convex problems, Q defined in the equation above must be positive semi-definite; if not, there may be multiple local solutions meeting minimization criteria and deemed non-convex. As later sections in this paper will discuss, problem dimensions may vary in size, but it is not an issue as certain quadratic algorithms are tailored to meet computational demand. Finally, the feasibility region must be non-empty- otherwise there will be no solution.

Active Set Methods

The active set algorithm is a method used to solve quadratic programming problems by iteratively identifying and working with the set of constraints that are most likely to influence the solution, called the active set. More specifically, the algorithm maintains a subset of constraints that are treated as equalities at each step, solving a simplified quadratic programming problem for this subset. Constraints can be added or removed from the active set as the solution progresses until optimality conditions are satisfied.

When to Use

Active set methods are best suited for most linear programming problems, particularly those with manageable dimensions, as they exploit the problem's structure and update estimates of active constraints iteratively. However, for problems where nonlinearity or degeneracy complicates the constraint structure, active set methods, as a broader class, are useful since they generalize the simplex approach to handle quadratic or nonlinear constraints. In cases with large-scale problems or poor simplex performance due to its exponential worst-case complexity, alternative methods like interior-point techniques may be more appropriate.

Implementation Steps

1. Start with an Initial Solution and Active Set
   • Begin with a feasible point that satisfies all constraints.
   • Identify which constraints are active (equality constraints or inequality constraints that are tight).
2. Iterative Process:
   • Solve a Reduced Problem: Fix the active constraints as equalities and solve the resulting smaller QP problem.
   • Check Optimality: Verify if the current solution satisfies the Karush-Kuhn-Tucker conditions.
   • Update the Active Set:
     • Add violated constraints to the active set if they are not satisfied.
     • Remove constraints from the active set if they are no longer binding.
3. Repeat Until Convergence:
   • Iterate through the process until the optimal solution is found, ensuring all constraints are satisfied.

Pseudocode

This is the algorithm for Active-Set Method for Convex QP where:

• $x\in R^{n}$ is the decision variable vector.
• $G\in R^{n\times n}$ is a symmetric, positive semi-definite $n\times n$ matrix representing the quadratic coefficients.
• $c\in R^{n}$ is a linear coefficient vector.
• $W$ represents the active constraints.

Compute a feasible starting point $x_{0}$; Set $W_{0}$ to be a subset of the active constraints at $x_{0}$; for $k=0,1,2...$

Solve for $p_{k}={\frac {1}{2}}x_{k}^{T}Gx_{k}+c^{T}x_{k}$

if $p_{k}=0$

Compute Lagrange multipliers ${\hat {\lambda }}_{i}$ that satisfy $\Sigma _{i\epsilon {\hat {W}}}a_{i}{\hat {\lambda }}_{i}=g=G{\hat {x}}+c,$ with ${\hat {W}}=W_{k}$

if ${\hat {\lambda }}_{i}\geq 0$ for all $i\in W_{k}\cap \jmath$

stop with solution $x^{*}=x_{k};$

else

$j\longleftarrow$ arg $min_{i\in W_{k}\cap \jmath }{\hat {\lambda }}_{j};$

$x_{k+1}\longleftarrow x_{k};W_{k+1}\longleftarrow W_{k}\ \{j\};$

Else $(p_{k}\neq 0)$

Compute $a_{k}=min(1,min({\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}}))$

$x_{k+1}\longleftarrow x_{k}+a_{k}p_{k};$

if there are blocking constraints:

obtain $W_{k+1}$ by adding one of the blocking constraints to $W_{k};$

else

$W_{k+1}\longleftarrow W_{k};$

end (for)

Interior Point Methods

Interior-point methods, developed in the 1980s, are a class of algorithms for solving large-scale linear programs using concepts from nonlinear programming. Unlike the active set methods, which navigate along the boundaries of the feasible region by testing vertices, interior-point methods approach the solution from within or near the interior, avoiding boundary constraints. These methods were inspired by the simplex method's poor worst-case complexity and the desire for algorithms with stronger theoretical guarantees, such as the ellipsoid method and Karmarkar's algorithm.

When to Use

Interior-point methods are particularly effective for large-scale optimization problems where the simplex method's boundary-focused approach may struggle. They require fewer iterations than simplex, although each iteration is computationally more intensive. Modern primal-dual interior-point methods are efficient, robust, and form the foundation of many current optimization software tools, making them the preferred choice for solving large or complex linear programs.

Implementation Steps (Convex Quadratic Program with a Positive Semi-Definite Matrix)

1. Initial
   • Analyze the optimization problem and constraints
   • Add slack variables to problem to account for inequalities (if applicable) and write problem in general form and take barrier approach by adding in logarithmic component
2. Iterative Process
   • Define the KKT conditions
   • Define a complementary measure
   • Define the perturbed KKT condition
   • Apply Newton’s method to formulate a system of linear equations
3. Solve
   • Solve and iterate until convergence.

Pseudocode

This is the psuedocode for the Basic Interior-Point Algorithm where:

• $A$ is a matrix of constraint coefficients.
• $b$ is a vector of constraints.
• $l$ represents the lower bounds on the decision variables.
• $u$ represents the upper bounds on the decision variables.
• $\mu$ is the barrier parameter; a small positive scalar controlling the size of the barrier term added to enforce inequality constraints.
• $\in$ is the convergance tolerance for stopping criteria.
• $\alpha$ is the step size for the line search during iterations.
• $k$ is the iteration number.
• $Q$ is the quadratic term coefficient.
• $c$ is the linear term coefficient.

Choose $x_{0}$ and $s_{0}\geq 0$, and compute initial values for the multipliers $y_{0}$ and $z_{0}\geq 0$.

Select an initial barrier parameter $\mu _{0}>0$ and parameters $\sigma ,\tau \in (0,1)$. Set $k\leftarrow 0$.

repeat until a stopping test for the nonlinear program is satisfied.

repeat unitl $E(x_{k},s_{k},y_{k},z_{k};\mu _{k})\leq \mu _{k}$

Solve ${\begin{bmatrix}\bigtriangledown _{xx}^{2}L&0&-A_{E}^{T}(x)&-A_{i}^{T}(x)\\0&Z&0&S\\A_{E}(x)&0&0&0\\A_{i}(x)&-I&0&0\end{bmatrix}}$${\begin{bmatrix}p_{x}\\p_{s}\\p_{y}\\p_{z}\end{bmatrix}}$$=-{\begin{bmatrix}\bigtriangledown f(x)-A_{E}^{T}(x)y-A_{i}^{T}(x)z\\Sz-\mu e\\c_{E}(x)\\c_{i}(x)-s\end{bmatrix}}$to obtain the search direction $p=(p_{x},p_{s},p_{y},p_{z});$

Compute $\alpha _{s}^{max},\alpha _{z}^{Max}$ using:

$\alpha _{s}^{max}=max\{\alpha \in (0,1):s+\alpha p_{s}\geq (1-\tau )s$

$\alpha _{z}^{max}=max\{\alpha \in (0,1):z+\alpha p_{s}\geq (1-\tau )z$

Compute $(x_{k+1},s_{k+1},y_{k+1},z_{k+1})$ using:

$x^{+}=x+a_{s}^{max}p_{x},s^{+}=s+a_{s}^{max}p_{s},$

$y^{+}=x+a_{z}^{max}p_{y},z^{+}=z+a_{z}^{max}p_{z},$

Set $\mu _{k+1}\leftarrow \mu _{k}$ and $k\leftarrow k+1;$

end

Choose $\mu _{k}\in (0,\mu _{k});$

end

Gradient Projection Methods

The gradient projection method is an optimization technique used to solve constrained problems, particularly those with simple bound or inequality constraints. It combines gradient descent with a projection step that ensures iterates remain within the feasible region by projecting them back onto the constraint set. The method is iterative and adjusts the search direction based on the negative gradient of the objective function, while ensuring feasibility at each step. This approach is widely used for convex problems and has extensions for handling more complex constraint sets.

When to Use

The gradient projection method is best suited for problems with simple constraints, such as box constraints or convex inequality constraints, where projection onto the feasible region can be performed efficiently. It is effective for convex optimization problems where gradient-based methods converge to global optima. This method is often employed in large-scale optimization, machine learning, and signal processing applications due to its simplicity and ease of implementation. However, it may be less efficient for problems with complex or nonconvex constraints. Instead, other methods, such as active-set or interior-point methods, may be more appropriate.

Implementation Steps

1. Initial
   1. Start by analyzing and visualizing the constraints. Pay special attention to constraints that are box-defined (e.g., variable bounds) or convex inequalities, as these are essential for the efficient execution of the gradient projection method and establish the feasibility region.
   2. Choose an initial feasible point that is within the constraints of the problem, this will be the starting point of the soon to be developed piecewise-linear path
   3. Find the gradient of the objective function
2. Develop Piecewise linear path          
   1. Insert the initial feasible point into the gradient of the objective function.
   2. Define the descent direction and project onto the feasible region with initial feasible point. This line will define the piecewise-linear path.
3. Find the Cauchy point
   1. Analyze the path where the line segment breaks or changes its projected path on the feasibility region
   2. Compute the value of each breakpoint point set by substituting them into the piecewise-linear path equation
   3. Write the quadratic of this line segment with respect to these breakpoints
   4. Differentiate the quadratic with respect to the new breakpoint
   5. Identify if minimizer was found, if not, analyze the next breakpoint set
4. Refine and execute
   1. Update the piecewise-linear path decision variable to include the minimizer
   2. Update the active set based on the new solution found with the minimizer
   3. Find the new gradient value with this point, if converged then the minimum has been found. If not, iterate and repeat steps 1.2-4.3.

Pseudocode

This is the pseudocode for the gradient projection method algorithm where:

• $A$ is a matrix of constraint coefficients.
• $x\in R^{n}$ is the decision variable vector.
• $G\in R^{n\times n}$ is a symmetric, positive semi-definite n x n matrix representing the quadratic coefficients.
• $c\in R^{n}$ is a linear coefficient vector.
• $l$ represents the lower bounds on the decision variables.
• $u$ represents the upper bounds on the decision variables.

Compute a feasible starting point $x_{0};$ for $k=0,1,2,...$

if $x^{k}$ satisfies the KKT conditions for the quadratic programming problem:

minimize $q={\frac {1}{2}}x^{T}Gx+x^{T}c$

subject to $l\leq x\leq u$

stop with solution $x^{*}=x^{k};$

Set $x=x^{k}$ and find the Cauchy point $x^{c};$

Find an approximate solution $x^{+}$ of:

minimize $q={\frac {1}{2}}x^{T}Gx+x^{T}c$

subject to $x_{i}=x_{i}^{c},i\in A(x^{c}),$ $l_{i}\leq x_{i}\leq \mu _{i},i\not \in A(x^{c})$

such that $q(x^{+})\leq q(x^{+})\leq q(x^{c})$ and $x^{+}$ is feasible;

$x^{k+1}\leftarrow x^{+};$

end(for)

Convexity in Quadratic Programming

Convex quadratic programming problems occur when Q is positive semi-definite guarantee that the problem has a global minimum. Convex quadratic programming problems occur when Q is not positive semi-definite and the solutions may involve local minima, requiring more advanced techniques for global optimization (e.g., branch-and-bound, global optimization methods).

Numerical Examples

Examples are provided for solving convex and non-convex quadratic program optimizations using Active Set, Simplex-Like, and Branch and Bound methods.

Active Set Method Example

Step-by-step instructions for determining the optimal solution of the following quadratic programming problem are provided:

minimize $f(x_{1},x_{2})=5x_{1}^{2}+8x_{2}^{2}-10x_{1}x_{2}-50x_{1}-80x_{2}$

subject to the constraints:

1. $g_{1}(x)=x_{1}+x_{2}-10\leq 0$
2. $g_{2}(x)=-x_{1}-x_{2}+5\leq 0$
3. $g_{3}(x)=x_{1}-3x_{2}+15\leq 0$

Step 1: Reformat Constraints as Necessary

Constraints should be reformatted to be $\leq 0$. All constraints are currently in this format; therefore, no changes are needed.

Step 2: Construct the Gradients

Compute the gradients for the objective function and constraints.

• $\bigtriangledown f={\begin{bmatrix}10x_{1}-10x_{2}-50\\16x_{2}-10x_{1}-80\end{bmatrix}}$
• $\bigtriangledown g_{1}={\begin{bmatrix}1\\1\end{bmatrix}}$
• $\bigtriangledown g_{2}={\begin{bmatrix}-1\\-1\end{bmatrix}}$
• $\bigtriangledown g_{3}={\begin{bmatrix}1\\-3\end{bmatrix}}$

Step 3: Determine if There is a Feasible Solution with All Constraints Set to Active

The system of equations can be solved to determine if there is a feasible solution with all 3 constraints set to active. First, solve for  using constraint (1) and substitute it into constraint (2).

From $g_{1}(x)=0,x_{1}+x_{2}=10\rightarrow x_{1}=-x_{2}+10$

$-x_{1}-x_{2}+5=0$

$-(-x_{2}+10)-x_{2}+5=0$

$x_{2}-10-x_{2}+5=0$

$-10+5=0$

$-5=0$

Solving the system with all constraints active is infeasible. This is because the rows of the coefficient matrix are linearly dependent. The system does not have a unique solution. Thus, the next steps will be to reduce the number of active constraints to determine a feasible solution.

Step 4: Determine Solution with Constraints (1) and (2) Set to Active

As determined in Step 3, solving with constraints (1) and (2) result in a contradiction. Thus, this solution is infeasible.

Step 5: Determine Solution with Constraints (1) and (3) Set to Active

Substitute $x_{1}$ using constraint (1) into constraint (3).

From $g_{1}(x)=0,x_{1}+x_{2}=10\rightarrow x_{1}=-x_{2}+10$

$x_{1}-3x_{2}+15=0$

$(-x_{2}+10)-3x_{2}+15=0$

$-4x_{2}+25=0$

$-4x_{2}=-25$

$x_{2}={\frac {25}{4}}=6.25$

Substitute $x_{2}=6.25$ into constraint (1).

$x_{1}=-x_{2}+10$

$x_{1}=-(6.25)+10$

$x_{1}=3.75$

Check whether the solution satisfies primal feasability for constraint (2), meaning $g_{2}\leq 0$:

$g_{2}(3.75,6.25)=-(3.75)-(6.25)+5=-5$

Primal feasibility is satisfied since $g_{2}(3.75,6.25)\leq 0$. Thus, the solution $(x_{1},x_{2})=(3.75,6.25)$ is feasible.

Step 6: Determine Solution with Constraints (2) and (3) Set to Active

Substitute $x_{1}$ using constraint (2) into constraint (3).

From $g_{2}(x)=0,-x_{1}-x_{2}+5=0\rightarrow x_{1}=-x_{2}+5$

$x_{1}-3x_{2}+15=0$

$(-x_{2}+5)-3x_{2}+15=0$

$-4x_{2}+20=0$

$-4x_{2}=-20$

$x_{2}={\frac {20}{4}}=5$

Substitute $x_{2}=5$ into constraint (2).

$x_{1}=-x_{2}+5$

$x_{1}=-(5)+5$ = 0

Check whether the solution satisfies primal feasibility for constraint (1), meaning $g_{1}\leq 0$:

$g_{1}(0,5)=0=5-10=-5$

Primal feasibility is satisfied since $g_{1}(0,5)\leq 0$. Thus, the solution $(x_{1},x_{2})=(0,5)$ is feasible.

Step 7: Solve Objective Function Using Feasible Solutions

$f(x_{1},x_{2})=f(3.75,6.25)$

$f(3.75,6.25)=5(3.75)^{2}+8(6.25)^{2}-10(3.75)-50(3.75)-80(6.25)=-539.0625$

$f(x_{1},x_{2})=f(0,5)$

$f(0,5)=5(0)^{2}+8(5)^{2}-10(0)-50(0)-80(5)=-200$

Step 8: Determine Optimal Solution

The feasible solution with the minimum value is at $f(3.75,6.25)=-539.0625$ . Thus, this is the optimal solution.

Simplex-Like Method Example

Step-by-step instructions for determining the optimal solution of the following quadratic programming problem are provided:

Minimize $f(x_{,}x_{2})={\frac {1}{2}}(x_{1}^{2}+3x_{2}^{2})+2x_{1}+6x_{2}$

Subject to the constraints:

1. $x_{1}+x_{2}\leq 5$
2. $2x_{1}+x_{2}\leq 8$
3. $x_{1}\geq 0$
4. $x_{2}\geq 0$

Step 1: Reformat Constraints as Necessary

Equation constraints should be reformatted to be $\leq 0$ to solve for standard form. All constraints are currently in this format; therefore, no changes are needed. Non-negativity constraints should remain $\geq 0$.

Step 2: Determine if the Objective Function and Constraints are Convex

To use the Simplex-like Method, both the objective function and constraints must be convex. For the objective function, convexity is proven by identifying if the eigenvalues of the Hessian matrix are $\geq 0$. For the constraints, convexity is proven by identifying if the constraints are linear.

Step 2.1 Find the Eigenvalues of the Hessian Matrix for the Objective Function

Solve for the first order partial derivatives.

$f(x_{1},x_{2})={\frac {1}{2}}(x_{1}^{2}+3x_{2}^{2})+2x_{1}+6x_{2}$

${\partial f \over \partial x_{1}}={\frac {1}{2}}\times 2x_{1}+2=x_{1}+2$

${\partial f \over \partial x_{2}}={\frac {1}{2}}\times 2\times 3x_{2}+6=3x_{2}+6$

Solve for the second order partial derivatives.

${\partial ^{2}f \over \partial x_{1}^{2}}=1$

${\partial ^{2}f \over \partial x_{2}^{2}}=3$

${\partial ^{2}f \over \partial x_{1}\partial x_{2}}=0$

${\partial ^{2}f \over \partial x_{2}\partial x_{1}}=0$

Construct the Hessian Matrix

$H={\begin{bmatrix}1&0\\0&3\end{bmatrix}}$

Determine the eigenvalues

$\lambda _{1}=1$

$\lambda _{2}=3$

The objective function is convex as $\lambda _{1}\lambda _{2}\geq 0$.

Step 2.2 Determine if the Constraints are Convex

1. $x_{1}+x_{2}\leq 5$
2. $2x_{2}+x_{2}\leq 8$
3. $x_{1}\geq 0$
4. $x_{2}\geq 0$

All constraints are linear and therefore convex. This method can be applied to solve as both the objective function and constraints are convex.

Step 3: Determine the Feasible Region

Change the inequalities to equalities.

1. $x_{1}+x_{2}=5$
2. $2x_{2}+x_{2}=8$
3. $x_{1}=0$
4. $x_{2}=0$

Solve for the intersection points using all combinations of the constraints.

• $x_{1}=0$ and $x_{1}+x_{2}=5$
  • $0+x_{2}=5$
  • Interesection at (0,5)
• $x_{1}=0$ and $2x_{1}+x_{2}=8$
  • $2(0)+x_{2}=8$
  • Intersection at (0,8)
• $x_{1}+x_{2}=5$ and $x_{2}=0$
  • $x_{1}+0=5$
  • Intersection at (5,0)
• $2x_{1}+x_{2}=8$ and $x_{2}=0$
  • $2x_{1}+0=8$
  • $x_{1}={\frac {8}{2}}=4$
  • Intersection at (4,0)
• $x_{1}+x_{2}=5$ and $2x_{1}+x_{2}=8$
  • $2x_{1}+x_{2}-x_{1}+x_{2}=8-5$
  • $x_{1}=3$
• Substitute $x_{1}=3$ into the first equation
  • $3+x_{2}=5$
  • $x_{2}=2$
  • Interesection at (3,2)

The feasible region is bounded & convex in the intersection points (0,5), (0,8), (5,0), (4,0), (3,2).

Step 4: Solve Objective Function using Feasible Solutions

$f(x_{1},x_{2})={\frac {1}{2}}(x_{1}^{2}+3x_{2}^{2})+2x_{1}+6x_{2}$

• Solve at (0,5)
  • $f(0,5)={\frac {1}{2}}(0^{2}+3(5)^{2})+2(0)+6(5)$
  • $f(0,5)={\frac {1}{2}}(75)+0+30$
  • $f(0,5)=67.5$
• Solve at (0,8)
  • $f(0,8)={\frac {1}{2}}(0^{2}+3(8)^{2})+2(0)+6(8)$
  • $f(0,8)={\frac {1}{2}}(192)+0+48$
  • $f(0,8)=144$
• Solve at (5,0)
  • $f(5,0)={\frac {1}{2}}(5^{2}+3(0)^{2})+2(5)+6(0)$
  • $f(5,0)={\frac {1}{2}}(25)+10+0$
  • $f(5,0)=22.5$
• Solve at (4,0)
  • $f(4,0)={\frac {1}{2}}(4^{2}+3(0)^{2})+2(4)+6(0)$
  • $f(4,0)={\frac {1}{2}}(16)+8+0$
  • $f(4,0)=16$
• Solve at (3,2)
  • $f(3,2)={\frac {1}{2}}(3^{2}+3(2)^{2})+2(3)+6(2)$
  • $f(3,2)={\frac {1}{2}}(21)+6+12$
  • $f(3,2)=28.5$

Step 5: Identify Edge Solutions along the Feasible Region

• $P_{1}=(3,2)$ and $P_{2}=(5,0)$
• Parameterize the edge to represent the points along each edge
  • $x_{1}(t)=x_{1P1}+t(x_{1P2}-x_{1P1})=3+t(5-3)$
  • $x_{2}(t)=x_{2P1}+t(x_{2P2}-x_{2P1})=2+t(0-2)$
    • $x_{1}(t)=3+2t$
    • $x_{2}(t)=2-2t$
    • $0\leq t\leq 1$
  • Use the parameterization in the objective function
  • $f(x_{1}(t),x_{2}(t))={\frac {1}{2}}(x_{1}(t)^{2}+3x_{2}(t)^{2})+2x_{1}(t)+6x_{2}(t)$
    • $f(x_{1}(t),x_{2}(t))={\frac {1}{2}}((3+2t)^{2}+3(2-2t)^{2})+2(3+2t)+6(2-2t)$
    • $={\frac {1}{2}}(9+12t+4t^{2}+12-24t+12t^{2})+6+4t+12-12t$
    • $={\frac {1}{2}}(21-12t+16t^{2})+18-8t$
    • $=8t^{2}-14t+28.5$
  • Solve for $t$ using the parameterization objective function
  • $f(x_{1}(t),x_{2}(t))=8t^{2}-14t+28.5$
    • ${\frac {\partial f}{\partial t}}=16t-14=0$
    • $t={\frac {7}{8}}$ which is within [0,1] and therefore a solution.
  • Solve for $x_{1}$ and $x_{2}$ using the parameterization equations and $t$ value
    • $x_{1}=3+2({\frac {7}{8}})=4.75$
    • $x_{2}=2-2({\frac {7}{8}})=0.25$
  • Solve the objective function for the edge solution
    • $f(4.75,0.25)={\frac {1}{2}}(4.75^{2}+3(0.25)^{2})+2(4.75)+6(0.25)=22.375$
  • Verify the minimum objective solution
    • At $t=0,f(3,2)=28.5$
    • At $t=1,f(5,0)=22.5$
    • At $t={\frac {7}{8}},f(4.75,0.25)=22.375$
    • The minimum solution is at $f(4.75,0.25)=22.375$

Repeat process for other edges

• $P_{1}=(3,2)$ and $P_{2}=(0,5)$
  • $x_{1}(t)=3-3t$
  • $x_{2}(t)=2+3t$
  • $0\leq t\leq 1$
  • $f(x_{1}(t),x_{2}(t))={\frac {1}{2}}((3-3t)^{2}+3(2+3t)^{2})+2(3-3t)+6(2+3t)$
    • $={\frac {1}{2}}(9-18t+9t^{2}+12+36t+27t^{2})+6-6t+12+18t$
    • $={\frac {1}{2}}(21+18t+36t^{2})+18+12t$
  • $f(x_{1}(t),x_{2}(t))=18t^{2}+21t+28.5$
    • ${\frac {\partial f}{\partial t}}=36t+21=0$
    • $t=-{\frac {7}{12}}$ which is not within [0,1] and therefore not a solution
  • At $t=0,f(3,2)=28.5$
  • At $t=1,f(0,5)=67.5$
  • The minimum solution is at $f(3,2)=28.5$
• $p_{1}=(0,8)$ and $p_{2}=(4,0)$
  • $x_{1}(t)=0+4t$
  • $x_{2}(t)=8-8t$
  • $0\leq t\leq 1$
  • $f(x_{1}(t),x_{2}(t))={\frac {1}{2}}((4t)^{2}+3(8-8t)^{2})+2(4t)+6(8-8t)$
    • $={\frac {1}{2}}(16t^{2}+192-384t+192t^{2})+8t+48-48t$
    • $={\frac {1}{2}}(208t^{2}-384t+192)+8t+48-48t$
  • $f(x_{1}(t),x_{2}(t))=104t^{2}-232t+144$
    • ${\frac {\partial f}{\partial t}}=208t-232=0$
    • $t={\frac {232}{208}}$ which is not within [0,1] and therefore not a solution
  • At $t=0,f(0,8)=144$
  • At $t-1,f(4,0)=16$
  • The minimum solution is at $f(4,0)=16$
• $p_{1}=(0,5)$ and $p_{2}=(0,8)$
• Since $x_{1}=0$ is fixed in both $p_{1}$ and $p_{2}$, solve objective function directly
  • $f(0,x_{2})={\frac {1}{2}}(0^{2}+3x_{2}^{2})+2(0)+6x_{2}={\frac {3}{2}}x_{2}^{2}+6x_{2}$
  • ${\frac {\partial f}{\partial x_{2}}}=3x_{2}+6$
    • $x_{2}=-2$ which is not within [5,8] and therefore not a solution
  • At $x_{2}=5,f(0,5)=67.5$
  • At $x_{2}=8,f(0,8)=144$
    • The minimum solution is at $f(0,5)=67.5$
• $p_{1}=(4,0)$ and $p_{2}=(5,0)$
• Since $x_{2}=0$ is fixed in both $p_{1}$ and $p_{2}$, solve objective function directly
  • $f(x_{1},0)={\frac {1}{2}}(x_{1}^{2}+0)+2x_{1}+0={\frac {1}{2}}x_{1}^{2}+2x_{1}$
  • ${\frac {\partial f}{\partial x_{1}}}=x_{1}+2$
    • $x_{1}=-2$ which is not within [4,5] and therefore not a solution
  • At $x_{1}=4,f(4,0)=16$
  • At $x_{1}=5,f(5,0)=22.5$
  • The minimum solution is at $f(4,0)=16$

Step 6: Determine the Optimal Solution

Compare all intersection and edge solutions to minimize the objective function. $P_{1}=(3,2)$ and $p_{2}=(5,0)$

• The minimum solution is at $f(4.75,0.25)=22.375$

$P_{1}=(3,2)$ and $P_{2}=(0,5)$

• The minimum solution is at f(3,2) = 28.5

$P_{1}=(0,8)$ and $p_{2}=(4,0)$

• The minimum solution is at $f(4,0)=16$

$P_{1}=(0,5)$ and $P_{2}=(0,8)$

• The minimum solution is at $f(0,5)=67.5$

$p_{1}=(4,0)$ and $p_{2}=(5,0)$

• The minimum solution is at $f(4,0)=16$

The optimal solution occurs at $f(4,0)=16$

Non-Convex Example Using Branch and Bound

Step-by-step instructions for determining the optimal solution of the following quadratic programming problem using branch and bound are provided:

maximize $f(x_{1},x_{2})=-x_{1}^{2}-x_{2}^{2}+5x_{1}+4x_{2}$

subject to the constraints:

1. $x_{1}\in \{0,1,2\}$
2. $0\leq x_{2}\leq 3$

Step 1: Determine if the Objective Function and Constraints are Convex

To determine if the objective function is convex, its eigenvalues are determined. The constraints are then analyzed for linearity.

Step 1.1 Find the Eigenvalues of the Hessian Matrix for the Objective Function

Solve for the first order partial derivatives.

$f(x_{1},x_{2})=-x_{1}^{2}-x_{2}^{2}+5x_{1}+4x_{2}$

${\partial f \over \partial x_{1}}=-2x_{1}+5$

${\partial f \over \partial x_{2}}=-2x_{2}+4$

Solve for the second order partial derivatives.

${\partial ^{2}f \over \partial x_{1}^{2}}=-2$

${\partial ^{2}f \over \partial x_{2}^{2}}=-2$

${\partial ^{2}f \over \partial x_{1}\partial x_{2}}=0$

${\partial ^{2}f \over \partial x_{2}\partial x_{1}}=0$

Construct the Hessian Matrix.

$H={\begin{bmatrix}-2&0\\0&-2\end{bmatrix}}$

Determime the eigenvalues.

$\lambda _{1}=-2$

$\lambda _{2}=-2$

The objective function is negative semi-definite since both eigenvalues are negative. This makes the objective function non-convex.

Step 1.2 Determine if the Constraints are Convex

The non-binary integer constraint for this given quadratic programming problem makes this example non-convex.

Step 2: Determine the Relaxed Solution

To help determine whether to prune future branches, the optimization will be solved by relaxing the integer constraint from $x_{1}\in \{0,1,2\}$  to $0\leq x_{1}\leq 2$. Thus, the relaxed problem formulation is as follows:

maximize $f(x_{1},x_{2})=-x_{1}^{2}-x_{2}^{2}+5x_{1}+4x_{2}$

subject to the constraints:

1. $0\leq x_{2}\leq 2$
2. $0\leq x_{2}\leq 3$

To solve the relaxed formulation the gradients are set to 0 and the system of equations is solved.

From $g_{1}(x)=0,-2x_{1}=-5\rightarrow x_{1}=2.5$

From $g_{2}(x)=0,-2x_{2}=-4\rightarrow x_{2}=2$

$f(2.5,2)=-(2.5)^{2}-(2)^{2}+5(2.5)+4(2)$

$f(2.5,2)=-6.25-4+12.5+8=10.25$

The relaxed solution results in an optimal value of 10.25. However, $x_{1}$ was a non-integer value. Therefore, the branch and bound method will be applied to find a solution that satisfies all constraints. The optimal value must be no greater than 10.25 since this was the solution found by relaxing constraints.

Step 3: Apply Branch and Bound

Since $x_{1}$ is an integer, the selected branches are $x_{1}=0,x_{1}=1,$ and $x_{1}=2$.

Step 3.1: Branch at $x_{1}=0$

Substitute $x_{1}=0$ into the objective function.

$f(0,x_{2})=-(0)^{2}-x_{2}^{2}+5(0)+4x_{2}$

$f(0,x_{2})=-x_{2}^{2}+4x_{2}$

Determine the critical points by setting the first derivative to 0.

${d \over dx_{2}}(-x_{2}^{2}+4x_{2})=-2x_{2}+4=0$

$-2x_{2}=-4$

$x_{2}=2$

Evaluate the objective function at the critical point $(x_{2}=2)$ and boundary points $(x_{2}=0,x_{2}=3)$.

$f(0,0)=-(0)^{2}-(0)^{2}+5(0)+4(0)=0$

$f(0,2)=-(0)^{2}-(2)^{2}+5(0)+4(2)=4$

$f(0,3)=-(0)^{2}-(3)^{2}+5(0)+4(3)=3$

The maximum value of these solutions is 4, which happens when $x_{1}=0$ and $x_{2}=2$.

Step 3.2: Branch at $x_{1}=1$

Substitute $x_{1}=1$ into the objective function.

$f(1,x_{2})=-(1)^{2}-x_{2}^{2}+5(1)+4x_{2}$

$f(1,x_{2})=-x_{2}^{2}+4x_{2}+4$

Determine the critical points by setting the first derivative to 0.

${\operatorname {d} \! \over \operatorname {d} \!x_{2}}(-x_{2}^{2}+4x_{2}+4)=-2x_{2}+4=0$

$-2x_{2}=-4$

$x_{2}=2$

Evaluate the objective function at the critical point $(x_{2}=2)$ and boundary points $(x_{2}=0,x_{2}=3)$.

$f(1,0)=-(1)^{2}-(0)^{2}+5(1)+4(0)=4$

$f(1,2)=-(1)^{2}-(2)^{2}+5(1)+4(2)=8$

$f(1,3)=-(1)^{2}-(3)^{2}+5(1)+4(3)=7$

The maximum value of these solutions is 8, which happens when $x_{1}=1$ and $x_{2}=2$.

Step 3.3: Branch at $x_{1}=2$

Substitute $x_{1}=2$ into the objective function.

$f(2,x_{2})=-(2)^{2}-x_{2}^{2}+5(2)+4x_{2}$

$f(2,x_{2})=-x_{2}^{2}+4x_{2}+6$

Determine the critical points by setting the first derivative to 0.

${\operatorname {d} \! \over \operatorname {d} \!x_{2}}(-x_{2}^{2}+4x_{2}+6)=-2x_{2}+4=0$

$-2x_{2}=-4$

$x_{2}=2$

Evaluate the objective function at the critical point $(x_{2}=2)$ and boundary points $(x_{2}=0,x_{2}=3)$.

$f(2,0)=-(2)^{2}-(0)^{2}+5(2)+4(0)=6$

$f(2,2)=-(2)^{2}-(2)^{2}+5(2)+4(2)=10$

$f(2,3)=-(2)^{2}-(3)^{2}+5(2)+4(3)=9$

The maximum value of these solutions is 10, which happens when $x_{1}=2$ and $x_{2}=2$.

Step 3.4: Compare Branches

The best solution across all branches was $x_{1}=2$ and $x_{2}=2$, resulting in an optimal value of 10.

Application

In this section, we will explore the wide applications of quadratic programming in fields ranging from finance, logistics management, data science, and various engineering fields.

Finance-Portfolio Optimization

In finance, quadratic programming is commonly used when formulating an investment portfolio that balances returns and risk to meet the investor's goal. Nobel Prize recipient Harry Markowitz developed a portfolio model using quadratic programming to maximize returns while minimizing risks, a model that would later become a cornerstone in Modern Portfolio Theory.¹⁰ Markowitz defined risk as a variance of the portfolio’s return, which captures an essence of a portfolio’s symmetric return volatility. Markowitz's method involved estimating stock returns based on historical data, analyzing variances from historical projections and its realized returns to formulate risk. When provided a budget and risk tolerance, the model would now be able to select a combination of stocks that would maximize returns within the defined constraints. Markowitz further constrained the portfolio model to not include short selling of stock, making this a convex quadratic programming problem. Complications to Markowitz's model arise when short selling stocks are considered. When a portfolio short sells a stock, the portfolio essentially takes a negative position on the asset, altering the objective function to include negative returns. A short selling stock portfolio would be an example of a non-convex quadratic programming problem. ^10,11

Quadratic Knapsack Problem (QKP)

The traditional knapsack optimization problem considers items (i) with associated values (v) and weights (w) and has the objective function to maximize the value of the items held in the knapsack while not exceeding its weight constraint. The decision variables in this scenario define items to include and not to include in the knapsack. This problem has proven to be beneficial when optimizing cargo loads and establishing transportation routes.

The QKP is an augmentation of the classic knapsack problem, where the objective function is quadratic and contains pairwise variables but still contains the same objective of maximizing value of items contained in the knapsack. The extension of this knapsack, initially proposed by Gallo in 1977, introduces the ability to optimize values with items that may have a unique relationship affecting their values.¹² QKP has applications in solving more complicated cargo load problems, telecommunications, and electrical engineering.

To expand on an electrical engineering application, in microchip design, quadratic programming has been used to optimize chip component placement to minimize costs and component connections. This is similar in nature to the QKP.¹³

Support Vector Machines (SVMs)

In machine learning, SVMs are learning models tasked with classification and regression demands. Use case examples of SVMs would include facial and text recognition. SVMs utilize quadratic programing to optimize a hyperplane used in a recognition task where the objective is to maximize a margin between classes and minimize classification errors and are commonly subject to linear constraints. Algorithms like sequential minimal optimization (SMO) have emerged to help solution growing data sets used in SVMs to make the computation more achievable by breaking the problem into sub quadratic programming problems.¹⁴

Plug in Hybrid Electric Vehicle Power Management

Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands.¹⁵

Software tools that can be used in Quadratic Programming

Tool	Description
Python	Python has multiple packages available to handle quadratic programming such as Pyomo, SciPY, Quadprong, and CVXPY with each library bringing its own strengths to a problem.
MATLAB	MathWorks MATLAB Optimization Toolbox is an add on package suitable to solve problems requiring quadratic programming with a either a problem based or solver based approach. If solver based, there are three algorithms available with quadprong: Interior-point-convex, trust-region-reflective, and active set.
GAMS	GAMS Gurobi suite contains several algorithms that are suitable for quadratic programming. For example, to solve a convex QCP, the algorithm used is the parallel barrier algorithm.
Excel Solver	The data package is suitable for solving linear and nonlinear problems which can include quadratic programming problems.
WOLFRAM	Wolfram Language & System solver is a versatile tool and can solve non linear quadratic problems.
SNOPT	Uses sequential quadratic programing which solves multiple smaller quadratic sub problems.
Julia	Julia offer's JuMP and Convex.jl packages that leverage solvers like Gurobi and MOSEK to support quadratic programming problems.

Conclusion

Quadratic programming and its ability to optimize quadratic functions is a vastly useful tool for solving real-world problems which are often depicted as quadratic functions. For this reason, QP has been used to model a variety of problems from signal processing to game theory to economics. As one of the simplest non-linear programming types, QP can be used to both solve quadratic functions with linear bounds, made especially straightforward with a convex objective function, and can be used as a step in more complicated optimization problems such as sequential quadratic programming. Though only first theorized in the 1950s, QP application has broadened to many fields including finance, scheduling, and engineering modeling.

References

1. J. Nocedal and S. J. Wright. Numerical Optimization. Springer (1999): Web. 2 December 2024.
2. H. B. Mann. Quadratic forms with linear constraints. The American Mathematical Monthly (1943): Web. 2 December 2024.
3. N. I. M. Gould and P. L. Toint. A Quadratic Programming Bibliography. RAL Numerical Analysis Group Internal Report (2012): Web. 2 December 2024.
4. E. W. Barankin and R. Dorfman. Toward quadratic programming. Report to the logistics branch, Office of Naval Research (1955): Web. 2 December 2024.
5. M. Frank and P. Wolfe. An Algorithm for Quadratic Programming. Naval Research Logistics Quarterly 3 (1956): Web. 2 December 2024.
6. R. J. Vanderbei. Linear Programming: Foundations and Extensions. Springer International Publishing (2008): Web. 2 December 2024.
7. C. Floudas and V. Visweswaran. Quadratic Optimization. Nonconvex Optimization and Its Applications, 2 (1995): Web. 2 December 2024.
8. R. J. Vanderbei. Linear Programming: International Series in Operations Research & Management Sceince. Springer International Publishing (2008): Web. 2 December 2024.
9. T. V.Mikosch, S. Resnick, B. Zwart and T. Dieker. Numerical Optimization: Springer Series in Operations Research and Financial Engineering. Springer International Publishing (2006): Web. 2 December 2024.
10. B. McCarl, et al. Quadratic Programming Applications. Omega, vol. 5, no. 1 (1977): Web. 2 December 2024
11. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press (2004): Web. 24 November 2024.
12. G. Gallo, P. L. Hammer and B. Simeone. Quadratic knapsack problems. In: Padberg, M.W. (eds) Combinatorial Optimization. Mathematical Programming Studies, vol 12. Springer, Berlin, Heidelberg (1980): Web. 24 November 2024.
13. N.A. Sherwani. Algorithms for VLSI Physical Design Automation (1993): Web. 24 November 2024.
14. J. Platt. Fast Training of Support Vector Machines Using Sequential Minimal Optimization. Microsoft Research, 17 Oct. 2018, www.microsoft.com/en-us/research/publication/fast-training-of-support-vector-machines-using-sequential-minimal-optimization/.
15. Z. Zhou and C. Mi. ‘Power management of PHEV using quadratic programming’, Int. J. Electric and Hybrid Vehicles, Vol. 3, No. 3, (2011): Web. 24 November 2024.