R: e04nk: LP or QP problem (sparse)

e04nk {NAGFWrappers}

R Documentation

e04nk: LP or QP problem (sparse)

Description

e04nk solves sparse linear programming or quadratic programming problems.

Usage

e04nk(n, m, iobj, ncolh, qphx, a, ha, ka, bl, bu, start, names, crname, ns, xs, istate, leniz, lenz, optlist,
      nnz = nrow(a),
      nname = nrow(crname))

Arguments

n

integer

, the number of variables (excluding slacks). This is the number of columns in the linear constraint matrix A.

m

integer

, the number of general linear constraints (or slacks). This is the number of rows in A, including the free row (if any; see iobj).

iobj

integer

If iobj > 0, row iobj of A is a free row containing the nonzero elements of the vector c appearing in the linear objective term c^Tx.

ncolh

integer

n_H

, the number of leading nonzero columns of the Hessian matrix H. For FP and LP problems, ncolh must be set to zero.

qphx

function

For QP problems, you must supply a version of qphx to compute the matrix product Hx. If H has zero rows and columns, it is most efficient to order the variables x = ( y z ) ^T so that

Hx = ( H_1 0 0 0 ) ( y z ) = ( H_1y 0 ) ,

where the nonlinear variables y appear first as shown. For FP and LP problems, qphx will never be called by e04nk and hence qphx may be the dummy function e04nku.

(HX) = qphx(nstate,ncolh,x)

a

double array

The nonzero elements of A, ordered by increasing column index. Note that elements with the same row and column indices are not allowed.

ha

integer array

ha[i]

must contain the row index of the nonzero element stored in a[i] for i=1 . . . nnz. Note that the row indices for a column may be supplied in any order.

ka

integer array

ka[j]

must contain the index in a of the start of the jth column for j=1 . . . n. To specify the jth column as empty, set ka[j] = ka[j+1]. Note that the first and last elements of ka must be such that ka[1] = 1 and ka[n+1] = nnz + 1.

bl

double array

, the lower bounds for all the variables and general constraints, in the following order. The first n elements of bl must contain the bounds on the variables x, and the next m elements the bounds for the general linear constraints Ax (or slacks s) and the free row (if any). To specify a nonexistent lower bound (i.e., l_j = - infinity), set bl[j] <= - bigbnd, where bigbnd is the value of the optional argument infiniteboundsize. To specify the jth constraint as an equality, set bl[j] = bu[j] = β, say, where abs(β) < bigbnd. Note that the lower bound corresponding to the free row must be set to - infinity and stored in bl[n+iobj].

bu

double array

, the upper bounds for all the variables and general constraints, in the following order. The first n elements of bu must contain the bounds on the variables x, and the next m elements the bounds for the general linear constraints Ax (or slacks s) and the free row (if any). To specify a nonexistent upper bound (i.e., u_j = + infinity), set bu[j] >= bigbnd. Note that the upper bound corresponding to the free row must be set to + infinity and stored in bu[n+iobj].

start

string

Indicates how a starting basis is to be obtained.

start='C'

: An internal Crash procedure will be used to choose an initial basis matrix B.

start='W'

: A basis is already defined in istate (probably from a previous call).

names

string array

A set of names associated with the so-called MPSX form of the problem, as follows:

names[1]

: Must contain the name for the problem (or be blank).

names[2]

: Must contain the name for the free row (or be blank).

names[3]

: Must contain the name for the constraint right-hand side (or be blank).

names[4]

: Must contain the name for the ranges (or be blank).

names[5]

: Must contain the name for the bounds (or be blank).

crname

string array

The optional column and row names, respectively.

ns

integer

n_S

, the number of superbasics. For QP problems, ns need not be specified if start='C', but must retain its value from a previous call when start='W'. For FP and LP problems, ns need not be initialized.

xs

double array

The initial values of the variables and slacks (xs). (See the description for istate.)

istate

integer array

If start='C', the first n elements of istate and xs must specify the initial states and values, respectively, of the variables x. (The slacks s need not be initialized.) An internal Crash procedure is then used to select an initial basis matrix B. The initial basis matrix will be triangular (neglecting certain small elements in each column). It is chosen from various rows and columns of ( A -I ) . Possible values for istate[j] are as follows:

leniz

integer

lenz

integer

optlist

options list

Optional parameters may be listed, as shown in the following table:

Name	Type	Default
`Check Frequency`	integer	Default = 60
`Crash Option`	integer	Default = 2
`Crash Tolerance`	double	Default = 0.1
`Defaults`
`Expand Frequency`	integer	Default = 10000
`Factorization Frequency`	integer	Default = 100
`Feasibility Tolerance`	double	Default = max(10^ - 6, sqrt(ε))
`Infinite Bound Size`	double	Default = 10^20
`Infinite Step Size`	double	Default = max(bigbnd, 10^20)
`Iteration Limit`	integer	Default = max(50, 5(n + m))
`Iters`
`Itns`
`List`		Default for e04nk = list
`Nolist`		Default for e04nk = nolist
`LU Factor Tolerance`	double	Default = 100.0
`LU Update Tolerance`	double	Default = 10.0
`LU Singularity Tolerance`	double	Default = ε^0.67
`Minimize`		Default
`Maximize`
`Monitoring File`	integer	Default = - 1
`Optimality Tolerance`	double	Default = max(10^ - 6, sqrt(ε))
`Partial Price`	integer	Default = 10
`Pivot Tolerance`	double	Default = ε^0.67
`Print Level`	integer	= 0
`Rank Tolerance`	double	Default = 100ε
`Scale Option`	integer	Default = 2
`Scale Tolerance`	double	Default = 0.9
`Superbasics Limit`	integer	Default = min(n_H + 1, n)

nnz

integer: default = nrow(a)

The number of nonzero elements in A.

nname

integer: default = nrow(crname)

The number of column (i.e., variable) and row names supplied in crname.

nname = 1

: There are no names. Default names will be used in the printed output.

nname = n + m

: All names must be supplied.

Details

R interface to the NAG Fortran routine E04NKF.

Value

`NS`	integer The final number of superbasics. This will be zero for FP and LP problems.
`XS`	double array The final values of the variables and slacks (xs).
`ISTATE`	integer array The final states of the variables and slacks (xs). The significance of each possible value of istate[j] is as follows:
`MINIZ`	integer The minimum value of leniz required to start solving the problem. If ifail =12, e04nk may be called again with leniz suitably larger than miniz. (The bigger the better, since it is not certain how much workspace the basis factors need.)
`MINZ`	integer The minimum value of lenz required to start solving the problem. If ifail =13, e04nk may be called again with lenz suitably larger than minz. (The bigger the better, since it is not certain how much workspace the basis factors need.)
`NINF`	integer The number of infeasibilities. This will be zero if ifail =0, ifail =1.
`SINF`	double The sum of infeasibilities. This will be zero if ninf = 0. (Note that e04nk does not attempt to compute the minimum value of sinf if ifail =3.)
`OBJ`	double The value of the objective function.
`CLAMDA`	double array A set of Lagrange multipliers for the bounds on the variables and the general constraints. More precisely, the first n elements contain the multipliers (reduced costs) for the bounds on the variables, and the next m elements contain the multipliers (shadow prices) for the general linear constraints.
`IFAIL`	integer ifail =0 unless the function detects an error or a warning has been flagged (see the Errors section in Fortran library documentation).

Author(s)

NAG

References

http://www.nag.co.uk/numeric/FL/nagdoc_fl23/pdf/E04/e04nkf.pdf

Examples


optlist <- list()

ifail <- 0
qphx = function(nstate, ncolh, x) {
    
    hx <- as.matrix(mat.or.vec(ncolh, 1))
    hx[1] <- 2 %*% x[1]
    hx[2] <- 2 %*% x[2]
    hx[3] <- 2 %*% (x[3] + x[4])
    hx[4] <- hx[3]
    hx[5] <- 2 %*% x[5]
    hx[6] <- 2 %*% (x[6] + x[7])
    hx[7] <- hx[6]
    list(HX = as.matrix(hx))
}

n <- 7

m <- 8

iobj <- 8

ncolh <- 7

a <- matrix(c(0.02, 0.02, 0.03, 1, 0.7, 0.02, 0.15, 
    -200, 0.06, 0.75, 0.03, 0.04, 0.05, 0.04, 1, -2000, 0.02, 
    1, 0.01, 0.08, 0.08, 0.8, -2000, 1, 0.12, 0.02, 0.02, 0.75, 
    0.04, -2000, 0.01, 0.8, 0.02, 1, 0.02, 0.06, 0.02, -2000, 
    1, 0.01, 0.01, 0.97, 0.01, 400, 0.97, 0.03, 1, 400), nrow = 48, 
    ncol = 1, byrow = TRUE)



ha <- matrix(c(7, 5, 3, 1, 6, 4, 2, 8, 7, 6, 5, 4, 
    3, 2, 1, 8, 2, 1, 4, 3, 7, 6, 8, 1, 7, 3, 4, 6, 2, 8, 5, 
    6, 7, 1, 2, 3, 4, 8, 1, 2, 3, 6, 7, 8, 7, 2, 1, 8), nrow = 48, 
    ncol = 1, byrow = TRUE)



ka <- matrix(c(1, 9, 17, 24, 31, 39, 45, 49), nrow = 8, 
    ncol = 1, byrow = TRUE)



bl <- matrix(c(0, 0, 400, 100, 0, 0, 0, 2000, -1e+25, 
    -1e+25, -1e+25, -1e+25, 1500, 250, -1e+25), nrow = 15, ncol = 1, 
    byrow = TRUE)



bu <- matrix(c(200, 2500, 800, 700, 1500, 1e+25, 1e+25, 
    2000, 60, 100, 40, 30, 1e+25, 300, 1e+25), nrow = 15, ncol = 1, 
    byrow = TRUE)



start <- "C"

names <- matrix(c("        ", "        ", "        ", 
    "        ", "        "), nrow = 5, byrow = TRUE)



crname <- matrix(c("...X1...", "...X2...", "...X3...", 
    "...X4...", "...X5...", "...X6...", "...X7...", "..ROW1..", 
    "..ROW2..", "..ROW3..", "..ROW4..", "..ROW5..", "..ROW6..", 
    "..ROW7..", "..COST.."), nrow = 15, byrow = TRUE)



ns <- -1232765364

xs <- matrix(c(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0), nrow = 15, ncol = 1, byrow = TRUE)



istate <- as.matrix(mat.or.vec(15, 1))

leniz <- 10000

lenz <- 10000

ans <- e04nk(n, m, iobj, ncolh, qphx, a, ha, ka, bl, 
    bu, start, names, crname, ns, xs, istate, leniz, lenz, optlist) 
ans

[Package NAGFWrappers version 24.0 Index]