next up previous
: ロングステップパス追跡法のサンプルプログラム : 内点法 : 参考文献


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

以下に, Scilabによるショートステップパス追跡法ののサンプルプログラムを示す. この例では, 制約条件を満たす領域を $ 1 \leq x_i \leq 2$, $ (1 \leq i \leq n)$なる$ n$次の超立方体の内部とし, 目的関数 $ x_1+\cdots+x_n$を最小化する問題を解いている. 変数SMALLは精度パラメータである. 主問題の解は 計算終了時に変数solに代入される. 解くべき問題を変更したいときには, A, b, cの定義を書き換えればよい.

//Short Step Path Following Algorithm
SMALL=1e-8; //Accuracy parameter
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);

sigma=1*(1-0.4/sqrt(n));

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

while mu>SMALL
  X  = diag(x);
  S  = diag(s);
  p=-S*X*e+mu*sigma*e;
  d=(S+X*M)\p;
  x=x+d;
  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日