Main Content

coneprog

Second-order cone programming solver

Since R2020b

Description

Theconeprogfunction is a second-order cone programming solver that finds the minimum of a problem specified by

min x f T x

subject to the constraints

A sc ( i ) x b sc ( i ) d sc T ( i ) x γ ( i ) A x b Aeq x = beq lb x ub .

f,x,b,beq,lb, andubare vectors, andAandAeqare matrices. For eachi, the matrixAsc(i), vectorsdsc(i) andbsc(i), and scalarγ(i) are in a second-order cone constraint that you create usingsecondordercone.

For more details about cone constraints, seeSecond-Order Cone Constraint.

example

x= coneprog(f,socConstraints)solves the second-order cone programming problem with the constraints insocConstraintsencoded as

  • Asc(i) =socConstraints(i).A

  • bsc(i) =socConstraints(i).b

  • dsc(i) =socConstraints(i).d

  • γ(i) =socConstraints(i).gamma

example

x= coneprog(f,socConstraints,A,b,Aeq,beq)solves the problem subject to the inequality constraintsA*xband equality constraintsAeq*x = beq. SetA = []andb = []if no inequalities exist.

example

x= coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub)defines a set of lower and upper bounds on the design variables,xso that the solution is always in the rangelb ≤ x ≤ ub. SetAeq = []andbeq = []if no equalities exist.

example

x= coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options)minimizes using the optimization options specified byoptions. Useoptimoptionsto set these options.

example

x= coneprog(problem)finds the minimum forproblem, a structure described inproblem.

example

[x,fval] = coneprog(___)also returns the objective function value at the solutionfval=f'*x, using any of the input argument combinations in previous syntaxes.

example

[x,fval,exitflag,output] = coneprog(___)additionally returns a valueexitflagthat describes the exit condition, and a structureoutputthat contains information about the optimization process.

example

[x,fval,exitflag,output,lambda] = coneprog(___)additionally returns a structurelambdawhose fields contain the dual variables at the solutionx.

Examples

collapse all

To set up a problem with a second-order cone constraint, create a second-order cone constraint object.

A = diag([1,1/2,0]); b = zeros(3,1); d = [0;0;1]; gamma = 0; socConstraints = secondordercone(A,b,d,gamma);

Create an objective function vector.

f = [-1,-2,0];

The problem has no linear constraints. Create empty matrices for these constraints.

Aineq = []; bineq = []; Aeq = []; beq = [];

Set upper and lower bounds onx(3).

lb = [-Inf,-Inf,0]; ub = [Inf,Inf,2];

Solve the problem by using theconeprogfunction.

[x,fval] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub)
Optimal solution found.
x =3×10.4851 3.8806 2.0000
fval = -8.2462

The solution componentx(3)is at its upper bound. The cone constraint is active at the solution:

norm(A*x-b) - d'*x% Near 0 when the constraint is active
ans = -2.5677e-08

To set up a problem with several second-order cone constraints, create an array of constraint objects. To save time and memory, create the highest-index constraint first.

A = diag([1,2,0]); b = zeros(3,1); d = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(A,b,d,gamma); A = diag([3,0,1]); d = [0;1;0]; socConstraints(2) = secondordercone(A,b,d,gamma); A = diag([0;1/2;1/2]); d = [1;0;0]; socConstraints(1) = secondordercone(A,b,d,gamma);

Create the linear objective function vector.

f = [-1;-2;-4];

Solve the problem by using theconeprogfunction.

[x,fval] = coneprog(f,socConstraints)
Optimal solution found.
x =3×10.4238 1.6477 2.3225
fval = -13.0089

Specify an objective function vector and a single second-order cone constraint.

f = [-4;-9;-2]; Asc = diag([1,4,0]); b = [0;0;0]; d = [0;0;1]; gamma = 0; socConstraints = secondordercone(Asc,b,d,gamma);

Specify a linear inequality constraint.

A = [1/4,1/9,1]; b = 5;

Solve the problem.

[x,fval] = coneprog(f,socConstraints,A,b)
Optimal solution found.
x =3×13.2304 0.6398 4.1213
fval = -26.9225

To observe the iterations of theconeprogsolver, set theDisplayoption to'iter'.

options = optimoptions('coneprog','Display','iter');

Create a second-order cone programming problem and solve it usingoptions.

Asc = diag([1,1/2,0]); b = zeros(3,1); d = [0;0;1]; gamma = 0; socConstraints = secondordercone(Asc,b,d,gamma); f = [-1,-2,0]; Aineq = []; bineq = []; Aeq = []; beq = []; lb = [-Inf,-Inf,0]; ub = [Inf,Inf,2]; [x,fval] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub,options)
Iter Fval原始Infeas双重Infeas二元性差距me 1 0.000000e+00 0.000000e+00 5.714286e-01 1.250000e-01 0.03 2 -7.558066e+00 0.000000e+00 7.151114e-02 1.564306e-02 0.04 3 -7.366973e+00 2.775558e-17 1.075440e-02 2.352525e-03 0.04 4 -8.243432e+00 1.387779e-17 5.191882e-05 1.135724e-05 0.05 5 -8.246067e+00 0.000000e+00 2.430813e-06 5.317403e-07 0.05 6 -8.246211e+00 0.000000e+00 6.154504e-09 1.346298e-09 0.05 Optimal solution found.
x =3×10.4851 3.8806 2.0000
fval = -8.2462

Create the elements of a second-order cone programming problem. To save time and memory, create the highest-index constraint first.

A = diag([1,2,0]); b = zeros(3,1); d = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(A,b,d,gamma); A = diag([3,0,1]); d = [0;1;0]; socConstraints(2) = secondordercone(A,b,d,gamma); A = diag([0;1/2;1/2]); d = [1;0;0]; socConstraints(1) = secondordercone(A,b,d,gamma); f = [-1;-2;-4]; options = optimoptions('coneprog','Display','iter');

Create a problem structure with the required fields, as described inproblem.

problem = struct('f',f,...'socConstraints',socConstraints,...'Aineq',[],'bineq',[],...'Aeq',[],'beq',[],...'lb',[],'ub',[],...'solver','coneprog',...'options',options);

Solve the problem by callingconeprog.

[x,fval] = coneprog(problem)
Iter Fval原始Infeas双重Infeas二元性差距me 1 0.000000e+00 0.000000e+00 5.333333e-01 5.555556e-02 0.12 2 -9.696012e+00 1.850372e-17 7.631901e-02 7.949897e-03 0.17 3 -1.178942e+01 9.251859e-18 1.261803e-02 1.314378e-03 0.17 4 -1.294426e+01 9.251859e-18 1.683078e-03 1.753206e-04 0.17 5 -1.295217e+01 0.000000e+00 8.994595e-04 9.369370e-05 0.18 6 -1.295331e+01 9.251859e-18 4.748841e-04 4.946709e-05 0.18 7 -1.300753e+01 1.850372e-17 2.799942e-05 2.916606e-06 0.18 8 -1.300671e+01 1.850372e-17 2.366136e-05 2.464725e-06 0.18 9 -1.300850e+01 0.000000e+00 8.204733e-06 8.546597e-07 0.19 10 -1.300843e+01 1.850372e-17 7.339071e-06 7.644866e-07 0.19 11 -1.300862e+01 9.251859e-18 2.693755e-06 2.805995e-07 0.19 12 -1.300892e+01 1.850372e-17 8.766586e-08 9.131860e-09 0.19 Optimal solution found.
x =3×10.4238 1.6477 2.3225
fval = -13.0089

Create a second-order cone programming problem. To save time and memory, create the highest-index constraint first.

A = diag([1,2,0]); b = zeros(3,1); d = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(A,b,d,gamma); A = diag([3,0,1]); d = [0;1;0]; socConstraints(2) = secondordercone(A,b,d,gamma); A = diag([0;1/2;1/2]); d = [1;0;0]; socConstraints(1) = secondordercone(A,b,d,gamma); f = [-1;-2;-4]; options = optimoptions('coneprog','Display','iter'); A = []; b = []; Aeq = []; beq = []; lb = []; ub = [];

Solve the problem, requesting information about the solution process.

[x,fval,exitflag,output] = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options)
Iter Fval原始Infeas双重Infeas二元性差距me 1 0.000000e+00 0.000000e+00 5.333333e-01 5.555556e-02 0.02 2 -9.696012e+00 5.551115e-17 7.631901e-02 7.949897e-03 0.03 3 -1.178942e+01 3.700743e-17 1.261803e-02 1.314378e-03 0.03 4 -1.294426e+01 1.850372e-17 1.683078e-03 1.753206e-04 0.03 5 -1.295217e+01 9.251859e-18 8.994595e-04 9.369370e-05 0.03 6 -1.295331e+01 9.251859e-18 4.748841e-04 4.946709e-05 0.03 7 -1.300753e+01 9.251859e-18 2.799942e-05 2.916606e-06 0.03 8 -1.300671e+01 9.251859e-18 2.366136e-05 2.464725e-06 0.03 9 -1.300850e+01 9.251859e-18 8.222244e-06 8.564838e-07 0.03 10 -1.300843e+01 1.850372e-17 7.318333e-06 7.623264e-07 0.03 11 -1.300865e+01 9.251859e-18 2.636568e-06 2.746425e-07 0.03 12 -1.300892e+01 1.850372e-17 3.407939e-08 3.549936e-09 0.03 Optimal solution found.
x =3×10.4238 1.6477 2.3225
fval = -13.0089
exitflag = 1
output =struct with fields:iterations: 12 primalfeasibility: 1.8504e-17 dualfeasibility: 3.4079e-08 dualitygap: 3.5499e-09 algorithm: 'interior-point' linearsolver: 'augmented' message: 'Optimal solution found.'
  • Both the iterative display and the output structure show thatconeprogused 12 iterations to arrive at the solution.

  • The exit flag value1and theoutput.messagevalue'Optimal solution found.'indicate that the solution is reliable.

  • Theoutput结构表明,不可能实行倾向于decrease through the solution process, as does the duality gap.

  • You can reproduce thefvaloutput by multiplyingf'*x.

f'*x
ans = -13.0089

Create a second-order cone programming problem. To save time and memory, create the highest-index constraint first.

A = diag([1,2,0]); b = zeros(3,1); d = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(A,b,d,gamma); A = diag([3,0,1]); d = [0;1;0]; socConstraints(2) = secondordercone(A,b,d,gamma); A = diag([0;1/2;1/2]); d = [1;0;0]; socConstraints(1) = secondordercone(A,b,d,gamma); f = [-1;-2;-4];

Solve the problem, requesting dual variables at the solution along with all otherconeprogoutput..

[x,fval,exitflag,output,lambda] = coneprog(f,socConstraints);
Optimal solution found.

Examine the returnedlambdastructure. Because the only problem constraints are cone constraints, examine only thesocfield in thelambdastructure.

disp(lambda.soc)
1.0e-05 * 0.0543 0.1853 0.0612

The constraints have nonzero dual values, indicating the constraints are active at the solution.

Input Arguments

collapse all

Coefficient vector, specified as a real vector or real array. The coefficient vector represents the objective functionf'*x. The notation assumes thatfis a column vector, but you can use a row vector or array. Internally,coneprogconvertsfto the column vectorf(:).

Example:f = [1,3,5,-6]

Data Types:double

Second-order cone constraints, specified as vector ofSecondOrderConeConstraint对象. Create these objects using thesecondorderconefunction.

socConstraintsencodes the constraints

A sc ( i ) x b sc ( i ) d sc T ( i ) x γ ( i )

where the mapping between the array and the equation is as follows:

  • Asc(i) =socConstraints.A(i)

  • bsc(i) =socConstraints.b(i)

  • dsc(i) =socConstraints.d(i)

  • γ(i) =socConstraints.gamma(i)

Example:Asc = diag([1 1/2 0]); bsc = zeros(3,1); dsc = [0;0;1]; gamma = -1; socConstraints = secondordercone(Asc,bsc,dsc,gamma);

Data Types:struct

Linear inequality constraints, specified as a real matrix.Ais anM-by-Nmatrix, whereMis the number of inequalities, andNis the number of variables (length off). For large problems, passAas a sparse matrix.

Aencodes theMlinear inequalities

A*x <= b,

wherexis the column vector ofNvariablesx(:), andbis a column vector withMelements.

For example, consider these inequalities:

x1+ 2x2≤ 10
3x1+ 4x2≤ 20
5x1+ 6x2≤ 30.

Specify the inequalities by entering the following constraints.

A = [1,2;3,4;5,6]; b = [10;20;30];

Example:To specify that the x-components add up to 1 or less, takeA = ones(1,N)andb = 1.

Data Types:double

Linear inequality constraints, specified as a real vector.bis anM-element vector related to theAmatrix. If you passbas a row vector, solvers internally convertbto the column vectorb(:). For large problems, passbas a sparse vector.

bencodes theMlinear inequalities

A*x <= b,

wherexis the column vector ofNvariablesx(:), andAis a matrix of sizeM-by-N.

For example, consider these inequalities:

x1+ 2x2≤ 10
3x1+ 4x2≤ 20
5x1+ 6x2≤ 30.

Specify the inequalities by entering the following constraints.

A = [1,2;3,4;5,6]; b = [10;20;30];

Example:To specify that the x components sum to 1 or less, useA = ones(1,N)andb = 1.

Data Types:double

Linear equality constraints, specified as a real matrix.Aeqis anMe-by-Nmatrix, whereMeis the number of equalities, andNis the number of variables (length off). For large problems, passAeqas a sparse matrix.

Aeqencodes theMelinear equalities

Aeq*x = beq,

wherexis the column vector ofNvariablesx(:), andbeqis a column vector withMeelements.

For example, consider these equalities:

x1+ 2x2+ 3x3= 10
2x1+ 4x2+x3= 20.

Specify the equalities by entering the following constraints.

Aeq = [1,2,3;2,4,1]; beq = [10;20];

Example:To specify that the x-components sum to 1, takeAeq = ones(1,N)andbeq = 1.

Data Types:double

Linear equality constraints, specified as a real vector.beqis anMe-element vector related to theAeqmatrix. If you passbeqas a row vector, solvers internally convertbeqto the column vectorbeq(:). For large problems, passbeqas a sparse vector.

beqencodes theMelinear equalities

Aeq*x = beq,

wherexis the column vector ofNvariablesx(:), andAeqis a matrix of sizeMe-by-N.

For example, consider these equalities:

x1+ 2x2+ 3x3= 10
2x1+ 4x2+x3= 20.

Specify the equalities by entering the following constraints.

Aeq = [1,2,3;2,4,1]; beq = [10;20];

Example:指定的x分量之和为1,使用Aeq = ones(1,N)andbeq = 1.

Data Types:double

Lower bounds, specified as a real vector or real array. If the length offis equal to the length oflb, thenlbspecifies that

x(i) >= lb(i)for alli.

Ifnumel(lb) < numel(f), thenlbspecifies that

x(i) >= lb(i)for1 <= i <= numel(lb).

In this case, solvers issue a warning.

Example:To specify that all x-components are positive, uselb = zeros(size(f)).

Data Types:double

Upper bounds, specified as a real vector or real array. If the length offis equal to the length ofub, thenubspecifies that

x(i) <= ub(i)for alli.

Ifnumel(ub) < numel(f), thenubspecifies that

x(i) <= ub(i)for1 <= i <= numel(ub).

In this case, solvers issue a warning.

Example:To specify that all x-components are less than1, useub = ones(size(f)).

Data Types:double

Optimization options, specified as the output ofoptimoptions.

Option Description
ConstraintTolerance

Feasibility tolerance for constraints, a scalar from0through1.ConstraintTolerancemeasures primal feasibility tolerance. The default is1e-6.

Display

Level of display (seeIterative Display):

  • 'final'(default) displays only the final output.

  • 'iter'displays output at each iteration.

  • 'off'or'none'displays no output.

LinearSolver

Algorithm for solving one step in the iteration:

  • 'auto'(default) —coneprogchooses the step solver.

    • If the problem is sparse, the step solver is'prodchol'.

    • Otherwise, the step solver is'augmented'.

  • 'augmented'— Augmented form step solver. See[1].

  • “也不mal'— Normal form step solver. See[1].

  • 'prodchol'— Product form Cholesky step solver. See[4]and[5].

  • 'schur'— Schur complement method step solver. See[2].

If'auto'does not perform well, try these suggestions forLinearSolver:

  • If the problem is sparse, try“也不mal'.

  • If the problem is sparse with some dense columns or large cones, try'prodchol'or'schur'.

  • If the problem is dense, use'augmented'.

For a sparse example, seeCompare Speeds of coneprog Algorithms.

MaxIterations

Maximum number of iterations allowed, a positive integer. The default is200.

SeeTolerances and Stopping CriteriaandIterations and Function Counts.

MaxTime

Maximum amount of time in seconds that the algorithm runs, a positive number orInf. The default isInf, which disables this stopping criterion.

OptimalityTolerance

Termination tolerance on the dual feasibility, a positive scalar. The default is1e-6.

Example:optimoptions('coneprog','Display','iter','MaxIterations',100)

Problem structure, specified as a structure with the following fields.

Field Name Entry

f

Linear objective function vectorf

socConstraints

Structure array of second-order cone constraints

Aineq

Matrix of linear inequality constraints

bineq

Vector of linear inequality constraints

Aeq

Matrix of linear equality constraints

beq

Vector of linear equality constraints
lb Vector of lower bounds
ub Vector of upper bounds

solver

'coneprog'

options

Options created withoptimoptions

Data Types:struct

Output Arguments

collapse all

Solution, returned as a real vector or real array. The size ofxis the same as the size off. Thexoutput is empty when theexitflagvalue is –2, –3, or –10.

Objective function value at the solution, returned as a real number. Generally,fval=f'*x. Thefvaloutput is empty when theexitflagvalue is –2, –3, or –10.

Reasonconeprogstopped, returned as an integer.

Value Description

1

The function converged to a solutionx.

0

The number of iterations exceededoptions.MaxIterations, or the solution time in seconds exceededoptions.MaxTime.

-2

No feasible point was found.

-3

The problem is unbounded.

-7

The search direction became too small. No further progress could be made.

-10

The problem is numerically unstable.

Tip

If you get exit flag0,-7, or-10, try using a different value of theLinearSolveroption.

Information about the optimization process, returned as a structure with these fields.

Field Description
algorithm

Optimization algorithm used

dualfeasibility

最大的双重约束违反

dualitygap

Duality gap

iterations

Number of iterations

message

Exit message

primalfeasibility

Maximum of constraint violations

linearsolver Internal step solver algorithm used

Theoutputfieldsdualfeasibility,dualitygap, andprimalfeasibilityare empty when theexitflagvalue is –2, –3, or –10.

Dual variables at the solution, returned as a structure with these fields.

Field Description
lower

Lower bounds corresponding tolb

upper

Upper bounds corresponding toub

ineqlin

Linear inequalities corresponding toAandb

eqlin

Linear equalities corresponding toAeqandbeq

soc Second-order cone constraints corresponding tosocConstraints

lambdais empty ([]) when theexitflagvalue is –2, –3, or –10.

The Lagrange multipliers (dual variables) are part of the following Lagrangian, which is stationary (zero gradient) at a solution:

f T x + i λ soc ( i ) ( d soc T ( i ) x gamma ( i ) A soc ( i ) x b soc ( i ) ) + λ ineqlin T ( b A x ) + λ eqlin T ( Aeq x beq ) + λ upper T ( ub x ) + λ lower T ( x lb ) .

The inequality terms that multiply thelambdafields are nonnegative.

More About

collapse all

Second-Order Cone Constraint

Why is the constraint

A x b d T x γ

called a second-order cone constraint? Consider a cone in 3-D space with elliptical cross-sections in thex-yplane, and a diameter proportional to thezcoordinate. Theycoordinate has scale ½, and thexcoordinate has scale 1. The inequality defining the inside of this cone with its point at [0,0,0] is

x 2 + y 2 4 z .

In theconeprogsyntax, this cone has the following arguments.

A = diag([1 1/2 0]); b = [0;0;0]; d = [0;0;1]; gamma = 0;

Plot the boundary of the cone.

[X,Y] = meshgrid(-2:0.1:2); Z = sqrt(X.^2 + Y.^2/4); surf(X,Y,Z) view(8,2) xlabel'x'ylabel'y'zlabel'z'

Cone with point at zero, widening in the vertical direction.

Thebandgammaarguments move the cone. TheAanddarguments rotate the cone and change its shape.

Algorithms

The algorithm uses an interior-point method. For details, seeSecond-Order Cone Programming Algorithm.

Alternative Functionality

App

TheOptimizeLive Editor task provides a visual interface forconeprog.

Version History

Introduced in R2020b

expand all