４．非線形計画
2018/6/15 2
非線形計画問題
n n
n f R R S R
R x
S x
x f
, :
, s.t.
) ( min
ただし
） 実行可能解（
） 実行可能集合（
solution feasible
:
set feasible
: S x
S
は 不等式制約 等式制約
その他の制約
ただし， と数式で表されることが多い
s.t.
2018/6/15 4
局所的最適解と大域的最適解
) ( x f
a S b c
は大域的最適解 は局所最適解，とくに
b
c
b
a , ,
局所的最適解と大域的最適解
) ( x f
は大域的最適解 は局所最適解，とくに
b
c b a , ,
局所最適解は各点での近傍での（大域的）最適解
a S b c
2018/6/15 6
凸集合と凸関数
凸集合の定義（
S
が凸集合） y S
x S
y
x , , 0 1 1
凸集合 凸でない
x x
y y
凸集合の例
一点のみ
全空間，空集合
部分空間，アフィン空間
線形方程式・不等式の組で表される集合(
凸 多面体)
二次錐（Lorentz
錐）→SOCP
半正定値対称行列全体の集合→SDP
など
二次錐計画Second Order Cone Programming, SOCP
x
2x
10
2
のとき n
x
3x
20
3
のとき n
x
1二次錐
Lorentz
錐2018/6/15 8
凸集合と凸関数
凸関数の定義（
f
が凸関数）
1 ( ) 1 ( )
1 0
,
, y R f x y f x f y
x n
凸関数 凸でない
x y x y
2018/6/15 10
凸関数の例
線形関数（アフィン関数）
二次関数 ただし，は半正定値対称
指数関数 ，対数関数 ，負のエント ロピー
ノルム ， ， などが凸関数のとき，
f
を凹関数という凸計画問題（目的関数が凸関数，実行可能領 域が凸集合）では
局所最適解は大域的最適解
【証明】
反する が局所解であることに
に近づけると，
を
定義より したがって，凸関数の
凸集合の定義より，
大域解とする 大域的でない局所解，
*
*
*
*
*
*
*
*
*
*
*
*
1
) ( )
( ) 1
( ) ( )
1 (
) 1
( 1
0
) ( )
( :
:
x
x f y
f x
f y
x f
S y
x
y f x
f y
x
2018/6/15 12
線形関数は凸関数
凸多面体（線形等式・不等式で表現）は凸集合 線形計画問題は凸計画
凸計画の例：凸二次計画，半正定値計画，二 次錐計画など
凸計画でないとき：大域解を求めるのは難しい 非線形最適化のアルゴリズム
→
一般には局所的最適解を求める関数の勾配とヘッセ行列
x
) ( x
f y
) ( y
f ) z
( z
f
その点で，関数が最も増加する方向を表す 勾配（ベクトル）は等高線と直交
勾配の定義
f
の等高線とするとき
2018/6/15 14
ヘッセ行列の定義
例題
20 40
40 2
40 ) 120
(
) (
20
) (
40 )
1 (
) 2 (
) (
10 )
1 (
) (
1
1 2
2 1
2 2 2
1 2
2 1 2
2 2
1 2
2
2 2
1
2 2
1 1 1
2 1
2 2 2
1 2
1
x
x x
x x
f x
x f
x x
f x
f x
f
x x
x x
x x
x f x f x
f
x x
x x
f
とすると2018/6/15 16
関数
f
のx
でのテーラー展開（１変数の場合）
制約なし最小化問題の最適性条件
明らかに，局所（最小）解では勾配は０
証明は簡単なので演習問題
) (
min f x
0 )
( *
f x
2018/6/15 18
停留点（勾配が０の点）
) ( x f
a b c
は局所最小値
c
b a , ,
p q
は局所最大値
q
p,
s
い（鞍点）
は最小でも最大でもな
s
１次の必要条件
:
0 )
( *
f x
２次の必要条件
局所的最小解では
【証明】
:
半正定値) ( *
2 f x
となる．
を十分小さくとると より，
となるが，
が存在 なる
ると，
が半正定値でないとす
) ( )
(
0 ) (
) 2 (
) ( )
( )
(
0 0
) ( )
(
*
*
*
3
* 2
2 T T
*
*
*
* 2
T
* 2
x f d
x f
x f
O d
x f d
d x
f x
f d
x f
d d
x f d
x f
2018/6/15 20
２次の十分条件
【証明】
は局所最小解 正定値
かつ
2 * *
* ) 0 ( ) :
( x f x x
f
) ( )
(
) 2 (
) (
) 2 (
) ( )
( )
(
0 ) (
0 )
( 0
) (
*
*
3
* 2
2 T
*
3
* 2
2 T T
*
*
*
*
* 2
T
* 2
x f d
x f
O d
x f d
x f
O d
x f d
d x
f x
f d
x f
x f
d x f d
d x
f
小さくとると を十分
より，
ので，
な
定値なので，
が正
す ２次の必要条件を満た
いが，
は最大でも最小でもな
0
)
(
3
x
x x
f
さない ２次の十分条件を満た
は大域的最小値
0
)
(
4
x
x x
f
-3 -2 -1 0 1 2 3
-3 -2 -1 0 1 2 3
0
1
2
3
4
5
2018/6/15 22
演習課題
１．制約なし最小化問題
の局所最小解 において， となることを示 せ．
２．
2
変数関数は凸関数かどうか調べよ．また大域的最小解があれ ば求めよ．
締切：
