NAG Library Function Document

nag_opt_lp (e04mfc)

1  Purpose

2  Specification

3  Description

4  References

5  Arguments

1:    $\mathbf{n}$ – IntegerInput

On entry: $n$, the number of variables.

Constraint: $\mathbf{n}>0$.

2:    $\mathbf{nclin}$ – IntegerInput

On entry: $m_{\mathit{lin}}$, the number of general linear constraints.

Constraint: $\mathbf{nclin}\ge 0$.

3:    $\mathbf{a}\left[\mathbf{nclin}\times \mathbf{tda}\right]$ – const doubleInput

Note: the $\left(i,j\right)$th element of the matrix $A$ is stored in $\mathbf{a}\left[\left(i-1\right)\times \mathbf{tda}+j-1\right]$.

On entry: the $\mathit{i}$th row of a must contain the coefficients of the $\mathit{i}$th general linear constraint (the $\mathit{i}$th row of $A$), for $\mathit{i}=1,2,\dots ,m_{\mathit{lin}}$.

If $\mathbf{nclin}=0$ then the array a is not referenced.

4:    $\mathbf{tda}$ – IntegerInput

On entry: the stride separating matrix column elements in the array a.

Constraint: if $\mathbf{nclin}>0$, $\mathbf{tda}\ge \mathbf{n}$

5:    $\mathbf{bl}\left[\mathbf{n}+\mathbf{nclin}\right]$ – const doubleInput

6:    $\mathbf{bu}\left[\mathbf{n}+\mathbf{nclin}\right]$ – const doubleInput

On entry: bl must contain the lower bounds and bu the upper bounds, for all the constraints in the following order. The first $n$ elements of each array must contain the bounds on the variables, and the next $m_{\mathit{lin}}$ elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $\mathbf{bl}\left[j-1\right]\le -\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$, and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $\mathbf{bu}\left[j-1\right]\ge \mathbf{options}\mathbf{.}\mathbf{inf\_bound}$; here $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$ is the value of the optional argument $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$, whose default value is ${10}^{20}$ (see Section 12.2). To specify the $j$th constraint as an equality, set $\mathbf{bl}\left[j-1\right]=\mathbf{bu}\left[j-1\right]=\beta$, say, where $\left|\beta \right|<\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$.

Constraint: $\mathbf{bl}\left[\mathit{j}-1\right]\le \mathbf{bu}\left[\mathit{j}-1\right]$, for $\mathit{j}=1,2,\dots ,\mathbf{n}+\mathbf{nclin}-1$.

7:    $\mathbf{cvec}\left[\mathbf{n}\right]$ – const doubleInput

On entry: the coefficients of the objective function when the problem is of type $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_LP}$. The problem type is specified by the optional argument $\mathbf{options}\mathbf{.}\mathbf{prob}$ (see Section 12.2) and the values $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_LP}$ or $\mathrm{Nag\_FP}$ represent linear programming problem and feasible point problem respectively. $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_LP}$ is the default problem type for nag_opt_lp (e04mfc).

If the problem type $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_FP}$ is specified then cvec is not referenced and a NULL pointer may be given.

8:    $\mathbf{x}\left[\mathbf{n}\right]$ – doubleInput/Output

On entry: an initial estimate of the solution.

On exit: the point at which nag_opt_lp (e04mfc) terminated. If $\mathbf{fail}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}$, NW_SOLN_NOT_UNIQUE or NW_NOT_FEASIBLE, x contains an estimate of the solution.

9:    $\mathbf{objf}$ – double *Output

On exit: the value of the objective function at $x$ if $x$ is feasible, or the sum of infeasibilities at $x$ otherwise. If the problem is of type $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_FP}$ and $x$ is feasible, objf is set to zero.

10:  $\mathbf{options}$ – Nag_E04_Opt *Input/Output

On entry/exit: a pointer to a structure of type Nag_E04_Opt whose members are optional arguments for nag_opt_lp (e04mfc). These structure members offer the means of adjusting some of the argument values of the algorithm and on output will supply further details of the results. A description of the members of options is given below in Section 12.2. Some of the results returned in options can be used by nag_opt_lp (e04mfc) to perform a ‘warm start’ if it is re-entered (see the member $\mathbf{options}\mathbf{.}\mathbf{start}$ in Section 12.2).

If any of these optional arguments are required, then the structure options should be declared and initialized by a call to nag_opt_init (e04xxc) immediately before being supplied as an argument to nag_opt_lp (e04mfc).

11:  $\mathbf{comm}$ – Nag_Comm *Input/Output

Note: comm is a NAG defined type (see Section 3.2.1.1 in the Essential Introduction).

On entry/exit: structure containing pointers for user communication with an optional user-defined printing function. See Section 12.3.1 for details. If you do not need to make use of this communication feature then the null pointer NAGCOMM_NULL may be used in the call to nag_opt_lp (e04mfc).

12:  $\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

5.1  Description of Printed Output

6  Error Indicators and Warnings

If one of NE_INT_ARG_LT, NE_2_INT_ARG_LT, NE_OPT_NOT_INIT, NE_BAD_PARAM, NE_INVALID_INT_RANGE_1, NE_INVALID_INT_RANGE_2, NE_INVALID_REAL_RANGE_FF, NE_INVALID_REAL_RANGE_F, NE_CVEC_NULL, NE_WARM_START, NE_BOUND, NE_BOUND_LCON, NE_STATE_VAL and NE_ALLOC_FAIL occurs, no values will have been assigned to objf, or to $\mathbf{options}\mathbf{.}\mathbf{ax}$ and $\mathbf{options}\mathbf{.}\mathbf{lambda}$. x and $\mathbf{options}\mathbf{.}\mathbf{state}$ will be unchanged.

NE_2_INT_ARG_LT

On entry, $\mathbf{tda}=〈\mathit{\text{value}}〉$ while $\mathbf{n}=〈\mathit{\text{value}}〉$. These arguments must satisfy $\mathbf{tda}\ge \mathbf{n}$.

NE_ALLOC_FAIL

Dynamic memory allocation failed.

NE_BAD_PARAM

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{print\_level}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{prob}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{start}$ had an illegal value.

NE_BOUND

The lower bound for variable $〈\mathit{\text{value}}〉$ (array element $\mathbf{bl}\left[〈\mathit{\text{value}}〉\right]$) is greater than the upper bound.

NE_BOUND_LCON

The lower bound for linear constraint $〈\mathit{\text{value}}〉$ (array element $\mathbf{bl}\left[〈\mathit{\text{value}}〉\right]$) is greater than the upper bound.

NE_BOUND_NLCON

The lower bound for nonlinear constraint $〈\mathit{\text{value}}〉$ (array element $\mathbf{bl}\left[〈\mathit{\text{value}}〉\right]$) is greater than the upper bound.

NE_CVEC_NULL

$\mathbf{options}\mathbf{.}\mathbf{prob}=〈\mathit{\text{value}}〉$ but argument $\mathbf{cvec}=$ NULL.

NE_INT_ARG_LT

On entry, $\mathbf{n}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{n}\ge 1$.

On entry, $\mathbf{nclin}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{nclin}\ge 0$.

NE_INVALID_INT_RANGE_1

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{fcheck}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{fcheck}\ge 1$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{max\_iter}\ge 0$.

NE_INVALID_INT_RANGE_2

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{reset\_ftol}$ not valid. Correct range is $0<\mathbf{options}\mathbf{.}\mathbf{reset\_ftol}<10000000$.

NE_INVALID_REAL_RANGE_F

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{ftol}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{ftol}>0.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}>0.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{inf\_step}$ not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{inf\_step}>0.0$.

NE_INVALID_REAL_RANGE_FF

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{crash\_tol}$ not valid. Correct range is $0.0\le \mathbf{options}\mathbf{.}\mathbf{crash\_tol}\le 1.0$.

NE_NOT_APPEND_FILE

Cannot open file $〈\mathit{string}〉$ for appending.

NE_NOT_CLOSE_FILE

Cannot close file $〈\mathit{string}〉$.

NE_OPT_NOT_INIT

options structure not initialized.

NE_STATE_VAL

$\mathbf{options}\mathbf{.}\mathbf{state}\left[〈\mathit{\text{value}}〉\right]$ is out of range. $\mathbf{options}\mathbf{.}\mathbf{state}\left[〈\mathit{\text{value}}〉\right]=〈\mathit{\text{value}}〉$.

NE_UNBOUNDED

Solution appears to be unbounded.
This value of $\mathbf{fail}\mathbf{.}\mathbf{code}$ implies that a step as large as $\mathbf{options}\mathbf{.}\mathbf{inf\_step}$ would have to be taken in order to continue the algorithm. This situation can occur only when the problem is of type $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_LP}$ and at least one variable has no upper or lower bound.

NE_WARM_START

$\mathbf{options}\mathbf{.}\mathbf{start}=\mathrm{Nag\_Warm}$ but pointer $\mathbf{options}\mathbf{.}\mathbf{state}=$ NULL.

NE_WRITE_ERROR

Error occurred when writing to file $〈\mathit{string}〉$.

NW_NOT_FEASIBLE

No feasible point was found for the linear constraints.
It was not possible to satisfy all the constraints to within the feasibility tolerance. In this case, the constraint violations at the final $x$ will reveal a value of the tolerance for which a feasible point will exist – for example, if the feasibility tolerance for each violated constraint exceeds its Residual at the final point. You should check that there are no constraint redundancies. If the data for the constraints are accurate only to the absolute precision $\sigma$, you should ensure that the value of the optional argument $\mathbf{options}\mathbf{.}\mathbf{ftol}$ is greater than $\sigma$. For example, if all elements of $A$ are of order unity and are accurate only to three decimal places, the optional argument $\mathbf{options}\mathbf{.}\mathbf{ftol}$ should be at least ${10}^{-3}$.

NW_OVERFLOW_WARN

Serious ill-conditioning in the working set after adding constraint $〈\mathit{\text{value}}〉$. Overflow may occur in subsequent iterations.
If overflow occurs preceded by this warning then serious ill-conditioning has probably occurred in the working set when adding a constraint. It may be possible to avoid the difficulty by increasing the magnitude of the optional argument $\mathbf{options}\mathbf{.}\mathbf{ftol}$ and re-running the program. If the message recurs even after this change, the offending linearly dependent constraint $j$ must be removed from the problem.

NW_SOLN_NOT_UNIQUE

Optimal solution is not unique.
$x$ is a weak local minimum (the projected gradient is negligible, the Lagrange multipliers are optimal but there is a small multiplier). This means that the solution $x$ is not unique.

NW_TOO_MANY_ITER

The maximum number of iterations, $〈\mathit{\text{value}}〉$, have been performed.
The value of the optional argument $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$ may be too small. If the method appears to be making progress (e.g., the objective function is being satisfactorily reduced), increase the value of $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$ and rerun nag_opt_lp (e04mfc) (possibly using the $\mathbf{options}\mathbf{.}\mathbf{start}=\mathrm{Nag\_Warm}$ facility to specify the initial working set).

7  Accuracy

8  Parallelism and Performance

9  Further Comments

10  Example

10.1  Program Text

Program Text (e04mfce.c)

10.2  Program Data

Program Options (e04mfce.opt)

10.3  Program Results

Program Results (e04mfce.r)

11  Further Description

11.1  Overview

11.2  Definition of the Search Direction

11.3  The Main Iteration

11.4  Choosing the Initial Working Set

12  Optional Arguments

12.1  Optional Argument Checklist and Default Values

12.2  Description of the Optional Arguments

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

12.3  Description of Printed Output

12.3.1  Output of results via a user-defined printing function

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

first – Nag_Boolean

Nag_TRUE on the first call to $\mathbf{options}\mathbf{.}\mathbf{print\_fun}$.

iter – Integer

The number of iterations performed.

n – Integer

The number of variables.

nclin – Integer

The number of linear constraints.

jdel – Integer

Index of constraint deleted.

jadd – Integer

Index of constraint added.

step – double

The step taken along the current search direction.

ninf – Integer

The number of infeasibilities.

f – double

The value of the current objective function.

bnd – Integer

Number of bound constraints in the working set.

lin – Integer

Number of general linear constraints in the working set.

nart – Integer

Number of artificial constraints in the working set.

nrz – Integer

Number of columns of $Z_r$.

norm_gz – double

Euclidean norm of the reduced gradient, $‖Z_r^{\mathrm{T}}{g}_{fr}‖$.

nopt – Integer

Number of non-optimal Lagrange multipliers.

min_lm – double

Value of the Lagrange multiplier associated with the deleted constraint.

condt – double

A lower bound on the condition number of the working set.

x – double *

x points to the n memory locations holding the current point $x$.

ax – double *

$\mathbf{options}\mathbf{.}\mathbf{ax}$ points to the nclin memory locations holding the current values $Ax$.

state – Integer *

$\mathbf{options}\mathbf{.}\mathbf{state}$ points to the $\mathbf{n}+\mathbf{nclin}$ memory locations holding the status of the variables and general linear constraints. See Section 12.2 for a description of the possible status values.

t – double *

The upper triangular matrix $T$ with $\mathbf{st}\mathbf{\to }\mathbf{lin}$ columns. Matrix element $i,j$ is held in $\mathbf{st}\mathbf{\to }\mathbf{t}\left[\left(i-1\right)*\mathbf{st}\mathbf{\to }\mathbf{tdt}+j-1\right]$.

tdt – Integer

The trailing dimension for $\mathbf{st}\mathbf{\to }\mathbf{t}$.

kx – Integer *

Indices of the bound constraints with associated multipliers. Value of $\mathbf{st}\mathbf{\to }\mathbf{kx}\left[\mathit{i}-1\right]$ is the index of the constraint with multiplier $\mathbf{st}\mathbf{\to }\mathbf{lambda}\left[\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{bnd}$.

kactive – Integer *

Indices of the linear constraints with associated multipliers. Value of $\mathbf{st}\mathbf{\to }\mathbf{kactive}\left[\mathit{i}-1\right]$ is the index of the constraint with multiplier $\mathbf{st}\mathbf{\to }\mathbf{lambda}\left[\mathbf{st}\mathbf{\to }\mathbf{bnd}+\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{lin}$.

lambda – double *

The multipliers for the constraints in the working set. $\mathbf{options}\mathbf{.}\mathbf{lambda}\left[\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{bnd}$ hold the multipliers for the bound constraints while the multipliers for the linear constraints are held at indices $i-1=\mathbf{st}\mathbf{\to }\mathbf{bnd}$,$\dots$,$\mathbf{st}\mathbf{\to }\mathbf{bnd}+\mathbf{st}\mathbf{\to }\mathbf{lin}$.

gq – double *

$\mathbf{st}\mathbf{\to }\mathbf{gq}\left[\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{nart}$ hold the multipliers for the artificial constraints.

refactor – Nag_Boolean

Nag_TRUE if iterative refinement performed. See Section 11.3 and optional argument $\mathbf{options}\mathbf{.}\mathbf{reset\_ftol}$.

jmax – Integer

If $\mathbf{st}\mathbf{\to }\mathbf{refactor}=\mathrm{Nag\_TRUE}$ then $\mathbf{st}\mathbf{\to }\mathbf{jmax}$ holds the index of the constraint with the maximum violation.

errmax – double

If $\mathbf{st}\mathbf{\to }\mathbf{refactor}=\mathrm{Nag\_TRUE}$ then $\mathbf{st}\mathbf{\to }\mathbf{errmax}$ holds the value of the maximum violation.

moved – Nag_Boolean

Nag_TRUE if some variables moved to their bounds. See the optional argument $\mathbf{options}\mathbf{.}\mathbf{reset\_ftol}$.

nmoved – Integer

If $\mathbf{st}\mathbf{\to }\mathbf{moved}=\mathrm{Nag\_TRUE}$ then $\mathbf{st}\mathbf{\to }\mathbf{nmoved}$ holds the number of variables which were moved to their bounds.

rowerr – Nag_Boolean

Nag_TRUE if some constraints are not satisfied to within $\mathbf{options}\mathbf{.}\mathbf{ftol}$.

feasible – Nag_Boolean

Nag_TRUE when a feasible point has been found.

iter – Integer

The number of iterations performed.

n – Integer

The number of variables.

nclin – Integer

The number of linear constraints.

x – double *

x points to the n memory locations holding the final point $x$.

f – double *

The final objective function value or, if $x$ is not feasible, the sum of infeasibilities. If the problem is of type $\mathbf{options}\mathbf{.}\mathbf{prob}=\mathrm{Nag\_FP}$ and $x$ is feasible then $\mathbf{st}\mathbf{\to }\mathbf{f}$ is set to zero.

ax – double *

$\mathbf{options}\mathbf{.}\mathbf{ax}$ points to the nclin memory locations holding the final values $Ax$.

state – Integer *

$\mathbf{st}\mathbf{\to }\mathbf{state}$ points to the $\mathbf{n}+\mathbf{nclin}$ memory locations holding the final status of the variables and general linear constraints. See Section 12.2 for a description of the possible status values.

lambda – double *

$\mathbf{st}\mathbf{\to }\mathbf{lambda}$ points to the $\mathbf{n}+\mathbf{nclin}$ final values of the Lagrange multipliers.

bl – double *

bl points to the $\mathbf{n}+\mathbf{nclin}$ lower bound values.

bu – double *

bu points to the $\mathbf{n}+\mathbf{nclin}$ upper bound values.

endstate – Nag_EndState

The state of termination of nag_opt_lp (e04mfc). Possible values of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$ and their correspondence to the exit value of $\mathbf{fail}\mathbf{.}\mathbf{code}$ are:

Value of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$	Value of $\mathbf{fail}\mathbf{.}\mathbf{code}$
$\mathrm{Nag\_Feasible}$ and $\mathrm{Nag\_Optimal}$	NE_NOERROR
$\mathrm{Nag\_Weakmin}$	NW_SOLN_NOT_UNIQUE
$\mathrm{Nag\_Unbounded}$	NE_UNBOUNDED
$\mathrm{Nag\_Infeasible}$	NW_NOT_FEASIBLE
$\mathrm{Nag\_Too\_Many\_Iter}$	NW_TOO_MANY_ITER

it_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the result of the current iteration.

sol_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the final result.

new_lm – Nag_Boolean

Will be Nag_TRUE when the Lagrange multipliers have been updated.

user – double

iuser – Integer

p – Pointer 

Pointers for communication of user information. If used they must be allocated memory either before entry to nag_opt_lp (e04mfc) or during a call to $\mathbf{options}\mathbf{.}\mathbf{print\_fun}$. The type Pointer will be void * with a C compiler that defines void *.