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

(1)

[2008][12-1]

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

(2)

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

Descent) 방법 방법

(3)

탐색

탐색 방향을 방향을 결정하기 결정하기 위한 위한 22차 차 계획 계획 문제의 문제의 정식화 정식화(1) (1)

여기서,

i i

i j

ij i j

ij i i

j j

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 H x x

x x

x

x + D @ f + Ñ f ^T D + D ^T D f ( ) ( ) ( ) 0 . 5

Minimize

m to j

g g

g

p to j

h h

h

T j j

j

T j j

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 급수의 2차항까지 고려한 목적 함수

선박기본설계개론

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

3 i

i

i j

ij i j

ij i i

j j

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

라고 가정하면

Matrix form

Minimize Subject to

) 1 ( ) ) (

1 ) (

1 ( 2

1 ´

´ ´

´ ´ +

= ^T ⁿ _n ^T ⁿ _n _n _n

f c d d H d

) 1 ( )

1 ) (

(

) 1 ( )

1 ) (

(

´

´ ´

´

´ ´

£

=

m n n

T m

p n n

T p

b d

A

e d

N

: 2차 형식의 목적 함수

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

(4)

황금분할법에

황금분할법에 의한 의한 이동 이동 거리의 거리의 결정 결정

강하 조건을 검토하기 위한 시행 설계점

1차원 탐색 방법(예: 황금 분할법)을 이용한 개선된 설계점 결정

(최종 결정된 가 로 변경됨)

( , ) ( ) ( )

( , )

k j k k

a

k j

= +

x x d

Æ 개선된 설계점을 구하기 위해 a_(k,j)를 얼마로 해야 하는가?

a

_(k,j)를 변경시켜 가면서 현재의 설계점보다 강하 함수를 감소시키는 설계점을 찾음

(1차원 탐색 방법(예: 황금 분할법) 이용 가능)

황금 분할법에 의해 최소값이 존재하는 구간을 찾은 뒤, 구간을 다시 내분하여 실제 최소값의 x좌표를 구함

) 1 ( +k ( , )k j

x

x x

^{( +}^k ¹⁾

4

황금 분할법에 의해 최소값이 존재하는 구간을 찾은 뒤, 구간을 다시 내분하여 실제 최소값의 x좌표를 구함

0 d

2.618d5.236d 9.472d

4 2

1

q = 0 …

16.326d 3

a _l a _a a _u

= = =

최소값이 존재하는 구간

) (x F

I

a _l a _a a _u _a

상한 하한

최소값이 존재하는 구간

a _b

0.618I 0.382I

) (x F

) 1 ( +k

x

(5)

2 2차 차 계획 계획 문제 문제(Quadratic Programming Problem) (Quadratic Programming Problem)의 의 정식화 정식화

Minimize Subject to

H_(nÍn) = I_(nÍn)라고 가정해서 근사화 한다.

) 1 ( ) ) (

1 ) (

1 ( 2

1 ´

´ ´

´ ´ +

= ^T ⁿ _n ^T ⁿ _n _n _n

f c d d H d

) 1 ( )

1 ) (

(

) 1 ( )

1 ) (

(

´

´ ´

´

´ ´

£

=

m n n

T m

p n n

T p

b d

A

e d

N

5

Minimize Subject to

) 1 ) (

1 ) (

1 ( ) ) (

1 ) (

1 ( 2

1 2

1 ´ ´

´ ´

´

´ ´

´ ´ + = +

= ^T ⁿ _n ^T ⁿ _n _n _n ^T ⁿ _n ^T ⁿ _n

f c d d I d c d d d

) 1 ( )

1 ) (

(

) 1 ( )

1 ) (

(

´

´ ´

´

´ ´

£

=

m n n

m T

p n n

T p

b d

A

e d

N

^{Æ H}^(nÍn) ^{= I}^(nÍn)이므로 목적 함수는 2차 형식이다.

Æ 모든 제약 조건은 선형이다.

Æ 이러한 문제는 볼록 계획(Convex Programming) 문제라고 하며, 해가 존재하면 이는 유일한 해 (전역 최적해)이다.

(6)

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

Simplex

Simplex 방법을 방법을 이용 이용, , 탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 22차 차 계획 계획 문제의 문제의 풀이 풀이(1/ (1/첫번째 첫번째 QP QP문제 문제))

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

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 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차 형식

6

) 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 ⁽ ⁾

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

2 0

0 1 0

1 0

0, , 1, 2, 3

i

L d

L u

i L

s i i

d u u

d d s

d s

u s u i

¶

= - + + - =

= + - + =

= - - + =

= - -

= ³ =

+ =

=

6 d₁ d₂

1 2 3 4 5

-1 -2

-1 -2 1 2 3 4 5 6

8.0 5.0 2.0 1.0 0.1 -0.8

A B

C

D

d₁=-1

d₂=-1 d₁+d₂=2

f Æ 도식화

(7)

Simplex

Simplex 방법을 방법을 이용 이용, , 탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 22차 차 계획 계획 문제의 문제의 풀이 풀이(2/ (2/첫번째 첫번째 QP QP문제 문제))

( )

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

2 0

0 1 0

1 0

0, , 1, 2, 3

i

L d

L u

i L

s i i

d u u

d d s

d s

u s u i

¶

= - + + - =

= + - + =

= - - + =

= - -

= ³ =

+ =

= u s

_{i i}²

= 0, u

_i

³ 0, i = 1, 2, 3

Minimize

Subject to

) (

5 . 0 )

( d

₁

d

₂

d

₁²

d

₂²

f = - - + +

1 1

2 1

3 2 2 3 1 1 3 1

£ -

£ +

d d

2차 계획 문제

7

을 으로 치환

2

s

i

s¢

_i

( )

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

2 0

0 1 0

1 0

0, , 1, 2, 3

i

L d

L u

i L

s i i

d u u

d d s

d s

u s u i

¶

= - + + - =

= + - + =

= - - + =

= - -

= ³ =

+ =

=

양변에 s

_i

를 곱한다.

2

0, 0, 1, 2, 3

i i i

u s = u ³ i =

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 1, 2, 3

, 0

i

L d

L u

L u L

i i

s

d u u

d d s

d s

d

s

s s

i u

u

¶

= - + + - =

= + - + ¢ =

= - - + ¢ =

¢

¢ ³ =

= =

편의상 을

이라고 표현

s¢

i

s

i

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 1, 2

, 0 , 3

i

i i

L d

L u

L u L s i i

d u u

d d s

d s

u s i u s

¶

= - + + - =

= + - + =

= - - + =

= - -

=

³

+ =

=

2

0

i i

s = s¢ ³

(8)

Simplex

Simplex 방법을 방법을 이용 이용, , 탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 22차 차 계획 계획 문제의 문제의 풀이 풀이(3/ (3/첫번째 첫번째 QP QP문제 문제))

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 0, 1, 2, 3

i

L d

L u

L u L s i i

i i

d u u

d d s

d s

u s

u s i

¶

= - + + - =

= + - + =

= - - + =

= =

³ =

Minimize Subject to

) (

5 . 0 )

( d

₁

d

₂

d

₁²

d

₂²

f = - - + +

1 1

2 1

3 2 2 3 1 1 3 1

£ -

£ +

d d

Matrix 형태로 표현

2차 계획 문제

8

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 0, 1, 2, 3

i

L d

L u

L u L s i i

i i

d u u

d d s

d s

u s

u s i

¶

= - + + - =

= + - + =

= - - + =

= =

³ =

여기서,

ú ú ú û ù ê ê ê ë é ú =

û ù ê ë

é

-

= -

ú û ù ê ë

= é ú û

ù ê ë é

-

= - ú û

ù ê ë

= é

´

1 1 1 ,

0 0 1

1 , 0

0 , 1

1 , 1

3 2

) 1 3 ( 3

1 3 1 )

3 2 (

) 2 2 ( )

1 2 ( 2 1 )

1 2 (

b A

H c

d d

d

(3 2) (2 1) (3 1) T

´ ´

£

´

A d b

Minimize Subject to

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

1 2 ) ( 2 1

(

2

1

´

´ ´

+

= c

^T

d d

^T

H d

f

Kuhn-Tucker 필요조건을 d, c, H, A, b를 이용하여 Matrix 형태로 표현하면?

(2 2)´

H

를

I_{(2 2)}_´

로 가정한다.

(9)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(4/ (4/첫번째 첫번째 QP QP문제 문제))

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 0, 1, 2, 3

i

L d

L u

L u L s i i

i i

d u u

d d s

d s

u s

u s i

¶

= - + + - =

= + - + =

= - - + =

= =

³ =

ú ú ú û ù ê ê ê ë é ú =

û ù êë

é

-

= -

úû ù êë

=é úû

ù êë é -

= - úû

ù êë

=é

´

1 1 1 ,

0 0 1

1 , 0

0 , 1

1 , 1

3 2

) 1 3 ( 3

1 3 1

) 3 2 (

) 2 2 ( )

1 2 ( 2 1 ) 1 2 (

b A

H c

d d

d

1

1 3 1 2

1

2 3 1 3

1 1

1 3

1 2

2 3

3

(2 1) (2 2) (2 1) (2 3) (3 1)

1 1

1 0

1 1 0

0 1

1 0 1

d u u

d u d u

u

´ ´ ´ ´ ´

- + + -

é ù

ê - + + - ú

ë û

é ù -

- é ù é ù

é ù é ù ê ú

= ê ë - ú û + ê ë ú û ë ê ú û + ê ë - ú û ê ú ê ë ú û

= c + H d + A u = 0

1 1 1 2

1 2 1 1

3 3 3 3

1

1 2 2

2

2 3 3

(3 2) (2 1) (3 1) (3 1)

( 2)

1 1 0 1

1 0 1 1

T

d d s s

d s d s

´ ´ ´ ´

+ - +

é ù é ù é ù é ù

é ù

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

ê ú ê ú ê ú ê ú

ë û

ê - - + ú ê - ú ê ú ë û ê ú

ë û ë û ë û

= A d + s - b = 0

9

Matrix 형태로 표현

( )

1

2

1

2

3

1

1 3 1 2

1

2 3 1 3

1

1 2 1

3

1 2

2 3

1 0

2 0

1 0

0 , 0, 1, 2, 3

i

L d

L u

L u L s i i

i i

d u u

d d s

d s

u s

u s i

¶

= - + + - =

= + - + =

= - - + =

= =

³ =

1 1 1 2

1 2 1 1

3 3 3 3

1

1 2 2

2

2 3 3

(3 2) (2 1) (3 1) (3 1)

( 2)

1 1 0 1

1 0 1 1

T

d d s s

d s d s

´ ´ ´ ´

+ - +

é ù é ù é ù é ù

é ù

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

ê ú ê ú ê ú ê ú

ë û

ê - - + ú ê - ú ê ú ë û ê ú

ë û ë û ë û

= A d + s - b = 0

-

´ +

´

´₁₎

=

₍₂ ₁₎

-

₍₂ ₁₎

2

(

d d

d

한편, 설계 변수 d는 부호의 제한이 없으므로

Simplex 방법을 이용하기 위해 다음과 같이 표현해야 함

= =

ú û ù ê ë

= é-

ú ú ú ú ú

û ù

ê ê ê ê ê

ë é ú û ù ê ë

é

- -

´

´ -

´ +

´

´ ´

´

) 1 3 (

) 1 2 (

) 1 3 (

) 1 2 (

) 3 3 ( ) 3 3 ) (

2 3 ( )

2 3 (

) 3 2 ( ) 3 2 ( )

2 2 ( )

2 2 (

b c

s u d d I

0 A

A

0 A

H H

T T

) 10 5

B

( ´

D

_{( ´}₅ ₁₎

) 1 10 ( ´

= X

(10)

ú û ù ê ë

= é-

ú ú ú ú ú

û ù

ê ê ê ê ê

ë é ú û ù ê ë

é

- -

´

´ -

´ +

´

´ ´

´

) 1 3 (

) 1 2 (

) 1 3 (

) 1 2 (

) 3 3 ( )

3 3 ) (

2 3 ( )

2 3 (

) 3 2 ( )

3 2 ( )

2 2 ( )

2 2 (

b c

s u d d I

0 A

A

0 A

H H

T T

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(5/ (5/첫번째 첫번째 QP QP문제 문제))

Ñ L ( d

⁺

, d

^-

, u , s ) = 0

) 10 5

B ( ´

= ⁼ D _{( ´} ₅ ₁ ₎

) 1 10 ( ´

X

=

10

여기서,

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

- -

´

=

1 0 0 0 0

0 1 0

1 0

0 1 0 0 0

0 0 1

0 1

0 0 1 0 0

0 0 0 0 1 0

1 0

0 0 0 0 1 0

1 0

1

3 1 3

1 3

1

3 1 3 1

) 10 5

B

(

[

₁ ₂ ₁ ₂ ₁ ₂ ₃ ₁ ₂ ₃

] ^,

⁽¹ ⁵⁾

[ ¹ ¹

₃²

¹ ¹ ]

) 10 1

( ^´

=

⁺ ⁺ ^- ^- ^T ^´

=

T

d d d d u u u s s s D

X

) 1 10 ( ´

X

ú ú ú û ù ê ê ê ë é ú =

û ù ê ë

é

-

= - ú û

ù ê ë

= é ú û

ù ê ë é

-

= - ú û

ù ê ë

= é ú û

ù ê ë

= é

_- _´ _´ _´ _´

- -

+ ´ + +

´

1 1 1 ,

0 0 , 1

1 0

0 , 1

1 , 1

,

3 2

) 1 3 ( 3

1 3 1 ) 3 2 ( )

2 2 ( )

1 2 ( 2 1 )

1 2

(

d c H A b

d d

d

(11)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(6/ (6/첫번째 첫번째 QP QP문제 문제))

) 1 5 ( )

1 10 ( ) 10 5

( ´ X ´ = D ´

B

Kuhn-Tucker 필요 조건(행렬식 표현)

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

=

ú ú ú ú ú ú ú ú ú ú ú ú ú ú

û ù

ê ê ê ê ê ê ê ê ê ê ê ê ê ê

ë é

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

- -

-

_-

- + +

1 1 1 1

1 0 0 0 0 0 1 0

1 0

0 1 0 0 0 0 0 1

0 1

0 0 1 0 0 0

0 0 0 1 0

1 0

0 0 0 0 1 0

1 0

1

3 2

3 2 1 3 2 1 2 1 2 1

3 1 3

1 3

1 3 1

3 1 3 1

s s s u u u d d d d

11

Æ X를 구하는 위 문제는 등호 제약 조건만으로 이루어진 선형 계획 문제임

Æ : Simplex 방법을 이용하여 부정 선형 연립 방정식에서 구한 해가 이 비선형 부정 방정식을 만족하는지

확인하여 해를 확정한다

3 1

;

0 i to s

u _i _i = =

구하려는 값

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

=

ú ú ú ú ú ú ú ú ú ú ú ú ú ú

û ù

ê ê ê ê ê ê ê ê ê ê ê ê ê ê

ë é

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

- -

-

_-

- + +

1 1 1 1

1 0 0 0 0 0 1 0

1 0

0 1 0 0 0 0 0 1

0 1

0 0 1 0 0 0

0 0 0 1 0

1 0

0 0 0 0 1 0

1 0

1

3 2

3 2 1 3 2 1 2 1 2 1

3 1 3

1 3

1 3 1

3 1 3 1

s

u

d

(12)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(7/ (7/첫번째 첫번째 QP QP문제 문제))

Simplex 방법을 이용한 QP 문제의 해법

1. Kuhn-Tucker 필요 조건의 해를 구하는 문제는 등호 제약 조건만으로 이루어진 부정 선형 연립 방정식의 해를 구하는 문제(선형 계획 문제)임

2. 부정 선형 연립 방정식의 해를 구하기 위하여 Simplex 방법에서 인위 변수 및 인위 목적 함수를 도입하여 초기 기저 가능해를 구하는 방법임

3. 인위 목적 함수는 다음과 같이 정의함

å åå

å å

=

= =

=

+

= -

=

10 1 0

10 1 5

1 5

1 j

j j j i

j ij i

i i

i D B X w C X

Y w

) 1 5 ( )

1 5 ( )

1 10 ( ) 10 5

( ´ X ´ + Y ´ = D ´

B

인위 변수

12

å åå

å å

=

= =

=

+

= -

=

10 1 0

10 1 5

1 5

1 j

j j j i

j ij i

i i

i D B X w C X

Y w

여기서,

3 14 3

2 5

1 0

5

1 1 1 1

1 + + + + =

=

= -

=

å å

=

i

i i

ij j

D w

B

C : 행렬 B의 j번째 열의 요소를 모두 더해 부호를 바꾼 것(상대 비용 계수)

4. Simplex 방법을 이용하여 해를 구하고 다음 식을 만족하는지 확인함

: 인위 목적 함수의 초기값으로 행렬 D의 모든 요소를 더한 것

3 1

;

0 i to s

u _i _i = = : Simplex 방법을 이용하여 부정 선형 연립 방정식에서 구한 해가

이 비선형 부정 방정식을 만족하는지 확인하여 해를 확정한다.

(13)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(8/ (8/첫번째 첫번째 QP QP문제 문제))

인위 변수

) 1 5 ( )

1 5 ( )

1 10 ( ) 10 5

( ´ X ´ + Y ´ = D ´

B ^Æ

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

= ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é +

ú ú ú ú ú ú ú ú ú ú ú ú ú ú

û ù

ê ê ê ê ê ê ê ê ê ê ê ê ê ê

ë é

=

ú ú ú ú ú ú

û ù

ê ê ê ê ê ê

ë é

- -

-

_-

- + +

1 1 1 1

) (

1 0 0 0 0 0 1 0 1 0

0 1 0 0 0 0 0 1 0 1

0 0 1 0 0 0

0 0 0 1 0

1 0

0 0 0 0 1 0

1 0

1

3 2

5 4 3 2 1

10 3

9 2

8 1

7 3

6 2

5 1

4 2

3 1

2 2

1 1

3 1 3 1 3

1 3 1

3 1 3 1

Y Y Y Y Y

X s

X u

X d

인위 목적 함수의 구성

1 1 1 1 2 14

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5

3

X +

3

X -

3

X -

3

X +

3

X - X - X + X + X + X + Y + Y + Y + Y + Y =

3

1행부터 5행까지 모두 더함:

13

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Y1 Y2 Y3 Y4 Y5 bi bi/ai

Y1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

Y2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

Y3 1/3 1/3 -1/3 -1/3 0 0 0 1 0 0 0 0 1 0 0 2/3 2/3

Y4 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 -

Y5 0 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -

A. Obj. -1/3 -1/3 1/3 1/3 -2/3 1 1 -1 -1 -1 0 0 0 0 0 w-14/3 -

1

각 열의 요소를 모두 더해 부호를 바꾼 것(예, 1열: -(1+0+1/3-1+0)=-1/3) 인위 목적 함수 식

1 1 1 1 2 14

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5

3

X +

3

X -

3

X -

3

X +

3

X - X - X + X + X + X + Y + Y + Y + Y + Y =

3

1행부터 5행까지 모두 더함:

인위 변수의 합을 w로 치환하고 정리:

w

1 1 1 1 2 14

1 2 3 4 5 6 7 8 9 10

3

X

3

X

3

X

3

X

3

X X X X X X w

3

- - + + - + + - - - = -

(14)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(9/ (9/첫번째 첫번째 QP QP문제 문제))

Y1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

Y2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

X8 1/3 1/3 -1/3 -1/3 0 0 0 1 0 0 0 0 1 0 0 2/3 -

Y4 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1

Y5 0 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -

A. Obj. 0 0 0 0 -2/3 1 1 0 -1 -1 0 0 1 0 0 w-4 -

2

Y1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

3

14

Y1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 1

Y2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

X8 1/3 1/3 -1/3 -1/3 0 0 0 1 0 0 0 0 1 0 0 2/3 2

X9 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 -

X10 0 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -

A. Obj. -1 -1 1 1 -2/3 1 1 0 0 0 0 0 1 1 1 w-2 -

Y1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

Y2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

X8 1/3 1/3 -1/3 -1/3 0 0 0 1 0 0 0 0 1 0 0 2/3 -

X9 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 -

Y5 0 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1

A. Obj. -1 0 1 0 -2/3 1 1 0 0 -1 0 0 1 1 0 w-3 -

4

(15)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(10/ (10/첫번째 첫번째 QP QP문제 문제))

X1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

Y2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 1

X8 0 1/3 0 -1/3 -1/9 1/3 0 1 0 0 -1/3 0 1 0 0 1/3 1

X9 0 0 0 0 1/3 -1 0 0 1 0 1 0 0 1 0 2 -

X10 0 -1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -

A. Obj. 0 -1 0 1 -1/3 0 1 0 0 0 1 0 1 1 1 w-1 -

5

6

15

X1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

X2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

X8 0 0 0 0 -2/9 1/3 1/3 1 0 0 -1/3 -1/3 1 0 0 0 -

X9 0 0 0 0 1/3 -1 0 0 1 0 1 0 0 1 0 2 -

X10 0 0 0 0 1/3 0 -1 0 0 1 0 1 0 0 1 2 -

A. Obj. 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 w-0 -

6

인위 목적 함수가 0이므로

초기 기저 가능해가 구해졌음

(16)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(10/ (10/첫번째 첫번째 QP QP문제 문제))

X1 1 0 -1 0 1/3 -1 0 0 0 0 1 0 0 0 0 1 -

X2 0 1 0 -1 1/3 0 -1 0 0 0 0 1 0 0 0 1 -

X8 0 0 0 0 -2/9 1/3 1/3 1 0 0 -1/3 -1/3 1 0 0 0 -

X9 0 0 0 0 1/3 -1 0 0 1 0 1 0 0 1 0 2 -

X10 0 0 0 0 1/3 0 -1 0 0 1 0 1 0 0 1 2 -

A. Obj. 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 w-0 -

6

인위 목적 함수가 0이므로 초기 기저 가능해가 구해졌음

[

1 2 1 2 1 2 3 1 2 3

]

) 10 1

(

d d d d u u u s s s

T + + - -

´

=

X

16

따라서 주어진 문제의 최적해는

d

₁

= d

₂

= 1 , u

₁

= u

₂

= u

₃

= 0 , s

₁

= 0 , s

₂

= s

₃

= 2

이다.

한편, 이들은 제약 조건

X

_i

X

₃₊_i

= 0 ; i = 5 to 7 , X

_i

³ 0 ; i = 1 to 1 0

을 모두 만족한다.

여기서 u₁과 s₁의 값이 동시에 0인 이유는 무엇인가?

[

1 2 1 2 1 2 3 1 2 3

]

) 10 1

(

d d d d u u u s s s

T + + - -

´

=

X

Æ Pivot 과정 중 선택 가능한 열 또는 행 또는 “b_i/a_i”의 계수가 중복인 경우, 어떤 것을 선택하느냐에 따라 다른 초기 기저 가능해가 얻어질 수 있음

Æ 비선형 방정식(u_i*s_i=0)을 만족하는 해가 나올 때까지 모든 경우를 확인해 봐야 함

1

1,

X = X =

₂

1, X =

₈

0, X =

₉

2, X

₁₀

= 2

기저 해를 구해보면

비기저 해는 다음과 같다.

3 4 5 6 7

0 X = X = X = X = X =

(17)

Simplex

Simplex 방법을 방법을 이용 이용,,탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(11/ (11/첫번째 첫번째 QP QP문제 문제))

d

₂

6 Æ 도식화

0 )

(

0 )

(

0 0 . 6 1

1 6 ) 1 (

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

주어진 문제의 최적해는 이다.

여기서 u₁과 s₁의 값이 동시에 0인 이유는 무엇인가?

2 ,

0 ,

1

₁ ₂ ₃ ₁ ₂ ₃

2

1

= d = u = u = u = s = s = s =

d

Minimize Subject to

) (

5 . 0 )

( d

₁

d

₂

d

₁²

d

₂²

f = - - + +

1 1

2 1

3 2 3 2

1 3 1

1

£ -

£ +

d d

2차 계획 문제

17

6 d

₁

1 2 3 4 5

-1 -2

-1 -2 1 2 3 4 5

8.0 5.0 2.0 1.0 0.1 -0.8

A B

C

D

d

₁

=-1

d

₂

=-1 d

₁

+d

₂

=2

본 예제의 첫번째 QP문제를 도식화 하면

f

오른쪽과 같다.

1

0 s =

제약조건 중 g₁(x)를 근사화한d₁+d₂=2 위에 최적점이 존재한다.

1 1

2 1

3 2 3 2

1 3 1

1

£ -

£ +

d d

2 3

0 최적점

u = u =

부등호 제약 조건이 작용하지 않는 가능 영역 안에 최적해가 존재할 것이다.

제약조건 g₁(x) 상에 최적점이 존재하나,

최적점의 위치가 2차로 근사화된 목적 함수 최적점의 위치와 동일하다.

따라서g₁(x)이 없는 경우에도 QP문제의 최적점은 변하지 않는다.

(g₁(x)는 본 문제의 최적점에 영향을 주지 않음)

1

0 u =

(18)

QP 문제의 풀이를 통한 탐색 방향(d⁽¹⁾)의 결정

2차 계획 문제

Simplex

Simplex 방법을 방법을 이용 이용, , 탐색 탐색 방향을 방향을 결정하기 결정하기 위한 위한 2

2차 차 계획 계획 문제의 문제의 풀이 풀이(1/ (1/두번째 두번째 QP QP문제 문제))

Minimize Subject to

) (

5 . 0 ) 732 . 1 732 . 1

( d₁ d₂ d₁² d₂²

f = - - + +

732 . 1

10 866 . 5 577

. 0 577 . 0

2 1

5 2

1

£ -

´

£

+ ^-

d d

제약 최적화 문제 (근사화 하기 전)

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 = + - j

732 . 1

, 732 . 1

2 2

1 1

-

= -

= x d

x d

여기서,

) 1 , 0 ( ,

732 . 1 ) 732 . 1 , 732 . 1 (

) 0 , 1 ( ,

732 . 1 ) 732 . 1 , 732 . 1 (

) 577 . 0 , 577 . 0 ( ,

10 866 . 5 ) 732 . 1 , 732 . 1 (

) 732 . 1 , 732 . 1 ( , 3 ) 732 . 1 , 732 . 1 (

3 3

2 2

1 5 1

-

= Ñ -

=

-

= Ñ -

=

= Ñ

´ -

=

- -

= Ñ -

=

-

g g

f f

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

)

18

732 . 1 (

) 732

. 1 (

] 10

866 . 5 ) (

577 . 0 [

) (

5 . 0

) 732 . 1 732

. 1 (

2 3 2

3

2 2 1

2

2 1 5 2

1 1

2 2 2 1

2 1

s d

u

s d

u

s d

d u

d d

L

+ -

- +

+ -

- +

+

´ -

+ +

- -

=

-

Lagrange 함수

k

l

0 s

u

d =

Ñ L ( , , )

732 . 1

, 732 . 1

2 2

1 1

-

= -

= x d

x d

( )

1

2

1

2

3

1 1 2

2 1 3

6 2

1 2 1

2

1 2

2

2 3

1.732 0.577 0 1.732 0.577 0

0.577 5.866 10 0 1.732 0

1.732 0 0, 0, 1, 2, 3

i

L d

L u

L u L s i i

d u u

d d s

d s

u s u i

¶

¶ -

¶

= - + + - =

= + - ´ + =

= - - + =

= = ³ =

) 1 , 0 ( ,

732 . 1 ) 732 . 1 , 732 . 1 (

) 0 , 1 ( ,

732 . 1 ) 732 . 1 , 732 . 1 (

) 577 . 0 , 577 . 0 ( ,

10 866 . 5 ) 732 . 1 , 732 . 1 (

) 732 . 1 , 732 . 1 ( , 3 ) 732 . 1 , 732 . 1 (

3 3

2 2

1 5 1

-

= Ñ -

=

-

= Ñ -

=

= Ñ

´ -

=

- -

= Ñ -

=

-

g g

f f

1. 양변에 s

_i

를 곱한 후 s

_i²

을 s

_i

’으로 치환

2. 편의상 s

_i

’을 s

_i

로 표기

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

[2008][12-1]