Page MenuHomec4science
Files F121882828

iswnbr.c
No OneTemporary
Actions

File Metadata

Created
Mon, Jul 14, 14:32

iswnbr.c
View Options

/*
% [delta,h,alpha] = iswnbr(vSQR,thetaSQR)
% ISWNBR Checks feasibility w.r.t. wide region/neighborhood of Sturm-Zhang.
%
% SEE ALSO sedumi
% ********** INTERNAL FUNCTION OF SEDUMI **********
function [delta,h,alpha] = iswnbr(vSQR,thetaSQR)
% This file is part of SeDuMi 1.1 by Imre Polik and Oleksandr Romanko
% Copyright (C) 2005 McMaster University, Hamilton, CANADA (since 1.1)
%
% Copyright (C) 2001 Jos F. Sturm (up to 1.05R5)
% Dept. Econometrics & O.R., Tilburg University, the Netherlands.
% Supported by the Netherlands Organization for Scientific Research (NWO).
%
% Affiliation SeDuMi 1.03 and 1.04Beta (2000):
% Dept. Quantitative Economics, Maastricht University, the Netherlands.
%
% Affiliations up to SeDuMi 1.02 (AUG1998):
% CRL, McMaster University, Canada.
% Supported by the Netherlands Organization for Scientific Research (NWO).
%
% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
%
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
% 02110-1301, USA
*/
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "mex.h"
#define DELTA_OUT myplhs[0]
#define H_OUT myplhs[1]
#define ALPHA_OUT myplhs[2]
#define NPAROUT 3
#define VSQR_IN prhs[0]
#define THETASQR_IN prhs[1]
#define NPARIN 2
/* ------------------------------------------------------------
Macros:
------------------------------------------------------------ */
#if !defined(SQR)
#define SQR(x) ((x)*(x))
#endif
#if !defined(MAX)
#define MAX(A, B) ((A) > (B) ? (A) : (B))
#endif
/* --------------------------------------
FLOAT COMPARE: FOR SORTING A FLOAT ARRAY
-------------------------------------- */
typedef int (*COMPFUN)(const void *pa,const void *pb);
#define fsort(vec,n) qsort((void *)(vec), (n), sizeof(double), (COMPFUN) fcmp);
signed char fcmp(const double *a, const double *b)
{
return( (*a > *b) - (*a < *b) );
}
/******** GETDELTA .... THE WIDE NBRHD MEMBERSHIP TEST ********
PURPOSE - THIS ROUTINE COMPUTES THE PROXIMITY MEASURE
WITH RESPECT TO THE WIDE REGION C(THETA). IT KEEPS A
GROWING SUBSET AND A SHRINKING SUPERSET OF T IN A
LINKED LIST, SO THAT THE ITERATIVE CALCULATIONS
ARE MINIMIZED.
INPUT:
vSQR - full n x 1 vector of squared v-space solution.
thetaSQR - Squared parameter of region C(theta).
n - order, i.e. length(vSQR).
OUTPUT:
h, alpha - such that vTAR = (1-alpha)*max(h,v) is the
projection of v onto theta-central region.
RETURNS:
delta - sqrt(r) * norm(vTAR - v) / norm(v), with r := n / theta^2
(i.e., sine measure)
Returns 1e100 if w(j) <= 0 for some j.
WORKING ARRAY
wQ - length n vector of doubles.
****************************************************************/
double getdelta(double *ph, double *palpha, const double *w,
const double thetaSQR, const mwIndex n, double *wQ)
{
double gap,r,h,hSQR,oldhSQR,hubSQR, sumdifv,sumdifw, sumwNT,wj,
deltaSQR,alpha;
mwIndex cardT,cardQ,i,j,STOP;
/* ------------------------------------------------------------
gap = sum(w), r = n / theta^2
------------------------------------------------------------ */
for(i = 0, gap = 0.0; i < n; i++)
gap += w[i];
r = n / thetaSQR;
/* ------------------------------------------------------------
In the following, T is the index set of w[i]'s that are too small,
and Q is the set for which we don't know in the first pass.
However, after sorting wQ=w[Q], we will sort that out too.
------------------------------------------------------------ */
/* ------------------------------------------------------------------
IF THETA == 1, WE HAVE:
h = sqrt(max(w))
sumdifv = sum (h-v_i) = n*h - sum(sqrt(w)), (v := sqrt(w))
sumdifw = sum (h^2-w_i) = n*h^2 - gap.
Use 2 passes to compute sumdifv,sumdifw in stable way.
------------------------------------------------------------------ */
if(1.0 - thetaSQR <= 1E-8){
for(i = 0, hSQR = 0.0; i < n; i++)
hSQR = MAX(hSQR,w[i]);
h = sqrt(hSQR);
sumdifv = 0.0; sumdifw = 0.0;
for(i = 0; i < n; i++){
sumdifw += hSQR - w[i];
sumdifv += h - sqrt(w[i]);
}
}
else{
/* ------------------------------------------------------------
0 < THETA < 1:
LB: hSQR = sumwNT/(r-|T|)
UB: sumwNT/(r-|T| - |Q|) (Q is first stage inconclusive set)
sumdifv = sum_{j in T} (h-v_j)
sumdifw = sum_{j in T} (h-w_j)
Notice that sum(dif) is much stabler than dif(sum).
i : next entry for wQ
------------------------------------------------------------ */
sumwNT = gap;
cardT = 0; sumdifv = 0; sumdifw = 0;
cardQ = n;
i = 0;
hSQR = sumwNT / (r - cardT);
hubSQR = sumwNT / (r-(n-1));
for(j = 0; j < n; j++){
wj = w[j];
if(wj >= hubSQR){ /* wj >= hubSQR ==> not in T */
--cardQ;
hubSQR = sumwNT / (r-cardT-cardQ);
}
else if(wj < hSQR){ /* wj < hSQR ==> in T */
if(wj <= 0.0)
return 1e100; /* error: w should be positive */
++cardT;
mxAssert(cardQ>0,"");
--cardQ;
hubSQR *= 1 - wj/sumwNT;
sumwNT -= wj;
oldhSQR = hSQR;
hSQR = sumwNT / (r - cardT);
sumdifw += (oldhSQR-wj) + cardT * (hSQR-oldhSQR);
sumdifv += (sqrt(oldhSQR)-sqrt(wj))+ cardT*(sqrt(hSQR)-sqrt(oldhSQR));
}
else /* Inconclusive: j in Q */
wQ[i++] = wj;
}
mxAssert(i == cardQ,"");
/* ------------------------------------------------------------
The same treatment for the Q set, but we
sort the (presumably short) wQ first.
------------------------------------------------------------ */
if(cardQ){
fsort(wQ, cardQ);
for(STOP = 0, j = 0; !STOP; ){
wj = wQ[j];
if(wj >= hSQR)
STOP = 1;
else{
++cardT;
sumwNT -= wj;
oldhSQR = hSQR;
hSQR = sumwNT / (r - cardT);
sumdifw += (oldhSQR-wj) + cardT * (hSQR-oldhSQR);
sumdifv += (sqrt(oldhSQR)-sqrt(wj)) +
cardT * (sqrt(hSQR)-sqrt(oldhSQR));
STOP = (cardQ == ++j);
}
}
} /* cardQ > 0 */
/* ------------------------------------------------------------
Let h := sqrt(hSQR)
------------------------------------------------------------ */
h = sqrt(hSQR);
} /* theta != 1 */
/* ------------------------------------------------------------
FOR ALL THETA :
alpha = sumdifv/(r*h)
deltaSQR = r * ( 2*alpha-alpha^2 - (1-alpha)^2 * sumdifw/gap )
(THE ABOVE DIFFERENCE SHOULD NOT BE NUMERICALLY DANGEROUS,
SINCE alpha IS *SIGNIF* BIGGER THAN sumdifw/gap )
------------------------------------------------------------ */
alpha = sumdifv/ (r*h);
deltaSQR = alpha*(2-alpha) - SQR(1-alpha) * sumdifw/gap;
*palpha = alpha;
*ph = h;
return sqrt(r * deltaSQR);
}
/* ============================================================
MAIN: MEXFUNCTION
============================================================ */
/* ************************************************************
PROCEDURE mexFunction - Entry for Matlab
[delta,h,alpha] = iswnbr(vSQR,thetaSQR)
Computes proximity "delta" w.r.t cregion C(theta).
The projection of v onto C(theta) is (1-alpha)*max(h,v).
************************************************************ */
void mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[])
{
mxArray *myplhs[NPAROUT];
double *w,*pdelta,*ph,*palpha, *fwork;
double thetaSQR;
mwIndex i,n;
/* ------------------------------------------------------------
Check for proper number of arguments
------------------------------------------------------------ */
mxAssert(nrhs >= NPARIN, "iswnbr requires more input arguments");
mxAssert(nlhs <= NPAROUT, "iswnbr produces less output arguments");
/* ------------------------------------------------------------
Get input vector w:=vSQR and cregion parameter thetaSQR
------------------------------------------------------------ */
w = mxGetPr(VSQR_IN);
n = mxGetM(VSQR_IN) * mxGetN(VSQR_IN);
thetaSQR = mxGetScalar(THETASQR_IN);
/* ------------------------------------------------------------
Allocate output DELTA, H, ALPHA.
------------------------------------------------------------ */
DELTA_OUT = mxCreateDoubleMatrix((mwSize)1, (mwSize)1, mxREAL);
pdelta = mxGetPr(DELTA_OUT);
H_OUT = mxCreateDoubleMatrix((mwSize)1, (mwSize)1, mxREAL);
ph = mxGetPr(H_OUT);
ALPHA_OUT = mxCreateDoubleMatrix((mwSize)1, (mwSize)1, mxREAL);
palpha = mxGetPr(ALPHA_OUT);
/* ------------------------------------------------------------
Allocate working array fwork(n)
------------------------------------------------------------ */
fwork = (double *) mxCalloc(n,sizeof(double));
/* ------------------------------------------------------------
The actual job is done here:.
------------------------------------------------------------ */
*pdelta = getdelta(ph,palpha, w,thetaSQR,n, fwork);
/* ------------------------------------------------------------
RELEASE WORKING ARRAY.
------------------------------------------------------------ */
mxFree(fwork);
/* ------------------------------------------------------------
Copy requested output parameters (at least 1), release others.
------------------------------------------------------------ */
i = MAX(nlhs, 1);
memcpy(plhs,myplhs, i * sizeof(mxArray *));
for(; i < NPAROUT; i++)
mxDestroyArray(myplhs[i]);
}

Event Timeline

c4science · Help