minTolOut
Outer tolerance principle to stop the primal-dual algorithm.
Contents
Syntax
pdaN = minTolOut(iOut,pdaNv,dis,disLin,relDis,seti) pdaN = minTolOut(iOut,pdaNv,dis,disLin,relDis,seti,dispDepth)
Description
pdaN = minTolOut(iOut,pdaNv,dis,disLin,relDis,seti) computes the number of inner iterations pdaN to stop the primal-dual algorithm. See "More About" for details.
pdaN = minTolOut(iOut,pdaNv,dis,disLin,relDis,seti,dispDepth) does the same but allows to control the displayed messages by dispDepth.
To use it in context of computational framework set seti.useTolOut = 1.
Input Arguments
- iOut : iteration number of outer iterations
- pdaNv : numbers of inner iterations stored in a vector (size 1 x seti.nOut, where nOut is the maximal number of outer iterations)
- dis : discrepancy of each outer iteration stored in vector (size 1 x seti.nOut, where nOut is the maximal number of outer iterations)
- disLin : linearized discrepancy of each outer iteration stored in vector (size 1 x seti.nOut, where nOut is the maximal number of outer iterations)
- relDis : relative discrepancy = disLin/dis of each outer iteration stored in vector (size 1 x seti.nOut, where nOut is the maximal number of outer iterations)
- seti.pdaNmax : Maximal iteration number, if seti.useTolIn or seti.useTolOut are 1 (default : 250).
- seti.relDisTol : Outer tolerance (default: 0.05).
Optional Input Argument
- dispDepth : Depth of displayed messages (0: no, 4 or greater: yes).
Output Arguments
- pdaN : number of inner iterations to stop the primal-dual algorithm
More About
The primal-dual algorithm is the inner iteration in the computational framework. The outer tolerance principle defines a stop index pdaN for the next application of primal-dual algorithm.
This method is described in paragraph "Stopping strategy 1" of Section 4.10 in [2]. We give a brief introduction here.
Notation
Scheme
- Choose the number of inner iterations in the
-th outer iteration:
- Review this choice: It is "good", if the following quotient is approximately 1:
(i.e. linearized discrepancy / non-linearized discrepancy)
If the choice was "good" we increase the number of inner iterations (first case), if not we decrease it (second case):
1st case:
2nd case:
Note, that and
.
- Start with conservative choice:
.
- Limit the number of inner iterations by
.
References
- [1] Florian Bürgel, Kamil S. Kazimierski, and Armin Lechleiter. A sparsity regularization and total variation based computational framework for the inverse medium problem in scattering. Journal of Computational Physics, 339:1-30, 2017. URL: https://doi.org/10.1016/j.jcp.2017.03.011.
See Also
Code
function pdaN = minTolOut(iOut,pdaNv,dis,disLin,relDis,seti,varargin) if nargin == 7 dispDepth = varargin{1}; else dispDepth = 0; end relDisTol = seti.relDisTol; % tolerance, e.g. 0.01 if iOut > seti.iOutIni+1 % Adapt the number of inner iterations pdaN. if dispDepth >= 4 disp('------------------------------------------') fprintf(' pdaN = %g\n',pdaNv(iOut-1)); fprintf('dis (nonlin) = %g\n',dis(iOut-1)); fprintf('dis (lin) = %g\n',disLin(iOut-1)); disp('------------------------------------------') end % Relative difference between linearized and non-linearized % discrepancy terms. RelDisVal = relDis(iOut-1); mu1 = 1+sqrt(1./iOut).*log(iOut); mu2 = min(1/RelDisVal,RelDisVal)^2; pdaNprev = seti.pdaN; if dispDepth >= 4 fprintf('|relDis| = %g\n',RelDisVal); end if 1-relDisTol < RelDisVal && RelDisVal < 1+relDisTol if dispDepth >= 4 fprintf('%g < |relDis| < %g\n',1-relDisTol,1+relDisTol); end pdaN = ceil(mu1*pdaNprev); % increase pdaN else if dispDepth >= 4 fprintf('|relDis| < %g OR |relDis| > %g\n',1-relDisTol,1+relDisTol); end pdaN = floor(mu2*pdaNprev); % decrease pdaN end if pdaN == 0 pdaN = 1; end if dispDepth >= 4 fprintf('pdaN = %g (prev.: %g)\n',pdaN,pdaNprev); end elseif seti.useTolIn == 0 pdaN = 1; % inner tolerance principle is not used, then do only 1 step. else pdaN = seti.pdaN; % no change end if pdaN > seti.pdaNmax pdaN = seti.pdaNmax; end end