BCLS: Bound Constrained Least Squares

Version 0.1

bcls.h File Reference

#include <stdio.h>
#include <setjmp.h>
#include "bctimer.h"

Include dependency graph for bcls.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  BCLS

Defines

#define BCLS_PROD_A   1
#define BCLS_PROD_At   2
#define BCLS_PROD_INIT   -1
#define BCLS_PROD_TERM   -2
#define BCLS_PRECON_U   1
#define BCLS_PRECON_Ut   2
#define BCLS_PRECON_INIT   -1
#define BCLS_PRECON_TERM   -2
#define BCLS_MIN_COLUMN_NORM   1e-8
 Min allowable col norm.
#define BCLS_PROJ_SEARCH_EXACT   0
 Exact projected linesearch.
#define BCLS_PROJ_SEARCH_APPROX   1
 Approximate projected linesearch.
#define BCLS_NEWTON_STEP_LSQR   0
 LSQR on least-squares formulation.
#define BCLS_NEWTON_STEP_CGLS   1
 CGLS on normal equations.
#define BCLS_TIMER_TOTAL   0
 Overall tiemr.
#define BCLS_TIMER_APROD   1
 Mat-vec routine timer.
#define BCLS_TIMER_LSQR   2
 LSQR timer.
#define BCLS_TIMER_USOLVE   3
 Usolve timer.
#define BCLS_EXIT_CNVGD   0
 Optimal solution found.
#define BCLS_EXIT_MAJOR   1
 Too many major iterations.
#define BCLS_EXIT_MINOR   2
 Too many minor iterations.
#define BCLS_EXIT_UNDEF   3
 Exit condition is undefined.
#define BCLS_EXIT_UNBND   4
 Found direction of infinite descent.
#define BCLS_EXIT_INFEA   5
 Bounds are inconsistent.
#define BCLS_EXIT_LFAIL   6
 Linesearch failure.
#define BCLS_EXIT_APROD   100
 Exit requested by user's aprod routine.
#define BCLS_EXIT_USOLVE   110
 Exit requested by user's usolve routine.
#define BCLS_EXIT_CALLBK   120
 Exit requested by user's callback routine.
#define BCLS_SOLN_UNDEF   0
 Solution is undefined.
#define BCLS_SOLN_OPTIM   1
 Solution is optimal.
#define BCLS_INFINITY   1e+20

Typedefs

typedef BCLS BCLS

Functions

BCLSbcls_create_prob (int mmax, int nmax)
 Create a BCLS problem instance.
void bcls_init_prob (BCLS *ls)
 Initialize a BCLS problem.
int bcls_free_prob (BCLS *ls)
 Free and reinitialize all resources in an existing BCLS problem.
char * bcls_exit_msg (int flag)
 Return an exit message.
int bcls_solve_prob (BCLS *ls)
 Solve the current problem instance.
void bcls_set_print_hook (BCLS *ls, void *info, int(*hook)(void *info, char *msg))
 Install a print-hook routine.
void bcls_set_fault_hook (BCLS *ls, void *info, int(*hook)(void *info, char *msg))
 Install a fault-hook routine.
void bcls_set_usolve (BCLS *ls, int(*Usolve)(int mode, int m, int n, int nix, int ix[], double v[], double w[], void *UsrWrk))
 Install a user-defined preconditioning routine.
void bcls_set_anorm (BCLS *ls, double anorm[])
 Give BCLS access to set of column weights.
int bcls_compute_anorm (BCLS *ls, int n, int m, int(*Aprod)(int mode, int m, int n, int nix, int ix[], double x[], double y[], void *UsrWrk), void *UsrWrk, double anorm[])
 Compute the column norms of A.
void bcls_set_problem_data (BCLS *ls, int m, int n, int(*Aprod)(int mode, int m, int n, int nix, int ix[], double x[], double y[], void *UsrWrk), void *UsrWrk, double damp, double x[], double b[], double c[], double bl[], double bu[])
 Load the problem into the BCLS data structure.


Detailed Description

BCLS library header file. This is the file "included" by the user.

Definition in file bcls.h.


Define Documentation

#define BCLS_EXIT_APROD   100

Exit requested by user's aprod routine.

Definition at line 143 of file bcls.h.

Referenced by bcls_aprod(), and bcls_exit_msg().

#define BCLS_EXIT_CALLBK   120

Exit requested by user's callback routine.

Definition at line 145 of file bcls.h.

Referenced by bcls_exit_msg(), and bcls_solver().

#define BCLS_EXIT_CNVGD   0

Optimal solution found.

Definition at line 136 of file bcls.h.

Referenced by bcls_exit_msg(), and bcls_solver().

#define BCLS_EXIT_INFEA   5

Bounds are inconsistent.

Definition at line 141 of file bcls.h.

Referenced by bcls_examine_bnds(), and bcls_exit_msg().

#define BCLS_EXIT_LFAIL   6

Linesearch failure.

Definition at line 142 of file bcls.h.

Referenced by bcls_proj_backtrack(), and bcls_solver().

#define BCLS_EXIT_MAJOR   1

Too many major iterations.

Definition at line 137 of file bcls.h.

Referenced by bcls_exit_msg(), and bcls_solver().

#define BCLS_EXIT_MINOR   2

Too many minor iterations.

Definition at line 138 of file bcls.h.

Referenced by bcls_exit_msg(), and bcls_solver().

#define BCLS_EXIT_UNBND   4

Found direction of infinite descent.

Definition at line 140 of file bcls.h.

Referenced by bcls_exit_msg(), bcls_proj_backtrack(), and bcls_solver().

#define BCLS_EXIT_UNDEF   3

Exit condition is undefined.

Definition at line 139 of file bcls.h.

Referenced by bcls_init_prob(), and bcls_solver().

#define BCLS_EXIT_USOLVE   110

Exit requested by user's usolve routine.

Definition at line 144 of file bcls.h.

Referenced by bcls_exit_msg(), and bcls_usolve().

#define BCLS_INFINITY   1e+20

Definition at line 170 of file bcls.h.

Referenced by bcls_init_prob().

#define BCLS_MIN_COLUMN_NORM   1e-8

Min allowable col norm.

Definition at line 82 of file bcls.h.

Referenced by bcls_compute_anorm().

#define BCLS_NEWTON_STEP_CGLS   1

CGLS on normal equations.

Examples:
/examples/bcsol.c.

Definition at line 94 of file bcls.h.

#define BCLS_NEWTON_STEP_LSQR   0

LSQR on least-squares formulation.

Examples:
/examples/bcsol.c.

Definition at line 93 of file bcls.h.

Referenced by bcls_init_prob(), bcls_newton_step(), bcls_print_params(), and bcls_solve_prob().

#define BCLS_PRECON_INIT   -1

Mode for Usolve: Initialize.

Examples:
/examples/bcsol.c.

Definition at line 74 of file bcls.h.

Referenced by bcls_newton_step().

#define BCLS_PRECON_TERM   -2

Mode for Usolve: Destroy.

Examples:
/examples/bcsol.c.

Definition at line 75 of file bcls.h.

Referenced by bcls_newton_step().

#define BCLS_PRECON_U   1

Mode for Usolve: U v = w.

Examples:
/examples/bcsol.c.

Definition at line 72 of file bcls.h.

Referenced by aprod_free_lsqr(), bcls_newton_step(), and bcls_usolve().

#define BCLS_PRECON_Ut   2

Mode for Usolve: U'w = v.

Examples:
/examples/bcsol.c.

Definition at line 73 of file bcls.h.

Referenced by aprod_free_lsqr(), and bcls_usolve().

#define BCLS_PROD_A   1

Mode for Aprod: y = A x.

Examples:
/examples/bcsol.c.

Definition at line 64 of file bcls.h.

Referenced by aprod_free(), aprod_free_lsqr(), bcls_cgls(), bcls_proj_backtrack(), and bcls_solver().

#define BCLS_PROD_At   2

Mode for Aprod: x = A'y.

Examples:
/examples/bcsol.c.

Definition at line 65 of file bcls.h.

Referenced by aprod_free(), aprod_free_lsqr(), bcls_cgls(), and bcls_solver().

#define BCLS_PROD_INIT   -1

Mode for Aprod: Initialize.

Examples:
/examples/bcsol.c.

Definition at line 66 of file bcls.h.

Referenced by bcls_aprod(), and bcls_newton_step().

#define BCLS_PROD_TERM   -2

Mode for Aprod: Destroy.

Examples:
/examples/bcsol.c.

Definition at line 67 of file bcls.h.

Referenced by bcls_aprod(), and bcls_newton_step().

#define BCLS_PROJ_SEARCH_APPROX   1

Approximate projected linesearch.

Examples:
/examples/bcsol.c.

Definition at line 91 of file bcls.h.

Referenced by bcls_print_params(), and bcls_solver().

#define BCLS_PROJ_SEARCH_EXACT   0

Exact projected linesearch.

Examples:
/examples/bcsol.c.

Definition at line 90 of file bcls.h.

Referenced by bcls_init_prob(), bcls_solve_prob(), and bcls_solver().

#define BCLS_SOLN_OPTIM   1

Solution is optimal.

Definition at line 154 of file bcls.h.

Referenced by bcls_solver().

#define BCLS_SOLN_UNDEF   0

Solution is undefined.

Definition at line 153 of file bcls.h.

Referenced by bcls_init_prob().

#define BCLS_TIMER_APROD   1

Mat-vec routine timer.

Definition at line 100 of file bcls.h.

Referenced by bcls_aprod(), bcls_init_prob(), and bcls_solve_prob().

#define BCLS_TIMER_LSQR   2

LSQR timer.

Definition at line 101 of file bcls.h.

Referenced by bcls_init_prob(), bcls_newton_step_lsqr(), and bcls_solve_prob().

#define BCLS_TIMER_TOTAL   0

Overall tiemr.

Definition at line 99 of file bcls.h.

Referenced by bcls_init_prob(), and bcls_solve_prob().

#define BCLS_TIMER_USOLVE   3

Usolve timer.

Definition at line 102 of file bcls.h.

Referenced by bcls_init_prob(), bcls_solve_prob(), and bcls_usolve().


Typedef Documentation

typedef struct BCLS BCLS

Definition at line 46 of file bcls.h.


Function Documentation

int bcls_compute_anorm ( BCLS ls,
int  n,
int  m,
int(*)(int mode, int m, int n, int nix, int ix[], double x[], double y[], void *UsrWrk)  Aprod,
void *  UsrWrk,
double  anorm[] 
)

Compute the column norms of A.

Compute the columns norms of A. Each column of A is generated by multiplying A by a unit vector. The two-norm squared of each column is stored in aprod.

This routine must be called *after* bcls_create_prob. (As with any other BCLS routine.)

Parameters:
[in] ls BCLS problem context.
[in] m Number of rows in A.
[in] n Number of columns in A.
[in] Aprod User's matrix-product routine.
[in,out] UsrWrk Pointer to user's workspace (could be NULL).
[out] anorm Vector of column norms of A.
Returns:
Returns any error codes returned by the user's aprod routine.

Definition at line 437 of file bcls.c.

References bcls_dload(), BCLS_MIN_COLUMN_NORM, cblas_dnrm2(), BCLS::ix, BCLS::wrk_u, and BCLS::wrk_v.

Here is the call graph for this function:

BCLS* bcls_create_prob ( int  mmax,
int  nmax 
)

Create a BCLS problem instance.

This routine create a BCLS problem. It *must* be called before any other BCLS routine. It will create and initialize a new BCLS problem with enough space to accomodate the specified problem. The problem is then initialized using bcls_init_prob.

In order to re-initialize the BCLS problem instance, but not deallocate memory that's already sufficient for an equal or smaller size problem, use bcls_init_prob.

Parameters:
[in] mmax Maximum number of rows in any A.
[in] nmax Maximum number of columns in any A.
Returns:
Return a pointer to a new BCLS problem. If the return is NULL, then the initialization failed.

Definition at line 93 of file bcls.c.

References BCLS::aBreak, bcls_free_prob(), bcls_init_prob(), BCLS::dx, BCLS::dxFree, BCLS::g, BCLS::iBreak, imax(), BCLS::ix, BCLS::mmax, BCLS::nmax, BCLS::r, BCLS::wrk_u, BCLS::wrk_v, BCLS::wrk_w, and xmalloc().

Here is the call graph for this function:

char* bcls_exit_msg ( int  flag  ) 

Return an exit message.

Parameters:
[in] flag The code of the error.
Returns:
Error messsage.

Definition at line 536 of file bcls.c.

References BCLS_EXIT_APROD, BCLS_EXIT_CALLBK, BCLS_EXIT_CNVGD, BCLS_EXIT_INFEA, BCLS_EXIT_MAJOR, BCLS_EXIT_MINOR, BCLS_EXIT_UNBND, and BCLS_EXIT_USOLVE.

Referenced by bcls_solve_prob().

int bcls_free_prob ( BCLS ls  ) 

Free and reinitialize all resources in an existing BCLS problem.

Returns:
  • 0: no errors
  • 1: the BCLS problem is NULL (ie, does not exist).

Definition at line 269 of file bcls.c.

References BCLS::aBreak, BCLS::dx, BCLS::dxFree, BCLS::g, BCLS::iBreak, BCLS::ix, BCLS::r, BCLS::wrk_u, BCLS::wrk_v, and BCLS::wrk_w.

Referenced by bcls_create_prob().

void bcls_init_prob ( BCLS ls  ) 

Initialize a BCLS problem.

Initialize a BCLS problem. You can call this routine to "reset" a BCLS problem, i.e., reset all parameter values. Note that it is automatically called by bcls_create_prob.

Parameters:
[in,out] ls BCLS problem context.

Definition at line 186 of file bcls.c.

References BCLS::anorm, BCLS::Aprod, BCLS::backtrack, BCLS::backtrack_limit, BCLS_EXIT_UNDEF, BCLS_INFINITY, BCLS_NEWTON_STEP_LSQR, BCLS_PROJ_SEARCH_EXACT, BCLS_SOLN_UNDEF, bcls_timer(), BCLS_TIMER_APROD, BCLS_TIMER_INIT, BCLS_TIMER_LSQR, BCLS_TIMER_TOTAL, BCLS_TIMER_USOLVE, BCLS::BigNum, BCLS::CallBack, BCLS::conlim, BCLS::damp, BCLS::damp_min, BCLS::eps, BCLS::eps2, BCLS::eps3, BCLS::epsfixed, BCLS::epsx, BCLS::exit, BCLS::fault_hook, BCLS::fault_info, BCLS::itnMaj, BCLS::itnMajLim, BCLS::itnMin, BCLS::itnMinLim, BCLS::m, BCLS::minor_file, BCLS::mmax, BCLS::mu, BCLS::n, BCLS_timer::name, BCLS::nAprod1, BCLS::nAprodF, BCLS::nAprodT, BCLS::newton_step, BCLS::nmax, BCLS::nUsolve, BCLS::optTol, BCLS::print_hook, BCLS::print_info, BCLS::print_level, BCLS::proj_search, BCLS::soln_dInf, BCLS::soln_jInf, BCLS::soln_rNorm, BCLS::soln_stat, BCLS::stopwatch, BCLS::unconstrained, BCLS::Usolve, and BCLS::UsrWrk.

Referenced by bcls_create_prob().

Here is the call graph for this function:

void bcls_set_anorm ( BCLS ls,
double  anorm[] 
)

Give BCLS access to set of column weights.

Define a set of column weights. BCLS will use these to scale the steepest-descent steps.

Parameters:
[in,out] ls BCLS problem context.
[in] anorm Array of columns norms of A.

Definition at line 374 of file bcls.c.

References BCLS::anorm.

void bcls_set_fault_hook ( BCLS ls,
void *  info,
int(*)(void *info, char *msg)  hook 
)

Install a fault-hook routine.

This routine installs a user-defined fault-hook routine.

The parameter info is a transit pointer passed to the hook routine.

The parameter "hook" is an entry point to the user-defined fault-hook routine. This routine is called by the routine "bcls_fault" every time an error message should be output. The routine "bcls_fault" passes to the hook routine the transit pointer info and the character string msg, which contains the message. If the hook routine returns zero, the routine print prints the message in an usual way. Otherwise, if the hook routine returns non-zero, the message is not printed.

In order to uninstall the hook routine the parameter hook should be specified as NULL (in this case the parameter info is ignored).

Parameters:
[in,out] ls BCLS problem context.
[in] info Transit pointer passed to the hook routine.
[in] hook Pointer to the fault-hook routine.

Definition at line 353 of file bcls.c.

References BCLS::fault_hook, and BCLS::fault_info.

void bcls_set_print_hook ( BCLS ls,
void *  info,
int(*)(void *info, char *msg)  hook 
)

Install a print-hook routine.

This routine installs a user-defined print-hook routine.

The parameter info is a transit pointer passed to the hook routine.

The parameter hook is an entry point to the user-defined print-hook routine. This routine is called by the routine "print" every time an informative message should be output. The routine "print" passes to the hook routine the transit pointer info and the character string msg, which contains the message. If the hook routine returns zero, the routine print prints the message in an usual way. Otherwise, if the hook routine returns non-zero, the message is not printed.

In order to uninstall the hook routine the parameter hook should be specified as NULL (in this case the parameter info is ignored).

Parameters:
[in,out] ls BCLS problem context.
[in] info Transit pointer passed to the hook routine.
[in] hook Pointer to the print-hook routine.

Definition at line 318 of file bcls.c.

References BCLS::print_hook, and BCLS::print_info.

void bcls_set_problem_data ( BCLS ls,
int  m,
int  n,
int(*)(int mode, int m, int n, int nix, int ix[], double x[], double y[], void *UsrWrk)  Aprod,
void *  UsrWrk,
double  damp,
double  x[],
double  b[],
double  c[],
double  bl[],
double  bu[] 
)

Load the problem into the BCLS data structure.

The routiens loads the complete problem description into a BCLS problem instance. No work is really being done: only the various structure elements are being set to point to the right places.

Parameters:
[in,out] ls BCLS problem context.
[in] m Number of rows in A. Note: m <= mmax.
[in] n Number of columns in A. Note: n <= nmax.
[in] Aprod Hook to user's matrix-vector product routine.
[in,out] UsrWrk Transit pointer passed directly to Aprod/Usolve.
[in] damp Regularization parameter.
[in,out] x The starting point.
[in] b The RHS vector.
[in] c Defines a linear term (set to NULL if one doesn't exist).
[in] bl Lower bounds on x.
[in] bu Upper bounds on x.

Definition at line 501 of file bcls.c.

References BCLS::Aprod, BCLS::b, BCLS::bl, BCLS::bu, BCLS::c, BCLS::damp, BCLS::m, BCLS::n, BCLS::UsrWrk, and BCLS::x.

void bcls_set_usolve ( BCLS ls,
int(*)(int mode, int m, int n, int nix, int ix[], double v[], double w[], void *UsrWrk)  Usolve 
)

Install a user-defined preconditioning routine.

Replace each subproblem

\[ \def\minimize{\displaystyle\mathop{\hbox{minimize}}} \minimize_x \| Ax - b \| \]

with

\[ \def\minimize{\displaystyle\mathop{\hbox{minimize}}} \minimize_y \| AU^{-1}y - b \| \quad\mbox{with}\quad Ux = y. \]

Parameters:
[in,out] ls BCLS problem context.
[in] Usolve Pointer to the user's preconditioning routine.

Definition at line 403 of file bcls.c.

References BCLS::Usolve.

int bcls_solve_prob ( BCLS ls  ) 

Solve the current problem instance.

Returns:

Definition at line 568 of file bcls.c.

References BCLS::aBreak, BCLS::anorm, BCLS::b, bcls_compilation_info(), bcls_examine_bnds(), bcls_examine_column_scales(), bcls_exit_msg(), BCLS_NEWTON_STEP_LSQR, bcls_primal_inf(), bcls_print_params(), BCLS_PROJ_SEARCH_EXACT, bcls_solver(), bcls_timer(), BCLS_TIMER_APROD, BCLS_TIMER_LSQR, BCLS_TIMER_START, BCLS_TIMER_STOP, BCLS_TIMER_TOTAL, BCLS_TIMER_USOLVE, bcls_version_info(), BCLS::bl, BCLS::bu, BCLS::c, BCLS::dx, BCLS::dxFree, BCLS::eps, BCLS::exit, BCLS::g, BCLS::iBreak, BCLS::itnMaj, BCLS::itnMin, BCLS::ix, BCLS::jmp_env, BCLS::m, BCLS::n, BCLS_timer::name, BCLS::nAprod1, BCLS::nAprodT, BCLS::newton_step, BCLS::nUsolve, PRINT1, BCLS::proj_search, BCLS::r, BCLS::soln_dInf, BCLS::soln_jInf, BCLS::soln_obj, BCLS::stopwatch, BCLS_timer::total, BCLS::Usolve, and BCLS::x.

Here is the call graph for this function:

Generated on Sun Mar 4 22:50:03 2007 by Doxygen 1.5.1