日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

1-A-7

双曲錐の露出性について
05000745 統計数理研究所*ロウレンソ 武流野 フィゲラ
ニューサウスウェールズ大学
モナシュ大学

1.

はじめに

2.

本発表では [5] の概要を述べる. 特に，双曲錐 (hyperbolicity cone) という錐のクラスに関する様々な結果を述べる．
双曲錐を説明するために，まず双曲多項式(hyperbolic polynomial) を定義しておく．p :Rn → R は斉次多項式とする．ある e ∈ Rn に対して，p(e) > 0 かつすべての x に対して一変数多項式

t 7→ p(te − x)(1)が実根のみを持つとき，p は双曲多項式と呼ばれる．(1) の根を λ1 (x), . . . , λr (x) と書く．pと e に関して凸錐

Λ+ (p, e) := {x ∈ Rn | λi (x) ≥ 0, i = 1, . . . , r}.
を定義する．明らかではないが，Λ+ (p, e) は閉凸錐である [2, 7]．Λ+ (p, e) のように表される凸錐は双曲錐と呼ばれる．
例 1. p : Rn → R が p(x) := x1 · · · xn とする．
p は双曲多項式である．e = (1, . . . , 1) とすれ
ば，Λ+ (p, e) が非負象限 Rn+ になる．
例 2. S n は n × n 実対称行列空間とする．p :S n → R が p(X) := det X とする．p は双曲多項式である．I は n × n 単位行列とすれば，Λ+ (p, I) が半正定値行列錐 S+n になる．
本発表では双曲錐の面の構造に関する様々な結果を紹介する．Renegar はすべての双曲錐が露出面錐 (facially exposed) であることを示した [7]．本研究では双曲錐が露出面性より強い性質を持つことを示す．

LOURENÇO Bruno F.
ROSHCHINA Vera
SAUNDERSON James

面と露出性について

ここで，K が閉凸錐とする．次に，F ⊆ Kは閉凸錐とする．条件x, y ∈ K, x + y ∈ F ⇒ x, y ∈ Fが成り立てば，F を K の面という．さらに，もし F が K と K の支持超平面の共通部分として表せる場合，F を露出面 (exposed face) という．K のすべての面が露出面であれば，Kを面露出錐 (facially exposed cone) という．
これから，面露出錐より強い露出性の概念を紹介する．まず，必要な記号を定義する．Rnの内積を h·, ·i で表す．それによって，kxk =√hx, xi というノルムを定義する．C, D が Rnに含まれている集合のとき，C と D の距離を以下のように定義する．

dist (C, D) = inf{kx − yk | x ∈ C, y ∈ D}.
また，span C は C の線型包を表す．K∗ と K⊥はそれぞれ K の双対錐および K の直交補空間を表す．
定義 1 (露出性の概念). F は K の面とする．
(i) P (K) = F を満たす線形射影 P （直交射影と限らない）が存在するとき，F は射影的露出面と呼ばれる．K のすべての面が射影的露出面の場合，K は射影的露出錐 (projectionally exposed cone)[1] と呼ばれる．

(ii) ある κ > 0 に対して
dist (x, F) ≤ κdist (x, K),∀x ∈ span Fが成り立てば，F は恭順面と呼ばれる．
K のすべての面が恭順面の場合，K は恭順錐 (amenable cone)[3] と呼ばれる．

(iii) 等式[4] B. F. Lourenço, V. Roshchina, and
F =K +F ,J. Saunderson. Amenable cones are particularly nice. arXiv e-prints, November
が成り立てば，F はナイス面と呼ばれる．
2020. arXiv:2011.07745.
K のすべての面がナイス面の場合，K はナイス錐 (nice cone)[1, 6] と呼ばれる． [5] B. F. Lourenço, V. Roshchina, and
J. Saunderson. Hyperbolicity cones are
以上の概念の中で次の関係が成り立つ [4].
amenable. arXiv e-prints, February 2021.
射影的露出錐 ⇒ 恭順錐 ⇒ ナイス錐 ⇒ 面露arXiv:2102.06359.
出錐. K の次元が 3 以下の場合，面露出錐 ⇒[6] G. Pataki. The geometry of semideﬁnite
射影的露出錐. また，K の次元が 4 以下の場
programming. In H. Wolkowicz, R. Sai合，恭順錐 ⇒ 射影的露出錐 [4]. しかし，gal, and L. Vandenberghe, editors, Hand ナイスではない面露出錐が存在する [8],book of semideﬁnite programming: theory, 恭順ではないナイス錐が存在する [4]，algorithms, and applications. Kluwer Aca 射影的露出錐ではない恭順錐が存在する
demic Publishers, 2000.
か知らていない（先程の結果によって，こ[7] J. Renegar. Hyperbolic programs, andのような錐が存在すれば，次元が 5 以上
their derivative relaxations. Foundationsである）．
of Computational Mathematics, 6(1):59–
3. 双曲錐と露出性
79, Feb 2006.
次の定理は我々の主な結果である．
[8] V. Roshchina. Facially exposed cones
定理 1. すべての双曲錐が恭順錐である．[5]are not always nice. SIAM J. Optim.,
本発表では定理 1が導かれるための必要な道
24(1):257–268, 2014.
具を紹介し，簡単に証明の概要を述べる．とくに，定理 1を証明するために，双曲錐の面の構造を調べる必要があった．
たとえば，F が双曲錐 Λ+ (p, e) の面の場合，F も双曲錐であるが，双曲多項式多項式 p との関係が明らかではない．F をなす双曲多項式多項式の作り方と p の関係も議論する．
∗∗⊥

参考文献
[1] J. Borwein and H. Wolkowicz. Regularizing the abstract convex program. Journal of Mathematical Analysis and Applications, 83(2):495 – 530, 1981.
[2] L. Gårding. An inequality for hyperbolicpolynomials. Journal of Mathematics andMechanics, 8(6):957–965, 1959.
[3] B. F. Lourenço. Amenable cones: error bounds without constraint qualiﬁcations. Mathematical Programming, 186:1–48, 2021.