Computer aided ship design Computer aided ship design Part 3. Optimization Methods Part 3. Optimization Methods

[2008][11-2]

Computer aided ship design Computer aided ship design Part 3. Optimization Methods Part 3. Optimization Methods

November 2008 Prof. Kyu-Yeul Lee

Department of Naval Architecture and Ocean Engineering,

Seoul National University of College of Engineering

5.3

5.3 순차적 순차적 선형 선형 계획법 계획법

(Sequential Linear Programming)

(Sequential Linear Programming)

SLP(Sequential Linear Programming) SLP(Sequential Linear Programming)

¡ 현재의 설계점에서 주어진 목적 함수와 제약 조건을 선형화 하여 선형 계획 문제(LP problem)로 만든 후,

¡ 이를 풀어 설계 변수의 변화 정도를 얻어냄으로써 개선된 설계점을 구하는 방법

¡ 즉, 선형 계획 문제(Linear Programming) 문제를 연속적(Sequential)으로 풀어 최적해를 구하는 방법

) ( )

( )

1

(k k k

d x

x

⁺

= +

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

3

¡ 현재의 설계점에서 주어진 목적 함수와 제약 조건을 선형화 하여 선형 계획 문제(LP problem)로 만든 후,

¡ 이를 풀어 설계 변수의 변화 정도를 얻어냄으로써 개선된 설계점을 구하는 방법

¡ 즉, 선형 계획 문제(Linear Programming) 문제를 연속적(Sequential)으로 풀어 최적해를 구하는 방법

현재의 설계점

LP problem으로부터 구하는 설계 변수의 변화 정도 개선된

설계점

순차적

순차적 선형 선형 계획법 계획법(SLP; Sequential Linear Programming) (SLP; Sequential Linear Programming) 예제 예제 -- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(1) (1)

0 )

(

0 )

(

0 0 . 6 1

1 6

) 1 (

1 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

x g

x g

x x

g

x x x Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

초기 시작점은

x

⁽⁰⁾

= ( 1 , 1 ),

x ₂

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

4

최적해는

x

^*

= ( 3 , 3 ), f ( x

^*

) = - 3

초기 시작점은

x

⁽⁰⁾

= ( 1 , 1 ), 001

.

2

0

1

= e =

e

이고, 15%의 설계 변화가

허용된다고 가정

1 2 3 4

1 2 3 4

x ₁

A

B C

g

₂

= 0

g

₃

= 0

g

₁

= x

₁²

+ x

₂²

- 6.0 = 0 )

3 , 3

*

(

= x

x

⁽⁰⁾

= (1, 1)

f = -25 f = -20

f = -10 f = -3 f = -1

순차적

순차적 선형 선형 계획법 계획법 예제 예제

-- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(2) (2)

0 )

(

0 )

(

0 0 . 6 1

1 6

) 1 (

1 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

x g

x g

x x

g

x x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

2 3 4

x₂

C g

₂

= 0

) 3 , 3

*

( x =

f = -25 f = -20

f = -10 f = -3

(1) 반복 과정 1(k = 0) (i) 단계 1

f = -1

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

5

1 2 3 4

1

x₁

A B

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0 x

⁽⁰⁾

= (1, 1)

001 . 0 ),

1 , 1

(

_{1 2}

) 0

(

= e = e =

x

문제에서 주어진 초기 조건으로부터

2

1 3

2 3

(1,1) 1

(1,1) 0

(1,1) 1 0 (1,1) 1 0 f

g g g

= -

= - <

= - <

= - <

Æ 제약 조건 만족 Æ 제약 조건 만족 Æ 제약 조건 만족

(ii) 단계 2: 목적 함수와 제약 조건 함수의 값 계산

순차적

순차적 선형 선형 계획법 계획법 예제 예제

-- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(2) (2)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

( ) 0

g x x

g x

g x

= + - £

= - £

= - £ x

x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

(1) 반복 과정 1(k = 0)

(iii) 단계 3: LP 문제의 정의(목적함수를 선형화 한다.) _{1 2 3 4}

1 2 3 4

x₁ x₂

A B

C g₂= 0

g₃= 0 g₁= x₁²+ x₂²- 6.0 = 0

) 3 , 3

* (

= x

x⁽⁰⁾= (1, 1)

f = -25 f = -20

f = -10 f = -3 f = -1

001 . 0 ),

1 , 1

( _{1 2}

) 0

( = e =e =

x

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

6

g₃= 0

(0) (0) (0) (0) (0)

( ) ( )

^T

( )

f x + D x @ f x + Ñ f x D x Taylor 급수의 1차항(선형항)만 고려한 목적 함수

Minimize:

(0) (0) (0) (0) (0)

( ) ( )

^T

( )

f x + D x - f x @ Ñ f x D x

Minimize:

[ ]

^{( 0 )}

(0)

(0) (0) (0) 1

1 2 2 1 (0)

2

( ) ( ) 2 3 2 3 d

f f x x x x

d

é ù

+ - @ - - ê ú

ë û

x d x

x

Minimize:

(0) (0) (0) (0) (0) (0) (0)

1 2 1 2 1 2

( ) (2 3 ) (2 3 )

f d @ x - x d + x - x d

(0) (0) (0)

1 2

( )

f d @ - d - d

1 2

(0) (0)

, f

^T

é

_¶^¶_x^f _¶^¶_x^f

ù

D x = d Ñ = ë û

선형화 된 목적 함수

(0) =(1,1)

x

^대입

순차적

순차적 선형 선형 계획법 계획법 예제 예제

-- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(2) (2)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

( ) 0

g x x

g x

g x

= + - £

= - £

= - £ x

x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

(1) 반복 과정 1(k = 0)

(iii) 단계 3: LP 문제의 정의(제약조건을 선형화 한다.) _{1 2 3 4}

1 2 3 4

x₁ x₂

A B

C g₂= 0

g₃= 0 g₁= x₁²+ x₂²- 6.0 = 0

) 3 , 3

* (

= x

x⁽⁰⁾= (1, 1)

f = -25 f = -20

f = -10 f = -3 f = -1

001 . 0 ),

1 , 1

( _{1 2}

) 0

( = e =e =

x

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

7

g₃= 0

Taylor 급수의 1차항(선형항)만 고려한

Subject to: g_j(x⁽⁰⁾ + Dx⁽⁰⁾)Þ g_j(x⁽⁰⁾)+ Ñg_j^T(x⁽⁰⁾)Dx⁽⁰⁾ £0; j =1 to m

제약조건

(0) (0) (0)

( ) ( ); 1

T

j j

g g j to m

Ñ x Dx £ - x =

1 2

(0) (0) (0) (0) (0) (0)

, g

^T_j

é

^¶_¶^g_x^{j ¶}_¶^g_x^j

ù , g

^T_j

( ) g

_j

( ) g

_j

( )

D = Ñ = Ñ D = D =

ë û

x d x x x d

Subject to:

(0)

(0) 1 (0) 1 (0) 1 1 (0) 1 (0)

1 2 1 2

1 3 3 (0) 3 3

2

(0) (0)

1 2

(0) (0)

3 2

( ) 2

3

( ) 1

( ) 1

g x x d d d

d

g d

g d

é ù

é ù

Þ ë û ê ú = + £

ë û

Þ - £

Þ - £

d d d

2

1 3

2 3

(1,1)

(1,1) 1 (1,1) 1 g

g g

= -

= -

선형화 된 제약 조건 = -

를 이항하면 (

(0)

)

g x

j

순차적

순차적 선형 선형 계획법 계획법 예제 예제

-- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(3) (3)

Minimize Subject to

2

1

d

d f = - -

15 . 0 15

. 0

15 . 0 15

. 0

1 1

2 1 2

1

3 2 3 2

1 3 1

1

£

£ -

£

£ -

£ -

£ -

£ +

d d d

d

d d

0 )

(

0 )

(

0 0 . 6 1

1 6

) 1 (

1 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

x g

x g

x x

g

x x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

) 1 , 0 ( ),

0 , 1 (

), , ( ),

1 , 1 (

1 ) 1 , 1 ( , 1 ) 1 , 1 (

, ) 1 , 1 ( , 1 ) 1 , 1 (

3 2

3 1 3 1 1 3 2

3 2 1

-

= Ñ -

= Ñ

= Ñ - -

= Ñ

-

= -

=

-

= -

=

g g

g f

g g

g f

(iv) 단계 4: LP 문제의 풀이를 통한 탐색 방향(d⁽⁰⁾)의 결정

목적 함수 및

제약조건을 선형화

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

8

15 . 0 15

. 0

15 . 0 15

. 0

1 1

2 1 2

1

3 2 3 2

1 3 1

1

£

£ -

£

£ -

£ -

£ -

£ +

d d d

d

d d

) 1 , 0 ( ),

0 , 1 (

), , ( ),

1 , 1 (

1 ) 1 , 1 ( , 1 ) 1 , 1 (

, ) 1 , 1 ( , 1 ) 1 , 1 (

3 2

3 1 3 1 1 3 2

3 2 1

-

= Ñ -

= Ñ

= Ñ - -

= Ñ

-

= -

=

-

= -

=

g g

g f

g g

g f

설계 변수의 변화 범위에 대한 제약 조건

(move limit)

오른 쪽 그림으로부터

최적해를 구하면,

15 . 0 ,

15 .

0

₂

1

= d =

d

(프로그램을 이용할 경우에는

Simplex 방법을 이용하여 최적해를 구함)

6

d

₁

d

₂

1 2 3 4 5

-1 -2

-1 -2 1 2 3 4

A B

C

d

₁

=-1

d

₂

=-1 d

₁

+d

₂

=2

1 2 0

f = -d -d =

0.15

설계 변수의 변화 범위 (move limit)

제한

1 2 0.3

f = -d -d = -

탐색 방향이 결정 되었음

순차적

순차적 선형 선형 계획법 계획법 예제 예제

-- 부등호 부등호 제약 제약 조건이 조건이 있는 있는 경우 경우 풀이 풀이 예 예(5) (5)

(v) 단계 5: 수렴 기준의 검토(결정된 탐색 방향(d⁽⁰⁾)을 이용한다.)

) 001 . 0 ( 212

. 0 15

. 0 15

. 0

) 15 . 0 , 15 . 0 ( ) , (

2 2

2 )

0 (

2 1 )

0 (

=

>

= +

=

=

=

e d

d d d

이므로 수렴 기준을 만족하지 않음

(vi) 단계 6: 새로운 설계점의 결정 및 반복 횟수의 갱신

) 15 . 1 , 15 . 1 ( ) 15 . 0 , 15 . 0 ( ) 1 , 1

)

(

0 ( )

0 ( )

1 , 1 ( )

1

(

= x = x + d = + =

x

1 1 = +

= k k

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

9

0. 개선된 설계점을 찾았으므로, 0. 개선된 설계점을 찾았으므로,

1. 다시 개선된 설계점에서 주어진 문제를 선형 계획 문제로 근사화하고, 1. 다시 개선된 설계점에서 주어진 문제를 선형 계획 문제로 근사화하고,

2. 선형 계획 문제를 풀어서 탐색 방향(d)을 정한 뒤, 2. 선형 계획 문제를 풀어서 탐색 방향(d)을 정한 뒤,

3. 개선된 설계점을 찾는다.

3. 개선된 설계점을 찾는다.

(중지 조건: 단, 탐색 방향 d의 크기가 e 보다 작으면 탐색을 중지 한다.)

SLP(Sequential Linear Programming)

SLP(Sequential Linear Programming) 알고리즘의 알고리즘의 요약 요약

¡ 단계 1: k=0으로 둔다. x

⁽⁰⁾

으로 설계 변수의 초기값을 추정한다. 또한 제약 조건의 위배 정도와 수렴 기준으로 작은 수 e

₁

, e

₂

의 적절한 초기값을 선정한다.

¡ 단계 2: x

^(k)

에서 목적 함수, 제약 조건과 이들의 경사도(gradient)를 계산한다.

¡ 단계 3: x

^(k)

의 변화 범위(move limit) Dx

_il^(k)

, Dx

_iu^(k)

를 적절히 선정하고, 선형 계획 문제를 수학적으로 정의한다. 즉,

¡ 단계 4: 앞서 정의된 선형 계획 문제를 Simplex 방법으로 풀어 d

^(k)

를 구한다.

¡ 단계 5: 수렴 여부를 확인한다. 즉, g

_i

£ e

₁

(i = 1 to m), |h

_i

| £ e

₁

(i = 1 to p), 그리고 ççd

^(k)

çç£ e

₂

인지 확인하여 그렇다면 현재의 x

^(k)

가 최적해라고 가정하고 종료한다.

그렇지 않다면 다음 단계로 간다.

¡ 단계 6: 새로운 설계 변수 x

^(k+1)

= x

^(k)

+ Dx

^(k)

로, 반복 횟수 k = k+1로 수정하고 단계 2로 간다.

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

10

¡ 단계 1: k=0으로 둔다. x

⁽⁰⁾

으로 설계 변수의 초기값을 추정한다. 또한 제약 조건의 위배 정도와 수렴 기준으로 작은 수 e

₁

, e

₂

의 적절한 초기값을 선정한다.

¡ 단계 2: x

^(k)

에서 목적 함수, 제약 조건과 이들의 경사도(gradient)를 계산한다.

¡ 단계 3: x

^(k)

의 변화 범위(move limit) Dx

_il^(k)

, Dx

_iu^(k)

를 적절히 선정하고, 선형 계획 문제를 수학적으로 정의한다. 즉,

¡ 단계 4: 앞서 정의된 선형 계획 문제를 Simplex 방법으로 풀어 d

^(k)

를 구한다.

¡ 단계 5: 수렴 여부를 확인한다. 즉, g

_i

£ e

₁

(i = 1 to m), |h

_i

| £ e

₁

(i = 1 to p), 그리고 ççd

^(k)

çç£ e

₂

인지 확인하여 그렇다면 현재의 x

^(k)

가 최적해라고 가정하고 종료한다.

그렇지 않다면 다음 단계로 간다.

¡ 단계 6: 새로운 설계 변수 x

^(k+1)

= x

^(k)

+ Dx

^(k)

로, 반복 횟수 k = k+1로 수정하고 단계 2로 간다.

) ( )

( )

( k

iu k

i k

il

x x

x £ D £ D

D

제약

제약 최적화 최적화 문제의 문제의 선형화 선형화

(Linear Programming Problem) (Linear Programming Problem)

) ( )

( )

( )

( )

( ) ( ) ( )

( ^{k k} f ^k f ^{T k k}

f x + D x @ x + Ñ x D x Minimize

m to j

g g

g

p to j

h h

h

k T k

j k

j k

k j

k T k

j k

j k

k j

1

; 0 )

( )

( )

(

1

; 0 )

( )

( )

(

) ( )

( )

( )

( )

(

) ( )

( )

( )

( )

(

=

£ D

Ñ +

@ D

+

=

= D

Ñ +

@ D

+

x x

x x

x

x x

x x

Subject to x

Taylor 급수의 1차항(선형항)만 고려한 목적 함수

Taylor 급수의 1차항(선형항)만 고려한 등호 제약 조건

Taylor 급수의 1차항(선형항)만 고려한 부등호 제약 조건

여기서,

) (

) ( )

( )

(

) ( )

( )

( )

( )

(

, / ) (

, / ) (

, / ) (

), (

), (

), (

) (

k i i

i k

j ij

i k

j ij

i k

i

k j j

k j j

k k

k

x d

x g

a x h

n x f

c

g b

h e

f f

f

D

=

¶

¶

=

¶

¶

=

¶

¶

=

-

= -

= -

D +

=

x x

x

x x

x x

x

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

11

여기서,

) (

) ( )

( )

(

) ( )

( )

( )

( )

(

, / ) (

, / ) (

, / ) (

), (

), (

), (

) (

k i i

i k

j ij

i k

j ij

i k

i

k j j

k j j

k k

k

x d

x g

a x h

n x f

c

g b

h e

f f

f

D

=

¶

¶

=

¶

¶

=

¶

¶

=

-

= -

= -

D +

=

x x

x

x x

x x

x

라고 가정하면

å

=

=

n

i

i i d c f

1

Minimize

m to j

b d

a

p to j

e d

n

j i

n

i

ij

j i

n

i

ij

1

;

1

;

1 1

=

£

=

=

å å

=

=

Subject to

Matrix form

Minimize Subject to

) 1 ) (

1

( ´ ´

= ^{T n} _n

f c d

) 1 ( )

1 ) (

(

) 1 ( )

1 ) (

(

´

´ ´

´

´ ´

£

=

m n n

m T

p n n

T p

b d

A

e d

N

Æ 선형 계획 문제(Linear Problem) Æ Simplex 방법을 이용해 해결 가능

) (

_il^(k) _i^(k) _iu^(k)

iu i

il

d d x x x

d £ £ D £ D £ D

: 선형화 된 목적 함수

: 선형화 된 등호 제약 조건 : 선형화 된

부등호 제약 조건

SLP

SLP 방법의 방법의 한계점 한계점

¡ 설계 변수의 변화 범위 (move limit)을 사용자가 주어야 함

¡ 설계 변수의 변화 범위가 작을 경우 최적해를 찾는 데에 많은 시간이 소요됨

¡ 반면, 설계 변수의 변화 범위가 클 경우 최적해를 못 찾을 수도 있음

) (x

f

원래의 목적 함수

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

12

)

x

1 ( +n ) x

x(n ) 2 ( +n

x

선형화 된 목적 함수 선형화 된 목적 함수

Æ 개선된 해를 찾지 못하고 진동(oscillation)함

5.4 CSD(Constrained Steepest 5.4 CSD(Constrained Steepest Descent)

Descent) 방법 방법

최적화

최적화 문제의 문제의 분류와 분류와 해법 해법

비제약 최적화 문제 제약 최적화 문제

선형 비선형 선형 비선형

목적 함수 (예시) 제약 조건

(예시)

^{없음 없음}

① 직접 탐사법 - Hooke&Jeeves - Nelder&Mead

② Gradient 방법

- Steepest Descent방법⁴⁾

- 공액 경사도 방법⁴⁾(Conjugate Gradient 방법)

- Newton 방법⁵⁾

- Davidon-Fletcher-Powell(DFP) 방법⁵⁾

- Broyden-Fletcher-Goldfarb- Shanno(BFGS) 방법⁵⁾

- Penalty Function¹⁾을 구성한 후 비제약 최적화 문제 로 변환한 후 해를 구함

2 1 2 2 2

1 3

)

( x x x x

f x = + -

2 1 2 2 2

1 3

)

( x x xx

f x = + -

1 2

( ) 2

f x = x + x f( )x =x₁+2x₂

1 2

1

( ) 5 0

( ) 0

h x x

g x

= + =

= - £ x

x

minimize f(x) minimize f(x) minimize f(x) minimize f(x)

2 2

1 1 2

2 1

1 1

( ) 1.0 0

6 6

( ) 0

g x x

g x

= + - £

= - £ x

x

2 1 2 2 2

1 3

)

( x x x x

f x = + - minimize f(x)

1 2

1

( ) 5 0

( ) 0

h x x

g x

= + =

= - £ x

x

Penalty Function으로 해를 구할 수 있으나 일반적으로 선형 계획법을 사용

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

14

국부 최적 화 방법

① 직접 탐사법 - Hooke&Jeeves - Nelder&Mead

② Gradient 방법

- Steepest Descent방법⁴⁾

- 공액 경사도 방법⁴⁾(Conjugate Gradient 방법)

- Newton 방법⁵⁾

- Davidon-Fletcher-Powell(DFP) 방법⁵⁾

- Broyden-Fletcher-Goldfarb- Shanno(BFGS) 방법⁵⁾

- Simplex 방법 (선형 계획법,

Linear Programming)

- 2차 계획 법

(Quadratic Programming)

- 근사화 방법 – SLP

선형 계획 문제²⁾로 근사화 후 개선된 탐색점을 찾고, 그 점에서 다시 선형 계획 문제를 푸는 방법

- 근사화 방법 – SQP 2차 계획 문제³⁾로 근사화 후 개선된 탐색점을 찾고, 그 점에서 다시 2차 계획 문 제를 푸는 방법

전역 최적 화 방법

Genetic Algorithms(GA), Simulated Annealing, etc.

2) 선형 계획 문제

(Linear Programming Problem) 목적함수: 1차 형식 제약조건: 1차 형식

3) 2차 계획 문제

(Quadratic Programming Problem) 목적함수: 2차 형식 제약조건: 1차 형식

1) Penalty Function

제약 조건의 위배량을 원래 목적 함수에 더한

수정된 목적 함수

4) Gradient 방법 중 함수의 1차 미분만을

고려하는 방법

5) Gradient 방법 중 함수의 2차 미분까지

고려하는 방법

Penalty Function으로 해를 구할 수 있으나 일반적으로 선형 계획법을 사용

순차적 순차적 22차 차 계획법 계획법(SQP; Sequential Quadratic Programming) (SQP; Sequential Quadratic Programming)과 과 CSD(Constrained Steepest Descent)

CSD(Constrained Steepest Descent) 방법 방법

¡ 순차적 2차 계획법(SQP; Sequential Quadratic Programming)

— ① 현재의 설계점에서 주어진 목적 함수와 제약 조건을 2차 계획

문제*로 만든 후, 이를 해결하여 탐색 방향(search direction) d

^(k)

를 구함

— ② 제약 조건의 위배량을 원래 목적 함수에 더한 수정된 목적 함수(강하 함수; Descent Function) 를 최소화하는 최적의 이동 거리(step size) α

_k

를 1차원 탐색 방법(예: 황금분할법)을 이용하여 찾아 더 나은

설계점을 구함

— ③ 개선된 설계점에서 다시 ①로 되돌아감

— 즉, 이차 계획 문제(Quadratic Programming) 문제를 연속적(Sequential)으로 풀어 최적해를 구하는 방법

¡ CSD(Constrained Steepest Descent) 방법

— SQP의 일종이다.

— 2차 계획 문제를 만들 때, 2차 미분 값에 해당하는 Hessian Matrix를 Identity Matrix로 가정한다.

— Pshenichny의 강하 함수(Descent Function)를 사용한다.

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

15

¡ 순차적 2차 계획법(SQP; Sequential Quadratic Programming)

— ① 현재의 설계점에서 주어진 목적 함수와 제약 조건을 2차 계획

문제*로 만든 후, 이를 해결하여 탐색 방향(search direction) d

^(k)

를 구함

— ② 제약 조건의 위배량을 원래 목적 함수에 더한 수정된 목적 함수(강하 함수; Descent Function) 를 최소화하는 최적의 이동 거리(step size) α

_k

를 1차원 탐색 방법(예: 황금분할법)을 이용하여 찾아 더 나은

설계점을 구함

— ③ 개선된 설계점에서 다시 ①로 되돌아감

— 즉, 이차 계획 문제(Quadratic Programming) 문제를 연속적(Sequential)으로 풀어 최적해를 구하는 방법

¡ CSD(Constrained Steepest Descent) 방법

— SQP의 일종이다.

— 2차 계획 문제를 만들 때, 2차 미분 값에 해당하는 Hessian Matrix를 Identity Matrix로 가정한다.

— Pshenichny의 강하 함수(Descent Function)를 사용한다.

CSD

CSD 알고리즘 알고리즘 요약 요약

x₁ x₂

최적해

현재 설계점

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

개선된 설계점에서 부터 과정 1을 다시 수행한다.

과정 2 현재 설계점에서

2차 계획 문제(QP)로 근사화 한다.

과정

1

1차 형식으로 근사화된 제약 조건 개선된 설계점

x₁ x₂

현재 설계점 2차 형식으로 근사화된

목적 함수

CSD에서는 2차 미분 값에 해당하는 Hessian Matrix를 Identity Matrix로 가정하기 때문에 목적 함수가 2변수 함수라면 동심원 모양으로 근사화 된다.

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

16

x₁ x₂

d⁽⁰⁾

x₁ x₂

d⁽⁰⁾ - Penalty Function:

제약 조건의 위배량을 원래 목적 함수에 더한 수정된 목적 함수

(제약 최적화 문제를 비제약 최적화 문제로 변경)

- 1차원 탐색의 예: 황금 분할법

개선된 설계점에서 부터 과정 1을 다시 수행한다.

종료 조건

탐색 방향의 크기 |d⁽⁰⁾|가 0으로 수렴하면

탐색을 종료한다.

2차 계획 문제(QP)를 풀어서 탐색 방향(d⁽⁰⁾)을 찾는다.

과정 2

Penalty Function을

정의한 후 탐색 방향으로 1차원 탐색을 수행하여 탐색 거리를 결정한다.

과정

3

개선된 설계점

[[참고 참고]]목적 목적 함수가 함수가 22변수 변수 함수인 함수인 경우 경우 Hessian Matrix Hessian Matrix를 를 Identity Matrix

Identity Matrix로 로 가정하면 가정하면 동심원 동심원 모양으로 모양으로 근사화되는 근사화되는 이유 이유

QP 문제의 정의(목적함수를 2차 형식으로 근사화 한다.)

(0) (0) (0) (0) (0) (0) (0)

( ) ( )

^T

( ) 0.5

^T

f x + D x - f x @ Ñ f x D x + D x H x D

Minimize:

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

(0) (0) (0) (0) (0) (0) (0)

( ) ( )

^T

( ) 0.5

^T

f x + D x @ f x + Ñ f x D x + D x H x D

Minimize:

Taylor 급수의 2차항까지

고려한 목적 함수

1 2

(0) (0)

, f

^T

é

_¶^¶_x^f _¶^¶_x^f

ù ,

D x = d Ñ = ë û H = I

(CSD 방법에서는 Hessian Matrix를 Identity Matrix로 가정함)

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

17

( 0 )

(0)

(0) (0) (0) 1 (0)2 (0)2

1 2

(0)

1 2 2

( ) ( ) f f d 0.5( )

f f d d

x x d

é ù é ¶ ¶ ù

+ - @ ê ú ê ú + +

¶ ¶

ë û

x

ë û

x d x

Minimize:

(0) (0)

(0) (0) (0) (0)2 (0)2

1 2 1 2

1 2

( ) ( )

( ) f f 0.5( )

f d d d d

x x

¶ ¶

@ + + +

¶ ¶

x x

d

1 2

(0) (0)

, f

^T

é

_¶^¶_x^f _¶^¶_x^f

ù ,

D x = d Ñ = ë û H = I

(CSD 방법에서는 Hessian Matrix를 Identity Matrix로 가정함)

상수 c

₁

으로 치환 상수c

₂

로 치환

(0) (0) (0) (0)2 (0)2

1 1 2 2 1 2

( ) 0.5( )

f d @ c d + c d + d + d

원의 방정식과 같은 형태이다.

2 2

1 2 1 1 2 2 3

0

x + x + c x + c x + c =

원의 방정식:

[[복습 복습] 1 ] 1변수 변수 함수의 함수의 최적성 최적성 조건 조건 -- 1 1계 계 필요 필요 조건 조건(1) (1)

§ 변수가 하나일 때, 극값을 가질 필요 조건 : f ' ( x ^* ) = 0

R x

dx x x f x d

dx x x x df

f x

f = + - +

₂

-

^{* 2}

+

* 2

*

*

*

( ) ( )

2 ) 1 ) (

) ( ( )

(

pf) 주어진 점

x ^*

에서 f(x)의 테일러 급수는 다음과 같다.

나머지항(Remainder) : 가 에 충분히

가까우면 그 값이 매우 작음

d x

x - ^* =

^{라고 놓으면}

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

18

나머지항(Remainder) : 가 에 충분히

가까우면 그 값이 매우 작음

x *

d x x

x - ^* =

^{라고 놓으면}

R d

x f

d x f x

f x

f =

^*

+

^*

+ '' (

^*

)

²

+ 2

) 1 ( ' )

( )

(

) ( )

( )

( x f x ^* f x f - = D

함수 값의 변화량

R d

x f

d x f x

f = + +

D

^*

'' (

^*

)

²

2 ) 1

( ' )

(

[[복습 복습] 2 ] 2변수 변수 함수의 함수의 테일러 테일러 전개 전개(Taylor Series Expansion)(1) (Taylor Series Expansion)(1)

R x

x x x f

x x x x

x x f

x x f

x x x

x f x x

x f x f x

x f

÷÷ + ø ö çç è

æ -

¶ + ¶ -

¶ -

¶ + ¶

¶ - + ¶

¶ - + ¶

¶ - + ¶

=

2

* 2 2 2

2 2

* 2 2

* 1 1 2 1

2 2

* 1 2 1

1 2

* 2 2 2

* 1 1 1

* 2

* 1 2

1

) (

) )(

( 2

) 2 (

1

) (

) (

) , ( )

, (

2변수 함수

f ( x

₁

, x

₂

)

에 대한 점

( x

₁^*

, x

₂^*

)

에서의 테일러 전개식

Æ

각 항을 다시 표현하면

*

1 1 1

* * * *

1 1 2 2 *

2 2

1 2

2

( ) ( ) ( ) ( )

T

T

f

x x x

f f

x x x x f

f x x

x x

x é¶ ù

ê¶ ú é - ù

¶ - + ¶ - =ê ú ê ú= Ñ -

¶

ê ú -

¶ ¶ ê¶ ú êë úû

ë û

x x x

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

19

( ) ( ) ^R

f f

f =

^*

+ Ñ

^{* T}

-

^*

+ -

^{* T}

(

^*

) -

^*

+ 2

) 1 (

) ( )

( )

( x x x x x x x H x x x

(

2 2

)

* 2

* 1

* 2

1

, ) , ( , ) ,

( = Î

_´

= x x

^T

x x x

^T

H M x

2x2 Matrix의 원소

*

1 1 1

* * * *

1 1 2 2 *

2 2

1 2

2

( ) ( ) ( ) ( )

T

T

f

x x x

f f

x x x x f

f x x

x x

x é¶ ù

ê¶ ú é - ù

¶ - + ¶ - =ê ú ê ú= Ñ -

¶

ê ú -

¶ ¶ ê¶ ú êë úû

ë û

x x x

2 2 2 2 2 2 2 *

1 1

* 2 * * * 2 * * * *

1 1 1 1 2 2 2 2 1 1 2 2 1 1 2 2 *

2 2 2 2

2 2

1 1 2 2 1 2 1 1 2 2

2 2

2

1 1 2

* *

1 1 2 2 2

1 1

( ) 2 ( )( ) ( ) ( ) ( ) ( ) ( )

2 2

1 2

x x

f f f f f f f

x x x x x x x x x x x x x x x x

x x

x x x x x x x x x x

f f

x x x

x x x x

é - ù

æ¶ ¶ ¶ ö é¶ ¶ ¶ ¶ ù

- + - - + - = - + - - + - ê ú

ç ¶ ¶ ¶ ¶ ÷ ê¶ ¶ ¶ ¶ ¶ ¶ úê - ú

è ø ë û ë û

¶ ¶

¶ ¶ ¶

é ù

= ë - - û ¶

( ) ( )

*

1 1

2 *

2 2

2

2 1 2

* * *

1 ( )

2

T

x x x x

f f

x x x

é ù

ê ú

é - ù

ê ú

ê ú

ê ¶ úêë - úû

ê ú

¶ ¶ ¶

ê ú

ë û

= x x- H x x x-

CSD(Constrained Steepest Descent)

CSD(Constrained Steepest Descent) 방법을 방법을 이용한 이용한 풀이 풀이 예 예(1) (1)

0 )

(

0 )

(

0 0 . 6 1

1 6

) 1 (

1 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

x g

x g

x x

g

x x x Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

^최적해는

x

^*

= ( 3 , 3 ), f ( x

^*

) = - 3

x₂

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

20

1 2 3 4

1 2 3 4

x₁

A

B C

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

(

= x

x

⁽⁰⁾

= (1, 1)

f = -25 f = -20

f = -10 f = -3

2

1 3

2 3

(1,1) 1

(1,1) 0

(1,1) 1 0 (1,1) 1 0 f

g g g

= -

= - <

= - <

= - <

Æ 제약 조건 만족 Æ 제약 조건 만족 Æ 제약 조건 만족

(i) 단계 1: 목적 함수와 제약 조건 값의 계산 (1) 반복 과정 1(k = 0)

초기 시작점은

x

⁽⁰⁾

= (1,1)

^{이라 가정}

CSD(Constrained Steepest Descent)

CSD(Constrained Steepest Descent) 방법을 방법을 이용한

이용한 풀이 풀이 예 예(2) (2)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

( ) 0

g x x

g x

g x

= + - £

= - £

= - £ x

x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

(1) 반복 과정 1(k = 0)

(ii) 단계 2: QP 문제의 정의(목적함수를 2차 형식으로 근사화 한다.)

1 2 3 4

1 2 3 4

x₁ x₂

A B

C g₂= 0

g₃= 0 g₁= x₁²+ x₂²- 6.0 = 0

) 3 , 3

* (

= x

x⁽⁰⁾= (1, 1)

f = -25 f = -20

f = -10 f = -3 f = -1 (0) =(1,1)

x

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

21

g₃= 0

(0) (0) (0) (0) (0) (0) (0)

( ) ( )

^T

( ) 0.5

^T

f x + D x - f x @ Ñ f x D x + D x H x D

Minimize:

[ ]

^{( 0 )}

(0)

(0) (0) (0) 1 (0)2 (0)2

1 2 2 1 (0) 1 2

2

( ) ( ) 2 3 2 3 d 0.5( )

f f x x x x d d

d é ù

+ - @ - - ê ú + +

ë û

x d x

x

Minimize:

(0) (0) (0) (0) (0) (0) (0) (0)2 (0)2

1 2 1 2 1 2 1 2

( ) (2 3 ) (2 3 ) 0.5( )

f d @ x - x d + x - x d + d + d

(0) (0) (0) (0)2 (0)2

1 2 1 2

( ) 0.5( )

f d @ - d - d + d + d

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

(0) (0) (0) (0) (0) (0) (0)

( ) ( )

^T

( ) 0.5

^T

f x + D x @ f x + Ñ f x D x + D x H x D

Minimize:

Taylor 급수의 2차항까지

고려한 목적 함수

1 2

(0) (0)

, f

^T

é

_¶^¶_x^f _¶^¶_x^f

ù ,

D x = d Ñ = ë û H = I

(CSD 방법에서는 Hessian Matrix를 Identity Matrix로 가정함)

1차항까지 근사화한 목적 함수 2차항까지 근사화한 목적 함수

CSD(Constrained Steepest Descent)

CSD(Constrained Steepest Descent) 방법을 방법을 이용한

이용한 풀이 풀이 예 예(3) (3)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

( ) 0

g x x

g x

g x

= + - £

= - £

= - £ x

x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

(1) 반복 과정 1(k = 0)

1 2 3 4

1 2 3 4

x₁ x₂

A B

C g₂= 0

g₃= 0 g₁= x₁²+ x₂²- 6.0 = 0

) 3 , 3

* (

= x

x⁽⁰⁾= (1, 1)

f = -25 f = -20

f = -10 f = -3 f = -1

(0) = (1,1) x

(ii) 단계 3: QP 문제의 정의(제약조건을 선형화 한다.)

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

22

g₃= 0

Taylor 급수의 1차항(선형항)만 고려한

Subject to:

g

j

⁽ x

⁽⁰⁾

+ D x

⁽⁰⁾

⁾ @ g

j

⁽ x

⁽⁰⁾

⁾ + Ñ g

j^T

⁽ x

⁽⁰⁾

⁾ D x

⁽⁰⁾

£ ^0; j = ¹ to m 제약조건

(0) (0) (0)

( ) ( ); 1

T

j j

g g j to m

Ñ x D x £ - x =

Subject to:

(0)

(0) 1 (0) 1 (0) 1 1 (0) 1 (0)

1 2 1 2

1 3 3 (0) 3 3

2

(0) (0)

2 1

(0) (0)

2 3

( ) 2

3

( ) 1

( ) 1

g x x d d d

d

g d

g d

é ù

é ù

Þ ë û ê ú = + £

ë û

Þ - £

Þ - £

d d d

2

1 3

2

3

(1,1)

(1,1) 1 (1,1) 1 g

g g

= -

= -

선형화 된 제약 조건 = -

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

탐색 방향(d

⁽⁰⁾

)을 결정하기 위하여 주어진 문제를 2차 계획 문제로 근사화 한다.

1 2

(0) (0) (0) (0) (0) (0)

, g

^T_j

é

^¶_¶^g_x^{j ¶}_¶^g_x^j

ù , g

^T_j

( ) g

_j

( ) g

_j

( )

D = Ñ = Ñ D = D =

ë û

x d x x x d

를 이항하면 (

(0)

)

g x

j

(iii) 단계 3: QP 문제의 풀이를 통한 탐색 방향(d⁽⁰⁾)의 결정

CSD(Constrained Steepest Descent)

CSD(Constrained Steepest Descent) 방법을 방법을 이용한

이용한 풀이 풀이 예 예(4) (4)

Minimize Subject to

) (

5 . 0 )

( d

₁

d

₂

d

₁²

d

₂²

f = - - + +

1 1

2 1

3 2 3 2

1 3 1

1

£ -

£ -

£ +

d d

d

j d

k

) 1 , 0 ( ), 0 , 1 (

), , ( ), 1 , 1 (

1 ) 1 , 1 ( , 1 ) 1 , 1 (

, ) 1 , 1 ( , 1 ) 1 , 1 (

3 2

3 1 3 1 1 3 2

3 2 1

-

= Ñ -

= Ñ

= Ñ - -

= Ñ

-

= -

=

-

= -

=

g g

g f

g g

g f

1

,

1 _{2 2}

1

1=x - d =x -

d

여기서,

0 )

(

0 )

(

0 0 . 6 1

1 6

) 1 (

2 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

x g

x g

x x

g

x x x

Minimize

Subject to

2 1 2

2 2

1

3

)

( x x x x

f x = + -

제약 최적화 문제 (근사화 하기 전) 2차 계획 문제

2차 계획 문제의 정의 - 목적 함수: 2차 형식 - 제약 조건: 1차 형식

선박기본설계개론

선박기본설계개론, 2006.3Computer Aided Ship Design 2008 Computer Aided Ship Design 2008 –– PART III: Optimization Methods, 2006.3 PART III: Optimization Methods _NAOE/SNU

23

) 1

(

) 1

(

] )

2 (

[

) (

5 . 0 ) (

2 3 2

3

2 2 1

2

2 1 2

3 1 1 1

2 2 2

1 2

1

s d

u

s d

u

s d

d u

d d

d d L

+ - - +

+ - - +

+ - +

+

+ +

- -

=

Lagrange 함수

k

Kuhn-Tucker 필요 조건:

l

(0)

1 2 3 (0)

1 2 3

(0)

1 2

( , , ) (0, 0, 0), ( , , )

(0,1.414,1.414), ( , ) (1,1)

u u u s s s

d d

= =

=

=

= =

u s

d

최적해를 구하면

*실제 프로그램에서는 Simplex 방법을 이용하여 최적해를 구함

0 s

u

d =

Ñ L ( , , )

탐색 방향이 결정 되었음

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1 2

1 2 1

3

2

1 2

2

2 3

1 0

1 0

2 0

1 0

1 0

0, 0, 1, 2, 3

i

L d

L d

L u

L u

L u L s i i

d u u

d u u

d d s

d s

d s

u s u i

¶

¶

¶

¶

¶

¶

¶

¶

¶

¶

¶

¶

= - + + - =

= - + + - =

= + - + =

= - - + =

= - - + =

= = ³ =