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},{aeq,beq}]

includes the linear equality constraints .

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.
  • The constraints cons can be specified by:
  • LessEqualscalar inequality
    GreaterEqualscalar inequality
    VectorLessEqualvector inequality
    VectorGreaterEqualvector inequality
    Equalscalar or vector equality
    Elementconvex 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}
    {{q_(f)},c}1/2(q_f.x).(q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]).(q_f.x)+c.x
    {{q_(f),c_(f)},c}1/2(c_f+q_f.x).(c_f+q_f.x)+c.x=1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x
  • 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 1/2(x.TemplateBox[{{q, _, f}}, Transpose]+c_f).(q_f.x+c_f)+c.x, 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={v1,} 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
    {"prop1","prop2",} several solution properties
  • The dual maximizer component is a function of and , given by .
  • The following options may be given:
  • MaxIterationsAutomaticmaximum number of iterations to use
    MethodAutomaticthe method to use
    PerformanceGoal$PerformanceGoalaspects of performance to try to optimize
    ToleranceAutomaticthe tolerance to use for internal comparisons
  • The option Method->method may be used to specify the method to use. Available methods include:
  • Automaticchoose 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
  • Computations are limited to MachinePrecision.

Examples

open all close all

Basic Examples  (2)

Minimize subject to the constraint :

In[1]:=
Click for copyable input
Out[2]=

The optimal point lies in a region defined by the constraints and where is smallest:

In[3]:=
Click for copyable input
Out[3]=

Minimize subject to the equality constraint and the inequality constraints :

In[1]:=
Click for copyable input
Out[1]=

Define objective as and constraints as and :

In[2]:=
Click for copyable input

Solve using matrix-vector inputs:

In[3]:=
Click for copyable input
Out[3]=

The optimal point lies where a level curve of is tangent to the equality constraint:

In[4]:=
Click for copyable input
Out[4]=

Scope  (19)

Options  (7)

Applications  (25)

Properties & Relations  (9)

Possible Issues  (4)

Introduced in 2019
(12.0)