4.非線形計画
2019/6/7 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.
2019/6/7 4
局所的最適解と大域的最適解
) ( x f
a S b c
は大域的最適解 は局所最適解,とくに
b
c
b
a , ,
局所的最適解と大域的最適解
) ( x f
は大域的最適解 は局所最適解,とくに
b
c b a , ,
局所最適解は各点での近傍での(大域的)最適解
a S b c
2019/6/7 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
錐2019/6/7 8
凸集合と凸関数
凸関数の定義(
f
が凸関数)
1 ( ) 1 ( )
1 0
,
, y R f x y f x f y
x n
凸関数 凸でない
x y x y
2019/6/7 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
2019/6/7 12
線形関数は凸関数
凸多面体(線形等式・不等式で表現)は凸集合 線形計画問題は凸計画
凸計画の例:凸二次計画,半正定値計画,二 次錐計画など
凸計画でないとき:大域解を求めるのは難しい 非線形最適化のアルゴリズム
→
一般には局所的最適解を求める関数の勾配とヘッセ行列
x
) ( x
f y
) ( y
f ) z
( z
f
その点で,関数が最も増加する方向を表す 勾配(ベクトル)は等高線と直交
勾配の定義
f
の等高線とするとき
2019/6/7 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
とすると2019/6/7 16
関数
f
のx
でのテーラー展開(1変数の場合)
制約なし最小化問題の最適性条件
明らかに,局所(最小)解では勾配は0
証明は簡単なので演習問題
) (
min f x
0 )
( *
f x
2019/6/7 18
停留点(勾配が0の点)
) ( x f
a b c
は局所最小値
c
b a , ,
p q
は局所最大値
q
p,
s
い(鞍点)
は最小でも最大でもな
s
1次の必要条件
:
0 )
( *
f x
2次の必要条件
局所的最小解では
【証明】
:
半正定値) ( *
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
2019/6/7 20
2次の十分条件
【証明】
は局所最小解 正定値
かつ
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
小さくとると を十分
より,
ので,
な
定値なので,
が正
す 2次の必要条件を満た
いが,
は最大でも最小でもな
0
)
(
3
x
x x
f
さない 2次の十分条件を満た
は大域的最小値
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
2019/6/7 22
演習課題
1.制約なし最小化問題
の局所最小解 において, となることを示 せ.
2.
2
変数関数は凸関数かどうか調べよ.また大域的最小解があれ ば求めよ.
締切: