# coneprog

Second-order cone programming solver

## Syntax

``x = coneprog(f,socConstraints)``
``x = coneprog(f,socConstraints,A,b,Aeq,beq)``
``x = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub)``
``x = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options)``
``x = coneprog(problem)``
``[x,fval] = coneprog(___)``
``[x,fval,exitflag,output] = coneprog(___)``
``[x,fval,exitflag,output,lambda] = coneprog(___)``

## Description

The `coneprog` function is a second-order cone programming solver that finds the minimum of a problem specified by

`$\underset{x}{\mathrm{min}}{f}^{T}x$`

subject to the constraints

`$\begin{array}{c}‖{A}_{\text{sc}}\left(i\right)\cdot x-{b}_{\text{sc}}\left(i\right)‖\le {d}_{\text{sc}}^{T}\left(i\right)\cdot x-\gamma \left(i\right)\\ A\cdot x\le b\\ \text{Aeq}\cdot x=\text{beq}\\ \text{lb}\le x\le \text{ub}.\end{array}$`

f, x, b, beq, lb, and ub are vectors, and A and Aeq are matrices. For each i, the matrix Asc(i), vectors dsc(i) and bsc(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.

example

````x = coneprog(f,socConstraints)` solves the second-order cone programming problem with the constraints in `socConstraints` encoded asAsc(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 constraints `A*x `≤` b` and equality constraints `Aeq*x = beq`. Set `A = []` and `b = []` 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, `x` so that the solution is always in the range `lb ≤ x ≤ ub`. Set `Aeq = []` and `beq = []` if no equalities exist.```

example

````x = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options)` minimizes using the optimization options specified by `options`. Use `optimoptions` to set these options.```

example

````x = coneprog(problem)` finds the minimum for `problem`, a structure described in `problem`.```

example

````[x,fval] = 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,fval,exitflag,output] = coneprog(___)` additionally returns a value `exitflag` that describes the exit condition, and a structure `output` that contains information about the optimization process.```

example

````[x,fval,exitflag,output,lambda] = coneprog(___)` additionally returns a structure `lambda` whose fields contain the dual variables at the solution `x`.```

## 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 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)`
```Optimal solution found. ```
```x = 3×1 0.4851 3.8806 2.0000 ```
```fval = -8.2462 ```

The solution component `x(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 the `coneprog` function.

`[x,fval] = coneprog(f,socConstraints)`
```Optimal solution found. ```
```x = 3×1 0.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×1 3.2304 0.6398 4.1213 ```
```fval = -26.9225 ```

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`.

```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×1 0.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 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 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.08 11 -1.300865e+01 9.251859e-18 2.636568e-06 2.746425e-07 0.08 12 -1.300892e+01 1.850372e-17 3.407939e-08 3.549936e-09 0.08 Optimal solution found. ```
```x = 3×1 0.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 Primal Infeas Dual Infeas Duality Gap Time 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×1 0.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 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`.

`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 other `coneprog` output..

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

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

`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 function `f'*x`. The notation assumes that `f` 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 of `SecondOrderConeConstraint` objects. Create these objects using the `secondordercone` function.

`socConstraints` encodes the constraints

`$‖{A}_{\text{sc}}\left(i\right)\cdot x-{b}_{\text{sc}}\left(i\right)‖\le {d}_{\text{sc}}^{T}\left(i\right)\cdot x-\gamma \left(i\right)$`

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. `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:

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, take ```A = ones(1,N)``` and `b = 1`.

Data Types: `double`

Linear inequality constraints, specified as a real vector. `b` is an `M`-element vector related to the `A` matrix. If you pass `b` as a row vector, solvers internally convert `b` to the column vector `b(:)`. For large problems, pass `b` as a sparse vector.

`b` encodes the `M` linear inequalities

`A*x <= b`,

where `x` is the column vector of `N` variables `x(:)`, and `A` is a matrix of size `M`-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, use ```A = ones(1,N)``` and `b = 1`.

Data Types: `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:

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, take `Aeq = ones(1,N)` and `beq = 1`.

Data Types: `double`

Linear equality constraints, specified as a real vector. `beq` is an `Me`-element vector related to the `Aeq` matrix. If you pass `beq` as a row vector, solvers internally convert `beq` to the column vector `beq(:)`. For large problems, pass `beq` as a sparse vector.

`beq` encodes the `Me` linear equalities

`Aeq*x = beq`,

where `x` is the column vector of `N` variables `x(:)`, and `Aeq` is a matrix of size `Me`-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: To specify that the x components sum to 1, use `Aeq = ones(1,N)` and `beq = 1`.

Data Types: `double`

Lower bounds, specified as a real vector or real array. If the length of `f` is equal to the length of `lb`, then `lb` 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 of `f` is equal to the length of `ub`, then `ub` 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 of `optimoptions`.

OptionDescription
`ConstraintTolerance`

Feasibility tolerance for constraints, a scalar from `0` through `1`. `ConstraintTolerance` measures primal feasibility tolerance. The default is `1e-6`.

`Display`

Level of display (see Iterative 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) — `coneprog` chooses 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].

• `'normal'` — 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 for `LinearSolver`:

• If the problem is sparse, try `'normal'`.

• 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, see Compare Speeds of coneprog Algorithms.

`MaxIterations`

Maximum number of iterations allowed, a positive integer. The default is `200`.

`MaxTime`

Maximum amount of time in seconds that the algorithm runs, a positive number or `Inf`. The default is `Inf`, which disables this stopping criterion.

`OptimalityTolerance`

Termination tolerance on the dual feasibility, a positive scalar. The default is `1e-6`.

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

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

Field NameEntry

`f`

Linear objective function vector `f`

`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 with `optimoptions`

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 when the `exitflag` 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 when the `exitflag` value is –`2`, –`3`, or –`10`.

Reason `coneprog` stopped, returned as an integer.

ValueDescription

`1`

The function converged to a solution `x`.

`0`

The number of iterations exceeded `options.MaxIterations`, or the solution time in seconds exceeded `options.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 flag `0`, `-7`, or `-10`, try using a different value of the `LinearSolver` option.

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

FieldDescription
`algorithm`

Optimization algorithm used

`dualfeasibility`

Maximum of dual constraint violations

`dualitygap`

Duality gap

`iterations`

Number of iterations

`message`

Exit message

`primalfeasibility`

Maximum of constraint violations

`linearsolver`Internal step solver algorithm used

The `output` fields `dualfeasibility`, `dualitygap`, and `primalfeasibility` are empty when the `exitflag` value is –2, –3, or –10.

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

FieldDescription
`lower`

Lower bounds corresponding to `lb`

`upper`

Upper bounds corresponding to `ub`

`ineqlin`

Linear inequalities corresponding to `A` and `b`

`eqlin`

Linear equalities corresponding to `Aeq` and `beq`

`soc`Second-order cone constraints corresponding to `socConstraints`

`lambda` is empty (`[]`) when the `exitflag` 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 the `lambda` fields are nonnegative.

collapse all

### Second-Order Cone Constraint

Why is the constraint

`$‖A\cdot x-b‖\le {d}^{T}\cdot x-\gamma$`

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

`$\sqrt{{x}^{2}+\frac{{y}^{2}}{4}}\le z.$`

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. The `A` and `d` arguments rotate the cone and change its shape.

## Algorithms

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

## Alternative Functionality

### App

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

## Version History

Introduced in R2020b

expand all