scipyで離散変数値を持つ関数を最小化する方法

Question

複数の入力変数（24と30の間）を持つターゲット関数を最適化しようとしています。これらの変数は、3つの異なる統計変数のサンプルであり、目標関数値はt検定確率値である。誤差関数は、所望のt検定確率と実際のt検定確率との誤差（差の二乗の和）を表す。私は、3つのt検定のすべてについて、誤差が1e-8未満の解のみを受け入れることができます。

私はscipy.optimize.fminを使用していました。ターゲット関数がゼロになった解決策はたくさんあります。

問題は、変数が0から10.0の間であり、整数であるか、2桁以上の小数部を持たない解を見つける必要があるということです。有効な値の例は0 10 3 5.5 6.8です。無効な値の例：-3 2.23 30または0.16666667

私は目標値が実際の測定データから来ているので、少なくとも1つの解決策があることを知りました。元のデータは失われていて、私の仕事はそれらを見つけることです。しかし、私はどのように知りません。試行錯誤の使用は選択肢ではありません。なぜなら各変数に約100の可能な値があり、変数の数が与えられれば、100 ** 30の数が多すぎます。 fminの使用は素晴らしいですが、慎重な値では機能しません。

これを解決する方法はありますか？解決策を見つけるために何時間もプログラムを実行する必要があるなら、問題はありません。しかし、私は数日以内に約10の目標値の解決策を見つける必要があり、私は新しいアイデアがありません。ここで

は、例えばMWEです：

整数計画と呼ばれ、それがNP困難であるされて何が（私はあなたのセットアップを理解している場合）を実行しようとしている

import math 
import numpy 
import scipy.optimize 
import scipy.stats 
import sys 

def log(s): 
    sys.stdout.write(str(s)) 
    sys.stdout.flush() 

# List of target T values: TAB, TCA, TCB 
TARGETS = numpy.array([ 
    [0.05456834, 0.01510358, 0.15223353 ], # task 1 to solve 
    [0.15891875, 0.0083665,  0.00040262 ], # task 2 to solve 
]) 
MAX_ERR = 1e-10 # Maximum error in T values 
NMIN,NMAX = 8,10 # Number of samples for T probes. Inclusive. 

def fsq(x, t, n): 
    """Returns the differences between the target and the actual values.""" 
    a,b,c = x[0:n],x[n:2*n],x[2*n:3*n] 
    results = numpy.array([ 
     scipy.stats.ttest_rel(a,b)[1], # ab 
     scipy.stats.ttest_rel(c,a)[1], # ca 
     scipy.stats.ttest_rel(c,b)[1] # cb 
    ]) 
    # Sum of squares of diffs 
    return (results - t) 

def f(x, t, n): 
    """This is the target function that needs to be minimized.""" 
    return (fsq(x,t,n)**2).sum() 

def main(): 
    for tidx,t in enumerate(TARGETS): 
     print "=============================================" 
     print "Target %d/%d"%(tidx+1,len(TARGETS)) 
     for n in range(NMIN,NMAX+1): 
      log(" => n=%s "%n) 
      successful = False 
      tries = 0 
      factor = 0.1 
      while not successful: 
       x0 = numpy.random.random(3*n) * factor 
       x = scipy.optimize.fmin(f,x0, [t,n], xtol=MAX_ERR, ftol=MAX_ERR) 
       diffs = fsq(x,t,n) 
       successful = (numpy.abs(diffs)<MAX_ERR).all() 
       if successful: 
        log(" OK, error=[%s,%s,%s]\n"%(diffs[0],diffs[1],diffs[2])) 
        print " SOLUTION FOUND " 
        print x 
       else: 
        tries += 1 
        log(" FAILED, tries=%d\n"%tries) 
        print diffs 
        factor += 0.1 
        if tries>5: 
         print "!!!!!!!!!!!! GIVING UP !!!!!!!!!!!" 
         break 
if __name__ == "__main__": 
    main() 

Answer 1

。 http://en.wikipedia.org/wiki/Integer_programming。私はあなたが整数解を探しているわけではないことを認識していますが、すべての入力を10で掛け、目標関数を100で割り算すると、入力がすべて整数であるという同等の問題が生じます。ポイントは、あなたの入力は離散的です。

あなたが扱っているターゲット関数は凸2次関数であり、[0、10]の区間で実数値入力に対して素早く解く良い制約付き最適化アルゴリズムがあります。これから、近くのすべての許容可能な点を丸めたりチェックしたりすることができますが、nは入力の数です。これを行っても、最適なソリューションがこれらのポイントの1つであるとは保証されません。

整数計画問題の近似アルゴリズムがあり、最適な点に達するのに十分な精度で動作することがあります。私が引用したWikipediaの記事で試してみるべきことのリストがありますが、あなたがこの問題を解決しようと幸せになることはわかりません。