bpnotes.m

来自「％ Atomizer Main Directory, Version .802 」· M 代码 · 共 65 行

% BPNotes -- New solvers for Atomizer BP and BPDN        April 14, 2001
%----------------------------------------------------------------------
% 
% 1998 solvers: BP_Interior.m,  BPDN_Interior.m
% 2001 solvers: BP_Interior2.m, BPDN_Interior2.m
% 
% The 1998 solvers use a primal-dual barrier method as described
% in the Basis Pursuit papers.  Search directions are computed
% by the conjugate gradient method (CG).  For the BP figures,
% rather loose tolerances are used to terminate CG and the
% barrier method itself.
% 
% The 2001 solvers are based on pdsco, which uses a similar barrier
% method but with more rigorous control over the computation.
% 
% o The problem is scaled using estimates of the primal and dual
%   variables x and z.  This permits better starting and stopping
%   decisions in the barrier method.  (The scaled variables have
%   maximum elements of order 1.)
% 
% o The search directions are computed by LSQR, a CG solver
%   for least-squares problems.  (LSQR converges more quickly
%   than CG on the equivalent problem, and it incorporates
%   reliable stopping rules.)
% 
% o An "inexact Newton" strategy is used to control the accuracy
%   of the search directions.  Low accuracy directions are
%   used for early barrier iterations (as in the 1998 solvers),
%   but increasing accuracy is requested according to progress.
%
% o The barrier parameter "mu" is also reduced according to
%   progress, but only if the x and z solutions are reasonably
%   "centered":  max(x.*z) / min(x.*z) < 100.
% 
% 
% CHOICE OF SOLVER
% 
% BPDemo provides an interactive menu to run the bp scripts
% with selected solvers.
% 
% Alternatively, individual scripts may be run manually.
% To see how to select the solver, type
%    help bpengine
% 
% 
% COMPARISON
% 
% Solver performance depends heavily on the input parameters
% (FeaTol, OptTol, CGAccuracy, etc).  The scripts specify
% various loose parameter values for the original solvers.
% (They have seemed suitable to date.)
% For the 2001 solvers, the scripts use uniform default values
% set in BP_Interior2 and BPDN_Interior2 (currently 1e-3).
% 
% As used in the bp scripts, the new solvers are sometimes
% significantly faster than the originals, and sometimes
% significantly slower, but the quality of the solution is
% always comparable (and sometimes significantly better).
% 
% In general, the original solvers seem to achieve "good"
% low accuracy solutions remarkably quickly.  We anticipate
% that the new solvers will perform more predictably and
% efficiently for medium and higher accuracy solutions
% (tolerances 1e-3 and smaller).
%----------------------------------------------------------------------