next up previous
: この文書について... : 内点法 : ショートステップパス追跡法のサンプルプログラム


ロングステップパス追跡法のサンプルプログラム

以下に, Scilabによるロングステップパス追跡法ののサンプルプログラムを示す. 使い方はショートステップパス追跡法のプログラムと同様である. $ \sigma_{\min}$, $ \sigma_{\max}$, $ \gamma$はプログラム中では それぞれsmin, smax, gmmaと標記され, 値はそれぞれ$ 0.001$, $ 0.999$, $ 1e-5$である. $ \sigma$(プログラム中ではsigma)の決定には乱数を用いている.

//Long Step Path Following Algorithm
SMALL=1e-8; //Accuracy parameter
smin=0.001;
smax=0.999;
gmma=1e-5;
stacksize(1000000);

//---A,b,c (canonical form) should be specified here---
//Below is the example of minimizing x_1+...+x_n
// subject to 1 <= x_i <= 2
n=10;
A=[eye(n,n);-eye(n,n)];
b=[ones(n,1);-2*ones(n,1)];
c=ones(n,1);
//---End of the definition of A,b,c---

x0=ones(size(A,2),1);
s0=1 ./ x0;
y0=ones(size(A,1),1);
t0=1 ./ y0;
bb=t0+b-A*x0;
cb=s0-c+A'*y0;
be=1-b'*y0+c'*x0;
M=[zeros(size(A,1),size(A,1))   A       -b      bb;
   -A'  zeros(size(A,2),size(A,2))      c       cb;
    b'          -c'                     0       be;
  -bb'          -cb'                    -be     0];
q=[zeros(1,size(A,1)),zeros(1,size(A,2)),...
   0,size(A,1)+size(A,2)+2]';
x=[y0' x0' 1 1]';

[n,junk]=size(x);
e=ones(n,1);

s=M*x+q;
mu=(s'*x)/n;

while mu>SMALL
  X  = diag(x);
  S  = diag(s);
  sigma=rand()*(smax-smin)+smin;
  p=-S*X*e+mu*sigma*e;
  dx=(S+X*M)\p;
  ds=M*dx;
  d0=0;
  d1=1;
  for i=(1:10)
    alp=((d0+d1)/2);
    xa=x+alp*dx;
    sa=s+alp*ds;
    if( xa.*sa-gmma*mu*ones(n,1) <= 0 )
      # v has negative element: alp is too large
      d1=alp;
    else
      d0=alp;
    end
  end
  x=x+alp*dx;
  s=M*x+q;
  mu=s'*x/n;
end
sol=x(size(A,1)+1:size(A,1)+size(A,2))/...
    x(size(A,1)+size(A,2)+1);
|

Shigeru HANBA 平成25年12月22日