技術要約：非凸QCQPのためのジョイント・レンジ不等式

問題設定

本論文は、混合整数非線形計画問題（MINLP）の中核となるクラスである、非凸二次制約付き二次計画問題（QCQP）に対して、効果的な切除平面（cutting planes）を生成するという課題に取り組んでいる。RLT（Reformulation-Linearization-Technique）や、Shorの緩和に代表される半正定値計画法（SDP）緩和などの標準的な緩和手法は、凸近似を提供するものの、タイトネス（緊密さ）とスパース性の間でトレードオフが生じることが多い。具体的には、固有値再定式化や高密度なSDP制約は、元のQCQPのスパース性を破壊してしまうため、MINLPソルバーへの統合が困難で計算コストの高いカットを招く。著者らは、元のQCQP定式化のスパース性を維持しつつ、非凸な幾何学的構造を利用して、強力かつ妥当な不等式を導出するためのフレームワークを追求している。

手法：射影・リフト（Project-Then-Lift）アプローチ

著者らは、混合整数線形計画法（MILP）で使用される混合整数丸め（MIR）不等式に着想を得た「射影・リフト」戦略を提案している。その手法は以下の通りである。

1. 基本不等式と射影：
   拡張されたQCQP定式化（変数 $x$ とリフトされた行列 $X$ を含む）に対する2つの基本有効不等式から出発し、著者らはこれらの不等式を2次元の像空間へと射影するアフィン写像 $A_{JR}$ を定義する。基本不等式を $\phi_i + \langle \Theta_i, X \rangle + \theta_i^\top x \geq 0$ ($i=1,2$) とする。この射影は、実行可能な $(X, x)$ のペアを、各不等式の左辺に対応するベクトル $y = (y_1, y_2)$ へと写像する。

2. ジョイント・レンジ解析：
   手法の核心は、基本不等式に関連する2つの二次関数 $f_1(x)$ と $f_2(x)$ のジョイント・レンジ（共同範囲） $F(\mathbb{R}^n)$ の解析にある。射影された実行可能点の集合は、このジョイント・レンジと、基本不等式によって定義される単体錐 $K_{JR}$ との交わりである。

   • 非凸ケース： 著者らは、ジョイント・レンジが非凸である場合の閉凸包を特徴付けている。特定の条件（二次部分の線形従属性）の下で、ジョイント・レンジは放物面のボウル状の境界やその外部といった、明示的な非凸形式をとることを示している。
   • 凸ケース： ジョイント・レンジが凸である場合、彼らは半正定値計画法（SDP）による表現を提供する。

3. 包絡（Hull）の特性付けと不等式の導出：
   著者らは、射影された集合の凸包（$H_{JR} = \text{cl}(\text{conv}(F(\mathbb{R}^n) \cap K_{JR}))$）の閉形式による記述を導出している。

   • 非凸ケースでは、凸包は単体錐と放物面ボウル（またはその補集合）との交わりとして記述され、多くの場合、錐のレイ（光線）が非凸集合から脱出する点によって定義される「割線（secant）カット（交差カット）」となる。
   • 凸ケースでは、凸包は支持関数を介して記述され、SDP制約付きの分離問題へと導かれる。

4. リフトとスパース性の維持：
   2次元の像空間で導出された有効な不等式は、アフィン写像の逆写像を用いて元の $(X, x)$ 空間へとリフトされる。極めて重要な点は、射影がわずか2つの基本不等式に基づいているため、得られるリフトされた不等式は、それらの基本不等式のスパース性（サポート）を継承することである。これにより、フルSDP緩和に伴う密度の問題が回避される。

5. セカント混合ジョイント・レンジ不等式：
   MIRの概念を拡張し、著者らは「セカント混合ジョイント・レンジ不等式」を導入している。これらは、基本不等式から「混合」項（分数線形結合または連続変数）を抽出することで、非凸の放物条件を満たすコアとなるペアを形成する。これにより、MIRがMILPにおける分数項を扱うのと同様に、より複雑な構造を扱うことが可能になる。

主な貢献

• 閉形式の凸包： 本論文は、単体錐と2つの二次関数の非凸ジョイント・レンジとの交わりに関する、完全な閉形式による凸包の特性付けを提供している。これには、様々な構成（例：頂点が放物面ボウルの内部/外部にある場合、回帰レイなど）に対する明示的な幾何学的記述が含まれる。
• 新しいカット・ファミリー： 著者らは、ジョイント・レンジ不等式およびセカント混合ジョイント・レンジ不等式を導入した。これらは拡張されたQCQP定式化に対して有効であり、2次元の射影空間における交差カットを通じて導出される。
• スパース性の維持： 標準的なSDPベースのカットとは異 달리、提案された不等式はスパースである。各リフトされた不等式のサポートは、それを生成するために使用された2つの基本不等式のサポートによって厳密に制御されている。
• 凸ケースにおけるSDP表現： 凸ジョイント・レンジの場合、著者らはShorのSDP緩和をスパースな経路で線形化するための半正定値表現を提供する。
• アルゴリズムによる分類： ジョイント・レンジを凸か非凸か分類し、その具体的な幾何学的形状（放物境界、実体領域、または穿孔平面など）を決定するためのアルゴリズムが提示されている。

結果

本論文では、提案されたジョイント・レンジ不等式の強さを、標準的な第1レベルRLT緩和と比較する予備的な幾何学的実験の結果を報告している。

• 指標： 強さは、射影されたRLT緩和の面積と、ジョイント・レンジの凸包との交差面積の比率によって測定される。この比率が低いほど、より強力なカット（面積の減少が大きい）であることを示す。
• 知見：
  • ジョイント・レンジが完全に錐の内部に含まれる「アンクリップ（unclipped）」ケースでは、カットによる追加の減少は得られない（比率 = 1）。
  • 非自明な非凸ケース（例：「Chord-Truncated Bowl」および「Ray-Truncated Bowl」）において、ジョイント・レンジの凸包は射影面積を大幅に減少させた。異なる次元と構成における面積比のシフト幾何平均は、約0.108から0.490の範囲であった。
  • 凸ジョイント・レンジのケース（Case 7）においても、大幅な面積減少（比率 0.219 から 0.403 の間）が示された。
  • これらの結果は、提案されたアプローチがRLTを介して構築された射影緩和を大幅にタイトにできることを示唆している。

意義と主張

著者らは、本研究が、交差カットの幾何学的な強さと、MINLPソルバーにおける計算上の必要性であるスパース性の間の溝を埋めるものであると主張している。

• 幾何学と次元の分離： 主要な意義は、困難な幾何学的ステップ（非凸性の処理）を、周囲の次元から切り離したことにある。複雑な幾何学は、閉形式の解が存在する低次元（2次元）空間で解決されるが、最終的なカットは元の高次元空間においてスパースなままである。
• 非凸性の活用： このフレームワークは、「隠れた凸性」（Sレマなど）や標準的な凸緩和のみに依存する手法では到達できない、非凸なジョイント・レンジを明示的に露出し、活用するものである。
• MIRの一般化： このアプローチは、MIR不等式の成功した「射影・リフト」パラダイムを非線形QCQP領域へと一般化し、高密度の行列制約を必要とせずに強力なカットを生成するメカニズムを提供する。
• 今後の方向性： 著者らは、完全なMINLPソルバー内での体系的な研究は現在の範囲を超えていると控えめに述べている。彼らは、効果的な基本不等式のペアを選択する自動化を今後の主要な研究方向として挙げており、MIRの分離で使用されるものと同様のヒューリスティックを適応して、必要な非凸幾何学を誘発するように二次係数を「整列（align）」させることを示唆している。