Socp: Second-order Cone Programming

Description

The function solves second-order cone problem by primal-dual interior point method. It is a wrapper function to the C-routines written by Lobo, Vandenberghe and Boyd (see reference below).

Usage

Socp(f, A, b, C, d, N,
     x = NULL, z = NULL, w = NULL, control = list())

Value

A list-object with the following elements:

x: Solution to the primal problem.
z: Solution to the dual problem.
iter: Number of iterations performed.
hist: see out_mode in SocpControl.
convergence: A logical code. TRUE indicates successful convergence.
info: A numerical code. It indicates if the convergence was successful.
message: A character string giving any additional information returned by the optimiser.

Arguments

f: Vector defining linear objective, length(f)==length(x)
A: Matrix with the $A_i$ vertically stacked: $A = [ A_1; A_2; \ldots; A_L]$.
b: Vector with the $b_i$ vertically stacked: $b = [ b_1; b_2; \ldots; b_L]$.
C: Matrix with the $c_i'$ vertically stacked: $C = [ c_1'; c_2'; \ldots; c_L']$.
d: Vector with the $d_i$ vertically stacked: $d = [ d_1; d_2; \ldots; d_L]$.
N: Vector of size L, defining the size of each constraint.
x: Primal feasible initial point. Must satisfy: $|| A_i*x + b_i || < c_i' * x + d_i$ for $i = 1, \ldots, L$.
z: Dual feasible initial point.
w: Dual feasible initial point.
control: A list of control parameters.

Author

Bernhard Pfaff

Details

The primal formulation of an SOCP is given as: $$minimise f' * x$$ subject to $$||A_i*x + b_i|| <= c_i' * x + d_i$$ for $i = 1,\ldots, L$. Here, $x$ is the $(n \times 1)$ vector to be optimised. The dual form of an SOCP is expressed as: $$maximise \sum_{i = 1}^L -(b' * z_i + d_i * w_i)$$ subject to $$\sum_{i = 1}^L (A_i' * z_i + c_i * w_i) = f$$ and $$||z_i || = w_i$$ for $i = 1,\ldots, L$, given strictly feasible primal and dual initial points.

The algorithm stops, if one of the following criteria is met:

abs.tol -- maximum absolute error in objective function; guarantees that for any x: $abs(f'*x - f'*x\_opt) <= abs\_tol$.
rel.tol -- maximum relative error in objective function; guarantees that for any x: $abs(f'*x - f'*x\_opt)/(f'*x\_opt) <= rel\_tol (if f'*x\_opt > 0)$. Negative value has special meaning, see target next.
target -- if $rel\_tol<0$, stops when $f'*x < target or -b'*z >= target$.
max.iter -- limit on number of algorithm outer iterations. Most problems can be solved in less than 50 iterations. Called with max_iter = 0 only checks feasibility of x and z, (and returns gap and deviation from centrality).
The target value is reached. rel\_tol is negative and the primal objective $p$ is less than the target.

References

Lobo, M. and Vandenberghe, L. and Boyd, S., SOCP: Software for Second-order Cone Programming, User's Guide, Beta Version, April 1997, Stanford University.