| |
 |
|
|
Science Forum Index » Math - Numerical Analysis Forum » Conjugate Gradient Algorithm Identification for Quad. Prog.
Page 1 of 1
|
| Author |
Message |
| Guest |
 Posted: Sun Mar 18, 2007 8:00 am |
|
|
|
|
Hi all,
Can anyone identify the algorithm used in the worksheet at this
location:
http://www.stanford.edu/~wfsharpe/ws/ws_styl.htm
Right-Click and select View Source to view the algorithm.
I know that it is a Quad. Prog. agorithm, perhaps something like the
conj. gradient?
function opt_var(x,lbd,ubd,mu) {
// find best variables to add and subtract
var iadd,isub,i,j,numa,muadd,musub,m;
numa = x.length;
m = new Array(2);
// find best variable to add
iadd = 0;
for (i=1;i<=numa;i++) {
if (x[i] < ubd[i]) {
if (iadd == 0) {
iadd = i;
muadd = mu[i];
}
if (iadd > 0) {
if (mu[i] > muadd) {
iadd = i;
muadd = mu[i];
}
}
}
}
// find best variable to subtract
isub = 0;
for (i=1;i<=numa;i++) {
if (x[i] > lbd[i]) {
if (isub == 0) {
isub = i;
musub = mu[i];
}
if (isub > 0) {
if (mu[i] < musub) {
isub = i;
musub = mu[i];
}
}
}
}
m[1] = iadd;
m[2] = isub;
return m;
}
function opt_mu(x,e,cv,rt) {
// computes marginal utilities
var numa,i,j,cp,m;
numa = cv.nrows;
m = new Array(numa);
for (i=1;i<=numa;i++) {
cp = 0;
for (j=1;j<=numa;j++) {
cp = cp + x[j]*cv.cell(i,j);
}
m[i] = e[i] - 2*cp/rt;
}
return m;
}
function opt_styl() {
// performs an optimization for style analysis
// set epsilon for mu difference
eps = 0.001;
// set up needed vectors
num = numa+1;
x = new Array(num);
e = new Array(num);
mu = new Array(num);
cp = new Array(num);
// initialize
for (i=1;i<=num;i++) {
x[i] = init[i];
e[i]= 0;
}
rt = 1;
// loop
done = false;
while (!done) {
// compute marginal utilities
mu = opt_mu(x,e,cv,rt);
// find best variables to add and subtract
m = opt_var(x,lbd,ubd,mu);
iadd = m[1];
isub = m[2];
// tests for completion
// stop if no switch possible
if ( (iadd==0) || (isub==0) ) {
done = true;
} else {
mudiff = mu[iadd] - mu[isub];
if ( mudiff < eps) {
done = true;
}
}
// make change
if ( !done ) {
// compute step size
dd = cv.cell(iadd,iadd) - 2*cv.cell(iadd,isub) +
cv.cell(isub,isub);
delta = mudiff/(2*dd/rt);
if ( (x[iadd]+delta) > ubd[iadd]) {
delta = ubd[iadd] - x[iadd];
}
if ( (x[isub]-delta) < lbd[isub]) {
delta = x[isub] - lbd[isub];
}
// change values
x[iadd] = x[iadd] + delta;
x[isub] = x[isub] - delta;
}
}
// end loop
return x;
} |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Tue Oct 07, 2008 5:29 am
|
|