単調増加の検出と比較（６）Isotonic programmingとquadratic programming(２次計画)について

単調増加の検出と比較の目次
２次計画問題は、最適化問題(こちら)のうちの一つで、目的関数が2次式で定義され、制約条件の集合が一次等式と一次不等式とを合わせたものによって定義されているもの
isotonic programming は前の記事で書いたように
- $min(\sum_{i=1}^N w_i (x_i-a_i)^2);x_i \ge x_j; \forall (i,j) \in E$ なるN個の実数集合 $X=\{x_i\};i=1,2,...,N$ を見つけることであるから
２次計画問題であることがわかる
ちなみに、半順序ではなく、全順序であるときには、制約がきつくなるので、より速く最適化をする方法が知られており、それ(その一つ)が pool adjacent violators algorithm (PAVA)である。
最小化したいのは
- $f(X=(x_1,...,x_n))=\sum_{i=1}^n w_i (x_i-a_i)^2=\sum_{i=1}^n w_i x_i^2 -2\sum_{i=1}^n w_ia_ix_i + \sum_{i=1}^n w_i a_i^2$
- を最小化することに同じ
  - ただし $W$ は $(w_i)$ を対角成分とする対角行列で、 $C=-(w_i a_i)$
これは、二次計画問題の最小化するべき関数の「一般表現 $f(x)=\frac{1}{2}x^T W x +C^T x$ になっている
$X$ の制約はどうだろうか？
$x_i \ge x_j$ は $(-1) \times x_i + 1 \times x_j \le 0$ なので
なる連立不等式が満足されるべきであり、ここで言うはからへのエッジに対してとなるような行列
- 全順序の場合には

N<-5

Q<-matrix(0,N-1,N)
for(i in 1:(N-1)){
	Q[i,i]<-1
	Q[i,i+1]<--1
}
Q

> Q
     [,1] [,2] [,3] [,4] [,5]
[1,]    1   -1    0    0    0
[2,]    0    1   -1    0    0
[3,]    0    0    1   -1    0
[4,]    0    0    0    1   -1

基準曲線が１つあって、それより下に来る曲線が複数あるときの制約条件行列は

N<-4
M<-3

D<-matrix(0,N,M)
D[,1]<-sort(runif(N),decreasing=TRUE)+1

for(i in 2:M){
	k<-0.2
	D[1,i]<-D[1,1]*(runif(1)*k+(1-k))
	for(j in 2:N){
		D[j,i]<-min(D[j-1,i],D[j,1])*(runif(1)*k+(1-k))
	}
}

matplot(D,type="b",pch=15)

for(i in 1:N){
	for(j in 2:M){
		segments(i,D[i,1],i,D[i,j],col=1+j)
	}
	
}

Q<-NULL
for(j in 1:M){
	for(i in 1:(N-1)){
	
		st<-(j-1)*N + i
		end<-st+1
		tmp<-rep(0,N*M)
		tmp[st]<--1
		tmp[end]<-1
		Q<-rbind(Q,tmp)
	}
}
for(i in 2:M){
	for(j in 1:N){
		st<-j
		end<-N*(i-1)+j
		tmp<-rep(0,N*M)
		tmp[st]<--1
		tmp[end]<-1
		Q<-rbind(Q,tmp)
	}
}
Q

> Q
    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
tmp   -1    1    0    0    0    0    0    0    0     0     0     0
tmp    0   -1    1    0    0    0    0    0    0     0     0     0
tmp    0    0   -1    1    0    0    0    0    0     0     0     0
tmp    0    0    0    0   -1    1    0    0    0     0     0     0
tmp    0    0    0    0    0   -1    1    0    0     0     0     0
tmp    0    0    0    0    0    0   -1    1    0     0     0     0
tmp    0    0    0    0    0    0    0    0   -1     1     0     0
tmp    0    0    0    0    0    0    0    0    0    -1     1     0
tmp    0    0    0    0    0    0    0    0    0     0    -1     1
tmp   -1    0    0    0    1    0    0    0    0     0     0     0
tmp    0   -1    0    0    0    1    0    0    0     0     0     0
tmp    0    0   -1    0    0    0    1    0    0     0     0     0
tmp    0    0    0   -1    0    0    0    1    0     0     0     0
tmp   -1    0    0    0    0    0    0    0    1     0     0     0
tmp    0   -1    0    0    0    0    0    0    0     1     0     0
tmp    0    0   -1    0    0    0    0    0    0     0     1     0
tmp    0    0    0   -1    0    0    0    0    0     0     0     1