socp: Second-order Cone Programming

In Rsocp: Rmetrics - An R Extenstion Library to Use SOCP from R

Second-order Cone Programming

Description

Solve Second-order Cone Problem by primal-dual interior point method.

Usage

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

Arguments

f	Vector defining linear objective, length(f)==length(x)
A	Matrix with the A(i) vertically stacked: A = [ A(1); A(2); ... A(L)]
b	Vector with the b(i) vertically stacked: b = [ b(1); b(2); ... b(L)]
C	Matrix with the c(i)\' vertically stacked: C = [ c(1)\'; c(2)\'; ... c(L)\']
d	Vector with the d(i) vertically stacked: d = [ d(1); d(2); ... d(L)]
N	vector of size L, defining the size of each constraint.
x	Primal feasible initial point. Must satisfy: norm(A(i)*x+b(i)) < c(i)'*x+d(i) , i=1,...,L
z	dual feasible initial point.
w	dual feasible initial point.
control	A list of control parameters. See below for details.

Details

minimize

f'*x

subject to

norm(A_i*x+b_i) <=c_i'*x+d_i , i=1,…, L

The dual problem is:

maximize

-(b'*z+d*w)

subject to

A'*z+C'*w == f

norm(z_i) <= w_i , i=1,…,L

(see description of input arguments for definition of A, b, C, d, z, w)

STOPPING CRITERIA: (stop when any of the following 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

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

OTHER PARAMETERS:

Nu – duality gap vs. deviation from centrality reduction weight. As a general rule, larger values of Nu yield faster convergence, up to a point where the deviation from centrality becomes too large and the convergence becomes very slow. Required Nu>0, recommended Nu>1, typical range 2<=Nu<=50. Try Nu=10.

out.mode – specifies what will be output in hist:

0	hist is returned empty (default value)
1	vector with duality gap (an upper bound on absolute
	error), for the initial point and after each iteration
2	matrix with duality gap and deviation from centrality

Value

x	Solution.
z	solution to the dual problem
iter	Number of iterations performed
hist	see out_mode.
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 optimizer.

Author(s)

R port by Yohan Chalabi and Diethelm Wuertz,
C Code for SOCP written by M. Lobo, L. Vandenberghe, and S. Boyd.

References

SOCP, Software for Second-order Cone Programming User's Guide, Beta Version April 1997, Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd.

https://web.stanford.edu/~boyd/old_software/SOCP.html

See Also

socpControl

Examples

## socp 
   # min   x + y
   # s.t.  x^2 + y^2 <= 1
   #       y >= 0
 
   f <- c(1, 1)
   A <- matrix(c(1, 0, 0, 0, 1, 0), ncol = 2)
   b <- c(0, 0, 0)
   C <- matrix(c(0, 0, 0, 1), ncol = 2)
   d <- c(1,0)
   N <- c(2, 1)
   x <- c(0, 0.5)
   z <- c(1, 0, 0)
   w <- c(2, 1)

   fit1 <- socp(f, A, b, C, d, N, x, z, w)
   fit1

   fit2 <- socp(f, A, b, C, d, N, x)
   fit2

   fit3 <- socp(f, A, b, C, d, N)
   fit3

Rsocp documentation built on Sept. 9, 2022, 3:10 p.m.