c オペレーションズ・リサーチ


多重共線性を考慮した回帰式の変数選択問題の定式化
田村

隆太，小林

健，高野

祐一，宮代

隆平，中田

和秀，松井

知己

重回帰分析では，複数の説明変数の間に強い線形従属性（多重共線性）が存在すると，回帰式の推定が数値的に不安定になり，分析結果の信頼性が低下する．このような多重共線性を回避するための簡単かつ有効な方法として，説明変数の有用な部分集合を選択して回帰式に使用する変数選択がある．本稿では，多重共線性を回避する制約条件の下で回帰式の残差二乗和を最小化する変数選択問題を，最適化ソルバーで直接求解可能な混合整数最適化問題に帰着する三種類の定式化を紹介する．

キーワード：重回帰分析，変数選択，多重共線性，混合整数最適化，条件数，分散拡大要因

1.

はじめに

最良の部分集合を選択できることである．
本稿では，多重共線性を回避する制約条件の下で，回多重共線性とは重回帰分析においてしばしば直面す

帰式の残差二乗和を最小化する変数選択問題を対象とる問題であり，回帰式の複数の説明変数の間に強い線

する．2 節では関連研究を紹介し，3 節では多重共線

形従属性が存在することである [1–3]．説明変数間の性の指標である相関係数行列の条件数と分散拡大要因

強い従属関係は，個々の説明変数が目的変数に与える（variance inflation factor, VIF）について説明する．

影響を不明瞭にし，偏回帰係数の推定が数値的に不安

4 節では，条件数を用いた混合整数半正定値最適化問

定になるため，分析結果の信頼性も損なわれる．

題による定式化 [7] を提示する．5 節では，VIF を用

多重共線性を回避する方法として，説明変数の有用ないた混合整数二次最適化問題による二種類の定式化 [8]部分集合を選択して回帰式に使用する変数選択が有効を提示する．これらの混合整数最適化問題は，最適化である．また近年は，変数選択問題の厳密解法として混ソルバーで直接求解することが可能である．多重共線合整数最適化が注目を集めている．この解法は 1970 年

性を回避する制約条件は一見扱い難そうに思えるが，代から提案されてはいたが [4]，当時は計算機が非力

上手く変形することで扱いやすい制約条件に帰着するだったために実用規模の問題を解くことは難しかった．

ことが可能であり，このような定式化の醍醐味が読者

しかし，計算機や最適化アルゴリズムの性能が飛躍的に伝われば幸いである．最後に 6 節で本稿のまとめをに向上した現在では [5]，混合整数最適化が実用的な変述べる．

数選択の手法となりつつある．ステップワイズ法 [6]に代表される多くの発見的解法とは対照的に，混合整数最適化の最大の利点は，回帰式の評価指標に関して

2. 関連研究
本節では，多重共線性を回避する方法について説明
し，混合整数最適化による変数選択の既存研究を紹介

たむら りゅうた
株式会社オクトーバー・スカイ〒 183–0055 東京都府中市府中町 1–25–12
こばやし けん株式会社富士通研究所〒 211–8588 神奈川県川崎市中原区上小田中 4–1–1
たかの ゆういち
専修大学ネットワーク情報学部〒 214–8580 神奈川県川崎市多摩区東三田 2–1–1
みやしろ りゅうへい
東京農工大学大学院工学研究院〒 184–8588 東京都小金井市中町 2–24–16
なかた かずひで，まつい ともみ
東京工業大学工学院経営工学系〒 152–8552 東京都目黒区大岡山 2–12–1

する．

2.1 多重共線性を回避する方法
多重共線性を回避する方法として，直交変換，罰則付き回帰，変数選択などの方法が知られている [2]．直交変換は主成分回帰 [9, 10] や PLS 回帰 [11, 12] に代表される方法であり，相関の強い説明変数を合成して使用する．直交変換を施すことで，推定の数値的不安
定性は解消される．一方で，変数を合成してしまうと元の変数の効果がわかり難くなるため，分析結果の解釈が難しくなり [13]，予測精度の悪化や外れ値の影響があることも指摘されている [14, 15]．

c by ORSJ. Unauthorized reproduction of this article is prohibited.
128（4）Copyright 

オペレーションズ・リサーチ

罰則付き回帰には ridge 回帰 [16]，lasso 回帰 [17]，

関の強い説明変数のペアに対して，少なくとも一方の

elastic net [18] などの方法があり，これらの方法では変数を削除する制約条件を課すことが考えられる [13]．

偏回帰係数の値をゼロに近づける罰則項を導入して推しかしながら，この方法では 3 個以上の変数間に存在定する．このことにより，モデルの過剰適合が軽減さする線形従属性を除去することができない．このようれ予測精度の向上が見込めるが，一方で罰則項の存在な線形従属性を除去することができる方法として切除により偏回帰係数の推定値に偏りが生じ，分析結果の平面法があり，多重共線性を有する変数集合を排除す

解釈の観点からは望ましいとは言えない [13, 19]．

る妥当不等式を逐次的に追加する [13]．変数減少法を

変数選択は，候補となる説明変数の中から有用な部利用して妥当不等式を強化し，切除平面法を高速化す

分集合を選択して回帰式に使用する方法であり，部分る方法も提案されている [7]．しかしながら切除平面法

集合選択，特徴選択，素性選択などと呼ばれることもを単純に実装すると，混合整数最適化問題を繰り返しある．変数選択問題に対しては多くの解法が提案され解くことになり，計算効率のよい方法とは言い難い．

ているが [20–23]，それらの多くは発見的解法やメタ戦略とみなすことができる．多重共線性を除去する場合には，多重共線性がなくなるまで説明変数を一つずつ削除していく方法がよく用いられる [2]．しかながら，

3. 多重共線性の指標
本節では多重共線性の指標として，相関係数行列の条件数と VIF について説明する．

このような方法では，回帰式の評価指標に関して最良

3.1 線形回帰の部分集合を最終的に得られる保証はない．変数選択

n 個の標本 {(yi ; xi1 , xi2 , . . . , xip ) | i = 1, 2, . . . , n}問題の厳密解法としては，変数集合の包含関係に基づが与えられ，yi は標本 i の目的変数の値とし，xij はく枝刈り操作を組み合わせた総当り法 [24] が知られて標本 i の j 番目の説明変数の値とする．説明変数の添いるが，候補変数が多い場合には実用的な方法とは言え字集合を P := {1, 2, . . . , p} とし，変数はすべて以い難い．そこで本稿では，混合整数最適化による変数

下のように正規化されていることを仮定する：

選択に着目する．

n

2.2 混合整数最適化による変数選択
混合整数最適化では，選択する説明変数の数を制限

i=1
n


する基数制約の下で，回帰式の残差二乗和や絶対偏差を最小化する問題として，変数選択問題を定式化する

i=1

xij =

n


yi = 0,(1)

i=1(xij )2 =n(yi )2 = 1(j ∈ P ).

ことが多い [4, 19, 25]．この定式化では選択変数の数

このとき，線形回帰式は以下のように書ける：

を指定する必要があるが，適切な数を事前に指定する

y = Xa + ε,

ことは難しい．一方で，回帰式の評価指標に基づいて，選択変数の数も同時に最適化する定式化が提案されており，Mallows の Cp 規準 [26]，自由度調整済み決定
係数 [27]，AIC や BIC などの情報量規準 [27]，離散型 Dantzig 選択器 [28] などの評価指標が活用されている．また，ロジスティック回帰 [29, 30]，逐次ロジット
回帰 [31]，サポートベクターマシン [32]，クラスター
分析 [33] などの分類モデルの変数選択や，分類木 [34]の構築に対しても，混合整数最適化手法が提案されて

(2)

i=1

ただし，y := (y1 , y2 , . . . , yn ) ,
X := x1 , x2 , . . . , xp⎛
x11 x12 · · ·⎜⎜⎜ x21 x22 · · ·
=⎜
..
..
⎜ ..
⎜ .
.
.
⎝
xn1

xn2

···

x1p

⎞

⎟
⎟
x2p ⎟
⎟
.. ⎟
. ⎟
⎠
xnp

いる．変数選択の問題構造を活用して，分枝限定法をとし，a := (a1 , a2 , . . . , ap ) は推定すべき偏回帰係数高速化する研究も行われている [35, 36]．混合整数最のベクトル，ε := (ε1 , ε2 , . . . , εn ) は各標本に対する適化による変数選択は，医学 [37, 38]，マーケティン

残差のベクトルとする．

グ [39, 40]，化学 [41–43]，金融 [44] などの分野の問題に応用され，データ解析環境 R のパッケージも公開

3.2 相関係数行列の条件数
説明変数の部分集合 S (⊆ P ) を選択したと想定し，
行列 X の部分行列 X S := (xj )j∈S を考える．このとされている [45]．

2.3 混合整数最適化による多重共線性の除去

き，回帰式の残差二乗和

多重共線性を除去するための簡易的な方法として，相2018 年 3 月号

c by ORSJ. Unauthorized reproduction of this article is prohibited.（5）Copyright 129y − X S aS 22 = (y − X S aS ) (y − X S aS )R2 (, S) := 1 − x − X S\{} â(,S) 22 .

が最小となる偏回帰係数 âS ∈ R|S| は最小二乗推定量

集合 S に属する説明変数の間に強い線形従属性が存在と呼ばれ，以下の正規方程式を解いて求めることがですると，回帰式 (6) の当てはまりがよくなり，決定係

きる：

数 R2 (, S) の値が 1 に近づく．
X
S X S âS = X S y.

(3)

集合 S に属する説明変数の相関係数行列は，仮定

この事実に基づいて，以下のように VIF を定義する
ことができ，式 (5) と等価な定義であることが知られている [1, 3]：(1)–(2) より，以下のように計算できる：
1
1 − R2 (, S)1.
=
x − X S\{} â(,S) 22

VIF(, S) :=RS := (rj )(j,)∈S×S = X 
S XS .
このとき相関係数行列 RS の条件数は，その最小固有値 λmin (RS ) と最大固有値 λmax (RS ) を用いて，以下のように定義される：

λmax (RS ).
cond(RS ) :=λmin (RS )(8)

4. 条件数に基づく定式化(4)

本節では，条件数に基づく変数選択問題の定式化 [7]について説明する．説明変数の選択を表す 0–1 決定変

条件数が大きいと，正規方程式 (3) の係数行列 RS =数のベクトルを z := (z1 , z2 , . . . , zp ) とし，選択されX
S X S が悪条件となり，方程式の解 âS が数値誤差

た説明変数の添え字集合を S(z) := {j ∈ P | zj = 1}の影響を強く受けることになる．条件数が 225 を超えとする．条件数の上限値を表すパラメータを κ (> 1)

ると，多重共線性の悪影響が強くなるとされる [2]．

とし，回帰式の残差二乗和を最小化する変数選択問題

3.3 分散拡大要因

は以下のように書ける：

VIF は説明変数ごとに定義され，  (∈ S) 番目の説
明変数の VIF は，相関係数行列 RS の逆行列の  番目

minimizey − Xa22の対角成分により，以下のように定義される：

subject tozj = 0 ⇒ aj = 0

VIF(, S) := [R−1
S ] .

(5)(9)(j ∈ P ),(10)

cond(RS(z) ) ≤ κ,(11)a ∈ Rp , z ∈ {0, 1}p .

(12)

選択された変数の間に強い相関が存在する場合には，相関係数行列 RS が特異行列に近づき，VIF の値が大

zj = 0 の場合には，論理制約 (10) により偏回帰係数きくなる．VIF が 10 を超えると，多重共線性の兆候

aj の値がゼロになり，j 番目の説明変数は回帰式から削とされる [2]．

除される．このような論理制約は，big-M やタイプ 1

VIF には定義 (5) と等価だが異なる形の定義が知られている．この定義を説明するために， (∈ S) 番目の変数を目的変数とし，集合 S に属するほかの変数を条件数の上限制約 (11) は，行列の半正定値制約とし行列のアダマール積 R ◦ (zz  ) を考える：(6)

ここで，a(,S) ∈ R|S|−1 と ε(,S) ∈ Rn はそれぞれ偏回帰係数と残差を表すベクトルである．
式 (3) と同様に，以下の正規方程式を解いて最小二乗推定量 â(,S) を求めることができる：
(,S)
X
= X
S\{} X S\{} â
S\{} x .

直接記述できる最適化ソルバーも存在する．
て記述できる．まず，以下の対角行列 Diag(1 − z) と，説明変数とした以下の線形回帰式を考える：

x = X S\{}a(,S) + ε(,S) ,の特殊順序集合を用いて表現可能であり，論理制約を⎛⎜⎜⎜Diag(1 − z) = ⎜⎜⎜⎝1 − z2
..
.

···
..
.
..
.

0
..
.

···

0

1 − zp1 − z1

0

0
..
.
0

0

⎞
⎟
⎟
⎟
⎟,
⎟
⎟
⎠

(7)

回帰式 (6) の決定係数は，仮定 (1)–(2) より，最小二乗推定量を用いて以下のように計算できる：
c by ORSJ. Unauthorized reproduction of this article is prohibited.
130（6）Copyright 

オペレーションズ・リサーチ⎛

r11 z1 z1⎜⎜⎜ r21 z2 z1R ◦ (zz ) = ⎜
..
⎜
⎜
.
⎝
rp1 zp z1

r12 z1 z2···

r22 z2 z2
..
.

···
..
.

rp2 zp z2···⎞の最適化ソルバーを用いて解くことができる．

⎟⎟
r2p z2 zp ⎟
⎟.
..
⎟
⎟
.
⎠
rpp zp zp

5.1 相関係数行列の逆行列に基づく定式化

r1p z1 zp

本節では，相関係数行列の逆行列に基づく VIF の
定義 (5) を利用する．決定変数の正方行列 Q :=(qj )(,j)∈P ×P ，U := (uj )(,j)∈P ×P を導入する．このとき VIF の上限制約 (16) は，以下のように論理制

非負決定変数 λ ∈ R+ を導入し，条件数の上限制約(11) は以下のように記述できる：
λI − Diag(1 − z)

約と線形制約で記述できる：

q ≤ αR ◦ (zz  )

κλI,

(13)

( ∈ P ),(19)

zj = 1 ⇒ uj = 0

ただし，I は適切なサイズの単位行列とする．
ここでは証明の概略を述べる．まず，R ◦ (zz  ) を計

(18)

QRP + U = I,( ∈ P, j ∈ P ),zj = 0 ⇒ qj = qj = 0(20)( ∈ P, j ∈ P ).

(21)

算すると，選択された変数の相関係数行列 RS(z) が残

ここでは証明の概略を述べる．制約条件 (20)–(21)り，ほかの成分はゼロになる．このとき制約条件 (13)を考慮すると，Q の主小行列 Q1 に関する等式条件

により，

Q1 RS(z) = I が制約条件 (19) から導かれる．したλ ≤ λmin (RS(z) ),となり，制約条件 (18) が定義 (5)がって Q1 = R−1
S(z)λmax (RS(z) ) ≤ κλに基づく VIF の上限制約 (16) を表す．定式化の詳細が保証され，条件数の定義 (4) より上限制約 (11) が満については論文 [8] を参照されたい．

5.2 正規方程式に基づく定式化

たされる．
さらに制約条件 (13) の双線形項 zz



を線形化

本 節 で は ，正 規 方 程 式 (7) に 基 づ く VIF の 定

し [46, 47]，目的関数 (9) を半正定値制約を用いて線

義 (8) を利用する．決定変数のベクトル a() :=形化する [48, 49]．問題 (9)–(12) は混合整数半正定値(aj )j∈P \{} ( ∈ P ) を導入し，以下の制約条件を最適化問題に帰着され，SCIP-SDP1 [50] などの最適考える：

化ソルバーを用いて解くことができる．定式化の詳細については論文 [7] を参照されたい．

5.

()

()
zj = 1 ⇒ x= xj X P \{} aj x

(j ∈ P \ {}),()zj = 0 ⇒ aj = 0

VIF に基づく定式化

本節では，VIF に基づく変数選択問題の二種類の定(j ∈ P \ {}).

(22)
(23)

ここでは p 個の説明変数のうち最初の s 個が選択され式化 [8] について説明する．VIF の上限値を表すパラ

る，すなわち S(z) = {1, 2, . . . , s} を仮定し， ∈ S(z)メータを α (> 1) とし，選択された説明変数に対してとする．制約条件 (23) より，ベクトル a() は以下の

VIF の上限制約を課す．このとき，回帰式の残差二乗ように分割できる：

和を最小化する変数選択問題は以下のように書ける：

minimizey − Xa22

subject tozj = 0 ⇒ aj = 0(j ∈ P ),(15)( ∈ P ), (16)a ∈ Rp , z ∈ {0, 1}p .

(17)以降では VIF の二種類の定義に基づいて，変数選択問題 (14)–(17) を混合整数二次最適化問題に帰着する．
混合整数二次最適化問題は，Gurobi2 や CPLEX3 など
1 http://www.opt.tu-darmstadt.de/scipsdp/

2 https://www.octobersky.jp/products/gurobi.html

3 http : / / www-03 . ibm . com / software / products / ja /2018 年 3 月号

a() = ⎝

()

a1

(14)

z = 1 ⇒ VIF(, S(z)) ≤ αibmilogcple

⎛

0

⎞
⎠.

このとき制約条件 (22) より，式 (7) と同様の正規方
程式
()


X
S(z)\{} X S(z)\{} a1 = X S(z)\{} x

(24)

()

が導かれ，a1 が最小二乗推定量になる．したがって，
定義 (8) より VIF は以下のように書ける：

VIF(, S(z)) =1()x − X S(z)\{} a1 22
1=.
x − X P \{} a() 22

よって，VIF の上限制約 (16) は以下のように書くこ
c by ORSJ. Unauthorized reproduction of this article is prohibited.（7）Copyright 131とができ，z = 0 の場合は冗長な制約となり，z = 1の場合に上限制約を表す：z ≤ αx − X P \{} a() 22( ∈ P ).

整数最適化の枠組みで取り扱うことは難しい．しかしながら，正規方程式 (24) を利用して，制約条件 (25)の右辺は以下のように線形化することができる：

x − X P \{} a() 22

()
= x
 x − 2x X P \{} a
()

()

+ (a1 ) X 
S(z)\{} X S(z)\{} a1



式 (24) を代入

()


()
= x
+ (a1 ) X  x − 2x X P \{} aS(z)\{} x

()
x
.
 x − x X P \{} a

したがって制約条件 (22)–(23) の下で，制約条件(25) は()z ≤ α(x) x − x X P \{} a( ∈ P )となり，VIF の上限制約 (16) は論理制約と線形制約で記述できる．

6.

本研究の一部は JSPS 科研費 JP26560165，(25)

ただし，この制約条件は逆凸制約となっており，混合=

謝辞

JP17K12983 の助成を受けたものです．

おわりに

本稿では，多重共線性を考慮した変数選択問題に対して，条件数に基づく混合整数半正定値最適化問題による定式化と，VIF に基づく二種類の混合整数二次最適化問題による定式化を提示した．これらの問題は最適化ソルバーで直接求解することができ，求解が終了
すれば残差二乗和に関して最良の説明変数の部分集合が得られる．また単一の問題として定式化されているため，計算を途中で打ち切ったとしても，良質な暫定解を得られる可能性が高い．計算機実験の結果については，論文 [7, 8] を参照されたい．
数理最適化の国際会議 ISMP 2015 の講演で，Dim-

itris Bertsimas は「私の統計学の授業では混合整数最適化を教えている．その理由は，統計学のさまざまな問題に対して混合整数最適化が利用される時代が将来必ず訪れるからだ」と述べていた．計算機と最適化アルゴリズムの性能は現在も向上を続けている．現状としては，候補変数が多い場合には混合整数最適化による変数選択は膨大な計算時間を要するが，このような状況も徐々に改善されていくだろう．統計的モデル選
択の標準的な手法として，混合整数最適化が利用される時代が訪れることを期待して，本稿を終えたい．

参考文献[1] D. A. Belsley, E. Kuh and R. E. Welsch, Regression
Diagnostics: Identifying Influential Data and Sourcesof Collinearity, John Wiley & Sons, 2005.
[2] S. Chatterjee and A. S. Hadi, Regression Analysis by
Example, 5th Edition, John Wiley & Sons, 2012.
[3] C. F. Dormann, J. Elith, S. Bacher, C. Buchmann,
G. Carl, G. Carré, J. R. G. Marquéz, B. Gruber,
B. Lafourcade, P. J. Leitão, T. Münkemüller, C. McClean, P. E. Osborne, B. Reineking, B. Schröder,A. K. Skidmore, D. Zurell and S. Lautenbach,“Collinearity: A review of methods to deal with it
and a simulation study evaluating their performance,”
Ecography, 36, pp. 27–46, 2013.
[4] T. S. Arthanari and Y. Dodge, Mathematical Programming in Statistics, John Wiley & Sons, 1981.
[5] R. E. Bixby, “A brief history of linear and mixedinteger programming computation,” Documenta
Mathematica, Extra Volume: Optimization Stories,
pp. 107–121, 2012.
[6] M. A. Efroymson, “Multiple regression analysis,”
Mathematical Methods for Digital Computers, A. Ralston and H. S. Wilf (eds.), John Wiley & Sons, pp. 191–
203, 1960.
[7] R. Tamura, K. Kobayashi, Y. Takano, R. Miyashiro,
K. Nakata and T. Matsui, “Best subset selection foreliminating multicollinearity,” Journal of the Operations Research Society of Japan, 60, pp. 321–336,
2017.
[8] R. Tamura, K. Kobayashi, Y. Takano, R. Miyashiro,
K. Nakata and T. Matsui, “Mixed integer quadratic
optimization formulations for eliminating multicollinearity based on variance inﬂation factor,”
Optimization Online, 2016, http://www.optimizationonline.org/DB HTML/2016/09/5655.html[9] I. T. Jolliﬀe, “A note on the use of principal components in regression,” Applied Statistics, 31, pp. 300–
303, 1982.
[10] W. F. Massy, “Principal components regression in
exploratory statistical research,” Journal of the American Statistical Association, 60, pp. 234–256, 1965.
[11] H. Wold, “Estimation of principal components andrelated models by iterative least squares,” Multivariate Analysis, P. R. Krishnaiah (ed.), Academic Press,
pp. 391–420, 1966.
[12] S. Wold, A. Ruhe, H. Wold and W. J. Dunn III,“The collinearity problem in linear regression. The partial least squares (PLS) approach to generalized inverses,” SIAM Journal on Scientific and StatisticalComputing, 5, pp. 735–743, 1984.
[13] D. Bertsimas and A. King, “OR forum—An algorithmic approach to linear regression,” Operations Research, 64, pp. 2–16, 2016.
[14] L. E. Frank and J. H. Friedman, “A statistical viewof some chemometrics regression tools,” Technometrics, 35, pp. 109–135, 1993.
[15] A. S. Hadi and R. F. Ling, “Some cautionary noteson the use of principal components regression,” Thec by ORSJ. Unauthorized reproduction of this article is prohibited.
132（8）Copyright 

オペレーションズ・リサーチ

American Statistician, 52, pp. 15–19, 1998.
[16] A. E. Hoerl and R. W. Kennard, “Ridge regression:
Biased estimation for nonorthogonal problems,” Technometrics, 12, pp. 55–67, 1970.
[17] R. Tibshirani, “Regression shrinkage and selection
via the lasso,” Journal of the Royal Statistical Society,
Series B (Methodological), 58, pp. 267–288, 1996.
[18] H. Zou and T. Hastie, “Regularization and variableselection via the elastic net,” Journal of the Royal Statistical Society, Series B (Statistical Methodology), 67,
pp. 301–320, 2005.
[19] D. Bertsimas, A. King and R. Mazumder, “Bestsubset selection via a modern optimization lens,” The
Annals of Statistics, 44, pp. 813–852, 2016.
[20] A. L. Blum and P. Langley, “Selection of relevant
features and examples in machine learning,” Artificial
Intelligence, 97, pp. 245–271, 1997.
[21] I. Guyon and A. Elisseeﬀ, “An introduction to variable and feature selection,” Journal of Machine Learning Research, 3, pp. 1157–1182, 2003.
[22] R. Kohavi and G. H. John, “Wrappers for feature
subset selection,” Artificial Intelligence, 97, pp. 273–
324, 1997.
[23] H. Liu and H. Motoda (eds.), Computational Methods of Feature Selection, CRC Press, 2007.
[24] G. M. Furnival and R. W. Wilson, “Regressions
by leaps and bounds,” Technometrics, 42, pp. 69–79,
2000.
[25] H. Konno and R. Yamamoto, “Choosing the best
set of variables in regression analysis using integer
programming,” Journal of Global Optimization, 44,
pp. 273–282, 2009.
[26] R. Miyashiro and Y. Takano, “Subset selection
by Mallows’ Cp : A mixed integer programming
approach,” Expert Systems with Applications, 42,
pp. 325–331, 2015.
[27] R. Miyashiro and Y. Takano, “Mixed integer
second-order cone programming formulations for variable selection in linear regression,” European Journalof Operational Research, 247, pp. 721–731, 2015.
[28] R. Mazumder and P. Radchenko, “The discrete
Dantzig selector: Estimating sparse linear models via
mixed integer linear optimization,” IEEE Transactions on Information Theory, 63, pp. 3053–3075, 2017.
[29] D. Bertsimas and A. King, “Logistic regression:
From art to science,” Statistical Science, 32, pp. 367–
384, 2017.
[30] T. Sato, Y. Takano, R. Miyashiro and A. Yoshise,“Feature subset selection for logistic regression via
mixed integer optimization,” Computational Optimization and Applications, 64, pp. 865–880, 2016.
[31] T. Sato, Y. Takano and R. Miyashiro, “Piecewiselinear approximation for feature subset selection in asequential logit model,” Journal of the Operations Research Society of Japan, 60, pp. 1–14, 2017.
[32] S. Maldonado, J. Pérez, R. Weber and M. Labbé,“Feature selection for support vector machines via
mixed integer linear programming,” Information Sciences, 279, pp. 163–175, 2014.
[33] S. Benati and S. Garcı́a, “A mixed integer linear
model for clustering with variable selection,” Comput-

2018 年 3 月号

ers & Operations Research, 43, pp. 280–285, 2014.
[34] D. Bertsimas and J. Dunn, “Optimal classiﬁcation
trees,” Machine Learning, 106, pp. 1039–1082, 2017.
[35] D. Bertsimas and R. Shioda, “Algorithm for
cardinality-constrained
quadratic
optimization,”
Computational Optimization and Applications, 43,
pp. 1–22, 2009.
[36] K. Kimura and H. Waki, “Minimization of Akaike’s
information criterion in linear regression analysis
via mixed integer nonlinear program,” Optimization
Methods and Software, in press.
[37] B. Ustun and C. Rudin, “Supersparse linear integermodels for optimized medical scoring systems,” Machine Learning, 102, pp. 349–391, 2015.
[38] B. Ustun and C. Rudin, “Optimized risk scores,” In
Proceedings of the 23rd ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining(KDD’17), pp. 1125–1134, 2017.
[39] T. Sato, Y. Takano and T. Nakahara, “Using mixed
integer optimisation to select variables for a store
choice model,” International Journal of Knowledge
Engineering and Soft Data Paradigms, 5, pp. 123–134,
2016.
[40] T. Sato, Y. Takano and T. Nakahara, “Investigating consumers’ store-choice behavior via hierarchicalvariable selection,” arXiv preprint, arXiv:1704.00665,
2017.
[41] W. Jian, L. Zhu, Z. Xu and X. Chen, “A variableselection method for soft sensor development throughmixed integer quadratic programming,” Chemometrics and Intelligent Laboratory Systems, 167, pp. 85–
95, 2017.
[42] M. J. Willis and M. von Stosch, “L0-constrained
regression using mixed integer linear programming,”
Chemometrics and Intelligent Laboratory Systems,
165, pp. 29–37, 2017.
[43] Z. T. Wilson and N. V. Sahinidis, “The ALAMO
approach to machine learning,” Computers & Chemical Engineering, 106, pp. 785–795, 2017.
[44] S. Maldonado, J. Pérez and C. Bravo, “Cost-based
feature selection for support vector machines: An application in credit scoring,” European Journal of Operational Research, 261, pp. 656–665, 2017.
[45] T. Hastie, R. Tibshirani and R. J. Tibshirani, “Extended comparisons of best subset selection, forward
stepwise selection, and the lasso,” arXiv preprint,
arXiv:1707.08692, 2017.
[46] F. A. Al-Khayyal and J. E. Falk, “Jointly constrained biconvex programming,” Mathematics of Operations Research, 8, pp. 273–286, 1983.
[47] G. P. McCormick, “Computability of global solutions to factorable nonconvex programs: Part
I—Convex underestimating problems,” Mathematical
Programming, 10, pp. 147–175, 1976.
[48] M. J. Todd, “Semideﬁnite optimization,” Acta Numerica, 10, pp. 515–560, 2001.
[49] L. Vandenberghe and S. Boyd, “Semideﬁnite programming,” SIAM Review, 38, pp. 49–95, 1996.
[50] T. Gally, M. E. Pfetsch and S. Ulbrich, “A framework for solving mixed-integer semideﬁnite programs,”
Optimization Methods and Software, in press.

c by ORSJ. Unauthorized reproduction of this article is prohibited.（9）Copyright 133