@ SDALAdvanced Ship Design Automation Lab.

(1)

2009 Fall, Computer Aided Ship Design – Part1 Optimal Ship Design

@ SDAL

Advanced Ship Design Automation Lab.

http://asdal.snu.ac.kr Seoul

National Univ.

Naval Architecture & Ocean Enginee ring

@ SDAL

2009 Fall, Computer Aided Ship Design – Part1.Optimal Ship Design

Computer Aided Ship design -Part I. Optimal Ship Design-

September, 2009 Prof. Kyu-Yeul Lee

Department of Naval Architecture and Ocean Engineering, Seoul National University of College of Engineering

학부3학년 교과목“전산선박설계(Computer Aided ship design)”강의 교재

(2)

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.3 Optimality Condition Using Kuhn- Tucker Necessary Condition

3.1 Optimal Solution Using Optimality Condition 3.2 Lagrange Multiplier for equality constraints

3.3 Kuhn-Tucker Necessary Condition for inequality

constraints

(3)

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.3 Optimality Condition Using Kuhn- Tucker Necessary Condition

3.1 Optimal Solution Using Optimality Condition

- Ch.3 Optimality Condition Using Kuhn-Tucker Necessary Condition

(4)

@ SDAL

1변수 함수의 최적성 조건

- 함수의 극대, 극소(고교 과정 Review)

x y

1 1

-1

x

y

1 1

-1

극대

극소

1) 극대값 : 에서 연속 함수 f(x)가 증가에서 감소 상태로 변함 2) 극소값 : 에서 연속 함수 f(x)가 감소에서 증가 상태로 변함

0 )

(

' x ^*  f

( 에서 극대 또는 극소값을 가질 필요 조건)

 고등학교 수학의 정석(수학 II) Review

- 수학의 정석 ‚6. 극대, 극소와 미분‛(p. 104)

x

*

x  x

*

x 

x

*

x 

4/54

(5)

@ SDAL

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

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

R x

dx x x f x d

dx x x x df

f x

f  ^*  ^*  ^*  ² ( ₂ ^* ) (  ^* ) ²  2

) 1 ) (

) ( ( )

(

pf) 주어진 점 x

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

나머지항(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   

함수 값의 변화량

R d

x f

d x f x

f   

 ^* '' ( ^* ) ²

2 ) 1

( ' )

(

5/54

(6)

@ SDAL

1변수 함수의 최적성 조건 - 1계 필요 조건(2)

x

*

x 

에서 국부적 후보 최소점이기 위해서는

f  0

따라서,

d (  x  x ^* )

^{의 부호에 상관없이}

f  0

^{를 만족하려면}

f ' ( x

^*

)  0

R d

x f

d x f x

f x

f     

 ^* ^* '' ( ^* ) ²

2 ) 1

( ' )

( )

(

0 )

(

' x ^* 

f

를 만족하는 점 : 국부적으로 최소, 최대, 또는 변곡점

총칭하여 상점(Stationary point)이라고 함

cf)

보다 함수 값이 작은 점(x^*+d )이 존재하므로 x^*는 최소점이 아님

) ( x ^* f

에서 최소값

) ( x ^* f

x * x ^*  d d

x ^*  x ^*  d x ^* x ^*  d x ^*  d x ^* x ^*  d

의미 : x^*에서의 함수 값이 x^*

d에서의

함수 값보다 작으면 x^*는 국부적

후보 최소점이 될 가능성이 있음

이어야 함



이와 유사한 개념으로 에서 국부적 후보 최대점이 되기 위해서는 이어야 하며,

의 부호에 상관없이 를 만족하려면 이어야 함

x

*

x  f  0

) ( x x ^*

d   f  0 f ' ( x

^*

)  0

에서 최대값

) ( x ^* f

- Ch.3 Optimality Condition Using Kuhn-Tucker Necessary Condition ^6/54

(7)

@ SDAL

1변수 함수의 최적성 조건 - 충분 조건과 2계 필요 조건

 상점( 를 만족하는 점) 중 어느 점이 최소점인지 결정하는 방법 상점이므로, . 따라서,

f ' ( x ^* )  0  f x  f '' ( x ^* ) d ²  R

2 ) 1 (

2차항이 다른 모든 고차항에 비해 지배적인 항이므로,

d≠0에 대하여 다음 조건을 만족하면 항상

f  0

0 )

(

'' x

^*

 f

cf) f ' ' ( x ^* )  0

인 경우 국부적으로 최소점인지 알 수 없다.

∵ 1계, 2계 미분이 모두 0이므로, 국부적으로 최소이기 위해서는

3계 미분계수는 0이 되어야 하고, 4계 미분계수가 양수(>0)여야 한다.

즉, R의 부호에 따라 달라지게 된다.

(충분 조건(Sufficient condition))

 2계 필요 조건 :

0 )

(

'' x

^*

 f

국부적으로 최소값을 가지면,

(※ 단, 역은 성립하지 않는다.)

R d

x f d

x f x

f x f x

f     

 ^* ^* '' ( ^* ) ²

2 ) 1

( ' )

( )

(

x

*

x 

에서 국부적 후보 최소점이기 위해서는

f  0

따라서,

d (  x  x ^* )

^{의 부호에 상관없이}

f  0

^{를 만족하려면}

f ' ( x

^*

)  0

^{이어야 함}

0 ) (

' x

^*

 f

(8)

@ SDAL

1변수 함수의 최적성 조건(요약)

 충분 조건, 필요 조건, 필요 충분 조건

(고등학교 수학의 정석 ‘명제와 조건’ 참고) 1) A는 B의 충분 조건이다.

“A이면 B이다.” ( ) 2) C는 D의 필요 조건이다.

“D이면 C이다.” ( ) 3) E는 F의 필요 충분 조건이다.

“E이면 F이고, F이면 E이다.” ( )

B A 

D C 

F E 

 1계 필요 조건(1

^st Order necessary condition)

 2계 필요 조건(2

^nd Order necessary condition)

 충분 조건(Sufficient condition)

0 )

(

' x ^*  f

가 국부적 후보 최소점이면,

cf)

f ' ( x ^* )  0

이면, 가 상점(극소, 극대, 변곡점) 이다.

0 )

( '

' x

^*

 f

상점( )일 경우

이면 가 국부적 최소점이다.

0 )

( '

' x

^*

 f

가 국부적 최소점이면,

x *

0 )

(

' x ^*  f

x *

8/54

(9)

@ SDAL

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

R x

x x x f

x x x x

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 2 2 2

* 1 1 1

x x

x 



 



 







 





 







 





 

 

 



_T

T

x f x

x x

x f x f x

x x x f x x

f

 



^*



^*



^*



* 2 2

* 1 1

2 2 2

1 2

2

2 1

2

2 1 2

* 2 2

* 1 1

* 2 2

* 1

* 1 2 2 2

2 2

* 1 1 2 1

2

* 2 2 1 2 2

* 1 2 1

1 2 2

* 2 2 2

2 2

* 2 2

* 1 1 2 1

2 2

* 1 2 1

1 2

) 2 (

1 2 1

) (

) 2 (

) 1 (

) )(

( 2

) 2 (

1 x x x H x

x  



 

 







 





 











 

 







 



 



 



 

 



 



 

 

 

 

 



 



 



 



 

 



T

x x

x f x

x f

x x

f x

x x x

x x

x x x

x x x f x x

x x f x x

x f x x

x f x x x x

x x f

(10)

@ SDAL

2변수 함수의 테일러 전개(2)

 2변수 테일러 전개식의 행렬 표기법

    ^R

f f

f  ^*   ^* ^T  ^*   ^* ^T ( ^* )  ^*  2

) 1 (

) ( )

( )

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

 다변수 함수의 테일러 전개식의 행렬 표기법 : 2변수 전개식과 동일

 2 2 

* 2

* 1

* 2

1 , ) , ( , ) ,

(   _

 x x ^T x x x ^T H M x

n

M n

f

 

 H

x

x ,

^*

, : n 차원 Vector

R f

f

f x  d  x   x ^T d  d ^T H ( x ) d  2

) 1 ( )

( )

( ^* ^* ^* ^*



x  x ^*  d

로 정의 하면, 다음과 같이 표현 가능

2x2 Matrix의 원소

, 0 )

( ^* 

 f x ^T ( ) 0 2

1 d ^T H x _* d   x  x ^*

에서 최소이기 위한 충분 조건

10/54

(11)

@ SDAL

[참고] 헷세 행렬(Hessian Matrix)

 





 







 



2 2

1 2

2 2 2

2 2

1 2

2 1 2

2 1

2 2

1 2

2 n n

n

n n

x f x

x f

x x

f x

x f

x x

f x

x f x

f











x x

) , , 2 , 1

; , , 2 , 1 (

2 n j

n x i

x f

j i



 

 

 



 







  H

 헷세 행렬(Hessian Matrix) : Gradient Vector를 한번 더 미분하면(각각, 에 대하여 미분), 함수 에 대한 2계 편도함수의 행렬을 얻게 되는데, 이를 헷세 행렬이라고 정의함.

x i

) (x f

 ^x ₁ ^x ₂ ^ ^x _n  ^T

 x

: n개의 변수를 가지는 column Vector(열벡터)

즉, Gradient Vector의 각 성분을

x ₁ , x ₂ ,  , x _n

으로 미분하면 다음을 얻는다.

 헷세 행렬은 보통 H 또는

 ² f

로 표시

 헷세 행렬의 대칭성

i j j

i x x

f x

x f



 



따라서, 헷세 행렬은 항상 대칭 행렬

11/54

(12)

@ SDAL

2차 형식(Quadratic Form)

 2차 형식 : 한 변수의 제곱항과 서로 다른 두 변수의 곱항(다변수 곱항)의 합으로 이루어진 함수

ex)  2 3 3 ² 

2 2 3

1 2

1 3

2 1 2 2 4 6 4 5

2 ) 1 , ,

( x x x x x x x x x x x x

F      

2차 형식은 다음과 같이 행렬로 표현이 가능하다.

    ^x ^T ^A ^x

x x x x

x x

x x x

F 2

1 5

2 2

2 6

1 2 1

2 2

, 1 ,

3 2 1 3

2 1

3 2

1 

 







 







 







 











A : 대칭 행렬

(Symmetric Matrix)

 대칭행렬 A의 구성 방법 (A의 (i,j) 성분을 a

_ij

로 나타냄)

1) 대각 성분은 제곱항의 계수

2) 대각 성분 이외의 성분은

다변수 곱항 계수의

½

 _i ² ^의 ^계수 

ii x

a 

 

2  1

 _i _j 의 계수

ij x x

a

Hd d ^T 2 1

12/54

(13)

@ SDAL

2차 형식의 형태

 2차 형식의 정의

1) 양정 형식(Positive Definite) : 인 모든 x에 대하여

2) 양반정 형식(Positive Semidefinite)

: 모든 x에 대하여

이고

3) 음정 형식(Negative Definite) : 인 모든 x에 대하여

4) 음반정 형식(Negative Semidefinite) : 모든 x에 대하여

5) 부정 형식(Indefinite)

: 어떤 x에 대해서는 양수 또는 음수

 0 x

 0

x x ^T Ax  0

 0 Ax x ^T

 0 Ax x ^T

 0 Ax x ^T

 2차 형식 정의의 이용

0 )

( '

' x

^*



f

^이면

x*는 국부적 최소점이다.

① 1변수 함수의 최소 조건

② 다변수 함수의 최소 조건

0 )

( x ^* d  H

d ^T

즉, 가 양정 형식이면

0 )

(

' x ^*  f

0 )

( x ^* d  H

d ^T

이면 인 x*(상점)에서

0

인

) ( 0 )

( ^*    ^* 

 f x ^T f x

**x*는 국부적 최소점이다.**

**x*(상점)에서**

 0 Ax

x ^T

^인

x  0

^{가 존재}

여기서, 가 양정 행렬이면

0 )

( x ^* d  H

d ^T

) ( x

^*

H

참고: KREYSZIG E., Advanced Engneering Mathematics, WILEY, 2006, 8.4. Eigenbasis. Diagonalization. Quadratic forms.

13/54

(14)

@ SDAL

2차 형식 행렬의 형태 결정을 위한 고유치 검사

Ax x

x ^T

F 2

) 1

( 

2차 형식 에 관련된 대칭

n  n

^행렬

A

^의

n

^{개의 고유치를}

n

i , i  1 ,...,



^{이라고 가정}

1) 가

F (x )

양정(Positive Definite)이기 위한 필요 충분 조건: 모든 고유치가 양수

2) 가

F (x )

양반정(Positive Semidefinite)이기 위한 필요 충분 조건: 모든 고유치가 음수가 아님

n

i  0 , i  1 ,...,



n

i  0 , i  1 ,...,



3) 가

F (x )

음정(Negative Definite)이기 위한 필요 충분 조건: 모든 고유치가 음수

n

i  0 , i  1 ,...,



n

i  0 , i  1 ,...,



4) 가

F (x )

음반정(Negative Semidefinite)이기 위한 필요 충분 조건: 모든 고유치가 양수가 아님

5) 적어도 하나의

 _i

가 음수이고 또 적어도 하나의

 _i

가 양수이면

F (x )

는 부정(Indefinite)임

14/54

(15)

@ SDAL

고유치 검사에 의한 2차 형식의 행렬의 형태 결정 예제

고유치 구하는 방법

v

Av   ( A   I ) v  0 det( A   I )  0

 







 









4 2 2

2 4 2

2 2 4 A

0 ) 8

( ) 2

( 4

2 2

2 4

2 2 2

4 det   ²  

 







 











8 , ) (

 2 중근

 

 

다음 행렬의 고유치를 구하여 행렬의 형태를 결정하시오.

모든 고유치가 양수이므로 주어진 행렬은 양정(Positive Definite) 행렬임

15/54

(16)

@ SDAL

**1) x*가 국부적 후보 최소점일 필요 조건 :**

2)

인 상점에서 x*가 국부적 최소점일 조건 :

다변수 함수의 후보 최적성 조건(요약)

 n개의 변수로 이루어진 다변수 함수

f (x )

에 대한 테일러 전개식

R f

f

f x  x   x ^T d  d ^T H ( x ) d  2

) 1 ( )

( )

( ^* ^* ^*

 함수의 변화량으로 위 식을 다시 쓰면,

R f

f   ^T  ^T 

 x d d H ( x ) d 2

) 1

( ^* ^*



x ^*

가 국부적으로 후보 최소점이면, 이어야 함

f  0

) 0 ( ^* 

 f x ^T

 0 )d H(x

d ^T ^*

^{ 위 조건은}

H(x ^* )

가 양정 행렬일 경우 성립한다.

) ,

2 , 1 (

, ) 0

( ^*

n x i

f

i

 

 

 x

즉,



0 ) ( 0 )

( ^*    ^* 

 f x ^T f x



(17)

@ SDAL

Solution

Optimum Problem

후보 최적성 필요 조건을 이용한 등호 제약 최적화 문제의 해법

2 2

2 1

2 1 , ) ( 1 . 5 ) ( 1 . 5 ) ( x x  x   x  f

0 2 )

,

( x ₁ x ₂  x ₁  x ₂   h

x₂를 x₁의 양함수(explicit function)로 표현하면,

2 )

( ₁ ₁

2   x   x  x

2 1

1 1 , ( )) ( 1 . 5 ) ( 2 1 . 5 ) ( x  x  x    x   f

0 4

1 2 1

0 ) 5 . 0 (

2 ) 5 . 1 (

2 2 1 2

1 2

1 1 1

1 























dx f d

x x

x

x dx x

df

) 1 , 1 ( ) ,

( ₁ ₂ 

 x x

^{: 국부적 최소점}

Minimize Subject to

(18)

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.3 Optimality Condition Using Kuhn- Tucker Necessary Condition

3.2 Lagrange Multiplier for equality constraints

(19)

@ SDAL

함수의 상점(Stationary Point)을 찾는 방법

Given: minimize f(x ₁ , x ₂ )

* * 1 2

( , x x )

* * 1 2

( , )

f x x

- 어떤 점 (x₁*, x₂*)에서 미소변위(dx₁, dx₂) 만큼 이동한 점에 서의 함수값의 변화량 df 는 다음과 같다.

Find: 상점 (x ₁ , x ₂ )

모든 방향으로의 함수값의 변화량 df 가 0인 점을상점

(Stationary Point)이라고 하며, 최소점, 최대점,

안장점(Saddle Point)은 상점에 속한다.

1 2

( , ) f x x

x

1

x

2

참고: 일반적인 공학적 최적화 문제에서는 목적 함수의 최적값 (Optimum Value)보다는 최적점(Optimum Point)이 더 중요하다.

[예시] 건조비를 최소화 하는 선박의 주요치수(L, B, D, C

_B

)가 건조비 자체보다 중요한 개념이다.

1 2

f f

df dx dx

x x

 

 

 

19/54

(20)

@ SDAL

제약조건이 없는 경우의 함수와 상점(Stationary Point)

1 2 3

f f f

df dx dx dx

x x x

  

  

  

상점에서의 df 는 0이다.

dx₁, dx_2,dx₃는 임의의 값이라고 하면 df 가 항상 0이 되기 위해서는

이 되어야 한다.

1 2 3

f f f 0

x x x

  

  

  

0   f

Given:

1 2 3

( , , ) minimize f x x x Find: 상점 (x ₁ , x ₂ , x ₃ *)

20/54

(21)

@ SDAL

제약조건이 있는 경우의 함수와 상점(Stationary Point)

1. 함수 h (제약조건)를 x₁에 대해서 정리

2. 함수 f 에 x₁을 대입하여 정리하고 f 의 전미분이 0임을 이 용하여 상점 구하기

제약 조건 h 를 하나의 변수로서 정리하기 어려울 수 있으며, 정리할 변수를 선택하는 것도 쉽지 않을 수 있다.

하나의 변수로 정리하지 않고, 상점을 구하 는 방법은 없을까?

상점에서의 df 는 0이다. h(x ₁ ,x ₂ ,x ₃ )=0 이므로 dh 는 0이다.

식 ①, ②는 모두 0이므로 다음 식이 항상 성립한다.

0 df ^{ }  dh ^

1 2 3

f f f 0

df dx dx dx

x x x

  

   

  

^①

h ₁ ¹ h ₂ ² h ₃ ³ 0

dh dx dx dx

x x x

  

   

  

^②

3

1 2 3 1 2

( , , ) tan cos

^x

0 h x x x  x  x  e 

예시) 제약 조건이 다음과 같은 경우 어느 한 변수로 정리하기 어려움

Given:

1 2 3

( , , ) minimize f x x x

Find: 상점 (x ₁ , x ₂ , x ₃ *)

1 2 3

( , , ) 0 h x x x 

 : Undetermined Coefficient

‘Lagrange multiplier’

21/54

(22)

@ SDAL

제약조건이 있는 경우의 함수와 상점(Stationary Point)

1 2 3

f f f 0

df dx dx dx

x x x

  

   

  

1 2 3

h h h 0

dh dx dx dx

x x x

  

   

  

위 식을 정리 하면

1 2 3 1 2 3

f f f h h h 0

dx dx dx dx dx dx

x x x  ^ x x x ^

             

       

1 2 3

1 1 2 2 3 3

f h f h f h 0

dx dx dx

x  x x  x ^ x  x ^

                 

         

     

- 제약조건 h가 있기 때문에 dx

₁

, dx

_2,

dx

₃

가 1차 독립이 아님.

①

②

0 df ^{ }  dh ^

Given:

1 2 3

( , , ) minimize f x x x

Find: 상점 (x ₁ , x ₂ , x ₃ *)

1 2 3

( , , ) 0 h x x x 

 : Undetermined Coefficient

‘Lagrange multiplier’

22/54

(23)

@ SDAL

제약조건이 있는 경우의 함수와 상점(Stationary Point)

1 2 3

1 1 2 2 3 3

f h f h f h 0

dx dx dx

x  x x  x ^ x  x ^

                 

         

     

λ값을 적절히 결정하여 첫번째 괄호 안의 값을 0으로 만들면 위 식은 dx₁에 무관하게 성립한다.

2 3

2 2 3 3

f h f h 0

dx dx

x  x ^ x  x ^

           

     

   

dx₂와 dx₃는 임의의 값이므로 위 식을 항상 만족하기 위해서는 괄호 안의 식이 0이 되어야 한다.

1 1 2 2 3 3

0, 0, 0

f h f h f h

x  x x  x ^ x  x ^

         

                        

따라서 다음을 만족하는 값

 , x ₁ , x ₂ , x ₃

을 찾으면 그 점이 상점이 된다.

1 2 3

, h x x x ( , , )  0

미지수: 4개 (x₁, x₂, x₃, λ) 식: 4개

유일해 존재

1 2 3

f f f

0

df dx dx dx

x x x

  

   

  

1 2 3

h h h

0

dh dx dx dx

x x x

  

   

  

- 제약조건 h가 있기 때문에 dx

₁

, dx

_2,

dx

₃

가 1차 독립이 아님.

①

②

0 df    dh 

Given:

1 2 3

( , , ) minimize f x x x

Find: 상점 (x ₁ , x ₂ , x ₃ *)

1 2 3

( , , ) 0 h x x x 

1 1 2 3 1 1 2 3 2 1 2 3 2 1 2 3

3 1 2 3 3 1 2 3

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

( , , ) ( , , ) 0

F x x x H x x x F x x x H x x x

F x x x H x x x

 



   

 

1, 2 3 1, 2 3

( , ), ( , )

i i

f h

F x x x H x x x

x x

   

 

 : Undetermined Coefficient

‘Lagrange multiplier’

23/54

(24)

@ SDAL

제약조건이 있는 경우의 함수와 상점(Stationary Point)

Given:

1 2 3

( , , ) minimize f x x x

Find: 상점 (x ₁ , x ₂ , x ₃ *)

1 2 3

( , , ) 0 h x x x 

1 1 2 2

1 2 3

3 3

0, 0

0, ( , , ) 0

f h f h

x x x x

f h

h x x x

x x

 



       

   

    

 

1 2 3 1 2 3 1 2 3

( , , , ) ( , , ) ( , , )

L x x x  ^ f x x x ^  h x x x

다음을 만족하는 값 을 찾으면

그 점이 상점이 된다.

¹ ² ³

, , , x x x



Lagrange 함수(L)를 정의 하고 L의 상점을 구함

1 2 3

( , , , ) 0 L x x x 

 

제약조건이 있는 최적화 문제를 제약조건이 없는 최적화 문제로 변경

1 1 1

L f h

0

x x  x

     

  

λ : Lagrange Multiplier L : Lagrange Function

1 2 3

( , , ) 0

L h x x x



  



2 2 2

L f h

0

x x  x

     

  

3 3 3

L f h

0

x x  x

     

  

_24/54

(25)

@ SDAL

[요약] 제약조건이 있는 경우의 함수와 상점

- 제약 최적화 문제와 그 해법 - 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

  

   

   ① ’

②

③

Necessary condition that minimize f : df = 0

⇒eq①’

dx

₁ , dx ₂ , dx ₃ are not independent because of h ₁

, h

₂

Optimization Problem

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 Number of variables: 3

Number of equation : 2

So, we cannot say that

1 2 3

0, 0, 0

f f f

x x x

     

  

Number of variables: 3 Number of equation : 3

We can solve it!

But it is difficult to solve.

처음에는 미지수 개수보다 식의 개수가 적은 부정 방정식 이었 는데, 어떻게 식의 개수와 미지수 개수가 같아 졌는가?

Minimize f 를 수식으로 표현 (df = 0) 하였기 때문에 식의 개수가 늘어 났음

(Num of Equation = Num of Variables)

25/54

(26)

@ SDAL

[요약] 제약조건이 있는 경우의 함수와 상점

- 제약 최적화 문제와 그 해법 - 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

  

   

   ① ’

②

③

Necessary condition that minimize f : df = 0

⇒eq①’

dx

₁ , dx ₂ , dx ₃ are not independent because of h ₁

, h

₂

Eq ②’, ③’are modified from eq ②, ③

Optimization Problem

①

②

③

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

To find relation between dx ₁ , dx ₂ , dx ₃ , modify eq②, ③

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

  

   

  

Number of variables: 3 Number of equation : 2

So, we cannot say that

1 2 3

0, 0, 0

f f f

x x x

     

  

26/54

(27)

@ SDAL

[요약] 제약조건이 있는 경우의 함수와 상점

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

①

②

③

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

Necessary condition

that minimize f and some

modification

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

  

   

  

그런데함수 f, h₁

, h

₂

(식①, ②, ③)는 주어진 것이고, 우리가

구하려고 하는 것은 x₁

, x

₂

, x

₃이기 때문에 x_1,x₂, x₃에 대한 미분 방정식이 됩니다.

식 ①’, ②’, ③’은 f, h₁, h₂에 대한미분 방정식이 아닌가요?

@ SDALAdvanced Ship Design Automation Lab.

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Computer Aided Ship design -Part I. Optimal Ship Design-

September, 2009 Prof. Kyu-Yeul Lee

Department of Naval Architecture and Ocean Engineering, Seoul National University of College of Engineering

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.3 Optimality Condition Using Kuhn- Tucker Necessary Condition

3.1 Optimal Solution Using Optimality Condition 3.2 Lagrange Multiplier for equality constraints

3.3 Kuhn-Tucker Necessary Condition for inequality

constraints

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.3 Optimality Condition Using Kuhn- Tucker Necessary Condition

3.1 Optimal Solution Using Optimality Condition

@ SDAL

1변수 함수의 최적성 조건

- 함수의 극대, 극소(고교 과정 Review)

1 1

-1

1 1

-1

1) 극대값 : 에서 연속 함수 f(x)가 증가에서 감소 상태로 변함 2) 극소값 : 에서 연속 함수 f(x)가 감소에서 증가 상태로 변함

0 )

(

' x *  f

( 에서 극대 또는 극소값을 가질 필요 조건)

 고등학교 수학의 정석(수학 II) Review

- 수학의 정석 ‚6. 극대, 극소와 미분‛(p. 104)

x

x  x

x 

x

x 

@ SDAL

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  2

) 1 ) (

) ( ( )

(

pf) 주어진 점 x

x

d x x

x 



R d

x f

d x f x

f x

f  *  *  '' ( * ) 2  2

) 1 ( ' )

( )

(

) ( )

( )

( x f x * f x

f   

R d

x f

d x f x

f   

 * '' ( * ) 2

2 ) 1

( ' )

(

@ SDAL

1변수 함수의 최적성 조건 - 1계 필요 조건(2)

x

x 

f  0

d (  x  x * )

' x ^*  f

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

f  ^*  ^*  ^*  ² ( ₂ ^* ) (  ^* ) ²  2

f  ^*  ^*  '' ( ^* ) ²  2

( x f x ^* f x

 ^* '' ( ^* ) ²

d (  x  x ^* )

 ^* ^* '' ( ^* ) ²

' x ^* 

) ( x ^* f

) ( x ^* f

x * x ^*  d d

x ^*  x ^*  d x ^* x ^*  d x ^*  d x ^* x ^*  d

) ( x x ^*

) ( x ^* f

f ' ( x ^* )  0  f x  f '' ( x ^* ) d ²  R

cf) f ' ' ( x ^* )  0

 ^* ^* '' ( ^* ) ²

d (  x  x ^* )