lp_interior.m

beamlet变化的工具箱

%  LP_Interior --
%         Primal-dual damped Newton method for solving a linear program
%         in standard form.
%         [x,pi] = pd( A,b,c,l,u ) computes a vector x that solves
%         the problem
%                         minimize     c'x
%                         subject to   Ax = b,    l <= x <= u.
%   Usage: [x,pi] = LP_Interior( b,c,l,u,m,par1,par2,par3
%                        [,PDGapTol,FeaTol,CGAccuracy,MaxBaIter])
%   Inputs
%        b,c,l,u         column vectors
%        m               # of columns of the implicit matrix A
%        par1,par2,par3  parameters of the fast implicit algorithms
%                        namely 'FastAnalysis' and 'FastSynthesis'
%        PDGapTol        primal-dual gap tolerance for LP, default = 1e-3
%        FeaTol          feasibibility tolerance for LP, default = 1e-3
%        CGAccuracy      accuracy of the CG solver, default = 1e-3
%        MaxBaIter       maximum number of interior point iterations,
%                        default = 30
%   Outputs
%        x               primal solutioon
%        pi              dual solution
% 
%   Description:
%        1. To specify infinity upper bounds:
%                u = 1e99
%        2. BP Iterations Stops when one of the following happens:
%           (1) Converged
%                Primal Feasiblity & Dual Feasibility < FeaTol   and
%                Primal-Dual Gap < PDGapTol
%           (2) CG Solver broke
%                CG Iteration > MaxCGIter (default = m * log2(n))
%           (3) # of Barrier Iteration > MaxBaIter (default = 30)
%        3. Tuning Parameters
%                (1) MaxBaIter controls the maximum number of BP iterations.
%                    The default 30 is often more than enough. One may
%                    want to set it to be, say 8, to save computation time.
%                (2) MaxCGIter controls the maximum number of CG iterations.
%                    The default m*log2(m) is often more than enough. But
%                    if one may want to increase this parameter when he
%                    gets message saying "Too many CG iterations".
%                (3) the default FeaTol, PDGapTol and CGAccuracy give
%                    resonably good solutions; use smaller values to
%                    get more accurate solutions.
%                (4) gamma and delta are two purturbation paramters(See
%                    Gill et al). The default value (1e-5) is good enough
%                    for common purpose.
%                (5) Iterative Line Search Scheme:
%                    At each Barrier iteration, after calculating the
%                    step directions, the algorithm uses a iterative
%                    line search scheme to decide the "best" step
%                    length to take, by reducing a certain merit function.
%                    The maximum steps of line search is controlled by
%                        jfmax (default = 10)
%                    (Dave: Don't worry about this)
% 
%
%
% Part of BeamLab Version:200
% Built:Friday,23-Aug-2002 00:00:00
% This is Copyrighted Material
% For Copying permissions see COPYING.m
% Comments? e-mail [e-mail]
%
%
% Part of BeamLab Version:200
% Built:Saturday,14-Sep-2002 00:00:00
% This is Copyrighted Material
% For Copying permissions see COPYING.m
% Comments? e-mail [e-mail]
%