多変数離散関数の最適化問題？

質問

信号処理で以下のような状況に行き当たったのですが、最適化数学の知識に乏しく、
取っ掛かりもつかめませんので、ご存知の方がおられましたらよろしくお願いします。

音声データなど１次元のn個の時系列データ fk(0≦k≦n-1:k整数)があるとします。

これらの時系列データはそれぞれ定義域がことなり、

時系列データ/定義域
f0 a0≦x≦b0
f1 a1≦x≦b1
f2 a2≦x≦b3
　　(以下同様)

のようになっていますが、それぞれの定義域はオーバーラップしながら増加して
います。つまり

a0＜a1＜b0＜b1
a1＜a2＜b1＜b2
　　(以下同様)

のような関係にあります。

このような状況において、各自系列データから１点ずつデータを選びその合計値を
最小化したいのです。このときデータの選び方に制約をつけます。

f0からx0を選び、f1からx1を選び、f2からx2を選び・・・、としたときに、x0<x1<x2...
となるように選びます。（定義域がオーバーラップしているので、制約をつけないと
逆転する可能性があります。）まとめると

目的関数：Σfk[xk]
制約条件：x0＜x1＜x2.....＜xn-1

の最適化問題になります。

各時系列の最小値を求めて、制約条件に合うように適当に解を修正していけば、
「それっぽい」ものは求まりそうですが、あまりにも無策な感じがします。

- 理想解を求めることは不可能
- 理想解を求めることは可能だが、現実的な時間では不可能
（nは数百オーダーです）
- 近似解は「○○」のアルゴリズムで求めることができる
- このキーワードを調べれば何かわかるかも
- この本　or webサイトで勉強しなさい

などご存知の方、よろしくお願いします。

回答No.1

ramayana

fkがどういうデータなのか（あるいはどういう関数なのか）、nがどれくらいの大きさなのか、というのがもう少し詳しく分からないと、雲をつかむような話なのですが…。

見当違いかもしれませんが、例えば、y0 = x0、y1 = x1 - x0、y2 = x2 - x1、…、yn = xn - yn-1と変数変換して、目的関数をy0、y1、…、ynであらわすと、制約条件がy1>0、y2>0…、yn>0となって、扱いやすくなることはありませんか？

補足

ramayana様、ご回答ありがとうございます。

質問にも書かせていただきましたが、nは”数百オーダー”です。fkは音声データ(PCM)を
念頭においておりますので、例えば48kHzでサンプリングされた16bit量子化データになります。

変数変換については、仰るとおり式上はとてもすっきりしますね。ただ

- 時系列データf0上のあるポイントx0
- 時系列データf1上のあるポイントx1
- 時系列データf2上のあるポイントx2
・・・

のように定義していますが、変数変換によってfkをどのように扱えばいいのか
よくわかりませんでした。

また仮に変数変換したとしても、最終的には多変数の離散関数の最適化には
なりますので、引き続き何かアドバイスがありましたらよろしくお願いします。