QuadraticOptimization
QuadraticOptimization[f,cons,vars]
finds values of variables vars that minimize the quadratic objective f subject to linear constraints cons.
QuadraticOptimization[{q,c},{a,b}]
finds a vector that minimizes the quadratic objective subject to the linear inequality constraints .
QuadraticOptimization[{q,c},{a,b},{a_{eq},b_{eq}}]
includes the linear equality constraints .
QuadraticOptimization[{q,c},…,{dom_{1},dom_{2},…}]
takes to be in the domain dom_{i}, where dom_{i} is Integers or Reals.
QuadraticOptimization[…,"prop"]
specifies what solution property "prop" should be returned.
Details and Options
 Quadratic optimization is also known as quadratic programming (QP) or linearly constrained quadratic optimization.
 Quadratic optimization is typically used in problems such as parameter fitting, portfolio optimization and geometric distance problems.
 Quadratic optimization is a convex optimization problem that can be solved globally and efficiently.
 Quadratic optimization finds that solves the primal problem: »

minimize subject to constraints where  The space consists of symmetric positive semidefinite matrices.
 Mixedinteger quadratic optimization finds and that solve the problem:

minimize subject to constraints where  The variable specification vars should be a list with elements giving variables in one of the following forms:

v variable with name and dimensions inferred v∈Reals real scalar variable v∈Integers integer scalar variable v∈ℛ vector variable restricted to the geometric region v∈Vectors[n,dom] vector variable in or v∈Matrices[{m,n},dom] matrix variable in or  The constraints cons can be specified by:

LessEqual scalar inequality GreaterEqual scalar inequality VectorLessEqual vector inequality VectorGreaterEqual vector inequality Equal scalar or vector equality Element convex domain or region element  With QuadraticOptimization[f,cons,vars], parameter equations of the form parval, where par is not in vars and val is numerical or an array with numerical values, may be included in the constraints to define parameters used in f or cons.
 The objective function may be specified in the following ways:

q {q,c}  In the factored form, and .
 The primal minimization problem has a related maximization problem that is the Lagrangian dual problem. The dual maximum value is always less than or equal to the primal minimum value, so it provides a lower bound. The dual maximizer provides information about the primal problem, including sensitivity of the minimum value to changes in the constraints.
 The Lagrangian dual problem for quadratic optimization with objective is given by: »

maximize subject to constraints where  With a factored quadratic objective , the dual problem may also be expressed as:

maximize subject to constraints where  The relationship between the factored dual vector and the unfactored dual vector is .
 For quadratic optimization, strong duality holds if is positive semidefinite. This means that if there is a solution to the primal minimization problem, then there is a solution to the dual maximization problem, and the dual maximum value is equal to the primal minimum value.
 The possible solution properties "prop" include:

"PrimalMinimizer" a list of variable values that minimizes the objective function "PrimalMinimizerRules" values for the variables vars={v_{1},…} that minimizes "PrimalMinimizerVector" the vector that minimizes "PrimalMinimumValue" the minimum value "DualMaximizer" vectors that maximize "DualMaximumValue" the dual maximum value "DualityGap" the difference between the dual and primal optimal values (0 because of strong duality) "Slack" the constraint slack vector "ConstraintSensitivity" sensitivity of to constraint perturbations "ObjectiveMatrix" the quadratic objective matrix "ObjectiveVector" the linear objective vector "FactoredObjectiveMatrix" the matrix in the factored objective form "FactoredObjectiveVector" the vector in the factored objective form "LinearInequalityConstraints" the linear inequality constraint matrix and vector "LinearEqualityConstraints" the linear equality constraint matrix and vector {"prop_{1}","prop_{2}",…} several solution properties  The dual maximizer component is a function of and , given by .
 The following options may be given:

MaxIterations Automatic maximum number of iterations to use Method Automatic the method to use PerformanceGoal $PerformanceGoal aspects of performance to try to optimize Tolerance Automatic the tolerance to use for internal comparisons  The option Method>method may be used to specify the method to use. Available methods include:

Automatic choose the method automatically "COIN" COIN library quadratic programming "SCS" SCS (splitting conic solver) library "CSDP" CSDP (COIN semidefinite programming) library "DSDP" DSDP (semidefinite programming) library "PolyhedralApproximation" objective epigraph is approximated using polyhedra  Computations are limited to MachinePrecision.
Examples
open allclose allBasic Examples (3)
Minimize subject to the constraint :
The optimal point lies in a region defined by the constraints and where is smallest:
Minimize subject to the equality constraint and the inequality constraints :
Define objective as and constraints as and :
Solve using matrixvector inputs:
The optimal point lies where a level curve of is tangent to the equality constraint:
Scope (23)
Basic Uses (12)
Minimize subject to the constraints :
Get the minimizing value using solution property "PrimalMinimumValue":
Minimize subject to the constraint :
Get the minimizing value and minimizing vector using solution property:
Minimize subject to the constraint :
Define the objective as and constraints as :
Solve using matrixvector inputs:
Minimize subject to the equality constraint and the inequality constraint :
Define objective as and constraints as and :
Solve using matrixvector inputs:
Minimize subject to the constraints :
Define the objective as and constraints as :
Solve using matrixvector inputs:
Minimize subject to the constraints :
Specify constraints using VectorGreaterEqual () and VectorLessEqual ():
Minimize subject to . Use vector variable with parameter equations to specify input:
Minimize subject to . Use NonNegativeReals to specify the constraint :
Specify integer domain constraints using Integers:
Specify integer domain constraints on vector variables using Vectors[n,Integers]:
Specify nonnegative integer domain constraints using NonNegativeIntegers ():
Specify nonpositive integer constraints using NonPositiveIntegers ():
Primal Model Properties (4)
Minimize subject to the constraint :
Get vector output using "PrimalMinimizer":
Get the rulebased result using "PrimalMinimizerRules":
Get the minimizing value of the optimization using "PrimalMinimumValue":
Obtain the primal minimum value using symbolic inputs:
Extract the matrixvector inputs of the optimization problem:
Solve using the matrixvector form:
Recover the symbolic primal value by adding the objective constant:
Find the slack for inequalities and equalities associated with a minimization problem:
Get the minimum value and the constraint matrices:
The slack for inequality constraints is a vector such that :
The slack for the equality constraints is a vector such that :
Dual Model Properties (3)
The dual problem is to maximize subject to :
The primal minimum value and the dual maximum value coincide because of strong duality:
So it has a duality gap of zero. In general, at optimal points:
Construct the dual problem using constraint matrices extracted from the primal problem:
Extract the objective and constraint matrices and vectors:
The dual problem is to maximize subject to :
Get the dual maximum value directly using solution properties:
Sensitivity Properties (4)
Use "ConstraintSensitivity" to find the change in optimal value due to constraint relaxations:
The first vector is inequality sensitivity and the second is equality sensitivity:
Consider new constraints where is the relaxation:
The approximate new optimal value is given by:
Compare to directly solving the relaxed problem:
Each sensitivity is associated with an inequality or equality constraint:
The inequality constraints and their associated sensitivity:
The equality constraints and their associated sensitivity:
The change in optimal value due to constraint relaxation is proportional to the sensitivity value:
Compute the minimal value and constraint sensitivity:
A zero sensitivity will not change the optimal value if the constraint is relaxed:
A negative sensitivity will decrease the optimal value:
A positive sensitivity will increase the optimal value:
The "ConstraintSensitivity" is related to the dual maximizer of the problem:
The inequality sensitivity satisfies , where is the dual inequality maximizer:
The equality sensitivity satisfies , where is the dual equality maximizer:
Options (8)
Method (5)
The method "COIN" uses the COIN library:
"CSDP" and "DSDP" reduce to semidefinite optimization:
"SCS" reduces to conic optimization:
"PolyhedralApproximation" approximates the objective using linear constraints:
For leastsquarestype quadratic problems, "CSDP" and "DSDP" will be slower than "COIN" or "SCS":
Solve the leastsquares problem using method "COIN":
Solve the problem using method "CSDP":
For leastsquarestype quadratic problems, "CSDP","DSDP" and "PolyhedralApproximation" will be slower than "COIN" or "SCS":
Solve the leastsquares problem using method "COIN":
Solve the problem using method "CSDP":
Solve the problem using method "PolyhedralApproximation":
Different methods may give different results for problems with more than one optimal solution:
Minimizing a concave function can be done only using Method"COIN":
Other methods cannot be used because they require the factorization of the objective matrix:
PerformanceGoal (1)
Tolerance (2)
A smaller Tolerance setting gives a more precise result:
Find the error between computed and exact minimum value using different Tolerance settings:
Visualize the change in minimum value error with respect to tolerance:
A smaller Tolerance setting gives a more precise answer, but typically takes longer to compute:
Applications (29)
Basic Modeling Transformations (7)
Maximize subject to . Solve the maximization problem by negating the objective function:
Negate the primal minimum value to get the corresponding maximum value:
Minimize by converting the objective function into :
Construct the objective function by expanding :
Since QuadraticOptimization minimizes , the matrix is multiplied by 2:
The minimal value of the original function is recovered as :
QuadraticOptimization directly performs this transformation. Construct the objective function using Inactive to avoid threading:
Minimize subject to the constraints . Transform the objective function to and solve the problem:
Recover the original minimum value using transformation :
Minimize subject to the constraints . The constraint can be transformed to :
Minimize subject to the constraints . The constraint can be interpreted as . Solve the problem with each constraint:
The optimal solution is the minimum of the two solutions:
Minimize subject to , where is a nondecreasing function, by instead minimizing . The primal minimizer will remain the same for both problems. Consider minimizing subject to :
The true minimum value can be obtained by applying the function to the primal minimum value:
Since , the solution is the true solution only if the primal minimum value is greater than 0. The true minimum value can be obtained by applying the function to the primal minimum value:
DataFitting Problems (7)
Find a linear fit to discrete data by minimizing :
Construct the factored quadratic matrix using DesignMatrix:
Find the coefficients of the line:
Find a quadratic fit to discrete data by minimizing :
Construct the factored quadratic matrix using DesignMatrix:
Find the coefficients of the quadratic curve:
Fit a quadratic curve discrete data such that the first and last points of the data lie on the curve:
Construct the factored quadratic matrix using DesignMatrix:
The two equality constraints are:
Find the coefficients of the line:
Find an interpolating function to noisy data using bases :
The interpolating function will be :
Find the coefficients of the interpolating function:
Minimize subject to the constraints :
Compare with the unconstrained minimum of :
Cardinality constrained least squares: minimize such that has at most nonzero elements:
Let be a decision vector such that if , then is nonzero. The decision constraints are:
To model constraint when , chose a large constant such that :
Solve the cardinality constrained leastsquares problem:
The subset selection can also be done more efficiently with Fit using regularization. First, find the range of regularization parameters that uses at most basis functions:
Find the nonzero terms in the regularized fit:
Find the fit with just these basis terms:
Find the best subset of functions from a candidate set of functions to approximate given data:
The approximating function will be :
A maximum of 5 basis functions is to be used in the final approximation:
The coefficients associated with functions that are not chosen must be zero:
Classification Problems (2)
Find a plane that separates two groups of 3D points and :
For separation, set 1 must satisfy and set 2 must satisfy . Find the hyperplane by minimizing :
The distance between the planes and is :
The plane separating the two groups of points is:
Plot the plane separating the two datasets:
Find a quadratic polynomial that separates two groups of 3D points and :
Construct the quadratic polynomial data matrices for the two sets using DesignMatrix:
For separation, set 1 must satisfy and set 2 must satisfy . Find the separating surface by minimizing :
Geometric Problems (3)
Find a point closest to the point that lies on the planes and :
Find the point closest to by minimizing . Use Inactive Plus when constructing the objective:
Find the distance between two convex polyhedra:
Show the nearest points with the line connecting them:
Find the radius and center of a minimal enclosing ball that encompasses a given region:
The original minimization problem is to minimize subject to . The dual of this problem is to maximize subject to :
Solve the dual maximization problem:
The center of the minimal enclosing ball is :
The radius of the minimal enclosing ball is Sqrt of the maximum value:
The minimal enclosing ball can be found efficiently using BoundingRegion:
Investment Problems (3)
Find the number of stocks to buy from four stocks, such that a minimum $1000 dividend is received and risk is minimized. The expected return value and the covariance matrix associated with the stocks are:
The unit price for the four stocks is $1. Each stock can be allocated a maximum of $2500:
The investment must yield a minimum of $1000:
A negative stock cannot be bought:
The total amount to spend on each stock is found by minimizing the risk given by :
The total investment to get a minimum of $1000 is:
Find the number of stocks to buy from four stocks, with an option to shortsell such that a minimum dividend of $1000 is received and the overall risk is minimized:
The capital constraint and return on investment constraints are:
A shortsale option allows the stock to be sold. The optimal number of stocks to buy/shortsell is found by minimizing the risk given by the objective :
The second stock can be shortsold. The total investment to get a minimum of $1000 due to the shortselling is:
Without shortselling, the initial investment will be significantly greater:
Find the best combination of six stocks to invest in out of a possible 20 candidate stocks, so as to maximize return while minimizing risk:
Let be the percentage of total investment made in stock . The return is given by , where is a vector of the expected return value of each individual stock:
Let be a decision vector such that if , then that stock is bought. Six stocks have to be chosen:
The percentage of investment must be greater than 0 and must add to 1:
Find the optimal combination of stocks that minimizes the risk given by and maximizes return:
The optimal combination of stocks is:
The percentages of investment to put into the respective stocks are:
Portfolio Optimization (1)
Find the distribution of capital to invest in six stocks to maximize return while minimizing risk:
Let be the percentage of total investment made in stock . The return is given by , where is a vector of expected return value of each individual stock:
The risk is given by , and is a riskaversion parameter:
The objective is to maximize return while minimizing risk for a specified riskaversion parameter :
The percentage of investment must be greater than 0 and must add to 1:
Compute the returns and corresponding risk for a range of riskaversion parameters:
The optimal over a range of gives an upperbound envelope on the tradeoff between return and risk:
Compute the percentage of investment for a specified number of riskaversion parameters:
Increasing the riskaversion parameter leads to stock diversification to reduce the risk:
Increasing the riskaversion parameter leads to a reduced expected return on investment:
Trajectory Optimization Problems (2)
Minimize subject to . The minimizing function integral can be approximated using the trapezoidal rule. The discretized objective function will be :
The constraint can be discretized using finite differences:
The constraints can be represented using the Indexed function:
The constraints can be discretized using finite differences, and only the first and last rows are used:
Solve the discretized trajectory problem:
Convert the discretized result into an InterpolatingFunction:
Compare the result with the analytic solution:
Find the shortest path between two points while avoiding obstacles. Specify the obstacle:
Extract the halfspaces that form the convex obstacle:
Specify the start and end points of the path:
The path can be discretized using points. Let represent the position vector:
The objective is to minimize . Let . The objective is transformed to :
Specify the end point constraints:
The distance between any two subsequent points should not be too large:
A point is outside the object if at least one element of is less than zero. To enforce this constraint, let be a decision vector and be the element of such that , then and is large enough such that :
Find the minimum distance path around the obstacle:
To avoid potential crossings at the edges, the region can be inflated and the problem solved again:
Optimal Control Problems (2)
The integral can be discretized using the trapezoidal method:
The time derivative in is discretized using finite differences:
The endcondition constraints can be specified using Indexed:
Solve the discretized problem:
Convert the discretized result into InterpolatingFunction:
Minimize subject to and and on the control variable:
The integral can be discretized using the trapezoidal method:
The time derivative in is discretized using finite differences:
The endcondition constraints can be specified using Indexed:
The constraint on the control variable is:
Solve the discretized problem:
Convert the discretized result into InterpolatingFunction:
Sequential Quadratic Optimization (2)
Minimize a nonlinear function subject to nonlinear constraints . The minimization can be done by approximating as and the constraints as as . This leads to a quadratic minimization problem that can be solved iteratively. Consider a case where and :
The gradient and Hessian of the minimizing function are:
The gradient of the constraints is:
The subproblem is to find by minimizing subject to :
Iterate starting with an initial guess of . The next iterate is , where is the step length to ensure that the constraints are always satisfied:
Visualize the convergence of the result. The final result is the green point:
The gradient and Hessian of the minimizing function are:
The gradient of the constraints is:
The subproblem is to minimize , subject to and :
Iterate starting with the initial guess :
Visualize the convergence of the result. The final result is the green point:
Properties & Relations (9)
QuadraticOptimization gives the global minimum of the objective function:
Visualize the objective function:
The minimizer can be in the interior or at the boundary of the feasible region:
Minimize gives global exact results for quadratic optimization problems:
NMinimize can be used to obtain approximate results using global methods:
FindMinimum can be used to obtain approximate results using local methods:
LinearOptimization is a special case of QuadraticOptimization:
In matrixvector form, the quadratic term is set to 0:
SecondOrderConeOptimization is a generalization of QuadraticOptimization:
Use auxiliary variable and minimize with additional constraint :
SemidefiniteOptimization is a generalization of QuadraticOptimization:
Use auxiliary variable and minimize with additional constraint :
ConicOptimization is a generalization of QuadraticOptimization:
Use auxiliary variable and minimize with additional constraint :
Possible Issues (5)
Constraints specified using strict inequalities may not be satisfied for certain methods:
The reason is that QuadraticOptimization solves :
The minimum value of an empty set or infeasible problem is defined to be :
The minimizer is Indeterminate:
The minimum value for an unbounded set or unbounded problem is :
The minimizer is Indeterminate:
Certain solution properties are not available for symbolic input:
Dual related solution properties for mixedinteger problems may not be available: