전산 전산 선박 선박 설계 설계 Part 1.

전산 전산 선박 선박 설계 설계 Part 1.

Part 1. 최적 최적 설계 설계 기법 기법

2006.9.

서울대학교 조선해양공학과

이규열

목차 목차

Ch1. 최적 설계 개요

Ch2. 비제약 최적화 기법

Ch3. 선형 계획법(Linear Programming)

Ch4. 쿤-터커(Kuhn-Tucker) 정리를 이용한 최적성 조건 Ch5. 제약 비선형 최적화 기법 및 응용 예

Ch6. 제약 비선형 최적화 프로그램 소개

Ch1.

Ch1. 최적 최적 설계 설계 개요 개요

1.1 최적 설계 문제의 일반적 정식화 1.2 최적 설계 문제의 구성 요소

1.3 최적화 기법의 분류

1.1 1.1 최적 최적 설계 설계 문제의 문제의 일반적 일반적 정식화 정식화

Objective Function Objective Function

Subject to Minimize

Constraints Constraints

) f ( x

m j

g _j ( x ) ≤ 0 , = 1 , Λ , p k

h _k ( x ) = 0 , = 1 , Λ ,

: 부등호 제약 조건(Inequality Constraint)

: 등호 제약 조건(Equality Constraint)

Where x = ( x ₁ , x ₂ , Λ , x _n )

u

l x x

x ≤ ≤

: 설계 변수 벡터에 대한 상·하한값 제약 조건

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

5

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

5/252

1.2 1.2 최적 최적 설계 설계 문제의 문제의 구성 구성 요소 요소 (1) (1)

설계 변수 (Design Variable)

설계하고자 하는 치수 , 위치 등을 나타내는 변수로서 자유

변수 (Free Variable) 또는 독립 변수(Independent Variable)라고 함

종속 변수 (Dependent Variable)

설계 변수의 결정 후 종속적으로 결정되어지는 변수

제약 조건 (Constraint)

설계에서 기능상 요구되는 조건 또는 크기의 제한 등을 정의 부등호 제약 조건 (Inequality Constraint), 등호 제약

조건 (Equality Constraint)

1.2 1.2 최적 최적 설계 설계 문제의 문제의 구성 구성 요소 요소 (2) (2)

목적 함수 (Objective Function)

최적 (Optimum)을 나타내는 기준으로 비용, 무게 등과 같은 값을

비교하여 어느 설계 대안 (Design Alternative)이 보다 나은지를 나타낼 수 있는 함수

제약 조건

목적 함수 (최대값)

설계 변수

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

7

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

7/252

1.2 1.2 최적 최적 설계 설계 문제의 문제의 구성 구성 요소 요소 (3) (3)

최적해 중에서도 가장 좋은 최적해

(전역 최적해) 특정 범위

내에서의 최적해 (국부 최적해)

국부 최적해

= 전역 최적해

제약 조건을 만족하는 설계 영역

제약 조건에 의해 최적해는 달라질 수 있음

목적 함수와 제약 조건에

따른 최적해 (최대값)의 결정

1.3 1.3 최적화 최적화 기법의 기법의 분류 분류 (1) (1)

전역 최적화 기법 (Global Optimization Methods) 장점

다수의 국부 최적해 (Local Optima)를 가진 대규모 문제에 적합

단점

최적해를 얻기 위해 많은 Iteration이 필요(긴 계산 시간 요구 )

Genetic Algorithms(GA), Simulated Annealing, etc.

국부 최적화 기법 (Local Optimization Methods) 장점

최적해를 얻기 위해 상대적으로 적은 Iteration이 필요(짧은 계산 시간 요구 )

단점

초기해 (Starting Point)에 가까운 국부 최적해를 도출(거의 국부 최적해만 찾음 )

Method of Feasible Directions(MFD), Sequential

Quadratic Programming(SQP), Multi-Start Optimization

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

9

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

9/252

1.3 1.3 최적화 최적화 문제의 문제의 분류 분류 (2) (2)

제약 조건의 유무

비제약 최적화 문제 (Unconstrained Optimization Problem)

제약 조건이 없는 최적화 문제

직접 탐사법 (Hooke & Jeeves Method, Nelder & Mead’s Simplex Method), Gradient 방법(Steepest Descent Method, etc.), etc.

제약 최적화 문제 (Constrained Optimization Problem)

제약 조건이 있는 최적화 문제

Penalty Function Method, Sequential Linear Programming, Constrained Steepest Descent Method, Method of Feasible Directions(MFD), Sequential Quadratic Programming(SQP), etc.

목적 함수의 수

단일 최적화 문제 (Single-Objective Optimization Problem) 다중 최적화 문제 (Multi-Objective Optimization Problem)

Weighting Method, Constraint Method

Ch2.

Ch2. 비제약 비제약 최적화 최적화 기법 기법

2.1 Gradient 방법

Steepest Descent 방법

공액 경사도 방법 (Conjugate Gradient 방법) Newton의 방법

Davidon-Fletcher-Powell(DFP) 방법

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

2.2 황금 분할에 의한 1차원 탐색 방법 2.3 직접 탐사법(Direct Search Method)

Hooke & Jeeves의 직접 탐사법

2.1 Gradient

2.1 Gradient 방법 방법

2.1 Gradient

2.1 Gradient 방법 방법

- - Steepest Descent Steepest Descent 방법 방법 ( ( 최속 최속 강하법 강하법 ) )

탐색 방향 (Search Direction)을 목적 함수의 Gradient Vector의 반대 방향으로 가정하고 순차적으로 최적해를 찾는 방법

¨ Gradient Vector(∇f(x)): 함수 값이 최대로 증가하는 방향

x ₁ x

₂

x ^*

x ⁽³⁾

x ⁽²⁾

x ⁽¹⁾

x ⁽⁰⁾

∇f(x ⁽¹⁾ )

탐색 방향

함수 값이 최대로 증가하는

방향

목적 함수를 최소화 하는 문제일 경우

) ( ^{( 1 )}

) 1 ( )

1

( c x

d = − ≡ −∇ f

탐색 방향

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

13

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

13/252

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

Steepest descent 방법(최속 강하법, 최대 경사법)을 이용하여 2변수

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

2 2 2

1 2

1 2

1 2

1 , ) 2 2

( x x x x x x x x

f = − + + +

Minimize

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

-4 -2 0 2 4

-4 -2 0 2 4

-4

-2

0

2

4

-4 -2

0 2

4

0 50 100

-4

-2

0

2

4

f(x

₁

, x

₂

)

x

₂

x

₁

x

₁

x

₂

A

A: True solution

x

₁^*

= -1.0, x

₂^*

= 1.5, f (x

₁^*

, x

₂^*

) = -1.25

-

0.5 0 0.5 1 1.5 2

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

- - Steepest descent Steepest descent 방법을 방법을 이용한 이용한 해법 해법 (1) (1)

단계 1 -

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

∇ ⎛

=

∇ 1

1 2

2 1

2 4

1 0

) 0 (

2 1

2 ) 1

0 (

x x

x f x

f x

) (

⁽⁰⁾

) 0 ( )

0 ( )

1

(

x x

x = − α ∇ f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

− −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

α α α

1 1 0

0

대체함 로

을

편의상 α

⁽⁰⁾

α α α 2 )

( x

⁽¹⁾

=

²

− f

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 1 (

) 1 (

α = d df

f x

x

0 .

= 1 α

구하기

) 1

x (

2 2 2

1 2

1 2

1 2

1 , ) 2 2

( x x x x x x x x

f = − + + +

Minimize

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

∇

=

∇

2 1

2 1

2

1

1 2 2

2 4

) 1 , ( )

( x x

x x x

x f f x

x

₂

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

∴ 1

)

1

1

x

(

) 0

x ( )

1

x (

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

15

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

15/252

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

- - Steepest descent Steepest descent 방법을 방법을 이용한 이용한 해법 해법 (2) (2)

단계 2 - x ^{( 2 )} 구하기

) (

⁽¹⁾

) 1 ( )

1 ( )

2

(

x x

x = − α ∇ f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ +

+

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

−

− −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

α α α

1 1 1

1 1

1

대체함 로

을

편의상 α

⁽¹⁾

α 1 2

5 )

( x

⁽²⁾

= α

²

− α − f

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 2 (

) 2 (

α = d df

f x

x

2 .

= 0 α

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

∴ 1 . 2

8 .

)

0

2

x

(

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

−

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

∇ ⎛−

=

∇ 1

1 2

2 1

2 4

1 1

) 1 (

2 1

2 ) 1

1 (

x x

x f x

f x

-

2

-

1.5

-

1

-

0.5 0 0.5 1

-

1

-

0.5 0 0.5 1 1.5 2

x

₁

x

₂

) 0

x ( )

1

x ( x ^{( 2 )}

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

- - Steepest descent Steepest descent 방법을 방법을 이용한 이용한 해법 해법 (3) (3)

단계 3 - x ^{( 3 )} 구하기

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

∇ ⎛−

=

∇ 0 . 2

2 . 0 2

2 1

2 4

1 2

. 1

8 . ) 0

(

2 1

2 ) 1

1 (

x x

x f x

f x

) (

⁽²⁾

) 2 ( )

2 ( )

3

(

x x

x = − α ∇ f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+

−

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

− −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

α α α

2 . 0 2 . 1

2 . 0 8 . 0 2

. 0 2 . 0 2

. 1

8 . 0

대체함 로

을

편의상 α

⁽²⁾

α

2 . 1 08

. 0 04

. 0 )

( x

⁽³⁾

= α

²

− α − f

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 3 (

) 3 (

α = d df

f x

x

0 .

= 1 α

⎟⎟ ⎞

⎜⎜ ⎛−

=

∴

₍₃₎

1

x ^-

^0.5

0 0.5 1 1.5 2

x

₂

) 0

x ( )

1

x ( x ^{( 2 )}

) 3

x (

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

17

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

17/252

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

- - Steepest descent Steepest descent 방법을 방법을 이용한 이용한 해법 해법 (4) (4)

단계 4 - 최적해 구하기

.

) 1 (

) ( ) 1 (

된다 최적해가

이 그때의

중지하며

경우 일

반복하여 과정을

같은 이와

+

+

− ≤

k

k k

x

x

x ε

-

2

-

1.5

-

1

-

0.5 0 0.5 1

-

1

-

0.5 0 0.5 1 1.5 2

x

₁

x

₂

) 0

x ( )

1

x ( x ^{( 2 )}

) 3

x (

Gradient

Gradient 방법 방법

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

탐색 방향을 수정하여 최속 강하법보다 수렴율을 향상시킨 방법 . 현재의 최속 강하 방향에 직전에 사용된 탐색 방향을 척도화 시켜 더한 것을 탐색 방향으로 사용함

단계 1 : 초기 설계점 를 추정한다 . 반복 횟수 번호를 으로 둔다 . 또한 수렴 매개 변수 을 선정하고 최적 탐색 방향을 계산한다 .

그리고, 식을 만족하면 반복 과정을 마치고 만족하지 않으면 단계 4로 간다(공액 경사법과 최속 강하법의 단계 1은 동일함).

단계 2 : 목적 함수의 경사도를 계산한다.

여기서 , 만일 이면 멈춘다 . 그렇지 않으면 계속한다.

) 0

x ( k = 0

ε

) ( ^{( 0 )}

) 0 ( )

0

( c x

d = − ≡ −∇ f ε

<

) 0

c (

) ( ^{( )}

)

(

k

f x

k

c = ∇ ε

<

)

c (k

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

19

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

19/252

Gradient

Gradient 방법 방법

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

단계 3 : 다음과 같이 새로운 탐색 방향을 계산한다.

단계 4 : 를 최소화 하는 를 계산한다 . 단계 5 : 현재의 설계점을 다음과 같이 변경한다.

로 두고 단계 2로 간다.

) ( ⁽

^k

^{) (}

^k

⁾

f x + α d α = α

_k

2 ) 1 ( )

(

) 1 ( )

( )

(

) /

( ⁻

−

=

+

−

=

k k

k

k k k

k

c c

d c

d β

β

) ( )

( )

1

(

k

k k

k

x d

x ⁺ = + α + 1

= k

k

-

0.5 0 0.5 1 1.5 2

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

- - Conjugate gradient Conjugate gradient 방법을 방법을 이용한 이용한 해법 해법 (1) (1)

단계 1 -

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

∇ ⎛

=

∇ 1

1 2

2 1

2 4

1 0

) 0 (

2 1

2 ) 1

0 (

x x

x f x

f x

) (

⁽⁰⁾

) 0 ( )

0 ( )

1

(

x x

x = − α ∇ f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

− −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

α α α

1 1 0

0

대체함 로

을

편의상 α

⁽⁰⁾

α α α 2 )

( x

⁽¹⁾

=

²

− f

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 1 (

) 1 (

α = d df

f x

x

0 .

= 1 α

구하기

) 1

x (

2 2 2

1 2

1 2

1 2

1 , ) 2 2

( x x x x x x x x

f = − + + +

Minimize

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

∇

=

∇

2 1

2 1

2

1

1 2 2

2 4

) 1 , ( )

( x x

x x x

x f f x

x

₂

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

∴ 1

)

1

1

x

(

) 0

x ( )

1

x (

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

21

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

21/252

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

- - Conjugate gradient Conjugate gradient 방법을 방법을 이용한 이용한 해법 해법 (2 ( 2) )

단계 2 - x ^{( 2 )} 구하기

.

"

"

) (

⁽¹⁾

) 1 (

구한다 을

구하고 를

에서

direction Conjugate

f x

x ∇

] )

( ) ) (

(

[

₂ ⁽⁰⁾

) 0 (

) 2 1 ( )

1 ( )

1 ( )

1 ( )

2

(

d

x x x

x

x ⋅

∇ + ∇

−∇

−

= f

f f α

.

) (

가정하고

⁽²⁾

이 최소가 되는

⁽¹⁾

를 구한다

로 f x α

. )

(

,

^{(0) (0)}

이다 여기서 d = −∇ f x

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

−

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

∇ ⎛−

=

∇ 1

1 2

2 1

2 4

1 1

) 1 (

2 1

2 ) 1

1 (

x x

x f x

f x

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

- - Conjugate gradient Conjugate gradient 방법을 방법을 이용한 이용한 해법 해법 (3 ( 3) )

⎭ ⎬

⎫

⎩ ⎨

⎧ ⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛

− −

⎟⎟ +

⎠

⎜⎜ ⎞

⎝

⎛

−

− −

⎟⎟ +

⎠

⎜⎜ ⎞

⎝

= ⎛−

1 ) 1 1 2 ( 2 1

1 1

)

1

2

(

α

x

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ +

= −

α 2 1

1

대체함 로

을

편의상 α

⁽¹⁾

α 1 2

4 )

( x

⁽²⁾

= α

²

− α − f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

∴ 1 . 5

)

1

2

x

(

)

0

2

(

이므로

c = ≤ ε

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 2 (

) 2 (

α = d df

f x

x

25 .

= 0 α

-

0.5 0 0.5 1 1.5 2

x

₂

) 0

x ( )

1

x (

) 2

x (

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

23

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

23/252

Gradient

Gradient 방법 방법 - - Newton Newton 의 의 방법 방법

헷세 행렬을 사용하여 탐색 방법을 개선한 방법

단계 1 : 시작점 을 추정한다 . 반복 회수 번호를 으로 둔다 . 그리고 종료 기준으로 허용치 을 선정한다 .

단계 2 : 에서 까지 를 계산한다 . 단계 3 : 헷세 행렬을 계산한다.

단계 4 : 탐색 방향을 계산한다.

단계 5 : 설계점을 로 수정한다 .

이때 는 를 최소화하도록 계산된다 . 를 계산하기 위해서는 어떠한 1차원 탐색법도 사용할 수 있다. 초기 이동 거리 추정으로 로 가정한다 .

단계 6 : 로 두고 단계 2를 수행한다.

) 0

x ( k = 0

ε

= 1

i n c

_i

⁽

^k

⁾ = ∂ f ( x ⁽

^k

⁾ ) / ∂ x

_i

n j

n x i

x H f

j i

k

) , 1 , , ; 1 , , (

2 )

( = Λ = Λ

⎥ ⎥

⎦

⎤

⎢ ⎢

⎣

⎡

∂

∂

= ∂ x

) ( 1 )

( )

(

k

d

k

H c

k

x = = − ⁻ Δ

) ( )

( )

1

(

k

k k

k

x d

x ⁺ = + α

α

k

_{f ( x} ⁽

^k

⁾ + α _d ⁽

^k

⁾ ₎ α

= 1 α

+ 1

= k k

d x H d d c x

x ( )

2 ) 1

( )

(

f ^{* T T *}

f

= + +

c x H d c d x H

d x H c x

1

*

*

*

) ( )

(

0 ) ( )

(

− −

=

⇒

−

=

⇒

= +

′ = f

일 때

최소값을 가질 조건

[ [ 참고 참고 ] 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 ^* ₂ ) 에서의 테일러 전개식

( ) ( ) ^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의 원소

¨ 이를 다시 표현하면 ,

⎥ ⎦

⎢ ⎤

⎣

⎡

−

−

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂

∂ ∂

∂

=

−

∇

_*

2 2

* 1 1

2

* 1

*

) ( )

( x x

x x x

f x f f

T

T

x x

x

( ) ( )

[ ] ^{⎥ ⎥} _⎢ ^{⎡ −} _⎥ ^⎤

⎤

⎢ ⎢

⎡

∂

∂

∂

∂

∂

−

−

=

⎥ ⎦

⎢ ⎤

⎣

⎡

−

⎥ −

⎦

⎢ ⎤

⎣

⎡ −

∂ + ∂

∂ −

∂

− ∂

∂

∂ + ∂

∂ −

= ∂

−

−

* 1 2 1

1 2 2

1 2

*

*

* 2 2

* 1

* 1 2 2 2

2 2

* 1 1 2 1

2

* 2 2 1 2

2

* 1 2 1

1 2

*

*

*

1

) (

) (

) (

) 2 (

) 1 2 (

1

x x x

x f x

f x

x x x

x x

x x x

x x x f

x x x x f

x x x x f

x x f

T

H x x x

x

x

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

25

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

25/252

[ [ 참고 참고 ] 2 ] 2 변수 변수 함수의 함수의 테일러 테일러 전개 전개 )(2) )(2)

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛ −

∂ + ∂

−

∂ −

∂ + ∂

∂ − + ∂

∂ − + ∂

∂ − + ∂

=

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

) (

) (

) , ( )

, (

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 1

2

* 1 2 1

1 2

1 1

2

1

x x

x x x f

x x f x

f x

x x

f −

∂

∂ + ∂

∂ − + ∂

∂

= ∂

∂

∂ ( , ) ( ) (

_*

)

2 2 2

2 2

* 1 1 2 1

2

2 2

2

1

x x

x x f

x x x

f x

f x

x x

f −

∂ + ∂

∂ −

∂ + ∂

∂

= ∂

∂

∂

ƒ 2변수 함수 f ( x ₁ , x ₂ ) 에 대한 점 ( x ₁ ^* , x ^* ₂ ) 에서의 테일러 전개식 (3차 이상의 고차항은 무시할 경우)

( ^{x x} ) ^{H x} ( ^{x x} ) ^{x c d d H x d}

x x x

x

x ( )

2 ) 1

( )

2 ( ) 1 (

) ( )

( )

( f

^*

f

^{* T * * T * *}

f

^{* T T *}

f = + ∇ − + − − = + +

¨

¨

( ^{x x} ) ^{c H x d}

x H x

x

) ( )

( )

(

) (

) (

) (

) (

) (

) (

) (

) (

) (

) (

) , (

) , ( )

(

*

*

*

*

* 2 2

* 1 1

2 1 2

2 1

2

2 1

2 2

1 2

2 1

* 2 2 2

2 2

* 1 1 2 1

2

* 2 2 2 1

2

* 1 2 1

1 2

2 1

* 2 2 2

2 2

* 1 1 2 1

2

2

* 2 2 2 1

2

* 1 2 1

1 2

1

1 2 1

1 2 1

+

=

− +

∇

=

⎥ ⎦

⎢ ⎤

⎣

⎡

−

−

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂ +

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂

∂ ∂

∂

=

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂ − + ∂

∂ −

∂

∂

∂ −

∂ + ∂

∂ −

∂ +

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂

∂ ∂

∂

=

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂ − + ∂

∂ −

∂ + ∂

∂

∂

∂ −

∂ + ∂

∂ − + ∂

∂

∂

=

⎥ ⎥

⎥ ⎥

⎦

⎤

⎢ ⎢

⎢ ⎢

⎣

⎡

∂

∂ ∂

∂

′ =

f

x x

x x x

f x

x f

x x

f x

f

x f x f

x x x

x f x x

x f

x x x

x x f

x x f

x f x f

x x x

x f x x

x f x

f

x x x

x x f

x x f x

f

x x x f

x x x f f

) (

),

( x

^*

d x x

^*

c = f ∇ = − ^{라 가정}

) (

),

( x

^*

d x x

^*

c = f ∇ = − ^{라 가정}

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

- - Newton Newton 방법을 방법을 이용한 이용한 해법 해법 (1) (1)

단계 1 - x ^{( 1 )} 구하기

2 2 2

1 2

1 2

1 2

1 , ) 2 2

( x x x x x x x x

f = − + + +

Minimize

.

^{( ) ( ) ( 1) ( ) ( )}

가정한다 갖는다고

최소값을 가

함수

에서 점

증가한 만큼

에서 출발점

방법은 이

f

k k

k k

k

x x x x

x Δ

⁺

= + Δ

.

,

,

,

) 1 ( 2 )

2 ( 2 )

1 ( 2 )

0 ( 1 ) 1 ( 1 )

0 ( 1

) 0 ( ) 1 ( )

0 (

이다 즉

여기서

x x

x x

x

x = − Δ = −

Δ

−

=

Δ x x x

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

⎟ ⎟

⎟ ⎟

⎠

⎞

⎜ ⎜

⎜ ⎜

⎝

⎛

∂

∂

∂

∂

∂

∂

∂

∂

∂

∂

= 2 2

2 ) 4

(

2 2 2

1

2 1 1

1

2 2 2

2 1

2

2 1

2 2

1 2

x x x

x

x x x

x

f f

f f

x f x

x f

x x

f x

f H x

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

∇

=

∇

2 1

2 1

2

1

1 2 2

2 4

) 1 , ( )

(

2 1

x x

x x

f x f

x f f

x

x

x

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

27

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

27/252

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

- - Newton Newton 방법을 방법을 이용한 이용한 해법 해법 (2) (2)

2 이므로 2

4

2 2

1

2 4

1

1 2 2

1 2 2

1 1 2 1

2 1

2 1

=

=

=

=

+ +

−

=

+ +

=

x x x

x x x

x x x x

f f

f f

x x

f

x x

f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

− −

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

⎛ Δ

⎟⎟ Δ

⎠

⎜⎜ ⎞

⎝

⎛

1 1 2

2

2 4

) 0 ( 2

) 0 ( 1

x x

. 5

. 1

, 1

₁⁽⁰⁾ ₂⁽⁰⁾

이다 에서 Δ x = − Δ x =

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝ + ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛ Δ

+

=

∴ 1 . 5

1 5

. 1

1 0

)

0

0 ( )

0 ( )

1

(

x x

x

⎟ 이고

⎟

⎠

⎞

⎜ ⎜

⎝

− ⎛

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

⎛ Δ Δ

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛

2 1

2 2 2 1

2 1 1 1

) 0 ( 2

) 0 ( 1

x x x

x x x

x x x x

f f x

x f

f

f f

-

2

-

1.5

-

1

-

0.5 0 0.5 1

-

1

-

0.5 0 0.5 1 1.5 2

x

₁

x

₂

) 0

x ( )

1

x (

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

- - Newton Newton 방법을 방법을 이용한 이용한 해법 해법 (3) (3)

단계 2 - x ^{( 2 )} 구하기

거치면 과정을

같은 과

단계 1

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

− ⎛

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

⎛ Δ Δ

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛

2 1

2 2 2 1

2 1 1 1

) 1 ( 2

) 1 ( 1

x x x

x x x

x x x x

f f x

x f

f

f f

⎟⎟ ⎠

⎜⎜ ⎞

⎝

− ⎛

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

⎛ Δ

⎟⎟ Δ

⎠

⎜⎜ ⎞

⎝

⎛

0 0 2

2

2 4

) 1 ( 2

) 1 ( 1

x x

. 0

, 0

₁⁽¹⁾ ₂⁽¹⁾

이다 에서 Δ x = Δ x =

.

001 . 0

) 2 (

) 1 ( ) 2 (

된다 최적해가

이

이므로 따라서

x

x

x − ≤ ε =

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝ + ⎛

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

Δ +

=

∴ 1 . 5

1 0

0 5

. 1

)

1

1 ( )

1 ( )

2

(

x x

x

-

0.5 0 0.5 1 1.5 2

x

₂

) 0

x ( ) 1 ( )

2

( x

x =

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

29

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

29/252

Gradient

Gradient 방법 방법

- - Davidon- Davidon -Fletcher Fletcher- -Powell(DFP Powell(DFP ) ) 방법 방법 (1/2) (1/2)

1차 미분만을 이용하여 의 역 헷세 행렬을 근사적으로 계산하는 방법

단계 1 : 시작점 를 추정한다 .

목적 함수의 역 헷세 행렬을 근사적으로 추정하기 위해 대칭의 양정 행렬 을 선정한다 . 처음 시작할 때는 를 선택할 수 있다 . 수렴 매개 변수 을 정하고 , 이라 두고 Gradient 벡터를 다음과 같이 계산한다 .

단계 2 : Gradient 벡터의 Norm 를 계산한다.

만일 이면 반복 과정을 멈추고 그렇지 않으면 다음 단계로 계속 진행한다 . 이 방법의 첫 단계는 최속 강하법과 같다. 즉, 첫 단계에서는 단계 4로 간다.

단계 3 : 탐색 방향을 다음과 같이 계산한다.

즉 , Newton 방법의 을 근사적으로 로 대체한다 .

) f (x

) 0

x ( )

0

A ( A ^{( 0 )} = I

= 0 ε k

) ( ^{( 0 )}

) 0 ( )

0

( c x

d = ≡ ∇ f

)

c (k

ε

<

)

c (k

) ( ) ( )

(

k

A

k

c

k

d = −

− 1

H A

Gradient

Gradient 방법 방법

- - Davidon- Davidon -Fletcher Fletcher- -Powell(DFP Powell(DFP ) ) 방법 방법 (2/2) (2/2)

단계 4 : 를 최소화하는 이동 거리 를 계산한다 .

단계 5 : 설계점을 로 수정한다 .

단계 6 : 목적 함수의 근사적 역 헷세 행렬 를 다음과 같이 보정한다 .

여기서, 보정 행렬 는 다음과 같이 계산한다.

단계 7 : 로 두고 단계 2를 수행한다.

) ( ⁽

^k

^{) (}

^k

⁾

f x + α d α

_k

= α

) ( )

( )

1

(

k

k k

k

x d

x ⁺ = + α

)

A (k

n

k

n

k k

k

^{+ 1 )} = ^{( )} + ^{( )} + ^{( )} ; ×

( A B C

A ^행렬

) ( )

(

^k

, C

^k

B

n

k

n

k

T k k

k

×

= ⋅ ; )

(

) (

) ( ) (

) ( ) ( )

(

y s

s

B s

_{k k}

n n

T k k

k

×

⋅

= − ; )

(

) (

) ( ) (

) ( ) ( )

(

z y

z C z

1

; )

(

1

;

1

;

) ( ) ( )

(

) 1 ( )

1 (

) ( )

1 ( )

(

) ( )

(

k k k

k k

k k

k

k k k

n f

n n

y A z

x c

c c

y

d s

=

×

∇

=

×

−

=

×

=

+ +

+

α

n n × [

; ^행렬 ][ n × 1 ^벡터 ] = n × 1 ^행렬

+ 1

= k k

행렬 행렬

벡터

벡터

벡터

선박기본설계개론

선박기본설계개론 , 2006.3 , 2006.3

_NAOE/SNU

31

서울대학교

서울대학교조선해양공학과조선해양공학과학부학부33학년학년교과목교과목““전산선박설계전산선박설계””, 2006, 2006학년도학년도2학기2학기

31/252

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

- - Davidon- Davidon -Fletcher Fletcher- -Powell(DFP Powell(DFP ) ) 방법을 방법을 이용한 이용한 해법 해법 (1) (1)

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

= −

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

1 1 2

2 1

2 4

1

2 1

2 ) 1

0 (

x x

x c x

001 . 0 )

1 (

1

^{2 2}

) 0

(

= + − > ε =

c

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

−

= 1

)

1

( ) ( )

0

(

A

0

c

0

d

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝ + ⎛−

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛

α α α

1 1 0

)

0 x

(1

으로부터

조건 가질

최소값을 가

함수 ) 0 (

) (

) 1 (

) 1 (

α = d df

f x

x

= 1 α

2 2 2

1 2

1 2

1 2

1 , ) 2 2

( x x x x x x x x

f = − + + +

⎟⎟ ⎠

⎜⎜ ⎞

⎝

⎛

+ +

−

+

= +

∇

=

∇

2 1

2 1

2

1

1 2 2

2 4

) 1 , ( )

( x x

x x x

x f f x

단계 1 - x ^{( 1 )} 구하기

I A

x ⎟⎟ =

⎠

⎜⎜ ⎞

⎝

= ⎛

⁽⁰⁾

) 0

(

,

0 0

α α 2 )

( x

⁽¹⁾

=

²

− f

-

2

-

1.5

-

1

-

0.5 0 0.5 1

-

1

-

0.5 0 0.5 1 1.5 2

x

₁

x

₂

) 0

x ( )

1

x (

⎟⎟ ⎠

⎜⎜ ⎞

⎝

= ⎛−

∴ 1

)

1

1

x

(