coneprog
Second-order cone programming solver
Syntax
Description
Theconeprog
function is a second-order cone programming solver that finds the minimum of a problem specified by
subject to the constraints
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。
solves the second-order cone programming problem with the constraints inx
= coneprog(f
,socConstraints
)socConstraints
encoded as
Asc(i) =
socConstraints(i).A
bsc(i) =
socConstraints(i).b
dsc(i) =
socConstraints(i).d
γ(i) =
socConstraints(i).gamma
Examples
Single Cone Constraint
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 theconeprog
function.
[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
Several Cone Constraints
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 theconeprog
function.
[x,fval] = coneprog(f,socConstraints)
Optimal solution found.
x =3×10.4238 1.6477 2.3225
fval = -13.0089
Cone Programming with Linear Constraints
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.
= (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
Cone Programming with Nondefault Options
To observe the iterations of theconeprog
solver, set theDisplay
option 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 Primal Infeas Dual Infeas Duality Gap Time 1 0.000000e+00 0.000000e+00 5.714286e-01 1.250000e-01 0.01 2 -7.558066e+00 0.000000e+00 7.151114e-02 1.564306e-02 0.02 3 -7.366973e+00 2.775558e-17 1.075440e-02 2.352525e-03 0.02 4 -8.243432e+00 1.387779e-17 5.191882e-05 1.135724e-05 0.02 5 -8.246067e+00 0.000000e+00 2.430813e-06 5.317403e-07 0.02 6 -8.246211e+00 1.387779e-17 6.154504e-09 1.346298e-09 0.02 Optimal solution found.
x =3×10.4851 3.8806 2.0000
fval = -8.2462
Cone Programming with Problem Structure
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 Primal Infeas Dual Infeas Duality Gap Time 1 0.000000e+00 0.000000e+00 5.333333e-01 5.555556e-02 0.06 2 -9.696012e+00 5.551115e-17 7.631901e-02 7.949897e-03 0.07 3 -1.178942e+01 3.700743e-17 1.261803e-02 1.314378e-03 0.07 4 -1.294426e+01 1.850372e-17 1.683078e-03 1.753206e-04 0.07 5 -1.295217e+01 9.251859e-18 8.994595e-04 9.369370e-05 0.07 6 -1.295331e+01 9.251859e-18 4.748841e-04 4.946709e-05 0.07 7 -1.300753e+01 9.251859e-18 2.799942e-05 2.916606e-06 0.07 8 -1.300671e+01 9.251859e-18 2.366136e-05 2.464725e-06 0.07 9 -1.300850e+01 9.251859e-18 8.222244e-06 8.564838e-07 0.07 10 -1.300843e+01 1.850372e-17 7.318333e-06 7.623264e-07 0.07 11 -1.300865e+01 9.251859e-18 2.636568e-06 2.746425e-07 0.07 12 -1.300892e+01 1.850372e-17 3.407939e-08 3.549936e-09 0.08 Optimal solution found.
x =3×10.4238 1.6477 2.3225
fval = -13.0089
Examineconeprog
Solution Process
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 Primal Infeas Dual Infeas Duality Gap Time 1 0.000000e+00 0.000000e+00 5.333333e-01 5.555556e-02 0.03 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.04 12 -1.300892e+01 1.850372e-17 3.407939e-08 3.549936e-09 0.04 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 that
coneprog
used 12 iterations to arrive at the solution.The exit flag value
1
and theoutput.message
value'Optimal solution found.'
indicate that the solution is reliable.The
output
structure shows that the infeasibilities tend to decrease through the solution process, as does the duality gap.You can reproduce the
fval
output by multiplyingf'*x
。
f'*x
ans = -13.0089
Obtainconeprog
Dual Variables
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 otherconeprog
output..
[x,fval,exitflag,output,lambda] = coneprog(f,socConstraints);
Optimal solution found.
Examine the returnedlambda
structure. Because the only problem constraints are cone constraints, examine only thesoc
field in thelambda
structure.
disp(lambda.soc)
1.0e-06 * 0.2109 0.7204 0.3662
The constraints have nonzero dual values, indicating the constraints are active at the solution.
Input Arguments
f
—Coefficient vector
real vector|real array
Coefficient vector, specified as a real vector or real array. The coefficient vector represents the objective functionf'*x
。The notation assumes thatf
is a column vector, but you can use a row vector or array. Internally,coneprog
convertsf
to the column vectorf(:)
。
Example:f = [1,3,5,-6]
Data Types:double
socConstraints
—Second-order cone constraints
vector ofSecondOrderConeConstraint
objects
Second-order cone constraints, specified as vector ofSecondOrderConeConstraint
objects. Create these objects using thesecondordercone
function.
socConstraints
encodes the constraints
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
A
—线性我nequality constraints
real matrix
线性我nequality constraints, specified as a real matrix.A
is anM
-by-N
matrix, whereM
is the number of inequalities, andN
is the number of variables (length off
). For large problems, passA
as a sparse matrix.
A
encodes theM
linear inequalities
A*x <= b
,
wherex
is the column vector ofN
variablesx(:)
, andb
is a column vector withM
elements.
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:指定that the x-components add up to 1 or less, takeA = ones(1,N)
andb = 1
。
Data Types:double
b
—线性我nequality constraints
real vector
线性我nequality constraints, specified as a real vector.b
is anM
-element vector related to theA
matrix. If you passb
as a row vector, solvers internally convertb
to the column vectorb(:)
。For large problems, passb
as a sparse vector.
b
encodes theM
linear inequalities
A*x <= b
,
wherex
is the column vector ofN
variablesx(:)
, andA
is 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:指定that the x components sum to 1 or less, useA = ones(1,N)
andb = 1
。
Data Types:double
Aeq
—Linear equality constraints
real matrix
Linear equality constraints, specified as a real matrix.Aeq
is an我
-by-N
matrix, where我
is the number of equalities, andN
is the number of variables (length off
). For large problems, passAeq
as a sparse matrix.
Aeq
encodes the我
linear equalities
Aeq*x = beq
,
wherex
is the column vector ofN
variablesx(:)
, andbeq
is a column vector with我
elements.
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:指定that the x-components sum to 1, takeAeq = ones(1,N)
andbeq = 1
。
Data Types:double
beq
—Linear equality constraints
real vector
Linear equality constraints, specified as a real vector.beq
is an我
-element vector related to theAeq
matrix. If you passbeq
as a row vector, solvers internally convertbeq
to the column vectorbeq(:)
。For large problems, passbeq
as a sparse vector.
beq
encodes the我
linear equalities
Aeq*x = beq
,
wherex
is the column vector ofN
variablesx(:)
, andAeq
is a matrix of size我
-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:指定that the x components sum to 1, useAeq = ones(1,N)
andbeq = 1
。
Data Types:double
lb
—Lower bounds
real vector|real array
Lower bounds, specified as a real vector or real array. If the length off
is equal to the length oflb
, thenlb
specifies that
x(i) >= lb(i)
for alli
。
Ifnumel(lb) < numel(f)
, thenlb
specifies that
x(i) >= lb(i)
for1 <= i <= numel(lb)
。
In this case, solvers issue a warning.
Example:指定that all x-components are positive, uselb = zeros(size(f))
。
Data Types:double
ub
—Upper bounds
real vector|real array
Upper bounds, specified as a real vector or real array. If the length off
is equal to the length ofub
, thenub
specifies that
x(i) <= ub(i)
for alli
。
Ifnumel(ub) < numel(f)
, thenub
specifies that
x(i) <= ub(i)
for1 <= i <= numel(ub)
。
In this case, solvers issue a warning.
Example:指定that all x-components are less than1
, useub = ones(size(f))
。
Data Types:double
options
—Optimization options
output ofoptimoptions
Optimization options, specified as the output ofoptimoptions
。
Option | Description |
---|---|
ConstraintTolerance |
Feasibility tolerance for constraints, a scalar from |
|
Level of display (seeIterative Display):
|
LinearSolver |
Algorithm for solving one step in the iteration:
If
For a sparse example, seeCompare Speeds of coneprog Algorithms。 |
|
Maximum number of iterations allowed, a positive integer. The default is SeeTolerances and Stopping CriteriaandIterations and Function Counts。 |
MaxTime |
Maximum amount of time in seconds that the algorithm runs, a positive number or |
|
Termination tolerance on the dual feasibility, a positive scalar. The default is |
Example:optimoptions('coneprog','Display','iter','MaxIterations',100)
problem
—Problem structure
structure
Problem structure, specified as a structure with the following fields.
Field Name | Entry |
---|---|
|
Linear objective function vectorf |
|
Structure array of second-order cone constraints |
|
Matrix of linear inequality constraints |
|
Vector of linear inequality constraints |
|
Matrix of linear equality constraints |
|
Vector of linear equality constraints |
lb |
Vector of lower bounds |
ub |
Vector of upper bounds |
|
'coneprog' |
|
Options created withoptimoptions |
Data Types:struct
Output Arguments
fval
— Objective function value at the solution
real number
Objective function value at the solution, returned as a real number. Generally,fval
=f'*x
。Thefval
output is empty when theexitflag
value is –2
, –3
, or –10
。
exitflag
— Reasonconeprog
stopped
integer
Reasonconeprog
stopped, returned as an integer.
价值 | Description |
---|---|
|
功能融合到一个解决方案 |
|
The number of iterations exceeded |
|
No feasible point was found. |
|
The problem is unbounded. |
|
The search direction became too small. No further progress could be made. |
|
The problem is numerically unstable. |
Tip
If you get exit flag0
,-7
, or-10
, try using a different value of theLinearSolver
option.
output
— Information about optimization process
structure
Information about the optimization process, returned as a structure with these fields.
Field | Description |
---|---|
algorithm |
Optimization algorithm used |
dualfeasibility |
最大的双重约束violations |
dualitygap |
Duality gap |
iterations |
Number of iterations |
message |
Exit message |
primalfeasibility |
Maximum of constraint violations |
linearsolver |
Internal step solver algorithm used |
Theoutput
fieldsdualfeasibility
,dualitygap
, andprimalfeasibility
are empty when theexitflag
value is –2, –3, or –10.
lambda
— Dual variables at the solution
structure
Dual variables at the solution, returned as a structure with these fields.
Field | Description |
---|---|
lower |
Lower bounds corresponding to |
upper |
Upper bounds corresponding to |
ineqlin |
|
eqlin |
|
soc |
Second-order cone constraints corresponding tosocConstraints |
lambda
is empty ([]
) when theexitflag
value is –2
, –3
, or –10
。
The Lagrange multipliers (dual variables) are part of the following Lagrangian, which is stationary (zero gradient) at a solution:
The inequality terms that multiply thelambda
fields are nonnegative.
More About
Second-Order Cone Constraint
为什么约束
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
In theconeprog
syntax, 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'
Theb
andgamma
arguments move the cone. TheA
andd
arguments 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 R2020bR2021a:Twoconeprog
lambda
Structures Renamed
Theconeprog
lambda
output argument fieldslambda.eq
andlambda.ineq
have been renamed tolambda.eqlin
andlambda.ineqlin
, respectively. This change causes theconeprog
lambda
structure fields to have the same names as the corresponding fields in other solvers.
Abrir ejemplo
Tiene una versión modificada de este ejemplo. ¿Desea abrir este ejemplo con sus modificaciones?
Comando de MATLAB
Ha hecho clic en un enlace que corresponde a este comando de MATLAB:
Ejecute el comando introduciéndolo en la ventana de comandos de MATLAB. Los navegadores web no admiten comandos de MATLAB.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select:。
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina(Español)
- Canada(English)
- United States(English)
Europe
- Belgium(English)
- Denmark(English)
- Deutschland(Deutsch)
- España(Español)
- Finland(English)
- France(Français)
- Ireland(English)
- Italia(Italiano)
- Luxembourg(English)
- Netherlands(English)
- Norway(English)
- Österreich(Deutsch)
- Portugal(English)
- Sweden(English)
- Switzerland
- United Kingdom(English)