錐最適化における 2 乗スラック変数法
Squared Slack Variables Method in Conic Optimization
福嶋 雅夫（京都情報大学院大学）
Masao Fukushima（The Kyoto College of Graduate Studies for Informatics）

Abstract
錐最適化問題は数理最適化における基本的な問題のクラスであり，そのサブクラスである線形計画問題
は実社会の問題解決において最もよく用いられてきた数学問題の一つである。錐最適化問題に対する研究の歴史は長いが，線形計画問題に対する内点法などの効率的解法の開発に伴い，実用面でも新しい応用領域が次々と開拓されている。本稿では錐最適化問題の重要なサブクラスであるいくつかの問題に対して，筆者らが近年行った 2 乗スラック変数法に関する研究を紹介する。
The conic optimization problem is a fundamental class of mathematical optimization problems,and contains the linear programming problem as its subclass, which is well-known as one of the mostpopular mathematical models for solving the real world problems. Although research on conic
optimization has a long history, recent advances in efficient computational methods such as interior
point methods have prompted development of new application areas. This article gives a briefsummary of the recent work of the author and his co-workers on the squared slack variable approachto several important classes of the conic optimization problem.

■ １．はじめに

内点法は大規模な線形計画問題に対する計算効率が

数理最適化あるいは数理計画とは，現実のさまざシンプレックス法を凌ぐという大きなインパクトをまな問題を「いくつかの制約条件のもとで目的関数与えただけでなく，線形計画問題を含む問題のクラと呼ばれる評価尺度を最大化または最小化する」とスである半正定値計画問題や 2 次錐計画問題といっいう形の数理モデルに定式化し，それを問題のタイた重要な応用をもつ凸最適化問題にも内点法の計算

プに応じて開発されたアルゴリズムを用いて解くこ

原理が拡張できることが明らかになった。これによとにより，問題解決に役立つ情報を提供する方法論

り 1990 ～ 2000 年代には数理最適化の様々な応用の体系である。現代の数理最適化の出発点は線形計分野が開拓されていった。その拡張の理論的根拠と画問題に対するシンプレックス法（単体法）や双対なったのは，半正定値計画問題や 2 次錐計画問題に理論など 1940 年代の研究に遡る。1940 年代とい含まれる錐制約が対称錐と呼ばれる凸錐のクラスにえばノイマン型コンピュータが提唱され，プログラ属し，また対称錐はユークリッド的ジョルダン代数

ム内蔵式コンピュータの開発が進められた時代であと呼ばれるベクトル空間と深く関わっていることかり，現在に繋がるコンピュータ社会の夜明けであっら，その性質を用いて統一的な扱いが可能になるとた。その後のコンピュータ技術の目覚ましい進歩という事実であった。

歩調を合わせるように，数理最適化の研究も線形計

錐最適化問題に対しては現在に至るまで様々な研画問題から様々なタイプの非線形最適化問題や組合究が行われているが，本稿では凸性を仮定しない一せ最適化問題に対象を広げ，その適用領域を拡張し般の非線形錐最適化問題に対して筆者らが行った 2ている。

乗スラック変数法に関する一連の研究 [4,5,9,10] の数理最適化の歴史には様々なブレークスルーが存在するが，その一つが線形計画問題に対する新しい

22解法として 1984 年に提案された内点法である [8]。

NAIS Journal

成果を紹介する。

■ ２．錐最適化問題(b) X が 2 次錐の直積集合の場合。
m 次元ベクトル y ＝ ( y0, y1,…, ym-1) を y ＝ ( y0, y-)

標準的な不等式制約付き最適化問題は次のようにそのとき，次式で定義される集合を m 次元 2 次錐表される。
Min f (x)s.t. gi(x) ≥ 0 (i ＝ 1, 2, …, m)-∊ R × Rm-1 と書く。ここで y ＝ ( y1, y2,…, ym-1) である。

(1)

ここで，x は n 次元変数ベクトル (x1, x2,…, xn) ∊ Rn，
f :Rn → R および gi :Rn → R (i ＝ 1, 2, …, m) は十分
滑らかな関数である。
この問題は f が凸関数で，gi がすべて凹関数のとき凸最適化問題あるいは凸計画問題と呼ばれる。特に f と gi がすべて 1 次関数ならば線形計画問題であと呼ぶ。
y) ∊ R × R m-1| y0 ≥∥ -y ∥ }Km ＝ { y ＝ (y0, -ただし，∥・∥はユークリッドノルムを表す。特に1 次元 2 次錐と 2 次元 2 次錐はそれぞれ
K1 ＝ { y ∊ R | y ≥ 0 }

K 2 ＝ { y ＝ (y0, y1) ∊ R × R | y0 ≥ | y1| }であるから，凸多面錐である。一方，m ≥ 3 のときはKm = { y ∊ Rm | y0る。なお，以下の議論は，等式制約を含む問題に対2
2
1 + 2 + ⋯+

2

−1

}

しても自然に拡張できるが，表記の煩雑さを避けるであり，有限個の半空間の共通部分としてあらわす

ため，不等式制約のみを含む場合を考える。
問題 (1) の制約条件は，関数 gi (i ＝ 1, 2, …, m)

ことはできないので凸多面錐ではない。
y0を成分とするベクトル値関数 g :Rn → Rm を用いて
g(x) ∊ R m‌+mと表されることに注意する。ただし，R m‌ は空間 R+の非負象限 { y ∊ Rm|yi ≥ 0 (i ＝ 1, 2, …, m)} である。

ベクトル空間 V の部分集合 X に属する任意のベ
クトル v と任意のスカラー α ≥ 0 に対してαv がまた V に属するとき，X を錐と呼び，凸集合かつ閉集合であるような錐を閉凸錐という。上述の Rm のm
非負象限 R m‌ はm個‌ は閉凸錐である。さらに，R ++の半空間 { y ∊ Rm | yi ≥ 0} (i ＝ 1, 2, …, m) の共通部

y0

y1
m=2

y2

y1
m=3

このように，2 次錐は，凸多面錐の場合（m ＝ 1
または m ＝ 2）とそうでない場合（m ≥ 3）でその性質が大きく異なる。例えば，問題 (2) において X
が 2 次錐で，目的関数 f と制約関数 g が一次関数の分として表される。このように，有限個の半空間のとき，m < 3 の場合には問題 (2) は線形計画問題であるが，m ≥ 3 の場合は非線形計画問題になる。こ

共通部分であるような閉凸錐を凸多面錐という。このように 2 次錐はそれ自身がある種の非線形性をのことから，不等式制約付き最適化問題 (1) は凸多有していることに注意が必要である。このことは後面錐制約を含む最適化問題ということができる。

述する半正定値錐や対称錐においても同様である。

錐最適化問題あるいは錐計画問題はこれを拡張した問題であり，次のように表される。
Min f (x)問題 (2) の制約条件に含まれる閉凸錐が 2 次錐であるとき，この問題を 2 次錐計画問題という。た(2)s.t. g(x) ∊ X
ここで g :Rn → V はベクトル値関数であり，X はベ

だし，現実の応用に現れる数理モデルでは一つだけの 2 次錐を含むケースは少なく，多くの場合 X は
いくつかの 2 次錐の直積の形で与えられる（いくクトル空間 V の閉凸錐である。X が一般の閉凸錐のつかの錐の直積は錐である）。すなわち，一般的な場合は，この問題は必ずしも扱いやすいとは限らな

2 次錐計画問題は次のように表される。
Min f (x)い。しかし，以下に述べるいくつかの特別な閉凸錐の場合には，現実に様々な応用があり，また問題の性質を利用した効果的なアプローチが開発されている。
(a) X が Rm の非負象限 R m‌ の場合。
+

このとき問題 (2) は上述の標準的な不等式制約付

き最適化問題になる。線形計画問題や通常の非線形計画問題が含まれる。

(3)s.t. gi(x) ∊ K (i ＝ 1, 2, …, r)
ここで gi :Rn → Rmi (i ＝ 1, 2, …, r) はそれ自身 mi 次
mi元ベクトル値関数であり，K mi は mi 次元 2 次錐である。
ここで 1 次元 2 次錐が K1= { y ∊ R | y0 ≥ 0} であったことに留意すると，m1= m2=…=mr=1 であれば，問題 (3) は問題 (1) に帰着することがわかる。すな

NAIS Journal23

わち，2 次錐計画問題は標準的な不等式制約付き問
題 (1) をその特別な場合として含んでいる。
(c) X が半正定値錐の場合。

た，錐 X に内点が存在し，任意の 2 つの内点 x, yに対して T (x) ＝ y かつ T (X) ＝ X となるような線
形全単射 T が存在するとき，錐 X は等質であると

m 次実対称行列の集合を S と書く。S はベクトル空間であり，その部分集合である m 次半正定値いう。そして，自己双対で等質な錐を対称錐という。

行列全体の集合mTmSm+ ={A ∈ S | x Ax ≥ 0 ∀x ∈ R }錐の特別な例であることがいえる。

定値錐という。
半正定値錐 S m
+ を制約条件に含む錐計画問題を半正定値計画問題と呼ぶ。そのとき問題 (2) は次のよ

ベクトル空間 V の対称錐である。上に述べたことうに表される。
Min f (x)から，半正定値計画問題 (4) や 2 次錐計画問題 (3)（その特別な場合である不等式制約の最適化問題 (1) もm

m

は S の閉凸錐である（ は転置記号）。これを半正
m

T

(4)

s.t. G(x) ∊ S m+
mn
ここで G : R → S + は（対称）行列値関数，変数は

詳細は省略するが，2 次錐や半正定値行列錐は対称
対称錐計画問題は次のように表される。
Min f (x)(5)

s.t. g(x) ∊ K
ここで g : Rn → V はベクトル値関数であり，K は含む）は対称錐計画問題に含まれる（下図参照）。

n 次元ベクトル x ∈ Rn である。（変数が対称行列であるような半正定値計画問題の定式化も考えられるが，問題 (4) の定式化と本質的な違いはない。）
2 次錐の場合と同様，m ≥ 2 の半正定値錐も凸多面錐として表せない，非線形性を有する錐である。
よって，たとえ関数 f と G が 1 次関数であっても，問題 (4) は非線形最適化問題となる。
y) ∊ K m は対称行列
2 次錐制約 y ＝ (y0, Y=

0

0

∈

に対する半正定値条件 Y ∈ S m+ として表すことができ

SOCP: Second-Order Cone Program（2 次 錐 計
画問題）
SDP: Semidefinite Program（半正定値計画問題）
SCP: Symmetric Cone Program（対称錐計画問
題）る。したがって，半正定値計画問題は 2 次錐計画

非線形の問題にも同様の包含関係が成り立つ。

問題を特別な場合として含んでいるとみなせる。
(d) X が対称錐の場合。

■ ３．対称錐とユークリッド的ジョルダン代数

2 次錐や半正定値錐を含む（抽象的であるが）一
般的な概念に対称錐と呼ばれるものがある。まず，
ベクトル空間 V において内積〈·,·〉が定義されているとする。内積の定義は考えているベクトル空間によって定まる。例えば V=Rm であれば，x, y ∈ Rm に対して

〈 , 〉=

であり，V=S m であれば，A, B ∈ S m に対して
〈 , 〉=と定義される。

()=

ベクトル空間 V の錐 X に対して
X* ＝ { y ∈ V |〈x, y〉≥ 0 ∀ x ∈ X }で定義される集合（凸錐）を X の双対錐と呼ぶ。X＝ X* であるような錐は自己双対であるという。ま24

LP: Linear Program（線形計画問題）

NAIS Journal

前節で述べた対称錐はユークリッド的ジョルダン代数と呼ばれるベクトル空間と深く関係している[3]。ベクトル空間 V において，次の性質 1 ～ 4 を満たす双線形写像 （これをジョルダン積と呼ぶ）°
が定義されるとき，V をユークリッド的ジョルダン
代数という。
1. y ° ( y2 ° z) ＝ y2 ° (y ° z)（ただし y2 ＝ y ° y ）2. y ° z ＝ z ° y
3. y ° e ＝ e ° y ＝ y（単位元 e の存在）

4. 〈 y ° z, w 〉 ＝〈 y, z ° w 〉
ここで，V のベクトル y と z のジョルダン積 y ° z はまた V のベクトルであることに注意しよう。ジョ
ルダン積を用いて定義される集合
K＝{z∈V|z＝y°y∀y∈V}

は対称錐になることが知られている。この集合は 2乗の錐と呼ばれる。
2 次錐や半正定値錐は対称錐であるから，それら■ ４．2 乗スラック変数法

はそれぞれに対応するジョルダン代数におけるジョ

前節で述べた事実より，錐制約は新しい変数（ス

ルダン積に関する 2 乗の錐として表されることにラック変数）を用いて（錐を含まない）通常の等式なる。本稿で取り扱う 2 乗スラック乗数法はこの制約に書き換えることができる。まず，最も一般的性質を利用した方法である。2 乗スラック乗数法にな場合である，次の対称錐計画問題から考える。
Min f (x)進む前に，2 次錐と半正定値行列錐に対するジョル
ダン積が具体的にどのように定義されるかを見ておこう。
A) 2 次錐におけるジョルダン積
Rm の 2 つのベクトル y ＝ ( y0, y-) ∈ R×Rm-1 と z ＝ (z0,-z) ∈ R×R

に対して，そのジョルダン積を
y ° z ＝〈( y, z〉, z0 -y + y0 z- ) ∈ R×Rm-1
m-1

で定義する。特に，ベクトル y と y のジョルダン積，
すなわち y の 2 乗は-y ° y ＝ (∥y∥ , 2y0 y) ∈ R×R
2

m-1

であるから，2 次錐 K の定義を思い出せば，y ° y∈ K m となることが簡単な計算により確かめられる。
m

逆に，2 次錐 K に属する任意のベクトル z に対して z ＝ y ° y を満たすベクトル y ∈ Rm が存在するこmともいえる。したがって，
Km ＝ {z ∈ Rm| z ＝ y ° y ∀ y ∈ Rm}

s.t. g(x) ∊ K
対称錐 K はK ＝ { z ∈ V | z ＝ y ° y ∀ y ∈ V}と表されるので，x が制約 g(x) ∊ K を満たすことは，
g(x) ＝ y ° y を満たす y ∈ V が存在することと等価である。よって，上の対称錐計画問題は次の（錐制約を含まない）等式制約の非線形計画問題に変換できる。
Min f (x)s.t. g(x) － y ° y ＝ 0

これが対称錐計画問題に対する 2 乗スラック変数法である（y ∈ V はスラック変数）。

半正定値計画問題や 2 次錐計画問題，さらに標準的な不等式制約つき最適化問題はすべて対称錐計画問題の特別な場合であるから，それぞれの問題にが成り立つので，確かに 2 次錐はジョルダン積に応じて 2 乗スラック変数法を適用することにより，関する 2 乗の錐になっている。

等式制約の非線形計画問題に変換できる。具体的にところで，標準的な不等式制約つき最適化問題 (1)mの制約条件は g(x) ∊ R m+ と表されるが，R + は非負

は以下のようになる。

実数の集合 R+ ＝ { y ∊ R | y ≥ 0 } の m 重の直積であり，R+ は 1 次元 2 次錐 K 1 と同一視できる。上で述べたことから
K1 ＝ { z ∈ R | z ＝ y ° y ＝ y 2 ∀y ∈ R}であるから，結局 R m+はmm
R + ＝ { z ∈ R | zi ＝ y 2i ∀ yi ∈ R (i=1, 2, …, m)}のように 2 乗の錐として表される。

B) 半正定値錐におけるジョルダン積m 次対称行列 X, Y ∈ S m に対して，そのジョルダン積を次式で定義する。
∘

1
= -(
2

+

)∈

特に，任意の Y ∈ S m に対して Y ° Y=YY は半正定値，
すなわち Y ° Y ∊ S m+ である。逆に，任意の半正定値行列 X ∊ S m+ に対して X=Y ° Y を満たす対称行列 Y ∈m
S が存在する。したがってmm
Sm+ ={ X ∈ S | X ＝ Y ° Y ∀Y ∈ S }が成り立つので，確かに半正定値錐 S m+ はジョルダ

ン積に関する 2 乗の錐である。

半正定値計画問題
Min f (x)s.t. G(x) ∊ S m+
mの 場 合，S + ={ X ∈ S m | X ＝ Y ° Y ∀ Y ∈ S m} であるから，スラック変数として行列変数 Y ∈ S m を導入することにより次の問題を得る。
Min f (x)s.t. G(x) － Y ° Y ＝ 0

2 次錐計画問題
Min f (x)s.t. gi(x) ∊ K mi (i ＝ 1, 2, …, r)の場合も，K m ＝ { z ∈ Rm | z ＝ y ° y ∀ y ∈ Rm} であるから，
スラック変数 yi ∊ R mi (i ＝ 1, 2, …, r) を用いて，次のように問題を変換できる。
Min f (x)s.t. gi (x) － yi ° yi ＝ 0 (i ＝ 1, 2, …, r)

不等式制約付き最適化問題
Min f (x)s.t. gi(x) ≥ 0 (i ＝ 1, 2, …, m)
は m 個の（1 次元）スラック変数 yi ∊ R (i ＝ 1, 2, …,
NAIS Journal25m) を用いて次のような等式制約の問題に変換できに対して結果を示すかわりに，（ふつうの不等式制る。

約の）非線形計画問題と，最も一般的な対称錐計画
Min f (x)s.t. gi(x) － y 2i ＝ 0 (i ＝ 1, 2, …, m)

なお，不等式制約つき最適化問題に対する 2 乗
スラック変数法は非線形計画の分野で古くから知られていたが [1]，あまりメリットがないことから大きな注目を集めることはなかった。しかし，対称錐計画問題をはじめとする錐最適化問題においては，
大きく事情は異なる。すなわち，2 乗スラック変数問題とに対する結果を述べ，2 次錐計画問題と半正定値計画問題については簡単に触れるにとどめる。
まず（ふつう不等式制約の）非線形計画問題
Min f (x)(NP1)
s.t. gi(x) ≥ 0 (i ＝ 1, 2, …, m)と，これをスラック変数 yi ∊ R (i ＝ 1, 2, …, m) を用いて変換した等式制約の問題
Min f (x)s.t.

法により，錐制約がふつうの等式制約に変換される
ので，錐制約を直接扱う代わりに通常の非線形最適を考える。前者の問題を (NP1)，後者の問題を (NP2)化の理論と方法を適用することが可能となる。次節と呼ぶ。(NP1) と (NP2) はどちらも通常の非線形ではそのような観点から筆者らが行った研究の一端

計画問題であるから，古典的な最適化理論が適用でを紹介する。

きて，(NP1) の KKT 条件は■( )５．最適性条件
前節では，いくつかの錐最適化問題に対して，2∇g ( ) = 0

λi ≥ 0, gi(x) ≥ 0, λi gi(x)=0 (i =1, 2, …, m)であり，(NP2) の KKT 条件は乗スラック変数を用いて錐制約を等式制約に変換し( )た非線形最適化問題を示した。変換前の問題と変換∇g ( ) = 0

後の問題は同じ最適解（大域的，局所的のいずれのλi yi ＝ 0, gi(x) － y 2i =0 (i=1, 2,…,m)

意味でも）をもつという意味で等価である。しかしとなる。ここで λi (i=1,2,…,m) はラグランジュ乗数

ながら，一般に数理最適化問題を解く手法（アルゴである。この 2 つの KKT 条件を比較すると，(NP2)

リ ズ ム ） は 問 題 の 1 次 の 最 適 性 条 件（KarushKuhn-Tucker 条件あるいは KKT 条件と呼ばれるの KKT 条件には (NP1) の KKT 条件に含まれている条件 λi ≥ 0 (i=1, 2,…, m) が欠落していることがわ[6]）を満たす解（停留点と呼ばれる）を求めるよかる。（それ以外の部分は見かけは異なるが実質的うに設計されている。ところが，上述の問題のペアに等価である。）すなわち，(NP1) の停留点は (NP2)についていえば，両者の問題の KKT 条件は互いにの停留点であるが，逆は必ずしも正しくない。した等価とは必ずしもいえない。より正確にいえば，変がって，(NP2) の停留点を求めても，それは元の問換後の問題を解いて得られる（KKT 条件を満たす）

題 (NP1) の停留点であるとは限らない。

解は元の（変換前の）問題の KKT 条件を無条件に

それでは 2 つの問題の停留点の等価性を保証す

満たすとは限らず，それを保証するためには何か付るには何が必要であろうか。そこで重要な役割を果

加的な条件が必要になる。このことから，両者の問たすのが，2 次の十分条件 [6] と呼ばれる条件であ

題の最適性条件を（KKT 条件だけでなく 2 次の条る。2 次の十分条件とは KKT 条件と組み合わせる

件，制約想定なども包括的に）調べることが重要にことにより，停留点が局所的最適解であることを保なる。

証できる条件である。(NP1) に対する 2 次の十分条

さらに加えて，元の錐最適化問題の最適性条件を件は，∇ gi (x)Td ＝ 0 if gi(x) ＝ 0, λi > 0∇ gi (x)Td ≥ 0 if gi(x) ＝ 0, λi ＝ 0

直接導出するには複雑な数学的な道具が必要である
が，変換後の問題は錐制約をもたない通常の最適化問題であるからそのような道具を必要としない。そ(6)

れにも関わらず，結果として錐最適化問題に対するを満たす任意のベクトル d ≠ 0 に対してd T ∇ 2x L (x, λ) d > 0

最適性条件を導出できる。これも 2 乗スラック乗数法を用いることの利点の一つである。
以下では，前節で紹介した錐最適化問題のすべて

26

(NP2)

gi(x) － y 2i ＝ 0 (i ＝ 1, 2, …, m)

NAIS Journal(7)が成り立つことである。ここで L は次式で定義される (NP1) のラグランジュ関数である。

( , )= ( )λ ° y ＝ 0, g (x ) － y ° y ＝ 0g( )と表される。この場合も，前述の (NP1), (NP2) の一方，(NP2) に対する 2 次の十分条件は~(∇gi (x)T, － 2 yi e Ti ) d =0

場合と同様，(SCP2) の KKT 条件には (SCP1) のKKT 条件に含まれている条件 λ ∈ K が欠落してい~を満たす任意のベクトル d ≠ 0 に対して~~~d T ∇2(x,y) L(x, y, λ) d >0

る。それ以外は，見かけは異なるが実質的に等価である。よって，(SCP1) の停留点は (SCP2) の停留~が成り立つことである。ここで L は次式で定義される (NP2) のラグランジュ関数である。
̃( , , ) = ( )(g ( )

点であるが，逆は必ずしも正しくない。
結論からいえば，(SCP2) の停留点が (SCP1) の2)

2 次の十分条件を考慮すれば，(NP2) の停留点が(NP1) の停留点になることだけでなく，それ以上の関係を示すことができる。
定理：1. (x, y) が (NP2) の 2 次の十分条件を満たす
停留点であれば，x は (NP1) の 2 次の十分条件と狭義相補性を満たす停留点であり，その逆も成り立つ。
2. (x, y) が (NP2) の 2 次の十分条件と 1 次独立制約
想定を満たす停留点であれば，x は (NP1) の 2 次の十分条件，狭義相補性，1 次独立制約想定を満たす
停留点であり，その逆も成り立つ。

停留点であるためには (SCP2) の停留点が (SCP2)に対する 2 次の十分条件を満たせばよい。(SCP2)
はふつうの非線形計画問題であるから，2 次の十分
条件はJg (x) v － 2y ° w ＝ 0

を満たす任意のベクトル (v,w) ≠ 0 に対して~〈(v,w), ∇ 2(x,y) L(x, y, λ)(v, w)〉> 0~が成り立つことである。ここで L は次式で定義される (SCP2) のラグランジュ関数である。
~
L(x, y, λ) ＝ f (x) －〈λ, g(x) － y ° y〉

さらに，前述の (NP1) と (NP2) に関する定理で述べたものと同様の結果を示すことができる。しかここで，(NP1) の狭義相補性とは，KKT 条件における λi gi(x) ＝ 0 を満たす λi と gi(x) のどちらか一し，それを記述するためには，錐最適化問題に対す方はゼロでないという性質であり，1 次独立制約想

独立制約想定の拡張）などを定義する必要があるが，定とは停留点において等号が成り立っているすべて

ここではこれ以上の深入りは避け，錐最適化問題にの制約条件（有効制約という）の制約関数の勾配がおける 2 次の最適性条件の本質に簡単に言及する。

1 次独立であるという性質である。

る 2 次の十分条件，狭義相補性，非退化性（一次凸多面錐上の最適化問題である (NP1) の 2 次の上述の定理の結果は 2 次錐計画問題，半正定値十分条件は式 (6) を満たすベクトルの集合上で，ラ計画問題，対称錐計画問題にも自然に拡張できる。

グランジュ関数のヘシアンが式 (7) を満たすこと，

ここではそれらの中で最も一般的な問題である対称すなわち一種の正定値性を有することと特徴づけら錐計画問題れる。しかし，多面錐ではない一般の凸錐は「境界Min f (x)s.t. g(x) ∊ K

面が曲がっている」ので，2 次の条件ではその曲率を考慮する必要が生じる [7]。これが多面錐と一般と，錐制約をジョルダン積に関する 2 乗スラックの凸錐（2 次錐，半正定値錐，対称錐を含む）の最変数を用いて等式制約に変換した非線形計画問題
Min f (x)大の相違である。

s.t. g(x) － y ° y ＝ 0について説明する。前者を (SCP1)，後者を (SCP2)と書く。(SCP1) の KKT 条件は，錐最適化の理論
より∇ f (x) － Jg(x)* λ = 0
λ ∈ K, g(x) ∈ K, λ ° g (x) ＝ 0と書ける。ここで Jg(x) は g のヤコビアン，* は随一般の凸錐制約つき最適化問題については，凸錐
K の点 z における接錐を TK (z) としたとき，停留点x に対してJg (x) d ∈ TK (g (x))

を満たす任意のベクトル d ≠ 0 が〈d, ( ∇ 2x L(x, λ) + σ(x,λ))d 〉> 0

を満たせば，停留点 x は局所的最適解になることが伴を表す。一方，(SCP2) の KKT 条件は通常の最知られている。ここで，ラグランジュ関数のヘシア
ンに付加された項 σ (x, λ) は凸錐 K の曲率を考慮し適化理論よりたために生じたものでありシグマ項と呼ばれる。
∇ f (x) － Jg(x)* λ = 0

シグマ項の具体的な形は 2 次錐計画問題や半正NAIS Journal27

定値計画問題については既知であるが [2,11]，対称錐計画問題を含む一般の錐最適化問題に対する研究はほとんど見当たらない。2 乗スラック変数法を用いると，2 次錐計画と半正定値計画に対するシグマ
項が 2 次接錐のような変分解析の概念を使わずに導けるだけでなく，既存研究が存在しない対称錐計画問題の 2 次の最適性条件についてもその表現を得ることができる。
具体的には，対称錐計画問題 (SCP1) に対する 2
次の十分条件は以下のように表せる。すなわち，停留点 x においてg( ) − 2 g( ) ∘ = 0
を満たす任意のベクトル (v,w) ≠ (0,0) に対して
〈v,( ∇ 2x L(x, λ)v〉+ 2〈w ° w, λ〉>0が成り立つならば，x は (SCP1) の局所的最適解である。ちなみに最後の不等式を〈v,( ∇ 2x L(x, λ)v〉+ 2〈w ° w, λ〉 ≥ 0と置き換えると 2 次の必要条件になることも示せる。この事実は，これらがある意味で最良の十分条
件と必要条件のペアであることを示している。

■ ６．おわりに
本稿では 2 乗スラック変数法を用いることにより錐最適化問題に対して新たなアプローチが可能となることを，主に理論面での成果 [4,5,9,10] をもとに紹介した。これに対して，2 乗スラック変数法のもう一つの側面は数値解法としての可能性である。
半正定値計画問題や 2 次錐計画問題には，それらに特化したアルゴリズム（およびソルバ）が開発さ

参考文献[1] D.P. Bertsekas, Nonlinear Programming, 2nd Edition,
Athena Scientific, 1999.
[2] J.F. Bonnans and C.H. Ramirez, Perturbation
analysis of second-order cone programming,
Mathematical Programming 104 (2005), pp. 205-227.
[3] J. Faraut and A. Korányi, Analysis on Symmetric Cones,
Oxford Mathematical Monographs, Clarendon Press,
1994.
[4] E.H. Fukuda and M. Fukushima, The use of squared
slack variables in nonlinear second-order cone
programming, Journal of Optimization Theory andApplications 170 (2016), pp. 394-418.
[5] E.H. Fukuda and M. Fukushima, A note on thesquared slack variables technique for nonlinear
optimization, Journal of the Operations Research Society ofJapan 60 (2017), pp. 262-270.
[6] 福島雅夫，『非線形最適化の基礎』，朝倉書店，2001.
[7] H. Kawasaki, An envelope-like effect of infinitely
many inequality constraints on second-ordernecessary conditions for minimization problems,Mathematical Programming 41 (1988), pp. 73-96.
[8] 小島政和，土谷隆，水野眞治，矢部博，『内点法』，朝倉書店，2001.
[9] B.F. Lourenço, E.H. Fukuda and M. Fukushima,
Optimality conditions for nonlinear semidefinite
programming via squared slack variables, Mathematical Programming 168 (2018), pp. 177-200.
[10] B.F. Lourenço, E.H. Fukuda and M. Fukushima,
Optimality conditions for problems over symmetriccones and a simple augmented Lagrangian method,
Mathematics of Operations Research 43 (2018), pp. 12331251.
[11] A. Shapiro, First and second order analysis ofnonlinear semidefinite programs, Mathematical
Programming 77 (1997), pp. 301-320.

れているが，2 乗スラック変数を用いて問題を通常の非線形計画問題に変換すれば汎用の最適化ソルバ
によって問題を解くことも可能である。実際，2 次
錐計画問題と半正定値問題のさまざまな問題例に対して計算実験を行ったところ，2 乗スラック変数法と汎用ソルバを組み合わせた方法のパフォーマンス
は錐最適化問題に特化したソルバに匹敵することが観測された [4,9]。
謝辞

本稿は京都大学情報学研究科福田エレン秀美

准教授，統計数理研究所 Bruno F. Lourenço 准教
授との共同研究の成果に基づいている。

28

NAIS Journal

◆著者紹介

福嶋

雅夫

Masao Fukushima

京都情報大学院大学教授
京都大学工学研究科修了 工学博士
京都大学名誉教授
元南山大学大学院教授
元奈良先端科学技術大学院大学教授