GALAHAD BLLS package#

purpose#

The blls package uses a preconditioned project-gradient method to solve a given bound-constrained linear least-squares problem. The aim is to minimize the (regularized) least-squares objective function

\[q(x) = \frac{1}{2} \| A_o x - b\|_W^2 + \frac{1}{2}\sigma \|x\|^2\]

subject to the simple bounds

\[x_l \leq x \leq x_u,\]

where the norms $\|r\|_W = \sqrt{\sum_{i=1}^o w_i r_i^2}$ and $\|x\| = \sqrt{\sum_{i=1}^n x_i^2}$, $A_o$ is a given $o$ by $n$ matrix, $b$, and $w$ are vectors, $\sigma \geq 0$ is a scalar, and any of the components of the vectors $x_l$ or $x_u$ may be infinite. The method offers the choice of direct and iterative solution of the key regularization subproblems, and is most suitable for problems involving a large number of unknowns $x$.

See Section 4 of $GALAHAD/doc/blls.pdf for additional details.

terminology#

Any required solution $x$ necessarily satisfies the primal optimality conditions

\[x_l \leq x \leq x_u,\]

the dual optimality conditions

\[A_o^T W( A_o x - b) + \sigma x = z, \;\; z = z_l + z_u, z_l \geq 0 \;\;\mbox{and}\;\; z_u \leq 0,\]

and the complementary slackness conditions

\[(x -x_l )^{T} z_l = 0 \;\;\mbox{and}\;\;(x -x_u )^{T} z_u = 0,\]

where the vector $z$ is known as the dual variables for the bounds, and where the vector inequalities hold component-wise.

method#

Projected-gradient methods iterate towards a point that satisfies these optimality conditions by ultimately aiming to satisfy $A_o^T W ( A_o x - b) + \sigma x = z$, while ensuring that the remaining conditions are satisfied at each stage. Appropriate norms of the amounts by which the optimality conditions fail to be satisfied are known as the primal and dual infeasibility, and the violation of complementary slackness, respectively.

The method is iterative. Each iteration proceeds in two stages. Firstly, a search direction $s$ from the current estimate of the solution $x$ is computed. This may be in a scaled steepest-descent direction, or, if the working set of variables on bounds has not changed dramatically, in a direction that provides an approximate minimizer of the objective over a subspace comprising the currently free-variables. The latter is computed either using an appropriate sparse factorization by the package SBLS, or by the conjugate-gradient least-squares (CGLS) method; tt may be necessary to regularize the subproblem very slightly to avoid a ill-posedness. Thereafter, a piecewise linesearch (arc search) is carried out along the arc $x(\alpha) = P( x + \alpha s)$ for $\alpha > 0$, where the projection operator is defined component-wise at any feasible point $v$ to be

\[P_j(v) = \min( \max( x_j, x_j^{l}), x_j^{u});\]

thus this arc bends the search direction into the feasible region. The arc search is performed either exactly, by passing through a set of increasing breakpoints at which it changes direction, or inexactly, by evaluating a sequence of different $\alpha$ on the arc. All computation is designed to exploit sparsity in $A_o$.

reference#

Full details are provided in

N. I. M. Gould (2022). ``A projection method for bound-constrained linear least-squares’’. STFC-Rutherford Appleton Laboratory Computational Mathematics Group Internal Report 2023-1 (2023).

matrix storage#

The unsymmetric $o$ by $n$ matrix $A_o$ may be presented and stored in a variety of convenient input formats.

Dense storage format: The matrix $A_o$ is stored as a compact dense matrix by rows, that is, the values of the entries of each row in turn are stored in order within an appropriate real one-dimensional array. In this case, component $n \ast i + j$ of the storage array Ao_val will hold the value $A_{ij}$ for $1 \leq i \leq o$, $1 \leq j \leq n$. The string Ao_type = ‘dense’ should be specified.

Dense by columns storage format: The matrix $A_o$ is stored as a compact dense matrix by columns, that is, the values of the entries of each column in turn are stored in order within an appropriate real one-dimensional array. In this case, component $o \ast j + i$ of the storage array Ao_val will hold the value $A_{ij}$ for $1 \leq i \leq o$, $1 \leq j \leq n$. The string Ao_type = ‘dense_by_columns’ should be specified.

Sparse co-ordinate storage format: Only the nonzero entries of the matrices are stored. For the $l$-th entry, $1 \leq l \leq ne$, of $A_o$, its row index i, column index j and value $A_{ij}$, $1 \leq i \leq o$, $1 \leq j \leq n$, are stored as the $l$-th components of the integer arrays Ao_row and Ao_col and real array Ao_val, respectively, while the number of nonzeros is recorded as Ao_ne = $ne$. The string Ao_type = ‘coordinate’should be specified.

Sparse row-wise storage format: Again only the nonzero entries are stored, but this time they are ordered so that those in row i appear directly before those in row i+1. For the i-th row of $A_o$ the i-th component of the integer array Ao_ptr holds the position of the first entry in this row, while Ao_ptr(o+1) holds the total number of entries plus one. The column indices j, $1 \leq j \leq n$, and values $A_{ij}$ of the nonzero entries in the i-th row are stored in components l = Ao_ptr(i), $\ldots$, Ao_ptr(i+1)-1, $1 \leq i \leq o$, of the integer array Ao_col, and real array Ao_val, respectively. For sparse matrices, this scheme almost always requires less storage than its predecessor. The string Ao_type = ‘sparse_by_rows’ should be specified.

Sparse column-wise storage format: Once again only the nonzero entries are stored, but this time they are ordered so that those in column j appear directly before those in column j+1. For the j-th column of $A_o$ the j-th component of the integer array Ao_ptr holds the position of the first entry in this column, while Ao_ptr(n+1) holds the total number of entries plus one. The row indices i, $1 \leq i \leq o$, and values $A_{ij}$ of the nonzero entries in the j-th columnsare stored in components l = Ao_ptr(j), $\ldots$, Ao_ptr(j+1)-1, $1 \leq j \leq n$, of the integer array Ao_row, and real array Ao_val, respectively. As before, for sparse matrices, this scheme almost always requires less storage than the co-ordinate format. The string Ao_type = ‘sparse_by_columns’ should be specified.

introduction to function calls#

To solve a given problem, functions from the blls package must be called in the following order:

blls_initialize - provide default control parameters and set up initial data structures
blls_read_specfile (optional) - override control values by reading replacement values from a file
set up problem data structures and fixed values by caling one of
- blls_import - in the case that $A_o$ is explicitly available
- blls_import_without_a - in the case that only the effect of applying $A_o$ and its transpose to a vector is possible
blls_reset_control (optional) - possibly change control parameters if a sequence of problems are being solved
solve the problem by calling one of
- blls_solve_given_a - solve the problem using values of $A_o$
- blls_solve_reverse_a_prod - solve the problem by returning to the caller for products of $A_o$ and its transpose with specified vectors
blls_information (optional) - recover information about the solution and solution process
blls_terminate - deallocate data structures

See the examples section for illustrations of use.

parametric real type T#

Below, the symbol T refers to a parametric real type that may be Float32 (single precision) or Float64 (double precision).

callable functions#

    function blls_initialize(T, data, control, status)

Set default control values and initialize private data

Parameters:

data

holds private internal data

control

is a structure containing control information (see blls_control_type)

status

is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):

0
The import was successful.

    function blls_read_specfile(T, control, specfile)

Read the content of a specification file, and assign values associated with given keywords to the corresponding control parameters. An in-depth discussion of specification files is available, and a detailed list of keywords with associated default values is provided in $GALAHAD/src/blls/BLLS.template. See also Table 2.1 in the Fortran documentation provided in $GALAHAD/doc/blls.pdf for a list of how these keywords relate to the components of the control structure.

Parameters:

control	is a structure containing control information (see blls_control_type)
specfile	is a one-dimensional array of type Vararg{Cchar} that must give the name of the specification file

    function blls_import(T, control, data, status, n, o,
                         Ao_type, Ao_ne, Ao_row, Ao_col, Ao_ptr_ne, Ao_ptr)

Import problem data into internal storage prior to solution.

Parameters:

control	is a structure whose members provide control parameters for the remaining procedures (see blls_control_type)
data	holds private internal data
status	is a scalar variable of type Int32 that gives the exit status from the package. Possible values are: 1 The import was successful, and the package is ready for the solve phase -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -3 The restrictions n > 0, o > 0 or requirement that type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’, or ‘dense_by_columns’; has been violated.
n	is a scalar variable of type Int32 that holds the number of variables.
o	is a scalar variable of type Int32 that holds the number of residuals.
Ao_type	is a one-dimensional array of type Vararg{Cchar} that specifies the unsymmetric storage scheme used for the Jacobian $A_o$. It should be one of ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’, or ‘dense_by_columns’; lower or upper case variants are allowed.
Ao_ne	is a scalar variable of type Int32 that holds the number of entries in $A_o$ in the sparse co-ordinate storage scheme. It need not be set for any of the other schemes.
Ao_row	is a one-dimensional array of size A_ne and type Int32 that holds the row indices of $A_o$ in the sparse co-ordinate or sparse column-wise storage scheme. It need not be set for any of the other schemes, and in this case can be C_NULL.
Ao_col	is a one-dimensional array of size A_ne and type Int32 that holds the column indices of $A_o$ in either the sparse co-ordinate, or the sparse row-wise storage scheme. It need not be set for any of the other schemes, and in this case can be C_NULL.
Ao_ptr_ne	is a scalar variable of type Int32, that holds the length of the pointer array if sparse row or column storage scheme is used for $A_o$. For the sparse row scheme, Ao_ptr_ne should be at least o+1, while for the sparse column scheme, it should be at least n+1, It need not be set when the other schemes are used.
Ao_ptr	is a one-dimensional array of size Ao_ptr_ne and type Int32, that holds the starting position of each row of $A_o$, as well as the total number of entries, in the sparse row-wise storage scheme. By contrast, it holds the starting position of each column of $A_o$, as well as the total number of entries, in the sparse column-wise storage scheme. It need not be set when the other schemes are used, and in this case can be C_NULL.

    function blls_import_without_a(T, control, data, status, n, o)

Import problem data into internal storage prior to solution when $A_o$ is not explicitly available.

Parameters:

control	is a structure whose members provide control parameters for the remaining procedures (see blls_control_type)
data	holds private internal data
status	is a scalar variable of type Int32 that gives the exit status from the package. Possible values are: 1 The import was successful, and the package is ready for the solve phase -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -3 The restriction n > 0 or m > 0 has been violated.
n	is a scalar variable of type Int32 that holds the number of variables.
o	is a scalar variable of type Int32 that holds the number of residuals.

    function blls_reset_control(T, control, data, status)

Reset control parameters after import if required.

Parameters:

control

is a structure whose members provide control parameters for the remaining procedures (see blls_control_type)

data

holds private internal data

status

is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:

1
The import was successful, and the package is ready for the solve phase

    function blls_solve_given_a(T, data, userdata, status, n, o,
                                Ao_ne, Ao_val, b, x_l, x_u, x, z, r, g,
                                x_stat, w, eval_prec)

Solve the bound-constrained linear least-squares problem when the Jacobian $A$ is available.

Parameters:

data	holds private internal data
userdata	is a structure that allows data to be passed into the function and derivative evaluation programs.
status	is a scalar variable of type Int32 that gives the entry and exit status from the package. On initial entry, status must be set to 1. Possible exit values are: 0 The run was successful. -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -3 The restrictions n > 0, o > 0 or requirement that a type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’ or ‘dense_by_columns’ has been violated. -4 The simple-bound constraints are inconsistent. -9 The analysis phase of the factorization failed; the return status from the factorization package is given in the component inform.factor_status -10 The factorization failed; the return status from the factorization package is given in the component inform.factor_status. -18 Too many iterations have been performed. This may happen if control.maxit is too small, but may also be symptomatic of a badly scaled problem. -19 The CPU time limit has been reached. This may happen if control.cpu_time_limit is too small, but may also be symptomatic of a badly scaled problem.
n	is a scalar variable of type Int32 that holds the number of variables
o	is a scalar variable of type Int32 that holds the number of residuals.
Ao_ne	is a scalar variable of type Int32 that holds the number of entries in the design matrix $A_o$.
Ao_val	is a one-dimensional array of size Ao_ne and type T that holds the values of the entries in the design matrix $A_o$ in any of the available storage schemes.
b	is a one-dimensional array of size m and type T that holds the constant term $b$ in the residuals. The i-th component of `b`, i = 1, … , o, contains $b_i$.
x_l	is a one-dimensional array of size n and type T that holds the lower bounds $x^l$ on the variables $x$. The j-th component of `x_l`, j = 1, … , n, contains $x^l_j$.
x_u	is a one-dimensional array of size n and type T that holds the upper bounds $x^l$ on the variables $x$. The j-th component of `x_u`, j = 1, … , n, contains $x^l_j$.
x	is a one-dimensional array of size n and type T that holds the values $x$ of the optimization variables. The j-th component of `x`, j = 1, … , n, contains $x_j$.
z	is a one-dimensional array of size n and type T that holds the values $z$ of the dual variables. The j-th component of `z`, j = 1, … , n, contains $z_j$.
r	is a one-dimensional array of size om and type T that holds the values of the residuals $r = A_o x - b$. The i-th component of `r`, i = 1, … , o, contains $r_i$.
g	is a one-dimensional array of size n and type T that holds the values of the gradient $g = A_o^T W r$. The j-th component of `g`, j = 1, … , n, contains $g_j$.
x_stat	is a one-dimensional array of size n and type Int32 that gives the optimal status of the problem variables. If x_stat(j) is negative, the variable $x_j$ most likely lies on its lower bound, if it is positive, it lies on its upper bound, and if it is zero, it lies between its bounds.
w	is an optional one-dimensional array of size m and type T that holds the values $w$ of the weights on the residuals in the least-squares objective function. It need not be set if the weights are all ones, and in this case can be C_NULL.
eval_prec	is an optional user-supplied function that may be C_NULL. If non-NULL, it must have the following signature: eval_prec(n, v, p, userdata) The product $p = P^{-1} v$ involving the user’s preconditioner $P$ with the vector v=$v$, the result $p$ must be retured in p, and the function return value set to 0. If the evaluation is impossible, return should be set to a nonzero value. Data may be passed into `eval_prec` via the structure `userdata`.

    function blls_solve_reverse_a_prod(T, data, status, eval_status, n, o, b,
                                       x_l, x_u, x, z, r, g, x_stat, v, p,
                                       nz_v, nz_v_start, nz_v_end, nz_p,
                                       nz_p_end, w)

Solve the bound-constrained linear least-squares problem when the products of the Jacobian $A$ and its transpose with specified vectors may be computed by the calling program.

Parameters:

data	holds private internal data
status	is a scalar variable of type Int32 that gives the entry and exit status from the package. Possible exit values are: 0 The run was successful. -1 An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -2 A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively. -3 The restriction n > 0 or requirement that a type contains its relevant string ‘coordinate’, ‘sparse_by_rows’, ‘sparse_by_columns’, ‘dense_by_rows’ or ‘dense_by_columns’ has been violated. -4 The simple-bound constraints are inconsistent. -9 The analysis phase of the factorization failed; the return status from the factorization package is given in the component inform.factor_status -10 The factorization failed; the return status from the factorization package is given in the component inform.factor_status. -11 The solution of a set of linear equations using factors from the factorization package failed; the return status from the factorization package is given in the component inform.factor_status. -18 Too many iterations have been performed. This may happen if control.maxit is too small, but may also be symptomatic of a badly scaled problem. -19 The CPU time limit has been reached. This may happen if control.cpu_time_limit is too small, but may also be symptomatic of a badly scaled problem. 2 The product $A_ov$ of the design matrix $A_o$ with a given output vector $v$ is required from the user. The vector $v$ will be stored in v and the product $A_ov$ must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. 3 The product $A_o^Tv$ of the transpose of the residual Jacobian $A_o$ with a given output vector $v$ is required from the user. The vector $v$ will be stored in v and the product $A_o^Tv$ must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. 4 The product $A_ov$ of the design matrix $A_o$ with a given sparse output vector $v$ is required from the user. The nonzero components of the vector $v$ will be stored as entries nz_in[nz_in_start-1:nz_in_end-1] of v and the product $A_ov$ must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged; The remaining components of v should be ignored. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. 5 The nonzero components of the product $A_ov$ of the design matrix $A_o$ with a given sparse output vector $v$ is required from the user. The nonzero components of the vector $v$ will be stored as entries nz_in[nz_in_start-1:nz_in_end-1] of v; the remaining components of v should be ignored. The resulting nonzeros in the product $A_ov$ must be placed in their appropriate comnponents of p, while a list of indices of the nonzeros placed in nz_out[0 : nz_out_end-1] and the number of nonzeros recorded in nz_out_end. Additionally, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v, nz_out_end and nz_out need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. 6 A subset of the product $A_o^Tv$ of the transpose of the design matrix $A_o$ with a given output vector $v$ is required from the user. The vector $v$ will be stored in v and components nz_in[nz_in_start-1:nz_in_end-1] of the product $A_o^Tv$ must be returned in the relevant components of p (the remaining components should not be set), status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. 7 The product $P^{-1}v$ of the inverse of the preconditioner $P$ with a given output vector $v$ is required from the user. The vector $v$ will be stored in v and the product $P^{-1} v$ must be returned in p, status_eval should be set to 0, and blls_solve_reverse_a_prod re-entered with all other arguments unchanged. If the product cannot be formed, v need not be set, but blls_solve_reverse_a_prod should be re-entered with eval_status set to a nonzero value. This value of status can only occur if the user has set control.preconditioner = 2.
eval_status	is a scalar variable of type Int32 that is used to indicate if the matrix products can be provided (see `status` above)
n	is a scalar variable of type Int32 that holds the number of variables
o	is a scalar variable of type Int32 that holds the number of residuals.
b	is a one-dimensional array of size m and type T that holds the constant term $b$ in the residuals. The i-th component of `b`, i = 1, … , o, contains $b_i$.
x_l	is a one-dimensional array of size n and type T that holds the lower bounds $x^l$ on the variables $x$. The j-th component of `x_l`, j = 1, … , n, contains $x^l_j$.
x_u	is a one-dimensional array of size n and type T that holds the upper bounds $x^l$ on the variables $x$. The j-th component of `x_u`, j = 1, … , n, contains $x^l_j$.
x	is a one-dimensional array of size n and type T that holds the values $x$ of the optimization variables. The j-th component of `x`, j = 1, … , n, contains $x_j$.
r	is a one-dimensional array of size o and type T that holds the values of the residuals $r = A_o x - b$. The i-th component of `r`, i = 1, … , o, contains $r_i$.
g	is a one-dimensional array of size n and type T that holds the values of the gradient $g = A_o^T W r$. The j-th component of `g`, j = 1, … , n, contains $g_j$.
z	is a one-dimensional array of size n and type T that holds the values $z$ of the dual variables. The j-th component of `z`, j = 1, … , n, contains $z_j$.
x_stat	is a one-dimensional array of size n and type Int32 that gives the optimal status of the problem variables. If x_stat(j) is negative, the variable $x_j$ most likely lies on its lower bound, if it is positive, it lies on its upper bound, and if it is zero, it lies between its bounds.
v	is a one-dimensional array of size n and type T that is used for reverse communication (see status=2-4 above for details).
p	is a one-dimensional array of size n and type T that is used for reverse communication (see status=2-4 above for details).
nz_v	is a one-dimensional array of size n and type Int32 that is used for reverse communication (see status=3-4 above for details).
nz_v_start	is a scalar of type Int32 that is used for reverse communication (see status=3-4 above for details).
nz_v_end	is a scalar of type Int32 that is used for reverse communication (see status=3-4 above for details).
nz_p	is a one-dimensional array of size n and type Int32 that is used for reverse communication (see status=4 above for details).
nz_p_end	is a scalar of type Int32 that is used for reverse communication (see status=4 above for details).
w	is an optional one-dimensional array of size o and type T that holds the values $w$ of the weights on the residuals in the least-squares objective function. It need not be set if the weights are all ones, and in this case can be C_NULL.

    function blls_information(T, data, inform, status)

Provides output information

Parameters:

data

holds private internal data

inform

is a structure containing output information (see blls_inform_type)

status

is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):

0
The values were recorded successfully

    function blls_terminate(T, data, control, inform)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a structure containing control information (see blls_control_type)
inform	is a structure containing output information (see blls_inform_type)

available structures#

blls_control_type structure#

    struct blls_control_type{T}
      f_indexing::Bool
      error::Int32
      out::Int32
      print_level::Int32
      start_print::Int32
      stop_print::Int32
      print_gap::Int32
      maxit::Int32
      cold_start::Int32
      preconditioner::Int32
      ratio_cg_vs_sd::Int32
      change_max::Int32
      cg_maxit::Int32
      arcsearch_max_steps::Int32
      sif_file_device::Int32
      weight::T
      infinity::T
      stop_d::T
      identical_bounds_tol::T
      stop_cg_relative::T
      stop_cg_absolute::T
      alpha_max::T
      alpha_initial::T
      alpha_reduction::T
      arcsearch_acceptance_tol::T
      stabilisation_weight::T
      cpu_time_limit::T
      direct_subproblem_solve::Bool
      exact_arc_search::Bool
      advance::Bool
      space_critical::Bool
      deallocate_error_fatal::Bool
      generate_sif_file::Bool
      sif_file_name::NTuple{31,Cchar}
      prefix::NTuple{31,Cchar}
      sbls_control::sbls_control_type{T}
      convert_control::convert_control_type

detailed documentation#

control derived type as a Julia structure

components#

Bool f_indexing

use C or Fortran sparse matrix indexing

Int32 error

unit number for error and warning diagnostics

Int32 out

general output unit number

Int32 print_level

the level of output required

Int32 start_print

on which iteration to start printing

Int32 stop_print

on which iteration to stop printing

Int32 print_gap

how many iterations between printing

Int32 maxit

how many iterations to perform (-ve reverts to HUGE(1)-1)

Int32 cold_start

cold_start should be set to 0 if a warm start is required (with variable assigned according to X_stat, see below), and to any other value if the values given in prob.X suffice

Int32 preconditioner

the preconditioner (scaling) used. Possible values are: /li 0. no preconditioner. /li 1. a diagonal preconditioner that normalizes the rows of $A$. /li anything else. a preconditioner supplied by the user either via a subroutine call of eval_prec} or via reverse communication.

Int32 ratio_cg_vs_sd

the ratio of how many iterations use CGLS rather than steepest descent

Int32 change_max

the maximum number of per-iteration changes in the working set permitted when allowing CGLS rather than steepest descent

Int32 cg_maxit

how many CG iterations to perform per BLLS iteration (-ve reverts to n+1)

Int32 arcsearch_max_steps

the maximum number of steps allowed in a piecewise arcsearch (-ve=infini

Int32 sif_file_device

the unit number to write generated SIF file describing the current probl

T weight

the value of the non-negative regularization weight sigma, i.e., the quadratic objective function q(x) will be regularized by adding 1/2 weight ||x||^2; any value smaller than zero will be regarded as zero.

T infinity

any bound larger than infinity in modulus will be regarded as infinite

T stop_d

the required accuracy for the dual infeasibility

T identical_bounds_tol

any pair of constraint bounds (x_l,x_u) that are closer than identical_bounds_tol will be reset to the average of their values

T stop_cg_relative

the CG iteration will be stopped as soon as the current norm of the preconditioned gradient is smaller than max( stop_cg_relative * initial preconditioned gradient, stop_cg_absolute)

T alpha_max

the largest permitted arc length during the piecewise line search

T alpha_initial

the initial arc length during the inexact piecewise line search

T alpha_reduction

the arc length reduction factor for the inexact piecewise line search

T arcsearch_acceptance_tol

the required relative reduction during the inexact piecewise line search

T stabilisation_weight

the stabilisation weight added to the search-direction subproblem

T cpu_time_limit

the maximum CPU time allowed (-ve = no limit)

Bool direct_subproblem_solve

direct_subproblem_solve is true if the least-squares subproblem is to be solved using a matrix factorization, and false if conjugate gradients are to be preferred

Bool exact_arc_search

exact_arc_search is true if an exact arc_search is required, and false if an approximation suffices

Bool advance

advance is true if an inexact exact arc_search can increase steps as well as decrease them

Bool space_critical

if space_critical is true, every effort will be made to use as little space as possible. This may result in longer computation times

Bool deallocate_error_fatal

if deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue

Bool generate_sif_file

if generate_sif_file is true, a SIF file describing the current problem will be generated

NTuple{31,Cchar} sif_file_name

name (max 30 characters) of generated SIF file containing input problem

NTuple{31,Cchar} prefix

all output lines will be prefixed by a string (max 30 characters) prefix(2:LEN(TRIM(.prefix))-1) where prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

struct sbls_control_type sbls_control

control parameters for SBLS

struct convert_control_type convert_control

control parameters for CONVERT

blls_time_type structure#

struct blls_time_type{T}
  total::T
  analyse::T
  factorize::T
  solve::T
  clock_total::T
  clock_analyse::T
  clock_factorize::T
  clock_solve::T

detailed documentation#

time derived type as a Julia structure

components#

T total

the total CPU time spent in the package

T analyse

the CPU time spent analysing the required matrices prior to factorization

T factorize

the CPU time spent factorizing the required matrices

T solve

the CPU time spent in the linear solution phase

T clock_total

the total clock time spent in the package

T clock_analyse

the clock time spent analysing the required matrices prior to factorization

T clock_factorize

the clock time spent factorizing the required matrices

T clock_solve

the clock time spent in the linear solution phase

blls_inform_type structure#

    struct blls_inform_type{T}
      status::Int32
      alloc_status::Int32
      factorization_status::Int32
      iter::Int32
      cg_iter::Int32
      obj::T
      norm_pg::T
      bad_alloc::NTuple{81,Cchar}
      time::blls_time_type{T}
      sbls_inform::sbls_inform_type{T}
      convert_inform::convert_inform_type{T}

detailed documentation#

inform derived type as a Julia structure

components#

Int32 status

reported return status.

Int32 alloc_status

Fortran STAT value after allocate failure.

Int32 factorization_status

status return from factorization

Int32 iter

number of iterations required

Int32 cg_iter

number of CG iterations required

T obj

current value of the objective function, r(x).

T norm_pg

current value of the Euclidean norm of projected gradient of r(x).

NTuple{81,Cchar} bad_alloc

name of array which provoked an allocate failure

struct blls_time_type time

times for various stages

struct sbls_inform_type sbls_inform

inform values from SBLS

struct convert_inform_type convert_inform

inform values for CONVERT

Index

example calls#

This is an example of how to use the package to solve a bound-constrained linear least-squares problem; the code is available in $GALAHAD/src/blls/Julia/test_blls.jl . A variety of supported Hessian and constraint matrix storage formats are shown.

# test_blls.jl
# Simple code to test the Julia interface to BLLS

using GALAHAD
using Test
using Printf
using Accessors

# Custom userdata struct
mutable struct userdata_blls{T}
  scale::T
end

function test_blls(::Type{T}) where T

  # Apply preconditioner
  function prec(n::Int, x::Vector{T}, p::Vector{T}, userdata::userdata_blls)
    scale = userdata.scale
    for i in 1:n
      p[i] = scale * x[i]
    end
    return 0
  end

  # Derived types
  data = Ref{Ptr{Cvoid}}()
  control = Ref{blls_control_type{T}}()
  inform = Ref{blls_inform_type{T}}()

  # Set user data
  userdata = userdata_blls(1.0)

  # Set problem data
  n = 10 # dimension
  o = n + 1 # number of residuals
  Ao_ne = 2 * n # sparse Jacobian elements
  Ao_dense_ne = o * n # dense Jacobian elements
  # row-wise storage
  Ao_row = zeros(Cint, Ao_ne) # row indices,
  Ao_col = zeros(Cint, Ao_ne) # column indices
  Ao_ptr_ne = o + 1 # number of row pointers
  Ao_ptr = zeros(Cint, Ao_ptr_ne)  # row pointers
  Ao_val = zeros(T, Ao_ne) # values
  Ao_dense = zeros(T, Ao_dense_ne) # dense values
  # column-wise storage
  Ao_by_col_row = zeros(Cint, Ao_ne) # row indices,
  Ao_by_col_ptr_ne = n + 1 # number of column pointers
  Ao_by_col_ptr = zeros(Cint, Ao_by_col_ptr_ne)  # column pointers
  Ao_by_col_val = zeros(T, Ao_ne) # values
  Ao_by_col_dense = zeros(T, Ao_dense_ne) # dense values
  b = zeros(T, o)  # linear term in the objective
  x_l = zeros(T, n) # variable lower bound
  x_u = zeros(T, n) # variable upper bound
  x = zeros(T, n) # variables
  z = zeros(T, n) # dual variables
  r = zeros(T, o) # residual
  g = zeros(T, n) # gradient
  w = zeros(T, o) # weights

  # Set output storage
  x_stat = zeros(Cint, n) # variable status
  st = ' '
  status = Ref{Cint}()

  x_l[1] = -1.0
  for i in 2:n
    x_l[i] = -Inf
  end
  x_u[1] = 1.0
  x_u[2] = Inf
  for i in 3:n
    x_u[i] = 2.0
  end

  #   A = ( I )  and b = (i * e)
  #       (e^T)          (n + 1)

  for i in 1:n
    b[i] = i
  end
  b[n + 1] = n + 1

  w[1] = 2.0
  w[2] = 1.0
  for i in 3:o
    w[i] = 1.0
  end

  # # A by rows
  for i in 1:n
    Ao_ptr[i] = i
    Ao_row[i] = i
    Ao_col[i] = i
    Ao_val[i] = 1.0
  end
  Ao_ptr[n + 1] = n + 1
  for i in 1:n
    Ao_row[n + i] = o
    Ao_col[n + i] = i
    Ao_val[n + i] = 1.0
  end
  Ao_ptr[o + 1] = Ao_ne + 1
  l = 0
  for i in 1:n
    for j in 1:n
      l = l + 1
      if i == j
        Ao_dense[l] = 1.0
      else
        Ao_dense[l] = 0.0
      end
    end
  end
  for j in 1:n
    l = l + 1
    Ao_dense[l] = 1.0
  end

  # # A by columns
  l = 0
  for j in 1:n
    l = l + 1
    Ao_by_col_ptr[j] = l
    Ao_by_col_row[l] = j
    Ao_by_col_val[l] = 1.0
    l = l + 1
    Ao_by_col_row[l] = o
    Ao_by_col_val[l] = 1.0
  end
  Ao_by_col_ptr[n + 1] = Ao_ne + 1
  l = 0
  for j in 1:n
    for i in 1:n
      l = l + 1
      if i == j
        Ao_by_col_dense[l] = 1.0
      else
        Ao_by_col_dense[l] = 0.0
      end
    end
    l = l + 1
    Ao_by_col_dense[l] = 1.0
  end

  @printf(" fortran sparse matrix indexing\n\n")
  @printf(" tests reverse-communication options\n\n")

  # reverse-communication input/output
  on = max(o, n)
  eval_status = Ref{Cint}()
  nz_v_start = Ref{Cint}()
  nz_v_end = Ref{Cint}()
  nz_v = zeros(Cint, on)
  nz_p = zeros(Cint, o)
  mask = zeros(Cint, o)
  v = zeros(T, on)
  p = zeros(T, on)
  nz_p_end = 1

  # Initialize BLLS
  blls_initialize(T, data, control, status)

  # Set user-defined control options
  @reset control[].f_indexing = true # fortran sparse matrix indexing

  # Start from 0
  for i in 1:n
    x[i] = 0.0
    z[i] = 0.0
  end

  st = "RC"
  for i in 1:o
    mask[i] = 0
  end
  blls_import_without_a(T, control, data, status, n, o)

  terminated = false
  while !terminated # reverse-communication loop
    blls_solve_reverse_a_prod(T, data, status, eval_status, n, o, b,
                              x_l, x_u, x, z, r, g, x_stat, v, p,
                              nz_v, nz_v_start, nz_v_end,
                              nz_p, nz_p_end, w)

    if status[] == 0 # successful termination
      terminated = true
    elseif status[] < 0 # error exit
      terminated = true
    elseif status[] == 2 # evaluate p = Av
      p[o] = 0.0
      for i in 1:n
        p[i] = v[i]
        p[o] = p[o] + v[i]
      end
    elseif status[] == 3 # evaluate p = A^Tv
      for i in 1:n
        p[i] = v[i] + v[o]
      end
    elseif status[] == 4 # evaluate p = Av for sparse v
      for i in 1:o
        p[i] = 0.0
      end
      for l in nz_v_start[]:nz_v_end[]
        i = nz_v[l]
        p[i] = v[i]
        p[o] = p[o] + v[i]
      end
    elseif status[] == 5 # evaluate p = sparse Av for sparse v
      nz_p_end = 0
      for l in nz_v_start[]:nz_v_end[]
        i = nz_v[l]
        nz_p_end = nz_p_end + 1
        nz_p[nz_p_end] = i
        p[i] = v[i]
        if mask[i] == 0
          mask[i] = 1
          nz_p_end = nz_p_end + 1
          nz_p[nz_p_end] = o
          p[o] = v[i]
        else
          p[o] = p[o] + v[i]
        end
      end
      for l in 1:nz_p_end
        mask[nz_p[l]] = 0
      end
    elseif status[] == 6 # evaluate p = sparse A^Tv
      for l in nz_v_start[]:nz_v_end[]
        i = nz_v[l]
        p[i] = v[i] + v[o]
      end
    elseif status[] == 7 # evaluate p = P^{-}v
      for i in 1:n
        p[i] = userdata.scale * v[i]
      end
    else
      @printf(" the value %1i of status should not occur\n", status)
    end
    eval_status[] = 0
  end

  # Record solution information
  blls_information(T, data, inform, status)

  # Print solution details
  if inform[].status == 0
    @printf("%s:%6i iterations. Optimal objective value = %5.2f status = %1i\n",
            st, inform[].iter, inform[].obj, inform[].status)
  else
    @printf("%s: BLLS_solve exit status = %1i\n", st, inform[].status)
  end

  # @printf("x: ")
  # for i = 1:n
  #   @printf("%f ", x[i])
  # @printf("\n")
  # @printf("gradient: ")
  # for i = 1:n
  #   @printf("%f ", g[i])
  # @printf("\n")

  # Delete internal workspace
  blls_terminate(T, data, control, inform)

  return 0
end

@testset "BLLS" begin
  @test test_blls(Float32) == 0
  @test test_blls(Float64) == 0
end