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

(1)

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

[2008][07-2]

October 2008 Prof. Kyu-Yeul Lee

Department of Naval Architecture and Ocean Engineering,

Seoul National University of College of Engineering

(2)

참고

참고 문헌 문헌

¡ 이규열, 노명일, 차주환, 전산선박설계, 3th Ed., 2003.9

¡ Arora, J. S., Introduction to Optimum Design, 2 ^nd Ed., Elsevier, 2004

¡ Michael G. Parsons, Optimization Methods For Use In

Computer-Aided Ship Design, The society of naval architects and marine engineers, 1975

2

¡ 이규열, 노명일, 차주환, 전산선박설계, 3th Ed., 2003.9

¡ Arora, J. S., Introduction to Optimum Design, 2 ^nd Ed., Elsevier, 2004

¡ Michael G. Parsons, Optimization Methods For Use In

Computer-Aided Ship Design, The society of naval architects

and marine engineers, 1975

(3)

최적 설계 문제의 예

선박기본설계개론

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

3

(4)

비제약 최적화 문제

¡ 다음의 다섯 가지 비제약 최적화 방법(unconstrained optimization

method)을 이용하여 2변수 함수의 최소점을 구하시오. 단, 시작점 x ⁽⁰⁾ = (0, 0), convergence tolerance e = 0.001이며, x ⁽³⁾ 까지 구하시오.

— Steepest descent 방법(최속 강하법, 최대 경사법)

— Conjugate gradient 방법(공액 경사도 방법)

— Newton 방법

— Davidon-Fletcher-Powell(DFP) 방법

— Broydon-Fletcher-Goldfarb-Shanno(BFGS) 방법

2 2 2

1 2

1 , ) 2 2

( x x x x x x x x

f = - + + +

Minimize

Æ 미지수 2개인 최적화 문제

4

¡ 다음의 다섯 가지 비제약 최적화 방법(unconstrained optimization

method)을 이용하여 2변수 함수의 최소점을 구하시오. 단, 시작점 x ⁽⁰⁾ = (0, 0), convergence tolerance e = 0.001이며, x ⁽³⁾ 까지 구하시오.

— Steepest descent 방법(최속 강하법, 최대 경사법)

— Conjugate gradient 방법(공액 경사도 방법)

— Newton 방법

— Davidon-Fletcher-Powell(DFP) 방법

— Broydon-Fletcher-Goldfarb-Shanno(BFGS) 방법

(5)

비제약 최적화 문제 – 응용 문제

ü Hooke & Jeeves의 탐사법 - 출발점: L/B = 1, C

_B

= 0.1

- 출발점의 step size: D(L/B) = 0.5, D(C

_B

) = 0.1 ü Nelder & Mead의 Simplex 방법

- 출발 모서리점: (L/B, CB) = (1, 0.1), (1.5, 0.1), (1.5, 0.2) - 중지 기준: 0.01

어느 선박의 상대적 건조비를 L/B와 C

_B

의 함수로 다음 그림과 같이 표시할 수 있다고 하면 건조비가 최소가 되는 L/B와 C

_B

의 값을 Hooke & Jeeves의 탐사법과 Nelder & Mead의 Simplex 방법을 이용하여 최적점을 구하고 그 과정을 그림에 각각 표시하시오.

문제:

5 C_B

L/B 0.1

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0

미지수 2개인 최적화 문제 Å

목적 함수의 contour line(f = const.)

ü Hooke & Jeeves의 탐사법 - 출발점: L/B = 1, C

_B

= 0.1

- 출발점의 step size: D(L/B) = 0.5, D(C

_B

) = 0.1 ü Nelder & Mead의 Simplex 방법

- 출발 모서리점: (L/B, CB) = (1, 0.1), (1.5, 0.1), (1.5, 0.2)

- 중지 기준: 0.01

(6)

선형 계획법 문제 – 응용 문제

- 선형 계획법을 이용한 최적 밸러스트 탱크 배치(1/2)

탱크 탱크의 용량 1,000m

³

탱크 용량의 트림 변화량(m)

1,000m

³

탱크 용량의 GM 변화량(m)

어느 선박의 밸러스트 탱크(ballast tank)는 다음과 같은 특성을 갖고 있다. 이 선박의 현재 트림(trim) 및 GM은 각각 2m, 0.1m인데, 밸러스트 탱크들을 부분적으로 또는 완전히 채워서 트림을 0.0mm로 GM을 0.5m 이상으로 유지하고자 한다. 어떤 탱크에 얼마의 양의 밸러스트 수(ballast water)를 채우면 되겠는가? 물론 이때 밸러스트 수의 양을 최소로 해야 한다.

6

1,000m

³

탱크 용량의 트림 변화량(m)

1,000m

³

탱크 용량의 GM 변화량(m)

1 500 0.0 0.1

2 1,000 -2.0 0.1

3 1,500 0.5 0.5

4 2,000 -1.0 0.2

5 2,500 -0.2 0.4

(7)

선형 계획법 문제 – 응용 문제

- 선형 계획법을 이용한 최적 밸러스트 탱크 배치(2/2)

탱크 탱크의

용량

1,000m³탱크 용량의 트림 변화량(m)

1,000m³탱크 용량의 GM 변화량(m)

1 500 0.0 0.1

2 1,000 -2.0 0.1

3 1,500 0.5 0.5

4 2,000 -1.0 0.2

5 2,500 -0.2 0.4

i번째 탱크에 채운 밸러스트 수의 양을 1,000m

³

단위로 x

_i

로서 표현하면

어느 선박의 밸러스트 탱크(ballast tank)는 다음과 같은 특성을 갖고 있다. 이 선박의 현재 트림(trim) 및 GM은 각각 2m, 0.1m인데, 밸러스트 탱크들을 부분적으로 또는 완전히 채워서 트림을 0.0mm로 GM을 0.5m

이상으로 유지하고자 한다. 어떤 탱크에 얼마의 양의 밸러스트 수(ballast water)를 채우면 되겠는가? 물론 이때 밸러스트 수의 양을 최소로 해야 한다.

7

5 2,500 -0.2 0.4

5 4

3 2

1 5

4 3 2

1 , , , , )

( x x x x x x x x x x

f = + + + +

Minimize

Find x ₁ , x ₂ , x ₃ , x ₄ , x ₅

Subject to

5 . 2 0

, 0 . 2 0

, 5 . 1 0

, 0 . 1 0

, 5 . 0 0

5 4

3 2

1 £

£

x x

x

4 . 0 4

. 0 2

. 0 5

. 0 1

.

0 x ₁ + x ₂ + x ₃ + x ₄ + x ₅ ³ 2

2 . 0 5

. 0

2 x ₂ - x ₃ + x ₄ + x ₅ =

: GM 요구 조건 : 트림 요구 조건

: 각 탱크의 용량 제한 조건

Æ 미지수 5개, 등호 제약 조건 1개, 부등호 제약 조건 6개인 최적화 문제

(8)

등호

등호 제약 제약 조건이 조건이 있는 있는 최적화 최적화 문제에서의 문제에서의 Lagrange

Lagrange 함수의 함수의 구성 구성

2 2

2

1

1 . 5 ) ( 1 . 5 ) (

)

( = x - + x - f x

0 2 )

( = x

₁

+ x

₂

- = h x

Original Problem Original Problem

) 2 (

) 5 . 1 ( ) 5 . 1 (

) ( ) ( ) , (

2 1

2 2

2 1

- + +

- + -

=

+

=

x x

h f

L

n n

n x x

x

Lagrange Function Lagrange Function

75 . 0

= f

5 . 0

= f

1 2

) (x f

Ñ

:

f (x )

^{의 증가 방향}

)

(x h

Ñ

:

h (x )

^{의 증가 방향}

úû ù êë é -

= -

Ñ 1

) 1 (C f

C

úû ù êë

=é

Ñ 1

) 1 (C h

0 . 0 ) ( , 5 . 0 )

(C = h C = f

D ^úû

ù êë

=é

Ñ 1

) 1 (D h

Minimize Subject to

Minimize

x

2

8

) 2 (

) 5 . 1 ( ) 5 . 1 (

) ( ) ( ) , (

2 1

2 2

2 1

- + +

- + -

=

+

=

x x

h f

L

n n

n x x

x

Necessary Condition:

0 ) ( )

(

^*

+

^*

Ñ

^*

= Ñ f x n h x

) ( )

( x

^* ^*

h x

^*

f = Ñ

-Ñ

\ n

1 2

0

= h

ú û ù ê ë

= é ú Ñ

û ù ê ë

é

-

= -

Ñ 1

) 1 ( ) ,

5 . 1 ( 2

) 5 . 1 ( ) 2

(

2

1

x

x h

x f x

úû ù êë é -

= -

Ñ 1

) 1 (C f

0

*

2

*

1

+ x - = x

) ( )

( x

^*

v

^*

h x

^*

f = Ñ

Ñ -

후보 최적점 C에서 의 의미를 살펴 보면,

0 . 0 ) ( , 75 . 0 )

(D = h D = f

úû ù êë é

= -

Ñ 1.73 ) 0

(D f

목적 함수 및 제약 함수의 Gradient 벡터는 동일 작용선 상에 있고, 서로 비례하며 이때 Lagrange multiplier v*가 비례 상수임

1 1 ,

) 1 ( 1 ,

) 1

( ú

^*

=

û ù ê ë

= é ú Ñ

û ù ê ë é

-

= -

Ñ f C h C n

*

* 2

*

1

1 . 5 ) , 2 ( 1 . 5 ) (

2 x - = v - x - = v -

1 ,

1

^*

* 2

*

1

= = =

Þ x x v

(점 C)

0 ) (

^* ^*

=

Ñ L x , n x

¹

(9)

후보

후보 최적성 최적성 필요 필요 조건을 조건을 이용한 이용한 부등호

부등호 제약 제약 최적화 최적화 문제의 문제의 해법 해법

2 2

2

1

1 . 5 ) ( 1 . 5 ) (

)

( = x - + x - f x

0 2 )

( = x

₁

+ x

₂

- £ g x

Original Problem Original Problem

[ ]

) 2 (

) 5 . 1 ( ) 5 . 1 (

) ( )

( ) , , (

2 2

1

2 2

2 1

2

s x

x u

x x

s g

u f

s u L

+ - + +

- + -

=

+ +

= x x

x

Lagrange Function Lagrange Function

75 . 0

= f

5 . 0

= f

1 2

C

úû ù êë

=é

Ñ 1

) 1 (C g

0 . 0 ) ( , 5 . 0 )

(C = g C = f

Æ g x ( ) + s

²

= x

₁

+ x

₂

- 2 + s

²

= 0

D Minimize

Subject to

Minimize

부등호 제약 조건을 등호 제약 조건으로

변환하기 위해 도입한 완화 변수(slack variable)

9

[ ]

) 2 (

) 5 . 1 ( ) 5 . 1 (

) ( )

( ) , , (

2 2

1

2 2

2 1

2

s x

x u

x x

s g

u f

s u L

+ - + +

- + -

=

+ +

= x x

x

Necessary Condition:

1

0

= g úû

ù êë é -

= -

Ñ 1

) 1 (C f

C

0.5 0.5

0 . 0 ) ( , 5 . 0 )

(C = g C = f

5 . 0

=

1 2 g

0 2

, 0 2

0 )

5 . 1 ( 2

, 0 )

5 . 1 ( 2

2 2

1

2 2

1 1

=

¶ =

= ¶ + - +

¶ =

¶

= + -

¶ =

= ¶ + -

¶ =

¶

s us s L

x u x

L

u x x

u L x x

L

0 ³

단,

u

(1) s = 0일 때(부등호 제약 조건이 등호 제약 조건으로 변환)

(2) u = 0일 때(부등호 제약 조건을 만족함, 즉 부등호 제약 조건이 없는 문제임)

1 , 1

^*

* 2

*

1

= x = u = x

1 ,

0 ,

5 .

1

^* ²

* 2

*

1

= x = u = s = -

x

(점 D: 제약 조건을 위배)

Æ 후보 최적점(점 C)

0 )

(

^* ^* ^*

=

Ñ L x , u , s

(10)

제약

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

-- Kuhn Kuhn--Tucker Tucker 필요 필요 조건을 조건을 이용한 이용한 국부적 국부적 후보 후보 최적해 최적해 도출 도출

0 2

3

2 ₁ ₂ ₁

1

= +

-

¶ =

¶ x x ux

x L

0 2

3

2 ₂ ₁ ₂

2

= +

-

¶ =

¶ x x ux

x L

0 , 0 ,

0

6 ² ²

2 2 2

1 + - + = ³ ³

¶ =

¶ x x s s u

u L

0 2 =

¶ =

¶ us s

L

2 1 2

2 2

1

3 )

( x x x x

f x = + -

0 6 )

( = x

₁²

+ x

₂²

- £ g x

Minimize

Æ 두가지 경우가 나옴

) 6

( 3

) , ,

( u s x

₁²

x

₂²

x

₁

x

₂

u x

₁²

x

₂²

s

²

L x = + - + + - +

1

2

3

10

CASE #1 : u = 0

CASE #2 : s = 0

0 2

3 0 3

2

2 1

= +

-

= -

x x

x

x x

₁^*

= 0 , x

^*₂

= 0 , f ( x

₁^*

, x

^*₂

) = 0

3 )

, ( ,

3

₁^* ^*₂

* 2

*

1

= x = f x x = -

x

2 , 1

2

3

1

= x = - u =

x

2 , 5

2

3

1

= - x = u = -

x

, 5

2

3

1

= - x = - u = -

x

2 , 1

2

3

1

= x = u =

x

B

C

(제약 조건을 고려하지 않아도 되는 경우)

(제약 조건의 경계 상에 해가 있는 경우) Æ

Æ Æ

점 A:

A 3

) , ( ,

3

₁^* ₂^*

* 2

*

1

= x = - f x x = -

x

점 B:

점 C:

Æ 점 D:

Æ 점 E:

D E

15 ) , ( , 3 ,

3

₂^* ₁^* ^*₂

*

1

= x = - f x x =

x

15 ) , ( , 3 ,

3

^*₂ ₁^* ^*₂

*

1

= - x = f x x =

x

(11)

K

K--T T 필요 필요 조건을 조건을 이용한 이용한 2 2차 차 계획 계획 문제 문제 최적해 최적해 구하기 구하기

0 4 2

) (

0 4 2

) (

2 1

2

2 1 1

£ + -

-

=

£ + -

-

=

x x

g

x x g

x x Minimize

Subject to

2 2

2 )

( = x

₁²

+ x

₂²

- x

₁

- x

₂

+ f x

최적해는

9

* 2 3

4 3

* 4

) ( ), ,

( =

= x

x f

단, x

₁

³ 0 , x

₂

³ 0

Lagrange 함수

x ₂

2 3

4 g

₁

= 0

9

* 2 3

4 3

* 4

) ( ), ,

( =

= x

x f

최적해(점 A)

가능해 공간

2 2 1

1

2 2 2

1 2

2 1 2

1 1

2 1

2 2 2

1

) 4

2 (

) 4

2 (

2 2

2 )

, , , (

x x

s x

x u

s x

x u

x x

L

z z - -

+ + -

- +

+ + -

- +

+ -

- +

ζ = s u x

11

x ₁

1 2 3 4

1 2

A

g

₂

= 0 가능해 공간

f = 1.32 f = 0.64

2 2 1

1

2 2 2

1 2

2 1 2

1 1

2 1

2 2 2

1

) 4

2 (

) 4

2 (

2 2

2 )

, , , (

x x

s x

x u

s x

x u

x x

L

z z - -

+ + -

- +

+ + -

- +

+ -

- +

ζ =

s

u

x

(12)

CSD(Constrained Steepest Descent)

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

x ₂ 0

) (

0 )

(

0 0 . 6 1

1 6

) 1 (

1 3

1 2

2 2 2

1 1

£ -

=

£ -

=

£ -

+

=

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 ),

12

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 초기 시작점은 x ⁽ ⁰ ⁾ = ( 1 , 1 ),

최적해는 x ^* = ( 3 , 3 ), f ( x ^* ) = - 3

이때 Lagrange multiplier는

) 0 , 0 , 3

* (

= u

001 . 0 ,

10 ₁ ₂

0 = e = e =

R

이라 가정

(13)

CSD(Constrained Steepest Descent)

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

(vi) 단계 6: 황금 분할법을 사용하여 탐색 방향(d

⁽⁰⁾

)으로 강하 함수를 최소화 하는 개선된 설계점 계산

1 2 3 4

x₂

C g₂= 0

) 3 , 3

*

(

= x

f = -25 f = -20

f = -10 f = -3

d

0

※ 황금분할법 수행시 시작점에서의 함수값보다 δ만큼 더한 위치에서의 함수값이 더 크면

시작점의 함수값보다 작을 때 까지 δ를 줄여나감 )

, ( ) 1 , 1

(

₁ ₂

0

= = d d

d ) 1 , 1

)

(

0 , 0

(

=

x

탐색방향 :

13

1 2 3 4

1

x₁

A B

g₃= 0 g₁= x₁²+ x₂²- 6.0 = 0 x⁽⁰⁾= (1, 1)

d

0

(

⁽⁰^,⁰⁾

) ⁼ (

⁽⁰^,⁰⁾

) ⁺ ^×

⁽⁰^,⁰⁾

⁼ ^- ¹ ⁺ ¹⁰ ^´ ⁰ ⁼ ^- ¹

F x f x R V

(

⁽⁰^,¹⁾

) ⁼ (

⁽⁰^,¹⁾

) ⁺ ^×

⁽⁰^,¹⁾

⁼ ^- ² ^. ²⁵ ⁺ ¹⁰ ^´ ⁰ ⁼ ^- ² ^. ²⁵

F x f x R V

( ) ( )

440 . 2 777 . 0 10 331 . 5

) 2 , 0 ( )

2 , 0 ( )

2 , 0 (

=

´ + -

=

× +

=

F x f x R V

) 1 , 1

)

(

0 , 0

(

=

x

) 5 . 1 , 5 . 1 ( ) 1

, 1

(

₁ ₂

) 1 , 0

(

= + d + d =

x

) 309 . 2 , 309 . 2 (

) 618 . 1 1

, 618 . 1 1

(

₁ ₁ ₂ ₂

) 2 , 0 (

=

+ + +

+

= d d d d

x

( ^x

⁽⁰^,⁰⁾

) ^> ^F ( ^x

⁽⁰^,¹⁾

) ( ^, ^F ^x

⁽⁰^,¹⁾

) ^< ^F ( ^x

⁽⁰^,²⁾

)

F ^이므로,

) 2 , 2 ( ) 1

, 1

(

₁ ₂

) 1 , 0

(

= + d + d =

x

(

⁽⁰^,¹⁾

) ⁼ (

⁽⁰^,¹⁾

) ⁺ ^×

⁽⁰^,¹⁾

⁼ ^- ⁴ ⁺ ¹⁰ ^´ ⁰ ^. ³³³ ⁼ ^- ⁰ ^. ⁶⁶⁷

F x f x R V

( ^x

⁽⁰^,⁰⁾

) ^< ^F ( ^x

⁽⁰^,¹⁾

)

F

이므로, δ를 줄여 다시 계산

) , ( ) 5 . 0 , 5 . 0

(

₁ ₂

0

= = d d

d

탐색방향 :

( ^x

⁽⁰^,⁰⁾

) ^> ^F ( ^x

⁽⁰^,¹⁾

)

F

이므로, 다음 계산 수행 이 구간에 최소값 존재함

(14)

-2

-1

0

1

-2

-1 0

1 2

0 50000 100000 150000 200000

-2

-1

0

1

제약 최적화 문제 #1 (1/2)

)}

27 36

48 12

32 18 ( ) 3 2

( 30 {

)}

3 6

14 3

14 19 ( ) 1 (

1 { ) , (

2 2 2

1 2

2 1 1

2 2 1

2 2 2

1 2

2 1 1

2 2 1 2

1

x x

x x x

x f

+ -

+ +

-

× -

+

×

+ +

- +

-

× + + +

=

0 2 )

, (

0 2 )

, (

0 2

) , (

0 2

) , (

2 2

1 4

1 2

1 3

2 2

1 2

1 1

£ -

=

£ -

=

£ - -

=

£ - -

=

x x

x g

x x

x g

x x

x g

x x

x g

Subject to Minimize

Goldstein-Price Function

14

-2

-1

0

1

-2

-1 0

1 2

0 50000 100000 150000 200000

-2

-1

0

x

₁ 1

f(x

₁

, x

₂

)

x

₂

0 2 )

, (

0 2 )

, (

0 2

) , (

0 2

) , (

2 2

1 4

1 2

1 3

2 2

1 2

1 1

£ -

=

£ -

=

£ - -

=

£ - -

=

x x

x g

x x

x g

x x

x g

x x

x g

Æ 미지수 2개, 부등호 제약 조건 4개인 최적화 문제

(15)

제약 최적화 문제 #1 (2/2)

Goldstein-Price Function

A : Global Minimum

B : Local Minimum

x

₁^*

= 0.0, x

₂^*

= -1.0, f(x

₁^*

, x

₂^*

) = 3.0

x

₁^*

= -0.6, x

₂^*

= -0.4, f(x

₁^*

, x

₂^*

) = 30.0

-2 -1 0 1 2

-2

-1 0 1 2

C

목적 함수의 contour line(f = const.)

15

C : Local Minimum

D : Local Minimum

x

₁^*

= 1.2, x

₂^*

= 0.8, f(x

₁^*

, x

₂^*

) = 840.0

x

₁^*

= 1.8, x

₂^*

= 0.2, f(x

₁^*

, x

₂^*

) = 84.0

-2 -1 0 1 2

-2

-1 0 1 2

x₁ x₂

A

B

D

(16)

제약 최적화 문제 #2 (1/2) – 응용 문제

¡ 어느 선박의 상대적 기관 마력 가격 f를 아래와 같이 B/T와 1/C _B 의 함수로 나타낼 수 있다고 하자.

상대적 기관 마력 가격:

그리고 B/T £ 3, C _B ³ 0.6이라는 제약 조건이 있을 때, Kuhn-Tucker 필요 조건을 이용하여 상대적 기관 마력 가격을 최소로 하는 B/T, C _B 의

값(최적해)을 Kuhn-Tucker 필요 조건을 이용하여 구하시오.

10 )

/ 1 ( ) / ( 2 ) / ( 4 )

/ 1 ( 2 )

/ ( ) ,

/

( B T C _B = B T ² + C _B ² - B T - B T × C _B + f

16

¡ 어느 선박의 상대적 기관 마력 가격 f를 아래와 같이 B/T와 1/C _B 의 함수로 나타낼 수 있다고 하자.

상대적 기관 마력 가격:

그리고 B/T £ 3, C _B ³ 0.6이라는 제약 조건이 있을 때, Kuhn-Tucker 필요 조건을 이용하여 상대적 기관 마력 가격을 최소로 하는 B/T, C _B 의

값(최적해)을 Kuhn-Tucker 필요 조건을 이용하여 구하시오.

10 2

4 2

) ,

( x ₁ x ₂ = x ₁ ² + x ₂ ² - x ₁ - x ₁ x ₂ +

Minimize f

Find x ₁ ( = B / T ), x ₂ ( = 1 / C _B )

Subject to

6 . 0 3

2 1

³

£

x

(17)

-10

-5

0

5 -4

-2 0

2 4

0 100 200 300

-10

-5

0

5

제약 최적화 문제 #2 (2/2) – 응용 문제

10 2

4 2

) ,

( x ₁ x ₂ = x ₁ ² + x ₂ ² - x ₁ - x ₁ x ₂ +

Minimize f

Find x

₁

( = B / T ), x

₂

( = 1 / C

_B

)

Subject to

0 3

/ 5 )

, (

0 3

) , (

2 2

1 2

1 1

£ -

=

£ -

= x x

x g

x x

x g

-10 -5 0 5 10

-4 -2 0 2 4 x

₂

목적 함수의 contour line(f = const.)

17 -10

-5

0

5 -4

-2 0

2 4

0 100 200 300

-10

-5

0

5

-10 -5 0 5 10

-4 -2 0 2 4

f(x

₁

, x

₂

)

x

₂

x

₁

3 x

5/3

A: True solution

x

₁^*

= 3.0, x

₂^*

= 1.5, f(x

₁^*

, x

₂^*

) = 2.5 Feasible region

g

₂

=5/3 A

g

₁

=3

(18)

프로펠러의 최적 주요 치수 결정 문제(간략화 된 문제)

Maximize

Subject to

Q T

O K

K J ×

= p

h 2

Q

P

K

D n n

P = ×

²

×

⁵

×

2 r

p

Find J , P _i / D _P

Given P , n , A _E / A _O , V

K_T와 K_Q가 모두 J와 P_i/D_p의 함수이므로 목적 함수 역시 J와 P_i/D_p의 함수임

18

Q

P

K

D n n

P = ×

²

×

⁵

×

2 r

p

: 주기관이 전달한 토오크를 프로펠러가 흡수하는 조건

Where,

) /

, (

) /

, (

) 1

(

P i

Q

P i

T

P

D P

J f K

D P

J f K

D n

w J V

=

×

= -

P: 프로펠러 전달 마력 n: 프로펠러 회전수 D_P: 프로펠러 직경 P_i: 프로펠러 피치

A_E/A_O: 프로펠러 날개 면적비 V: 선속

(19)

선박의 최적 주요 치수 결정 문제

3 3 / 2 6 . 1

6 . 1

) (

) , , , (

V C

T B L C

B L C D

B L C DWT

NMCR C

B L C D

B L C DWT

C D B L LWT DWT

C C

T B L

B power

o s

given

ma o

s given

B given

sw B

×

× +

×

× + +

× +

=

× +

×

× + +

× +

=

+

=

×

× r

_a

부력(buoyancy)-중량(displacement) 평형 조건(등호 제약 조건)

구하는 값(설계 변수)

C

B

D B

L , , ,

주어진 값(선주 요구 조건)

DWT , CC

_req

, T

_max

( = T ), V

길이 폭 깊이 방형 계수 재화 중향 요구 화물창 용적 최대 흘수 선속

19 3

3 / 2 6 . 1

6 . 1

) (

) , , , (

V C

T B L C

B L C D

B L C DWT

NMCR C

B L C D

B L C DWT

C D B L LWT DWT

C C

T B L

B power

o s

given

ma o

s given

B given

sw B

×

× +

×

× + +

× +

=

× +

×

× + +

× +

=

+

=

×

× r

_a

요구되는 화물창 용적(cargo capacity) 조건(부등호 제약 조건)

D B L C

CC

_req

£

_CH

× × ×

최소 요구 건현 조건(부등호 제약 조건)

D C

T

D ³ +

_FB

×

목적 함수(주요 치수 선정 기준)

NMCR C

C B L C C

D B L C C

Cost

Building =

_PS

×

_s

×

¹^.⁶

( + ) +

_PO

×

_o

× × +

_PM

×

_ma

×

Æ 미지수 4개, 등호 제약 조건 1개, 부등호 제약 조건 2개인 최적화 문제

(20)

선박의 최적 주요 치수 결정 문제의 수학적 정식화

Minimize

Subject to

* 부력(buoyancy)-중량(displacement) 평형 조건

Find L , B , D , C _B

3 3 / 2 6 . 1

6 . 1

) (

) , , , (

V C

T B L C

B L C D

B L C DWT

NMCR C

B L C D

B L C DWT

C D B L LWT DWT

C C

T B L

B power

o s

given

ma o

s given

B given

sw B

×

× +

×

× + +

× +

=

× +

×

× + +

× +

=

+

=

×

× r

_a

NMCR C

C B L C C

D B L C C

Cost

Building =

_PS

×

_s

×

¹^.⁶

( + ) +

_PO

×

_o

× × +

_PM

×

_ma

×

20

* 최소 요구 건현 조건

* 요구되는 화물창 용적 조건

3 3 / 2 6 . 1

6 . 1

) (

) , , , (

V C

T B L C

B L C D

B L C DWT

NMCR C

B L C D

B L C DWT

C D B L LWT DWT

C C

T B L

B power

o s

given

ma o

s given

B given

sw B

×

× +

×

× + +

× +

=

× +

×

× + +

× +

=

+

=

×

× r

_a

D B L C

CC

_req

£

_CH

× × ×

D C

T

D ³ +

_FB

×

(21)

Ch0.

Ch0. 최적 최적 설계 설계 소개 소개

(22)

최적

최적 설계에 설계에 앞서 앞서

-- 부정 부정 방정식과 방정식과 그 그 해법 해법

변수: x

₁

, x

₂

, x

₃

식: x

₁

+ x

₂

+ x

₃

=3

ü 변수의 개수:

ü 식의 개수:

3개 1개

속도: 15knot = 27.78 km/h

1knot = 0.5144 m/s

= 1.852 km/h

t초 후의 선박의 위치(d)는?

22

ü 식의 개수: 1개

변수의 개수가 식의 개수보다 많으므로

위의 문제는

부정 방정식

이다.

위의 부정 방정식 해법 2개의 변수를 가정한다.

예) x

₁

= 1, x

₂

= 0로 가정 à x

₃

= 2

변수의 개수(3) – 식의 개수(1)

t초 후의 선박의 위치(d)는?

d = × + v t d

0

식:

변수: d t ,

^{(v: 속도, d}0: 초기 위치)

ü 변수의 개수:

ü 식의 개수:

2개 1개

시간 t를 가정하여 임의의 시간에 대한

선박의 위치 d를 알 수 있다.

(23)

최적

최적 설계에 설계에 앞서 앞서

-- 부정 부정 방정식과 방정식과 그 그 해법 해법

ü 변수의 개수: 3개

식 f

₁

, f

₂

, f

₃

이 모두 독립이라면

변수: x

₁

, x

₂

, x

₃

연립 방정식

f

₂

(x

₁

, x

₂

, x

₃

)=0 f

₃

(x

₁

, x

₂

, x

₃

)=0 식: f

₁

(x

₁

, x

₂

, x

₃

)=0

ü 변수의 개수: 3개

식 f

₁

, f

₂

이 서로 독립이라면

부정 방정식

변수: x

₁

, x

₂

, x

₃

f

₂

(x

₁

, x

₂

, x

₃

)=0 f

₃

(x

₁

, x

₂

, x

₃

)=0 식: f

₁

(x

₁

, x

₂

, x

₃

)=0

23

ü 변수의 개수:

ü 식의 개수:

3개 3개

식의 개수와 변수의 개수가 같으므로 풀 수 있는 문제

만일 2×f

₃

= f

₂

라면?

서로 독립인 식의 개수가 변수의 개수 보다 적으므로

부정 방정식이 된다.

f

₂

는 f

₃

로 표현이 가능하므로 독립이 아님

ü 변수의 개수:

ü 식의 개수:

3개 2개

식의 개수가 변수의 개수보다 적으므로 식을 추가하여 해를 구한다.

1

4 0

f =

추가한 식 구한 해

1 1 1

1 2 3

( ,x x x, )

2

4 0

f = (x x x₁², ₂², ₃²)

추가한 식에 따라

무수히 많은 해가 구해짐 à 부정 방정식

무수히 많은 해 중 어떤 것이 좋은지 판단할 기준이 필요하며, 판단 기준으로서 목적함수 를 추가하면

최적화 문제가 된다.

무수히 많은 해 중 어떤 것이 좋은지 판단할

기준이 필요하며, 판단 기준으로서 목적함수

를 추가하면

최적화 문제가 된다.

(24)

최적

최적 설계에 설계에 앞서 앞서

-- 제약 제약 최적화 최적화 문제와 문제와 그 그 해법 해법 -- Lagrange Multiplier Lagrange Multiplier를 를 이용 이용

1

( ,

1 2

,

3

) 0 h x x x =

2

( ,

1 2

,

3

) 0 h x x x =

1 2 3

f f f 0

df dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

①’

②

③

함수 f 값이 최소가 되기 위한 필요조건: 식 ①’

식 h₁, h₂로 인하여 dx₁, dx₂, dx₃는 서로 독립이 아니다.

최적화 문제

Minimize Subject to

①

②

③

1

( ,

1 2

,

3

) 0 h x x x =

2

( ,

1 2

,

3

) 0 h x x x =

1 2 3

( , , ) f x x x

dx₁, dx₂, dx₃의 관계를 알기 위해 식②, ③를 변형

24 식 ②, ③ 으로부터 식 ②’, ③’를 유도

1 2 3

f f f 0

df dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶ ①’

②’

③’

1 1 1

1 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

2 2 2

2 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

1 1 2 2

0 df + l dh + l dh =

=0(dx₃는 독립변수 이므로, 식⑥)

1 2

1 2 1

1 1 1

f f

F dx

x l x l x

æ¶ ¶ ¶ ö

+ +

ç ÷

¶ ¶ ¶

è ø

1 2

1 2 2

2 2 2

f f

F dx

x l x l x

æ¶ ¶ ¶ ö

+ç + + ÷

¶ ¶ ¶

è ø

1 2

1 2 3

3 3 3

f f 0

F dx

x l x l x

æ¶ ¶ ¶ ö

+ç + + ÷ =

¶ ¶ ¶

è ø

=0(dx₂를 소거하기 위함, 식⑤)

=0(dx₁를 소거하기 위함, 식④)

식 ①’의 dx₁, dx₂를 소거하기 위하여 식 ②’, ③’을 이용하여 다음 식을 유도

②’

③’

1 1 1

1 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

2 2 2

2 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

①’에 새로운 변수 를 도입하고

②’, ③’을 대입 à 식④,⑤,⑥을 유도

¹ ² l l

,

(25)

최적

최적 설계에 설계에 앞서 앞서

-- 제약 제약 최적화 최적화 문제와 문제와 그 그 해법 해법 -- Lagrange Multiplier Lagrange Multiplier를 를 이용 이용 최적화 문제

Minimize Subject to

①

②

③

1

( ,

1 2

,

3

) 0 h x x x =

2

( ,

1 2

,

3

) 0 h x x x =

1 2 3

( , , ) f x x x

=0(dx₃는 독립변수 이므로, 식⑥)

1 2

1 2 1

1 1 1

f f

F dx

x l x l x

æ¶ ¶ ¶ ö

+ +

ç ÷

¶ ¶ ¶

è ø

1 2

1 2 2

2 2 2

f f

F dx

x l x l x

æ¶ ¶ ¶ ö

+ç + + ÷

¶ ¶ ¶

è ø

1 2

1 2 3

3 3 3

f f 0

F dx

x l x l x

æ¶ ¶ ¶ ö

+ç + + ÷ =

¶ ¶ ¶

è ø

=0(dx2를 소거하기 위함, 식⑤)

=0(dx₁를 소거하기 위함, 식④)

②’

③’

1 1 1

1 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

2 2 2

2 1 2 3

1 2 3

h h h 0

dh dx dx dx

x x x

¶ ¶ ¶

= + + =

¶ ¶ ¶

25

변수가 총 5개( )이므로 식 ②, ③, ④, ⑤, ⑥을 사용하여 문제를 풀 수 있다.

x x x

₁

,

₂

,

₃

, l l

₁

,

₂

1

,

2

l l

함수

f, h

₁

, h

₂

는 이미 주어진 함수이기 때문에 식 ④, ⑤, ⑥은 x

₁

, x

₂

, x

₃

의 (비)선형 대수 방정식

형태이다.

식 ④, ⑤, ⑥은 식 ①로 부터 유도 되었다.(변수 가 추가되어 식의 개수가 3개가 됨)

그런데

함수 F, f

₁

, f

₂

(식①, ②, ③)는 이미 주어진 것이고, 우리가 구하려고 하는 것은 x

₁

, x

₂

, x

₃이기 때문에 미분 방정식이 아닙니다.

1. 식 ①’, ②’, ③’은미분 방정식이 아닌가요?

à 만일 다음과 같은 문제라면 미분 방정식이 맞습니다.

- Given: - Find: 함수 F, f1 2 3 ₁, f₂

1 2 3

F F F 0,

dx dx dx

x x x

¶ ¶ ¶

+ + =

¶ ¶ ¶

1 1 1

1 2 3

f f f 0,

dx dx dx

x x x

¶ ¶ ¶

+ + =

¶ ¶ ¶

2 2 2

1 2 3

f f f 0,

dx dx dx

x x x

¶ ¶ ¶

+ + =

¶ ¶ ¶

(26)

함수

함수 값이 값이 최소가 최소가 되기 되기 위한 위한 필요 필요 조건 조건

2

* * 2

2

( ) ( ) 1 ( )

2 f f

f x x f x x x

x x

¶ ¶

+ D = + D + D

¶ ¶

목적 함수: f(x)

1변수 최적화 문제의 경우

목적 함수를 최소화하는 점 x*

Given Find

2

* * 2

2

( ) ( ) 1 ( )

2

f f

f x x f x x x

x x

¶ ¶

+ D - = D + D

¶ ¶

목적 함수를 테일러 전개 (2차항까지 전개)

목적 함수: f(x

₁

, x

₂

)

2변수 최적화 문제의 경우

목적 함수를 최소화하는 점 x*

Given Find

목적 함수를 테일러 전개 (2차항까지 전개)

* * * *

1 1 2 2 1 2 1 2

1 2

2 2 2

2 2

1 1 2 2

2 2

1 1 2 2

( , ) ( , )

1 1

( ) ( )

2 2

f f

f x x x x f x x x x

x x

f f f

x x x x

¶ ¶

+ D + D = + D + D +

¶ ¶

¶ ¶ ¶

D + D D + D

¶ ¶ ¶ ¶

26

x*에서 함수 값이 최소

라고 하면

* *

( ) ( ) 0 f x + D x - f x ³ LHS

2

* * 2

2

( ) ( ) 1 ( )

2

f f

f x x f x x x

x x

¶ ¶

+ D - = D + D

¶ ¶

x

D

가 독립이므로(부호를 알 수 없으므로)

RHS

* * * *

1 1 2 2 1 2 1 2

1 2

2 2 2

2 2

1 1 2 2

2 2

1 1 2 2

( , ) ( , )

1 1

( ) ( )

2 2

f f

f x x x x f x x x x

x x

f f f

x x x x

¶ ¶

+ D + D = + D + D +

¶ ¶

¶ ¶ ¶

D + D D + D

¶ ¶ ¶ ¶

[ ]

1

* * * *

1 1 2 2 1 2

1 2 2

2 2

2

1 1 2 1

1 2 2 2

2 2

1 2 2

( , ) ( , )

1 2

f f x f x x x x f x x

x

x x

f f

x x x x

x x

x

f f

x x x

é¶ ¶ ù éD ù + D + D = + êë¶ ¶ ú êûëD úû

é ¶ ¶ ù

ê ú

¶ ¶ ¶ éD ù

ê ú

D D êê ¶ ¶ ú Dúêë úû

¶ ¶ ¶

ê ú

ë û

f

T

Ñ Dx

T

Dx

Dx H

x*에서 함수 값이 최소

라고 하면 f 0,

x

¶ =

¶

필요 조건

2

0 f x

¶ >

¶

필요 충분 조건

Ñ = f 0, H

(Hessian Matrix)는 양정행렬

(27)

최적

최적 설계에 설계에 앞서 앞서

-- Design Design

Esthetic* Design

- 팔 길이, 소재, 색상 등..

제약 조건

27

목적 함수(주요 치수 선정 기준) - 선호도, 가격 등..

- 설계 변수로서 수치화 하기 어려움

* 미적가치관, 미적인 감각

- 제약 조건이 있지만 수치화 하기 어려움

- Designer의 설계 감각으로 제약 조건을 만족시킴

(28)

최적

최적 설계에 설계에 앞서 앞서

-- Design Design

Engineering Design

( , , , )

B sw given B

L B T C × × × × r × C

_a

= DWT + LWT L B D C

부력(buoyancy)-중량(displacement) 평형 조건(등호 제약 조건)

x

₁

, x

₂

, x

₃

, x

₄

1 2 3 4

( ), ( ), ( ),

_B

( ) L = x B = x D = x C = x

길이 폭 깊이 방형 계수

h(x

₁

, x

₂

, x

₃

, x

₄

)=0

등호 제약 조건

최적화 문제

Æ 제약 조건을 만족하면서 목적함수를 최소화(최대화)하는 설계 변수를 결정 하는 것

28

제약조건의 특징

ü 물리 법칙은 보통 등식으로 표현 됨 (선박 설계의 예: 부력-중량 평형 조건)

ü 정치, 경제, 사회, 문화적으로 정의된 규약이나 조건은 부등호 제약 조건식으로 표현 된다.

(선박 설계의 예: 최소 요구 건현 조건, 요구되는 화물창 용적 조건)

( , , , )

B sw given B

L B T C × × × × r × C

_a

= DWT + LWT L B D C

목적 함수(주요 치수 선정 기준)

h(x

₁

, x

₂

, x

₃

, x

₄

)=0

f (x

₁

, x

₂

, x

₃

, x

₄

)

목적 함수

1 2 4 1 2

( ,

1 2

,

3

,

4

)

x x × × x C × = C + h x x x x ¢

1 2 4 1 2

( ,

1 2

,

3

,

4

) ( ,

1 2

,

3

,

4

) 0 x x × × x C × - C + h x x x x ¢ = h x x x x =

1.6

( )

PS s PO o PM ma

Building Cost = C × C L × B + D + C × C × × L B C + × C × NMCR

1.6

1 2 3 4 3 1 2 3 4 1 2 5

( , , , ) ( )

f x x x x = C x × x + x + C × x x × + C

- C_i, ρ_sw, DWT_given, NMCR : 주어진 계수

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