coneprog - Second-order cone programming solver - MATLAB (original) (raw)

Second-order cone programming solver

Since R2020b

Syntax

Description

The coneprog 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, and ub are vectors, and A and_Aeq_ are matrices. For each i, the matrix_A_soc(i), vectors_d_soc(i) and_b_soc(i), and scalar_γ_(i) are in a second-order cone constraint that you create using secondordercone.

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

[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329) = coneprog([f](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fmw%5Fc6be2066-be1c-45dc-9184-b7f385faf273),[socConstraints](#mw%5Ff1e7ce9c-2caa-4efb-a48f-1c3e1dd2b5e5)) solves the second-order cone programming problem with the constraints insocConstraints encoded as

• _A_soc(i) =socConstraints(i).A
• _b_soc(i) =socConstraints(i).b
• _d_soc(i) =socConstraints(i).d
• γ(i) =socConstraints(i).gamma

example

[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329) = coneprog([f](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fmw%5Fc6be2066-be1c-45dc-9184-b7f385faf273),[socConstraints](#mw%5Ff1e7ce9c-2caa-4efb-a48f-1c3e1dd2b5e5),[A](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-A),[b](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-b),[Aeq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-Aeq),[beq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-beq)) solves the problem subject to the inequality constraintsA*x ≤ b and equality constraintsAeq*x = beq. Set A = [] andb = [] if no inequalities exist.

example

[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329) = coneprog([f](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fmw%5Fc6be2066-be1c-45dc-9184-b7f385faf273),[socConstraints](#mw%5Ff1e7ce9c-2caa-4efb-a48f-1c3e1dd2b5e5),[A](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-A),[b](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-b),[Aeq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-Aeq),[beq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-beq),[lb](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-lb),[ub](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-ub)) defines a set of lower and upper bounds on the design variables, x so that the solution is always in the range lb ≤ x ≤ ub. Set Aeq = [] and beq = [] if no equalities exist.

example

[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329) = coneprog([f](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fmw%5Fc6be2066-be1c-45dc-9184-b7f385faf273),[socConstraints](#mw%5Ff1e7ce9c-2caa-4efb-a48f-1c3e1dd2b5e5),[A](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-A),[b](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-b),[Aeq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-Aeq),[beq](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fshared-beq),[lb](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-lb),[ub](#mw%5Fa64104e7-60c8-4370-9481-a8fa3facf992%5Fsep%5Fbuusznx-ub),[options](#mw%5F3159abce-1444-4850-bb21-1b73934406cf)) minimizes using the optimization options specified by options. Useoptimoptions to set these options.

example

[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329) = coneprog([problem](#mw%5F81e53ba0-cc4c-461b-9b00-4e040c3e56bf)) finds the minimum for problem, a structure described in problem.

example

[[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329),[fval](#mw%5F5c0e8415-cd91-4253-9b0b-38c930bbc114)] = coneprog(___) also returns the objective function value at the solution fval =f'*x, using any of the input argument combinations in previous syntaxes.

example

[[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329),[fval](#mw%5F5c0e8415-cd91-4253-9b0b-38c930bbc114),[exitflag](#mw%5F04f9ab9a-aa5e-4961-bb6e-ef0f94c0602e),[output](#mw%5Fadb20aec-ebb8-4821-b696-72dd5719f061)] = coneprog(___) additionally returns a value exitflag that describes the exit condition, and a structure output that contains information about the optimization process.

example

[[x](#mw%5F2d660da5-3f78-4fb2-8eef-9a88daa51329),[fval](#mw%5F5c0e8415-cd91-4253-9b0b-38c930bbc114),[exitflag](#mw%5F04f9ab9a-aa5e-4961-bb6e-ef0f94c0602e),[output](#mw%5Fadb20aec-ebb8-4821-b696-72dd5719f061),[lambda](#mw%5F91def31d-be50-4ca7-b78f-151125b569de)] = coneprog(___) additionally returns a structure lambda whose fields contain the dual variables at the solution x.

example

Examples

collapse all

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

Asoc = diag([1,1/2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = 0; socConstraints = secondordercone(Asoc,bsoc,dsoc,gamma);

Create an objective function vector.

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

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

Set upper and lower bounds on x(3).

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

Solve the problem by using the coneprog function.

[x,fval] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub)

x = 3×1

0.4851
3.8806
2.0000

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

norm(Asoc*x-bsoc) - dsoc'*x % Near 0 when the constraint is active

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.

Asoc = diag([1,2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(Asoc,bsoc,dsoc,gamma);

Asoc = diag([3,0,1]); dsoc = [0;1;0]; socConstraints(2) = secondordercone(Asoc,bsoc,dsoc,gamma);

Asoc = diag([0;1/2;1/2]); dsoc = [1;0;0]; socConstraints(1) = secondordercone(Asoc,bsoc,dsoc,gamma);

Create the linear objective function vector.

Solve the problem by using the coneprog function.

[x,fval] = coneprog(f,socConstraints)

x = 3×1

0.4238
1.6477
2.3225

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

f = [-4;-9;-2]; Asoc = diag([1,4,0]); bsoc = [0;0;0]; dsoc = [0;0;1]; gamma = 0; socConstraints = secondordercone(Asoc,bsoc,dsoc,gamma);

Specify a linear inequality constraint.

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

Solve the problem.

[x,fval] = coneprog(f,socConstraints,A,bsoc)

x = 3×1

3.2304
0.6398
4.1213

To observe the iterations of the coneprog solver, set the Display option to "iter".

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

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

Asoc = diag([1,1/2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = 0; socConstraints = secondordercone(Asoc,bsoc,dsoc,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 0 0.000000e+00 0.000000e+00 5.714286e-01 2.000000e-01 0.02 1 -7.558066e+00 0.000000e+00 7.151114e-02 2.502890e-02 0.02 2 -7.366973e+00 0.000000e+00 1.075440e-02 3.764040e-03 0.02 3 -8.243432e+00 0.000000e+00 5.191882e-05 1.817159e-05 0.02 4 -8.246067e+00 0.000000e+00 2.430813e-06 8.507845e-07 0.03 5 -8.246211e+00 0.000000e+00 6.154504e-09 2.154077e-09 0.03 Optimal solution found.

x = 3×1

0.4851
3.8806
2.0000

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

Asoc = diag([1,2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([3,0,1]); dsoc = [0;1;0]; socConstraints(2) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([0;1/2;1/2]); dsoc = [1;0;0]; socConstraints(1) = secondordercone(Asoc,bsoc,dsoc,gamma); f = [-1;-2;-4]; options = optimoptions("coneprog",Display="iter");

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

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

Solve the problem by calling coneprog.

[x,fval] = coneprog(problem)

Iter Fval Primal Infeas Dual Infeas Duality Gap Time 0 0.000000e+00 0.000000e+00 5.333333e-01 9.090909e-02 0.04 1 -9.696012e+00 5.551115e-17 7.631901e-02 1.300892e-02 0.04 2 -1.178942e+01 0.000000e+00 1.261803e-02 2.150800e-03 0.04 3 -1.294426e+01 9.251859e-18 1.683078e-03 2.868883e-04 0.04 4 -1.295217e+01 9.251859e-18 8.994595e-04 1.533170e-04 0.04 5 -1.295331e+01 0.000000e+00 4.748841e-04 8.094615e-05 0.04 6 -1.300753e+01 0.000000e+00 2.799942e-05 4.772628e-06 0.04 7 -1.300671e+01 9.251859e-18 2.366136e-05 4.033187e-06 0.05 8 -1.300850e+01 9.251859e-18 8.251573e-06 1.406518e-06 0.05 9 -1.300842e+01 4.625929e-18 7.332583e-06 1.249872e-06 0.05 10 -1.300866e+01 9.251859e-18 2.616719e-06 4.460317e-07 0.05 11 -1.300892e+01 1.850372e-17 2.215835e-08 3.776991e-09 0.05 Optimal solution found.

x = 3×1

0.4238
1.6477
2.3225

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

Asoc = diag([1,2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([3,0,1]); dsoc = [0;1;0]; socConstraints(2) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([0;1/2;1/2]); dsoc = [1;0;0]; socConstraints(1) = secondordercone(Asoc,bsoc,dsoc,gamma); f = [-1;-2;-4]; options = optimoptions("coneprog",Display="iter"); Aineq = []; bineq = []; Aeq = []; beq = []; lb = []; ub = [];

Solve the problem, requesting information about the solution process.

[x,fval,exitflag,output] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub,options)

Iter Fval Primal Infeas Dual Infeas Duality Gap Time 0 0.000000e+00 0.000000e+00 5.333333e-01 9.090909e-02 0.05 1 -9.696012e+00 5.551115e-17 7.631901e-02 1.300892e-02 0.06 2 -1.178942e+01 0.000000e+00 1.261803e-02 2.150800e-03 0.06 3 -1.294426e+01 9.251859e-18 1.683078e-03 2.868883e-04 0.06 4 -1.295217e+01 9.251859e-18 8.994595e-04 1.533170e-04 0.06 5 -1.295331e+01 0.000000e+00 4.748841e-04 8.094615e-05 0.06 6 -1.300753e+01 0.000000e+00 2.799942e-05 4.772628e-06 0.06 7 -1.300671e+01 9.251859e-18 2.366136e-05 4.033187e-06 0.06 8 -1.300850e+01 9.251859e-18 8.251573e-06 1.406518e-06 0.07 9 -1.300842e+01 4.625929e-18 7.332583e-06 1.249872e-06 0.07 10 -1.300866e+01 9.251859e-18 2.616719e-06 4.460317e-07 0.07 11 -1.300892e+01 1.850372e-17 2.215835e-08 3.776991e-09 0.07 Optimal solution found.

x = 3×1

0.4238
1.6477
2.3225

output = struct with fields: iterations: 11 primalfeasibility: 1.8504e-17 dualfeasibility: 2.2158e-08 dualitygap: 3.7770e-09 algorithm: 'interior-point' linearsolver: 'augmented' message: 'Optimal solution found.'

• Both the iterative display and the output structure show that coneprog takes 11 iterations to arrive at the solution.
• The exit flag value 1 and the output.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 multiplying f'*x.

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

Asoc = diag([1,2,0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = -1; socConstraints(3) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([3,0,1]); dsoc = [0;1;0]; socConstraints(2) = secondordercone(Asoc,bsoc,dsoc,gamma); Asoc = diag([0;1/2;1/2]); dsoc = [1;0;0]; socConstraints(1) = secondordercone(Asoc,bsoc,dsoc,gamma); f = [-1;-2;-4];

Solve the problem, requesting dual variables at the solution along with all other coneprog output..

[x,fval,exitflag,output,lambda] = coneprog(f,socConstraints);

Examine the returned lambda structure. Because the only problem constraints are cone constraints, examine only the soc field in the lambda structure.

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 function f'*x. The notation assumes thatf is a column vector, but you can use a row vector or array. Internally, coneprog converts f to the column vector f(:).

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

Data Types: double

Second-order cone constraints, specified as vector or cell array of SecondOrderConeConstraint objects. Create these objects using the secondordercone function.

socConstraints encodes the constraints

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

• _A_soc(i) =socConstraints.A(i)
• _b_soc(i) =socConstraints.b(i)
• _d_soc(i) =socConstraints.d(i)
• γ(i) =socConstraints.gamma(i)

Example: Asoc = diag([1 1/2 0]); bsoc = zeros(3,1); dsoc = [0;0;1]; gamma = -1; socConstraints = secondordercone(Asoc,bsoc,dsoc,gamma);

Linear inequality constraints, specified as a real matrix. A is an M-by-N matrix, where M is the number of inequalities, and N is the number of variables (length of f). For large problems, pass A as a sparse matrix.

A encodes the M linear inequalities

A*x <= b,

where x is the column vector of N variables x(:), and b is a column vector with M elements.

For example, consider these inequalities:

_x_1 + 2_x_2 ≤ 10
3_x_1 + 4_x_2 ≤ 20
5_x_1 + 6_x_2 ≤ 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, take A = ones(1,N) and b = 1.

Data Types: double

Data Types: single | double

Linear equality constraints, specified as a real matrix. Aeq is an Me-by-N matrix, where Me is the number of equalities, and N is the number of variables (length of f). For large problems, pass Aeq as a sparse matrix.

Aeq encodes the Me linear equalities

Aeq*x = beq,

where x is the column vector of N variables x(:), and beq is a column vector with Me elements.

For example, consider these equalities:

_x_1 + 2_x_2 + 3_x_3 = 10
2_x_1 + 4_x_2 +_x_3 = 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, take Aeq = ones(1,N) andbeq = 1.

Data Types: double

Data Types: single | double

Lower bounds, specified as a real vector or real array. If the length off is equal to the length of lb, thenlb specifies that

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

If numel(lb) < numel(f), then lb specifies that

x(i) >= lb(i) for 1 <= i <= numel(lb).

In this case, solvers issue a warning.

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

Data Types: double

Upper bounds, specified as a real vector or real array. If the length off is equal to the length of ub, thenub specifies that

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

If numel(ub) < numel(f), then ub specifies that

x(i) <= ub(i) for 1 <= i <= numel(ub).

In this case, solvers issue a warning.

Example: To specify that all x-components are less than 1, use ub = ones(size(f)).

Data Types: double

Optimization options, specified as the output ofoptimoptions.

Code generation does not support the MaxTime option.

Example: optimoptions("coneprog",Display="iter",MaxIterations=100)

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

Data Types: struct

Output Arguments

collapse all

Solution, returned as a real vector or real array. The size of x is the same as the size of f. The x output is empty (NaN for code generation) when theexitflag value is –2, –3, or –10.

Objective function value at the solution, returned as a real number. Generally,fval = f'*x. The fval output is empty (NaN for code generation) when theexitflag value is –2, –3, or –10.

Reason coneprog stopped, returned as an integer.

Tip

If you get exit flag 0, -7, or-10, try using a different value of theLinearSolver option.

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

The output fields algorithm,dualfeasibility, dualitygap,linearsolver, and primalfeasibility are empty (numeric values are NaN for code generation) when theexitflag value is –2, –3, or –10.

The iterations field has int32 type for code generation, not double.

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

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:

More About

collapse all

Why is the constraint

called a second-order cone constraint? Consider a cone in 3-D space with elliptical cross-sections in the _x_-y plane, and a diameter proportional to the z coordinate. The y coordinate has scale ½, and the x coordinate has scale 1. The inequality defining the inside of this cone with its point at [0,0,0] is

In the coneprog 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'

The b and gamma arguments move the cone. TheA and d arguments rotate the cone and change its shape.

Alternative Functionality

App

The Optimize Live Editor task provides a visual interface for coneprog.

Extended Capabilities

expand all

Usage notes and limitations:

• coneprog supports code generation using either the codegen (MATLAB Coder) function or the MATLAB® Coder™ app. You must have a MATLAB Coder license to generate code.
• The target hardware must support standard double-precision floating-point computations.
• Code generation targets do not use the same math kernel libraries as MATLAB solvers. Therefore, code generation solutions can vary from solver solutions, especially for poorly conditioned problems.
• coneprog does not support the problem argument for code generation.
  [x,fval] = coneprog(problem) % Not supported
• All coneprog input matrices such as A,Aeq, secondordercone inputs, lb, and ub can be full or sparse. To use sparse inputs, you must enable dynamic memory allocation. See Code Generation Limitations (MATLAB Coder). Solvers have good performance with sparse inputs when the fraction of nonzero entries is small.
• Pass cone constraints as a cell array of SecondOrderConeConstraint objects, not as an array of these objects. If you have no cone constraints, pass an empty cell {}.
• The lb and ub arguments must have the same number of entries as the number of problem variables, or must be empty[].
• If your target hardware does not support infinite bounds, use optim.coder.infbound.
• For advanced code optimization involving embedded processors, you also need an Embedded Coder® license.
• Code generation supports these options for optimoptions:
  • ConstraintTolerance
  • Display
  • LinearSolver
  • MaxIterations
  • OptimalityTolerance
• Generated code has limited error checking for options. The recommended way to update an option is to use dot notation, not optimoptions.
  opts = optimoptions("coneprog",ConstraintTolerance=1e-4);
  opts = optimoptions(opts,MaxIterations=1e4); % Not preferred
  opts.MaxIterations = 1e4; % Recommended
• coneprog supports options passed to the solver, not only options created in the code.
• If you specify an option that is not supported, the option is typically ignored during code generation. For reliable results, specify only supported options.

Version History

Introduced in R2020b

expand all

• All input matrices for coneprog code generation such asA, Aeq, lb,ub, and the inputs to secondordercone can be full or sparse.
• The new exitflag -8 applies only to code generation with sparse data.
• You can now update options using optimoptions, though the recommended way is to use dot notation.
  opts = optimoptions("coneprog",ConstraintTolerance=1e-4);
  opts = optimoptions(opts,MaxIterations=1e4); % Not preferred
  opts.MaxIterations = 1e4; % Recommended

For details, see Code Generation for coneprog Background.

The coneprog lambda output argument fields lambda.eq and lambda.ineq have been renamed to lambda.eqlin and lambda.ineqlin, respectively. This change causes the coneprog lambda structure fields to have the same names as the corresponding fields in other solvers.