ConicOptimization

ConicOptimization[f,cons,vars]

finds values of variables vars that minimize the linear objective f subject to conic constraints cons.

ConicOptimization[,"prop"]

specifies what solution property "prop" should be returned.

Details and Options

  • Conic optimization is also known as linear conic optimization or linear conic programming.
  • Conic optimization includes many other forms of optimization, including linear optimization, linear fractional optimization, quadratic optimization, second-order cone optimization, semidefinite optimization and geometric optimization.
  • Conic optimization is a convex optimization problem that can be solved globally and efficiently.
  • Conic optimization finds that solves the primal problem:
  • minimize
    subject to constraints
    where
  • The set should be a proper convex cone of dimension . Common cone specifications for and the sets corresponding to (VectorGreaterEqual[{x,0},κj]) are:
  • {"NonNegativeCone", m} such that
    {"NormCone", m} such that TemplateBox[{{{, {{x, _, 1}, ,, ..., ,, {x, _, {(, {m, -, 1}, )}}}, }}}, Norm]<=x_m
    {"SemidefiniteCone", m}symmetric positive semidefinite matrices
    "ExponentialCone" such that
    "DualExponentialCone" such that or
    {"PowerCone",α} such that
    {"DualPowerCone",α} such that
  • Mixed-integer conic 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:
  • vvariable with name and dimensions inferred
    vRealsreal scalar variable
    vIntegersinteger scalar variable
    vvector variable restricted to the geometric region
    vVectors[n,dom]vector variable in or
    vMatrices[{m,n},dom]matrix variable in or
  • 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 ConicOptimization[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 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 conic optimization has a dual problem: »
  • maximize
    subject to constraints
    where and is the dual cone to
  • The possible solution properties "prop" include: »
  • "PrimalMinimizer"a list of variable values that minimizes
    "PrimalMinimizerRules"values for the variables vars={v1,} that minimize
    "PrimalMinimizerVector"the vector that minimizes
    "PrimalMinimumValue"the minimum value
    "DualMaximizer"the vector that maximizes
    "DualMaximumValue"the dual maximum value
    "DualityGap"the difference between the dual and primal optimal values
    "Slack"vectors that convert inequality constraints to equality
    "ConstraintSensitivity"
    sensitivity of to constraint perturbations
    "ObjectiveVector"the linear objective vector
    "ConicConstraints" the list of conic constraints in canonical form
    "ConicConstraintConeSpecifications" the list of specifications for the cones
    "ConicConstraintConeDimensions" {TemplateBox[{Dimensions, paclet:ref/Dimensions}, RefLink, BaseStyle -> {3ColumnTableMod}][kappa_(1)],...}the list of dimensions for the cones in the conic constraints
    "ConicConstraintAffineLists" the list of matrix, vector pairs for the affine transforms in the conic constraints
    {"prop1","prop2",} several solution properties
  • 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
    "SCS"SCS (splitting conic solver) library
    "CSDP"CSDP (COIN semidefinite programming) library
    "DSDP"DSDP (semidefinite programming) library
  • Computations are limited to MachinePrecision.

Examples

open allclose all

Basic Examples  (3)

Minimize over a two-dimensional "NormCone":

The optimal point is where is smallest within the region defined by the constraints:

Minimize over the intersection of a triangle and a disk :

Visualize the location of the minimizing point:

Minimize subject to the constraint TemplateBox[{{{, {x, ,, y}, }}}, Norm]<=1,x in Z,y in R:

Scope  (30)

Basic Uses  (15)

Minimize subject to constraints :

Several linear inequality constraints can be expressed with VectorGreaterEqual:

Use v>= or \[VectorGreaterEqual] to enter the vector inequality sign :

An equivalent form using scalar inequalities:

Use a vector variable :

The inequality may not be the same as due to possible threading in :

To avoid unintended threading in , use Inactive[Plus]:

Use parameter equations to avoid unintended threading in :

VectorGreaterEqual represents a conic inequality with respect to the "NonNegativeCone":

To explicitly specify the dimension of the cone, use {"NonNegativeCone",n}:

Find the solution:

Minimize subject to the constraint :

Specify the constraint using a conic inequality with "NormCone":

Find the solution:

Minimize subject to the positive semidefinite matrix constraint (x 1; 1 y)_(TemplateBox[{2}, SemidefiniteConeList])0:

Find the solution:

Use a vector variable and Indexed[x,i] to specify individual components:

Use Vectors[n] to specify the dimension of a vector variable when it is ambiguous:

Specify non-negative constraints using NonNegativeReals ():

An equivalent form using vector inequality :

Specify integer domain constraints using Integers:

Specify integer domain constraints on vector variables using Vectors[n,Integers]:

Specify non-negative integer domain constraints using NonNegativeIntegers ():

Specify non-positive integer domain constraints using NonPositiveIntegers ():

Primal Model Properties  (4)

Minimize over the intersection of a triangle and a disk :

Get the primal minimizer as a vector:

Get the minimal value:

Plot the solution:

Extract the objective vector:

Extract the conic constraints:

Extract the cone specification in the conic constraints:

Extract the cone dimensions in the conic constraints:

Extract the affine lists in the conic constraints:

The slack for an inequality at the minimizer is given by :

Extract the minimizer and conic constraint affine lists:

Verify that the slack satisfies s={s0,,sk} with aj.x*+bj-sj=0.

A conic optimization problem in standard form is defined by some authors as minimizing subject to and . To convert to standard form, for each conic constraint , add a variable and corresponding linear equality constraint :

Extract the objective vector, conic constraint affine lists and the conic specifications:

The slack constraints are the same as :

Form the linear equality constraint :

Solve the transformed standard form conic problem:

The "Slack" property allows you to get the values of without doing the actual transformation:

Dual Model Properties  (3)

Minimize subject to and :

The dual problem is to maximize subject to :

The primal minimum value and the dual maximum value coincide because of strong duality:

That is the same as having a duality gap of zero. In general, at optimal points:

Construct the dual problem using coefficients extracted from the primal problem:

Extract the objective vector and constraint affine lists:

Get the and :

The dual problem is to maximize subject to :

Get the dual maximum value and dual maximizer directly using solution properties:

The "DualMaximizer" can be obtained with:

The dual maximizer vector partitions match the number and dimensions of the dual cones:

Sensitivity Properties  (3)

Find the change in optimal value due to constraint perturbations:

Compute the "ConstraintSensitivity":

Consider new constraint a.{x,y}+b+delta_(TemplateBox[{3}, NormConeList])0 where is the perturbation:

The new optimal value can be estimated to be:

Compare to directly solving the perturbed problem:

The optimal value changes according to the signs of the sensitivity elements:

At negative sensitivity element position, a positive perturbation will decrease the optimal value:

At positive sensitivity element position, a positive perturbation will increase the optimal value:

The constraint sensitivity can also be obtained as the negative of the dual maximizer:

Supported Convex Cones  (5)

"NonNegativeCone"  (1)

Minimize over a regular nonagon:

Show the minimizer on a plot of the objective function:

Show the cones used in the conic constraints:

"NormCone"  (1)

Minimize over a disk:

Show the minimizer on a plot of the objective function:

Show the cones used in the conic constraints:

"SemidefiniteCone"  (1)

Minimize such that is positive semidefinite:

Show the minimizer on a plot of the objective function:

Show the cones used in the conic constraints:

"ExponentialCone"  (1)

Minimize subject to the constraints :

Show the minimizer on a plot of the objective function:

Show the cones used in the conic constraints:

"PowerCone"  (1)

Minimize over the 4-norm unit disk:

Show the minimizer on a plot of the objective function:

Show the cones used in the conic constraints:

Options  (11)

Method  (8)

"SCS" uses a splitting conic solver method:

"CSDP" is an interior point method for semidefinite problems:

"DSDP" is an alternative interior point method for semidefinite problems:

"IPOPT" is an interior point method for nonlinear problems:

Different methods have different default tolerances, which affects the accuracy and precision:

Compute exact and approximate solutions:

"SCS" has a default tolerance of :

"CSDP", "DSDP" and "IPOPT" have default tolerances of :

When method "SCS" is specified, it is called with the SCS library default tolerance of 10-3:

With default options, this problem is solved by method "SCS" with tolerance 10-6:

Use methods "CSDP" or "DSDP" for up to semidefinite constraints:

Solve the problem using method "CSDP":

Solve the problem using method "DSDP":

Use method "IPOPT" to obtain accurate solutions when "CSDP" and "DSDP" are not applicable:

"IPOPT" produces more accurate results than "SCS" but is typically slower:

Compare timing with method "SCS":

PerformanceGoal  (1)

The default value of the option PerformanceGoal is $PerformanceGoal:

Use PerformanceGoal"Quality" to get a more accurate result:

Use PerformanceGoal"Speed" to get a result faster, but at the cost of quality:

Compare the timings:

The "Speed" goal gives a less accurate result:

Tolerance  (2)

A smaller Tolerance setting gives a more precise result:

Compute the exact minimum value with Minimize:

Compute the error in the minimum value with different Tolerance settings:

Visualize the change in minimum value error with respect to tolerance:

A smaller Tolerance setting gives a more precise answer, but may take longer to compute:

A smaller tolerance takes longer:

The tighter tolerance gives a more precise answer:

Applications  (28)

Basic Modeling Transformations  (13)

Maximize subject to . Solve a maximization problem by negating the objective function:

Negate the primal minimum value to get the corresponding maximal value:

Minimize over a disk centered at with radius . Convert the objective into a linear function with the additional constraint , which is equivalent to :

The disk constraint can also be represented using Norm:

Minimize over a regular pentagon. Convert the objective into a linear function using and the additional constraints :

Minimize . Using auxiliary variable , the objective is transformed to minimize subject to the constraint :

Minimize subject to . Using two auxiliary variables , transform the problem to minimize subject to :

Minimize . Using auxiliary variable , convert the problem to minimize subject to the constraints :

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 to the minimum value of :

Minimize over a disk centered at with radius Using the auxiliary variable , the objective is transformed to minimizing with the additional constraint :

The constraint is equivalent to the exponential cone constraint iff {t,1,x+y}_(TemplateBox[{}, ExponentialConeString])0:

Minimize TemplateBox[{{x, +, y}}, Abs]^(1.5) over a disk centered at with radius . Using auxiliary variable , convert the problem to minimize subject to the constraint TemplateBox[{{x, +,  , y}}, Abs]^(1.5)<=t:

The constraint TemplateBox[{{x, +,  , y}}, Abs]^(1.5)<=t is equivalent to  TemplateBox[{{x, +, y}}, Abs]<=t^((1/1.5))<==> TemplateBox[{{x, +, y}}, Abs]<=t^((1/1.5))1^((1-1/1.5)). This can be represented using "PowerCone" by  {t,1,x+y}_(TemplateBox[{{1, /, 1.5}}, PowerConeList])0:

Find that minimizes :

Using auxiliary variable , convert the problem to minimize subject to the constraint :

This can be represented using "PowerCone" constraints. Since ||a.x-b||_(1.5)= (sum_(i=1)^nTemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))^(1/1.5)<=t iff sum_(i=1)^n(TemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))/(t^(1.5-1))<=t, bounding (TemplateBox[{{{{a, _, i}, x}, -, {b, _, i}}}, Abs]^(1.5))/(t^(1.5-1)) with where gives {s_i,t,a_ix-b_i}_(TemplateBox[{{1, /, 1.5}}, PowerConeList])0, i=1,...,n:

Find that minimizes the largest eigenvalue of a symmetric matrix that depends linearly on the decision variables , . The problem can be formulated as linear matrix inequality since is equivalent to , where is the ^(th) eigenvalue of . Define the linear matrix function :

A real symmetric matrix can be diagonalized with an orthogonal matrix so . Hence iff . Since any , taking , , hence iff . Numerically simulate to show that these formulations are equivalent:

The resulting problem:

Run a Monte Carlo simulation to check the plausibility of the result:

Minimize subject to , assuming when . Using the auxiliary variable , the objective is to minimize such that :

Check that implies :

A Schur complement condition says that if , a block matrix iff . Therefore iff . Use Inactive Plus for constructing the constraints to avoid threading:

For quadratic sets , which include ellipsoids, quadratic cones and paraboloids, determine whether , where are symmetric matrices, are vectors and scalars:

Assuming that the sets i are full dimensional, the S-procedure says that iff there exists some non-negative number such that Visually see that there exists a non-negative :

Since λ0, it follows that :

Data-Fitting Problems  (4)

Minimize subject to the constraints :

Using auxiliary variable , the transformed objective is to minimize subject to :

Fit a cubic curve to discrete data such that the first and last points of the data lie on the curve:

Construct the matrix using DesignMatrix:

Define the constraint so that the first and last points must lie on the curve:

Find the coefficients by minimizing . Using auxiliary variable , the transformed objective is to minimize subject to :

Compare fit with data:

Find a robust fit to nonlinear discrete data by minimizing :

Fit the data using the bases . The interpolating function will be :

Since , using auxiliary variables . The problem is transformed to minimize subject to the constraints :

Visualize the fit:

Compare interpolating function with reference function:

Represent a given polynomial in terms of sum-of-squares polynomial :

The objective is to find such that , where is a vector of monomials:

Construct the symmetric matrix :

Find the polynomial coefficients of and and make sure they are equal:

Find the elements of :

The quadratic term , where is a lower-triangular matrix obtained from the Cholesky decomposition of :

Compare the sum-of-squares polynomial to the given polynomial:

Geometry Problems  (5)

Find the minimum distance between two disks of radius 1 centered at and . Let be a point on disk 1. Let be a point on disk 2. The objective is to minimize . Using auxiliary variable , the transformed objective is to minimize subject to :

Visualize the position of the two points:

The auxiliary variable gives the distance between the points:

Find the radius and center of a minimal enclosing ball that encompasses a given region:

Minimize the radius subject to the constraints :

Visualize the enclosing ball:

The minimal enclosing ball can be found efficiently using BoundingRegion:

Find the plane that separates two non-intersecting convex polygons:

Let be a point on . Let be a point on . The objective is to minimize . Using auxiliary variable , the transformed objective is to minimize subject to :

According to the separating hyperplane theorem, the dual associated with the constraint will give the normal of the hyperplane:

The dual associated with the "NormCone" is:

The hyperplane is constructed as:

Visualize the plane separating the two polygons:

Find the maximum area ellipse parametrized as that can be fitted into a convex polygon:

Each segment of the convex polygon can be represented as intersections of half-planes . Extract the linear inequalities:

Applying the parametrization to the half-planes gives . The term . Thus, the constraints are:

Minimizing the area is equivalent to minimizing , which is equivalent to minimizing :

Convert the parameterized ellipse into the explicit form as :

Find the analytic center of a convex polygon. The analytic center is a point that maximizes the product of distances to the constraints:

Each segment of the convex polygon can be represented as intersections of half-planes . Extract the linear inequalities:

The objective is to maximize . Taking and negating the objective, the transformed objective is :

Using auxiliary variable , the transformed objective is subject to the constraint :

Visualize the location of the center:

Classification Problems  (3)

Find a line that separates two groups of points and :

For separation, set 1 must satisfy and set 2 must satisfy :

The objective is to minimize , which gives twice the thickness between and . Using the auxiliary variable , the objective function is transformed to the constraint :

The separating line is:

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 polynomial by minimizing . Using auxiliary variable , the transformed objective is to minimize with the additional constraint :

The polynomial separating the two groups of points is:

Plot the polynomial separating the two datasets:

Separate a given set of points into different groups. This is done by finding the centers for each group by minimizing , where is a given local kernel and is a given penalty parameter:

The kernel is a -nearest neighbor () function such that , else . For this problem, nearest neighbors are selected:

Using the auxiliary variable , the objective is transformed to minimize subject to the constraint :

Find the group centers:

For each data point there exists a corresponding center. Data belonging to the same group will have the same center value:

Extract and plot the grouped points:

Optimal Control Problems  (1)

Minimize subject to , and :

The minimizing function integral can be approximated using the trapezoidal rule. The discretized objective function will be subject to additional constraints :

The time derivative in is discretized using finite differences:

The initial condition constraints can be specified using Indexed:

Using auxiliary variable , the objective is transformed to minimize subject to :

Convert the discretized result into InterpolatingFunction:

Plot the control variables:

Plot the state variables. The state variables try and track the function :

Facility Location Problems  (1)

Find the positions of various cell towers and the range needed to serve clients located at :

Each cell tower consumes power proportional to its range, which is given by . The objective is to minimize the power consumption:

Let be a decision variable indicating that if client is covered by cell tower :

Each cell tower must be located such that its range covers some of the clients:

Each cell tower can cover multiple clients:

Each cell tower has a minimum and maximum coverage:

Collect all the variables:

Find the cell tower positions and their ranges:

Extract cell tower position and range:

Visualize the position and range of the towers with respect to client locations:

Portfolio Optimization  (1)

Find the distribution of capital to invest in six stocks to maximize return while minimizing risk:

The return is given by , where is a vector of expected return value of each individual stock:

The risk is given by ; is a risk-aversion parameter and :

The objective is to maximize return while minimizing risk for a specified risk-aversion parameter:

The effect on market prices of stocks due to the buying and selling of stocks is modeled by , which is modeled by a power cone using the epigraph transformation:

The weights must all be greater than 0 and the weights plus market impact costs must add to 1:

Compute the returns and corresponding risk for a range of risk-aversion parameters:

The optimal over a range of gives an upper-bound envelope on the tradeoff between return and risk:

Compute the weights for a specified number of risk-aversion parameters:

By accounting for the market costs, a diversified portfolio can be obtained for low risk aversion, but when the risk aversion is high, the market impact cost dominates, due to purchasing a less diversified stock:

Properties & Relations  (8)

ConicOptimization gives the global minimum of the objective function:

Plot the objective function with the minimum value over the feasible region:

Minimize gives global exact results for conic problems:

NMinimize can be used to obtain approximate results using global methods:

FindMinimum can be used to obtain approximate results using local methods:

SemidefiniteOptimization is a special case of ConicOptimization:

SecondOrderConeOptimization is a special case of ConicOptimization:

QuadraticOptimization is a special case of ConicOptimization:

Use auxiliary variable and minimize with additional constraint :

LinearOptimization is a special case of ConicOptimization:

Possible Issues  (5)

The constraints at the optimal point are expected to be satisfied up to some tolerance:

The constraint violation can often be controlled with the Tolerance option:

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:

Badly scaled problems can produce results with large error:

The correct result is:

After scaling by 10-10, this is mathematically equivalent to the following problem:

Any result for , within ±10-6 of 5*10-10 will fall within the tolerance of 10-6 and when scaled back can produce an error of up to:

You could solve the preceding scaled problem or try to tighten the default tolerance:

Dual related solution properties for mixed-integer problems may not be available:

Introduced in 2019
 (12.0)
 |
Updated in 2020
 (12.1)