"ビーム群により送達される放射線量を最適化する方法であって、各ビームは、粒子線治療ビームであり、該方法は、前記ビーム群のモデルおよび標的線量を提供するステップと、前記モデルから、グラム行列を含む、通常形態のモデルおよび標的線量を決定するステップと、前記標的線量をサブサンプリングして、前記ビーム群の初期強度値を決定し、収束するまで、以下のステップ:非常に小さな正の値0<ε<<1を各強度値に加算して前記強度値がゼロよりも大きいことを保証する、加算するステップ、強度値のベクトルに前記グラム行列を乗算して積を求める、乗算するステップ、要素毎に、前記積を除算して標的線量形態にし、対応する比率を求める、除算するステップ、および前記比率が、数値許容誤差内ですべて1に近いか否かを判断し、真の場合、前記ビーム群の前記強度値を出力し、そうではなく、偽の場合、次の繰り返しの前に、前記強度値に前記比率を乗算する、判断するステップ、を繰り返す、サブサンプリングするステップと、を含む、ビーム群により送達される放射線量を最適化する方法。前記グラム行列の各要素は、ビーム対毎に、該ビーム対により送達される前記放射線量の内積を表す、請求項1に記載の方法。可能な限り、前記グラム行列を分解して、外積にし、該外積の係数を前記ビーム群の前記強度値に直接適用する、分解するステップをさらに含む、請求項1に記載の方法。矩形の部分領域内の線量値が欠けることに関して、前記比率の分母に、追加のペナルティを表す補助行列-ベクトル積を追加することにより、前記放射線量の誤差を前記標的線量の前記部分領域に縮小するステップをさらに含む、請求項1に記載の方法。前記比率の分子に、ハード放射線制約を確保する潜在価格を表す補助行列-ベクトル積を追加することにより、ハード放射線制約を前記放射線量の任意の部分領域に対して課すステップをさらに含む、請求項1に記載の方法。前記標的線量に対して規定される制約毎の潜在価格を計算するために、前記モデルを双対形態にし、該双対モデルにサブサンプリングステップを適用するステップをさらに含む、請求項1に記載の方法。ビーム群により送達される放射線量を最適化する装置であって、各ビームは粒子線治療ビームであり、該装置は、前記ビーム群のモデルおよび標的線量を提供する手段と、前記モデルから、グラム行列を含む、通常形態のモデルおよび標的線量を決定する手段と、前記標的線量をサブサンプリングする手段であって、前記ビーム群の初期強度値を決定し、収束するまで、以下のステップ:非常に小さな正の値0<ε<<1を各強度値に加算し、前記強度値がゼロよりも大きいことを保証する、加算するステップ、強度値のベクトルに前記グラム行列を乗算し、積を求める、乗算するステップ、要素毎に、前記積を除算し、標的線量形態にし、対応する比率を求める、除算するステップ、および前記比率が、数値許容誤差内ですべて1に近いか否かを判断し、真の場合、前記ビーム群の前記強度値を出力し、そうではなく、偽の場合、次の繰り返しの前に、前記強度値に前記比率を乗算する、判断するステップ、を繰り返す、サブサンプリングする手段と、を備える、ビーム群により送達される放射線量を最適化する装置。前記グラム行列の各要素は、ビーム対毎に、該ビーム対により送達される前記放射線量の内積を表す、請求項7に記載の装置。可能な限り、前記グラム行列を分解して、外積にし、該外積の係数を前記ビーム群の前記強度値に直接適用する、分解する手段をさらに備える、請求項7に記載の装置。矩形の部分領域内の線量値が欠けることに関して、前記比率の分母に、追加のペナルティを表す補助行列-ベクトル積を追加することにより、前記放射線量の誤差を前記標的線量の前記部分領域に縮小する手段をさらに備える、請求項7に記載の装置。前記比率の分子に、ハード放射線制約を確保する潜在価格を表す補助行列-ベクトル積を追加することにより、ハード放射線制約を前記放射線量の任意の部分領域に対して課す手段をさらに備える、請求項7に記載の装置。前記モデルを双対形態にし、該双対モデルにサブサンプリングステップを適用して、前記標的線量に対して規定される制約毎の潜在価格を計算する、双対形態にし、適用する手段をさらに備える、請求項7に記載の装置。[発明の効果]本発明の実施の形態は、二次計画法QPを用いて、放射線治療の粒子線を最適化する極めて大きく複雑な問題を解く。QPは、ネットワーク最適化、機械学習、物流、制御、および他の多くの用途に広く普及している。QPは、負になり得ない、多くの場合にジュール、時間、または金銭で示される数量を推定する場合に特に有用である。QPを解く方法は、第二次世界大戦から集中的に開発され、少なくとも1つのノーベル賞がその分野の研究に結びついているHarryMarkowitz-1990。近年、強力な方法の大きなコレクションがあるが、問題のサイズは、手に負えなくなっている。本発明は、線形率収束を用いて、線形時間、線形空間内でQPを解く新しく非常に簡易な不動点を提供する。これは、QPが>104個の変数および>106個の制約を有することができる粒子線の最適化に対して特に有用であることがわかる。不動点は、その簡易性に起因して、非常に高速であり、並列化可能である。従来技術によるQPでは、問題を解くために数時間を要した。本明細書に記載の方法は、ビデオフレームレートで問題を解くことができる。本発明について、好ましい実施形態の例として説明したが、他の様々な適合および変更を、本発明の趣旨および範囲内で行うことができることを理解されたい。したがって、添付の特許請求の目的は、本発明の真の趣旨および範囲内にあるすべての変形および変更を包含することである。本発明の実施の形態は、粒子線治療ビームの二乗誤差最適性および非負性荷重を保証するかなり高速の方法を提供する。ペンシルビーム治療の場合、約n~106個のボクセルがあり、m~104個のビームがある。その結果、計算時間は、大方、ボクセル数によって決まり、ボクセルに基づく計算を最小化するように、問題を再公式化することが望ましい。方法のステップは、当該技術分野において既知のメモリおよび入出力インタフェースに接続されたプロセッサで実行することができる。また、ステップに対応する手段もプロセッサ内で実行することができる。したがって、本発明による装置は、手段で構成される。図1に示されるように、方法への入力は、ビームモデル101、標的線量102、および危険に曝されている臓器OAR103の位置を含む。第1のステップ110は、正規化モデルおよび非正規化標的線量を決定する。ビームモデルのグラム行列が事前に決定される115。ただし、Tは、転置演算子である。次に、同じ変換を標的線量に適用して、を取得する。内積空間内のベクトル群のグラム行列は、内積のエルミート行列である。標的線量がサブサンプリングされて120、ビーム群に対する初期強度値が決定される。ここでは、不等式制約は、無視される。目的関数は、制約なしの最小二乗LS問題として書き換えられ、これは、元のLSIよりも2桁小さい。通常の形態では、数値精度がいくらか失われているが、これは、線量行列Aの疎性により軽減されることに留意されたい。制約のない最小二乗問題は、ハード不等式制約Ax≒bをソフト二乗誤差制約Ax≧bで置換する。この問題は、非負でありA,b≧0、過制約であるn>>mため、LS最適解は、2つの欠点を有する:いくつかのLS最適ビーム荷重は、かなり負になりXi<0、いくつかのボクセルは、線量不足になるAix<bi。本発明による方法は、負のビーム荷重という第1の問題を完全になくす。非負最小二乗NNLS問題が与えられる場合、とする。乗法更新130は、任意の正のhおよび正の確定したQについて、任意の正の荷重ベクトルx>0から最適に収束する縮小である。この式は、xの各要素を、勾配に関連する比率で乗算する。実際には、収束は、すべての乗数が、数値許容誤差内で1に等しい場合に達成される150。この場合、真であれば、ビーム群の強度値が出力される160。そうではなく、偽の場合、強度値は、次の反復前に結果を乗算される170。線量最適化の状況では、であり、したがって、反復を単一の行列-ベクトル積に簡単化することができ、その場合、ビーム荷重毎に乗算130および除算140を行い、粒度の細かい並列化を受け入れるようにする。反復のコストは、グラム行列Q内の非ゼロエントリの数により支配され、非ゼロの数は、消失しない重複を有するビーム対の数である。線量不足の第2の問題は、最小二乗解が誤差を平滑に分散させ、その結果、治療すべき組織体積の境界上のボクセルが、健康な組織に対応する隣接ボクセルへの線量過剰を最小に抑える一手段として、線量不足になるために生じる。式2.2のNNLS問題の場合、線量不足の回避は、単なるソフト制約である。問題を解くことを根本的に難しくすることなく、その制約を強化するいくつかのヒューリスティックがある。1Qにを追加することにより、治療すべきボクセルへの線量の分散に明示的にペナルティを課す。ただし、Sは、これらのボクセルを選択する二値行列であり、Iは、恒等行列であり、1は、すべて1の行列であり、tは、そのようなボクセルの数であり、τは、分散に対して線量誤差を平衡させる加重項である。2境界ボクセルでの線量誤差が、その他の場所よりもはるかに重くペナルティが課されるように、二乗誤差の和を再加重し、同様に、治療体積外部のボクセルの重みを軽くする。すなわち、あるボクセル誤差加重ベクトルwおよび集合がある。3下式であり、4ビームの減衰プロファイルに減衰がおおよそ一致する、正の値のスカートにより囲まれた標的組織体積を変更する。厳密解線量不足の回避が、ハード制約として設定される場合、問題は、ボクセル線量の非常に広い空間内での計算を設定するとともに、ランクが不十分な行列とともに動作することが必要になり、これらの条件は、両方とも、反復ソルバの収束を遅くさせるため、はるかに厄介になる。他方、ヒューリスティックは必要ない。このセクションでは、線量不足がないことを保証し、乗法更新を介して解を提供する元のLSI/QPの再公式化を考慮する。合計線量の最小化線量不足禁止制約nounderdoseconstraintを受ける合計線量∥Ax∥1を最小化することが望ましい場合がある。一般性を失うことなく、非負のAは、単位列和を有するため、∥Ax∥1=∥x∥1である。∥x∥2≧∥x∥1であるため、合計線量の上限を以下の最小距離問題LDPにおいて最小化することができ、これは、等価のNNLS形態を有することがわかっており、等価のNNLS形態は、NNLS反復を介して解くことができる。LDPおよびNNLSの最適は、元の制約に矛盾がない場合、によって関係付けられ、そうでない場合、右辺はゼロである。このLDPでは、目的∥x∥2がより平滑な解を好むため、式1.2の元のQPよりも大きな線量過剰が可能なことに留意されたい。また、LDPは、非常に大きく、dimudimv=ボクセル未知のビームである。しかし、これでは、速度のために行列Aの疎性を利用することができない。LSIを回転させてLDS形態にする元のLSIは、となるように、変数をzに変更することにより、僅かにより複雑なLDPに変換することによって、厳密に解くことができる。次に、LSIは、等価のLDPとして書き換えることができる。Aの薄いQR分解は、UR=Aであり、ただし、Uはユニタリであり、Rは対角上で上三角かつ非負である。QPは、L2ノルムを保持した状態で変数を変更して書き換えられて、最小を取得し、であり、†は、疑似逆を示す。対応するNNLSは、であり、最適は、によって関係付けられ、このときである。対応する乗法更新は、線量不足なし、負の荷重なし、かつ最小二乗和線量過剰で線量問題を解く。しかし、前のLDP/NNLSが疎であったのに対して、このNNLSは、密であり、反復毎にかなり多くの更なる計算が必要とされる。また、問題が2回変換されることによる精度の損失もある。QP双対を解く厳密な凸二次計画が主形態で与えられる場合、二次計画のラグランジュ双対は、の形態をとり、である。主最適および双対最適は、によって関係付けられ、双対は、NNLS反復により解くことができる。x≧0が、制約Ax≧bに明示的に符号化されない限り保証されないことに留意されたい。これを式1.2の線量最適化LSI/QPに対して特殊化するために、およびを設定し、を解く。ここで、制約x≧0を組み込むためにおよびである。逆数ATA-1は、上述した畳み込み分解を用いて効率的に計算することができる。ATAの条件付けが不十分である可能性が高いため、注意しなければならない。反復を介して縮小した主QPを解く放射線量の誤差は、矩形の部分領域内の線量値が欠けることに関して、比率の分母に、追加のペナルティを表す補助行列-ベクトル積を追加することにより、標的線量の部分領域に縮小される。特に、元のQPの制約群を、k≦2mボクセルでのみ、例えば、境界上にあり、ビーム中心から最も離れたボクセルでのみ、線量不足を禁止するように制限することを考える。非負のQ、h、A、bを有する制限付きQPおよびすべてのi、Qij>0、hi>0について、補助行列-ベクトル積が提供され、ただし、b’’は、k個の制約付きボクセルに対応するbの部分集合であり、A’’は、線量行列Aの行の対応する部分集合である。補助行列-ベクトル積は、潜在価格shadowpriceとしても知られる双対変数を制約し、この変数は、制約が有効な場合には解において正であり、その他の場合はゼロである。本明細書でのような制約付き最適化では、潜在価格は、1単位だけ制約を緩和することにより得られる最適問題の最適解の目的値の変更を表す。この方法は、ハード制約を任意のボクセル群に対する最大累積線量または最小累積線量に対して課すためにも用いることができる。λの更新は、λに関するラグランジアンの勾配に沿って小さなステップに変更することができる。反復の計算詳細乗法反復手順は、線形複雑性を有し、正円錐内の任意の箇所から線形率で収束する。一定数の精度ビットが、各反復で得られる。乗法更新は、すべての非負制約が暗黙的に強制されるという利点を有する。しかし、数値誤差が、非常に小さな強度値をゼロに丸め、その後、強度がゼロ境界に固定されたままである場合もある。したがって、ステップ130において、非常に小さな正の値0<ε<<1が各強度値に加算されて、乗算前に正の強度値を生成する。これにより、反復は、ゼロ境界を免れる。変数毎の更新は、メッセージパッシングプロシージャとしてベクトルに並行して実行することができるか、または逐次実行することができ、この場合、ビーム荷重Xiの更新は、Qij≠0である場合には、常に、荷重Xjの更新から利益を受ける。この結果、収束がいくらか高速になる。この用途では、±2.5の誤差の線量を施すことが珍しくないため、早期終了が推奨され、したがって、7ビットを越えるビーム荷重xのいかなる精度も無駄になる。線量最適化の計算詳細可分畳み込みseparableconvolution行列Q=ATAの形成は、通常、これらの方式の中で最も時間のかかる演算である。多くの場合、その全体を回避することができる。鍵となる洞察は、Qijが2つのビームの内積であり、したがって、畳み込みにより計算することができることである。これを可能な限り単純なビームモデルにおいて利用することができる。ビームは、標準偏差σを有するxy平面ガウス関数と、zでのブラッグ曲線との外積である。結果として、p、q、rだけずれた2つのビームの3D畳み込みは、1D畳み込みの外積に分解される。上記式において、は単純にの逆数である。したがって、行列Qのエントリは、自動畳み込みブラッグ曲線と2つの1Dガウス関数との外積である。この構造を利用して、恒等式の再形成を介してxに対するQの動作を高速で求めることができる。この恒等式を外積毎に1回用いることにより、行の係数BG2だけ、すなわち、平面内のビームスポットの数だけ、スカラー乗算の総数が低減される。利点として、xyzボクセルの体積の場合、ベクトルQB、QG、QG内のxyz個のみのエントリが、グラム行列Q内のxyz2個のエントリに代えて用いられる。同じ論理により、1Dガウス関数を用いてx軸およびy軸に沿って3D標的線量bを逐次畳み込み、次に、ブラッグ曲線を用いてz軸に沿って逐次畳み込むことにより、ベクトルh=Atbを効率的に形成することができる。有界領域内の加重誤差ガウス畳み込みが、有限xy平面全体に広がり、これが、1があらゆる箇所での最小二乗誤差であることを暗示することに留意する。標的線量は、略あらゆる箇所で暗黙的にゼロであるため、有限の広がりは、標的の境界での減衰に寄与する。この寄与は、無視できるほどに小さく見えるが、場合によっては、その積分は、ある小さな体積を有界とする。ただし、Φは、誤差関数である。ここでも、これは非負の外積である。加重誤差放射線量の誤差は、矩形の部分領域内の線量値が欠けることに関して、比率の分母に、追加のペナルティを表す仕様にない補助的な加重誤差セクション行列-ベクトル積の第2の式を追加することにより、部分領域に縮小される。グラム行列Qの有界形態は、加重二乗誤差を最小化する場合に有用になる。通常の形態と共に動作するには、加重積は、である。不都合なことに、wの大半の選択が、構造体Qへの外積分解の使用を回避する。しかし、いくつかの有用な場合、加重されたQを2つの行列に分けることにより、外積を得ることができる。例えば、wi=c>1により、ある境界ボックス、例えば、危険に曝されている臓器の周囲の境界ボックスを均一に過度に加重することにより、第2の被加数は、単純に、上述したように、C2-1を乗算される有界積分Q行列である。小数の個々のピクセルを過度に加重するために、とする。そして、W’がdiagw’の非ゼロ列を含むものとすると、第2の被加数は、として書くことができる。の列は、hと同じ方法で事前に計算することができ、xに対するその動作は、として最も効率的に計算される。外積乗算、xに対する2つの被加数の動作、および和を用いるために、結果が別個に求められることに留意されたい。[発明の効果]本発明の実施の形態は、二次計画法QPを用いて、放射線治療の粒子線を最適化する極めて大きく複雑な問題を解く。QPは、ネットワーク最適化、機械学習、物流、制御、および他の多くの用途に広く普及している。QPは、負になり得ない、多くの場合にジュール、時間、または金銭で示される数量を推定する場合に特に有用である。QPを解く方法は、第二次世界大戦から集中的に開発され、少なくとも1つのノーベル賞がその分野の研究に結びついているHarryMarkowitz-1990。近年、強力な方法の大きなコレクションがあるが、問題のサイズは、手に負えなくなっている。本発明は、線形率収束を用いて、線形時間、線形空間内でQPを解く新しく非常に簡易な不動点を提供する。これは、QPが>104個の変数および>106個の制約を有することができる粒子線の最適化に対して特に有用であることがわかる。不動点は、その簡易性に起因して、非常に高速であり、並列化可能である。従来技術によるQPでは、問題を解くために数時間を要した。本明細書に記載の方法は、ビデオフレームレートで問題を解くことができる。本発明について、好ましい実施形態の例として説明したが、他の様々な適合および変更を、本発明の趣旨および範囲内で行うことができることを理解されたい。したがって、添付の特許請求の目的は、本発明の真の趣旨および範囲内にあるすべての変形および変更を包含することである。"