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())

Arguments

Vector defining linear objective, length(f)==length(x)

Matrix with the $A_i$ vertically stacked: $A = [ A_1; A_2; \ldots; A_L]$.

Vector with the $b_i$ vertically stacked: $b = [ b_1; b_2; \ldots; b_L]$.

Matrix with the $c_i'$ vertically stacked: $C = [ c_1'; c_2'; \ldots; c_L']$.

Vector with the $d_i$ vertically stacked: $d = [ d_1; d_2; \ldots; d_L]$.

Vector of size L, defining the size of each constraint.

Primal feasible initial point. Must satisfy: $|| A_i*x + b_i || < c_i' * x + d_i$ for $i = 1, \ldots, L$.

Dual feasible initial point.

control

A list of control parameters.

Value

A list-object with the following elements:
xSolution to the primal problem.
zSolution to the dual problem.
iterNumber of iterations performed.
histsee out_mode in SocpControl.
convergenceA logical code. TRUE indicates successful convergence.
infoA numerical code. It indicates if the convergence was successful.
messageA character string giving any additional information returned by the optimiser.

Details

The primal formulation of an SOCP is given as:

m i n i m i s e 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.="" dual="" form="" of="" an="" socp="" expressed="" as:=""

m a x i m i s e = " " \sum_{i = " 1}^{L} " - (b^{'} = " " z_{i} = " " d_{i} = " " w_{i})

="" subject=""

\sum_{i = " 1}^{L} " (a_{i}^{'} = " " c_{i} = " " w_{i}) = " f

" and=""

| | z_{i} = " " | | = " w_{i}

" l$,="" given="" strictly="" feasible="" primal="" initial="" points.="" algorithm="" stops,="" if="" one="" following="" criteria="" met:=""

abs.tol-- maximum absolute error in objective function; guarantees that for any x:$abs(f'*x - f'*x\_opt) <= abs\_tol$.<="" li="">

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 withmax_iter = 0only checks feasibility ofxandz, (and returns gap and deviation from centrality).

The target value is reached.rel_tolis negative and the primal objective$p$is less than thetarget.

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.

Last chance! 50% off unlimited learning