Previous Next whatsnew

Changes and Additions to ckbs

Introduction
This section contains a list of changes to ckbs (in reverse order by date). Its purpose is to assist you in learning about changes between versions.

11-08-01
Merged following changes from aravkin branch into the trunk:  
----------------------------------------------------------------

11-7-15
  1. Removed block tridiagonal inverter from this branch, along with example for it. This will go into a different branch and different release.
  2. Modernized ckbs_kuhn_tucker to use block tridiagonal and block diagonal multiplication
  3. Modified ckbs_affine to do a more robust interior point relaxation scheme, where the maximum of the complementarity conditions is taken into account.
  4. Made progress in fixing bug in ckbs_nonlinear that was causing the unit test to fail for the constrained sine and box sine. Committed algorithm now passes committed test.
  5. Added two more difficult datasets, z2 and z3, to allow for better testing.


2-6-17
Updated nonlinear test to read in dataset that makes the algorithm crash on Matlab. Added dataset to the nonlinear folder.

11-5-17
Added routine ckbs_L1_nonlinear and a test. The routine is the nonlinear robust L1 smoother, and the test checks that the optimization problem has converged and makes a plot of the robust smoother result compared to the iterated result from ckbs_affine for the Van Der Pol oscillator. The problem is set up to have a moderately high proportion of very noisy outliers, and the user can easily tweak the parameters to experiment by using L1_nonlinear_ok.m as a template.

11-5-10
Added routine ckbs_L1_affine and a test. The routine is the affine robust L1 smoother, and the test checks that the optimization problem has converged and makes a plot of the robust smoother result compared to the iterated result from ckbs_affine . The problem is set up to have a high proportion of very noisy outliers, and the user can easily tweak the parameters to experiment by using L1_affine_ok.m as a template.

11-5-9
  1. Rewrote ckbs_blkdiag_mul and ckbs_blkdiag_mul_t to work on matrices as well as vectors.
  2. Rewrote test for ckbs_blktridiag_mul so that it does not rely on any other routines.
  3. Rewrote tests for ckbs_kuhn_tucker and ckbs_newton_step to use lower level routines, eliminating redundant code and increasing transparency of these tests.
  4. Rewrote tests for ckbs_tridiag_solve and ckbs_tridiag_solve_b to use ckbs_blktridiag_mul for transparency.
  5. Added routines ckbs_newton_step_L1 and test to compute the newton iteration for the L1 robust smoother.


11-5-4
Added ckbs_kuhn_tucker_L1 and test. This function computes the Kuhn-Tucker residual for the robust L1 smoothing problem.

11-5-3
  1. Added ckbs_L2L1_obj and test. This function computes the affine least squares (for process) and L1 robust (for residuals) norm, and is used by the robust L1 smoother.
  2. Added ckbs_process_grad and test. This routine computes the process portion of the gradient of the objective, and is used by the L1 smoother.
  3. Added ckbs_process_hes and test. This routine computes the process portion of the Hessian to the objective, and is used by the L1 smoother.


11-5-2
Rewrote ckbs_newton_step . New algorithm uses one fewer tridiagonal solve, only inverts the augmented tridiagonal system, avoid the Woodbury inversion lemma, and requires much less exposition.

11-5-1
Added tridiagonal inverse routine and test, subsequently deleted. Given a packed tridiagonal matrix  A , the routine computes the block diagonal of  A^{-1} . The work to compute this scales linearly with the number of time points. This routine is useful for obtaining the a posteriori variance estimate from a kalman smoothing fit.

11-4-30
Added ckbs_tridiag_solve_b to src directory and tridiag_solve_b_ok.m to example directory. This routine is an alternate version to ckbs_tridiag_solve currently used by ckbs. The new routine is used by the robust smoother, and in some instances it may be more stable than the standard version.

11-4-29
Added ckbs_blktridiag_mul to src directory and blktridiag_mul_ok.m to example directory. This utility routine is used by the robust smoother, and also can be used to quickly convert a block tridiagonal matrix from compact to explicit form via multiplication with the identity.  
----------------------------------------------------------------

10-11-15
  1. Move vanderpol_ok.m , vanderpol_sim and vanderpol_sim_ok.m from example directory to example/nonlinear directory.
  2. Create persist_g.m a general purpose transition utility for use with ckbs_nonlinear . Change get_started_ok.m to use this utility.
  3. Change get_started_ok.m to use direct_h.m and box_f.m . In addition, make other improvements to get_started_ok.m.


10-11-14
  1. Make the unconstrained, box constrained, and nonlinear constrained cases options to the routine sine_wave_ok.m . This replaces the old nl_measure_ok.m and nonlinear_ok_sin.m examples.
  2. Create sine_f.m a general purpose constraint utility for use with ckbs_nonlinear . Change sine_wave_ok.m to use this utility.


10-11-13
Create distance_h.m a general purpose distance measurement utility for use with ckbs_nonlinear . Change examples to use this utility.

10-11-12
Create pos_vel_g.m a general purpose position and velocity utility for use with ckbs_nonlinear . Change examples to use this utility.

10-11-10
  1. Create box_f.m a general purpose box constraint utility for use with ckbs_nonlinear . Change examples to use this utility.
  2. Document and make no_f.m a general purpose utility for unconstrained problems. Change examples to use this utility.


10-11-03
Create a subdirectory called example/nonlinear and move nonlinear_ok_simple.m to nonlinear/get_started_ok.m, and nonlinear_ok_box.m to nonlinear/nl_measure_ok.m. Improve the get_started_ok.m and nl_measure_ok.m, implementation and documentation.

10-10-28
Add the vanderpol_ok.m example and test of non-linear dynamical system. You can run this example as follows: 
 
	cd example
	octave
	vanderpol_ok(true)
You can replace octave by matlab. The argument true instructs vanderpol_ok to plot the results.

10-06-07
Have ckbs_nonlinear report an error when an argument, or call back function return value, is not finite valued.

10-03-25
  1. Moves the test directory to example
  2. Created the file test/affine_line_search_ok.m which demonstrated a bug in ckbs_affine .
  3. Fixed the bug in ckbs_affine .


10-02-28
Change download instructions to correspond COIN-OR distribution instead of form Brad Bell's home page .

07-09-02
The ckbs_nonlinear algorithm has been modified to conform with the global convergence theory of Burke and Han. This involved adding the exact penalty parameter  \alpha which is included in the trace and info return.

07-08-31
In the case where the constraints were not active, the ckbs_affine return value uOut was a three dimensional array instead of a matrix. This has been fixed.

06-11-05
Fix plotting the wrong variables in constrained case for nl_measure_ok.m.

Improve the documentation of the initial state estimate in g_fun and qinv for ckbs_nonlinear.

Improve the documentation of the initial state estimate in g_fun and qinv for ckbs_nonlinear.

06-11-03
The order of the variables in the state vector for nl_measure_ok.m and for nonlinear_ok_sin.m was changed to group each component of velocity with the corresponding position (instead of grouping position with position and velocity with velocity). This made the variance matrix  Q_k block diagonal (simpler).

06-10-24
The fonts got misaligned in the ckbs_affine syntax documentation. This has been fixed.

06-10-20
The ckbs_nonlinear implementation was greatly simplified using the fact that ckbs_affine no longer requires a feasible starting point. This removed the need for an augmented problem and hence the info return value from ckbs_nonlinear no longer has a penalty parameter; i.e., it has one less value per row.

all_ok.m was extended so that if no argument is provided, only the quick tests are run.

06-10-19
The ckbs_affine routine has been improved so that it no longer requires a feasible input point so the input argument xIn has been removed. Since the sequence of iterates is no longer necessarily feasible, the info return value now has been changed so that it now includes a measure of feasibility. The input argument max_itr has been added to ckbs_affine. The affine_ok_box.m example has been changed to use the new meaning for the arguments and return values of ckbs_affine.

The itr_out return value has been removed from the ckbs_nonlinear syntax. It was the same as size(info, 1). The following examples have been changed to remove the use of itr_out in the calls to ckbs_nonlinear: get_started_ok.m , nl_measure_ok.m, nonlinear_ok_sin.m.

The implementation of ckbs_nonlinear has been changed to use the new calling sequence to ckbs_affine (this is implementation detail and does not affect the user).

06-10-13
The line search in ckbs_affine had a bug where the sign of the condition it was checking was reversed. This has been changed. In addition, the minimum line search step size in the sub-problem was added to the info return value for ckbs_nonlinear .

There was a syntax error in get_started_ok.m that caused a problem in Matlab®, but not in octave. This has been fixed.

06-10-05
  1. Matlab® does not combine character matrices with different numbers of columns. A debugging message assignment in ckbs_nonlinear.m was removed to avoid this.
  2. Documentation for missing data values was added to rinv .
  3. Some minor Matlab compatibility problems in the files example/nonlinear/nl_measure_ok.m and example/nonlinear_ok_sin.m were fixed.
  4. The directory created when the download file was extracted was ckbs instead of ckbs-yy-mm-dd. This has been fixed.
  5. The utility section, and all its subsections, were missing from the documentation.
  6. The number of input arguments and output values for ckbs_nonlinear has been changes to allow for control of the number of iterations.
  7. Line search failure in ckbs_nonlinear was converted from an error to a warning.


06-10-01
  1. The test_path.m function was added so that it is easier to run a single test at the command line (you need to run this function first).
  2. A tracing argument called level was added to ckbs_nonlinear . This tracing was turned on in the nl_measure_ok.m example.
  3. The nonlinear constraint example nonlinear_ok_sin.m was added. It demonstrates significant improvement by the inclusion of the constraints.
  4. The draw_plot argument to the nl_measure_ok.m example was documented.
  5. The quick argument was added to all_ok.m .
  6. The files example/nonlinear_ok_sin.r and example/nonlinear/nl_measure_ok.r were added to the distribution. (These are R source code files that are used to make plots from the corresponding example output files.)


06-09-30
The function ckbs has been changed to ckbs_nonlinear . This enables the ckbs section to refer to the documentation for the entire system.
Input File: omh/whatsnew.omh