@ 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.6 Constrained Nonlinear Optimization method

6.3 Sequential Quadratic Programming;

SQP

- Ch.6 Constrained Nonlinear Optimization Method

(3)

@ SDAL

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

 순차적 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차 형식

3/89

(4)

@ SDAL

SQP 알고리즘 요약

x ₁ x ₂

최적해

x ₁ x ₂

현재 설계점

d

⁽⁰⁾

x ₁ x ₂

d

⁽⁰⁾

- Penalty Function:

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

(제약 최적화 문제를 Unconstrained optimization problem로 변경)

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

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

종료 조건

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

탐색을 종료한다.

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

과정 2 현재 설계점에서

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

과정 1

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

과정 3

개선된 설계점

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

x ₁ x ₂

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

목적 함수

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

- Ch.6 Constrained Nonlinear Optimization Method ^4/89

(5)

@ SDAL

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

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

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

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

( ) ( ) ^T ( ) 0.5 ^T

f x   x  f x   f x  x   x H x 

Minimize:

( 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

탐색 방향(d

⁽⁰⁾

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

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

( ) ( ) ^T ( ) 0.5 ^T

f x   x  f x   f x  x   x H x 

Minimize: Taylor 급수의 2차항까지

고려한 목적 함수

1 2

(0) (0)

, f

^T



_^_x^f _^_x^f

 ,

 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

원의 방정식:

(6)

@ 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

( ' )

(

6/89

(7)

@ 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의 원소

 각 항을 다시 표현하면

*

1 1 1

* * * *

1 1 2 2 *

2 2

1 2

2

( ) ( ) ( ) ( )

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 

7/89

(8)

@ SDAL

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(1)

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 ^*  ( 3 , 3 ), f ( x ^* )   3

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

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) ^{이라 가정}

(9)

@ SDAL

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(2)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

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

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

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

( ) ( ) ^T ( ) 0.5 ^T

f x   x  f x   f x  x   x H x 

Minimize:

 

^{( 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차 계획 문제로 근사화 한다.

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

( ) ( ) ^T ( ) 0.5 ^T

f x   x  f x   f x  x   x H x 

Minimize: Taylor 급수의 2차항까지

고려한 목적 함수

1 2

(0) (0)

, f

^T



_^_x^f _^_x^f

 ,

 x  d     H  I

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

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

(10)

@ SDAL

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(3)

2 2

1 1 2

2 1

3 2

1 1

( ) 1.0 0

6 6

( ) 0

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

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

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

Subject to: g

j

⁽ x

⁽⁰⁾

  x

⁽⁰⁾

⁾  g

j

⁽ x

⁽⁰⁾

⁾   g

j^T

⁽ x

⁽⁰⁾

⁾  x

⁽⁰⁾

 ^0; j  ¹ to m 제약조건

(0) (0) (0)

( ) ( ); 1

T

j j

g g j to m

 x  x   x 

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

탐색 방향(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

( )

 x  d      x  x   x  d 를 이항하면

(

(0)

) g x

j

Subject to:

   

 

(0) 2 2

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

1 2 1 2

1 3 3 (0)

2 (0)

(0) (0) 1 (0)

1 1

2 (0)

(0) (0) 1 (0)

2 2

3 (0)

2

1 1

( ) 1.0

6 6

( ) 0

g x x d x x

d

g x d x

d

g x d x

d

   

 

              

 

        

 

 

        

  d

d

(0) 1 (0) 1 (0)

1 2

1 3 3

(0) (0)

1 2

(0) (0)

2 3

( ) 2

3 ( ) 1

( ) 1

g d d

g d

  

  

   d

d d

선형화 된 제약 조건

(0)

 (1,1)

x 대입

10/89

(11)

@ SDAL

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

⁽⁰⁾

)의 결정

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(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

) 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 함수 Kuhn-Tucker 필요 조건:







(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

최적해를 구하면

) 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

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

0 s

u

d 

 L ( , , )

(0) (0)

1 1 1

,

2 2 2

x   d x x  d  x

탐색 방향이 결정 되었음

 

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

1 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

 

     

    

    

   

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차 계획 문제

(0) (0)

1

1,

2

1 x  x 

^{을 대입 하면,}

1 1 2 2

1   d x , 1  d  x

11/89

(12)

@ SDAL

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(5)

(1) (0)

0  (0)

 

x x d

현재의 설계점

2차 계획 문제로부터 구한 탐색 방향 개선된

설계점

Find α _k : Minimize ^{f x}  

⁽¹⁾

^ ^f  ^x

⁽⁰⁾

^ ^ ⁰ ^d

⁽⁰⁾

 ^ ^f ^{ } ^ ⁰

주어진 목적 함수 Given

Find

1 2 3 4

x₁ x₂

A B

C g₂= 0

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

f = -25 f = -20

f = -10 f = -3

f = -1

(iv)단계 4:탐색 방향(d

⁽⁰⁾

)이 결정되었으므로, 다음 방법을 통하여 최적의 이동거리를 구한다.

탐색 방향으로 목적 함수를 최소화하는 최적의 이동 거리

탐색 방향(d

⁽⁰⁾

)이 정해졌고, 이 방향으로 목적함수 값을 최소로 하는 이동거리를 구하면 개선된 설계점이 제약조건을 위배한다.

(0)

1 2

( , d d ) (1,1)

 

d ^{탐색 방향이} _{결정 되었음}

d

(0)

0 0

 d ( )

목적 함수의 최소점

따라서 제약조건 위배 값을 Penalty로 부가하여, 목적 함수 값에 더한다. (Penalty Function)

(0)

1 2 3

(0)

1 2

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

u u u d d

 

u d

제약조건을 위배하면 목적 함수 값이 커지므로,

제약조건을 위배하지 않는 범위에서 목적 함수 값이 최소가 되는 점을 찾을 수 있다.

12/89

(13)

@ SDAL

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(6)

(v) 단계 5: 벌칙 매개 변수 R _k 의 계산 (본 예제에서는 초기값으로 R

₀

=10을 가정한다.)



  



 ^m

i

k i p

i

k i

k v u

r

1 ) ( 1

)

(

0 , 0 , 0 ( ) , ,

(

₁ ₂ ₃

) 0

(

 u u u 

u ^이고 ^로부터 



 ^m

i

u i

r

1 ) 0 (

0

0 따라서 R

0

 max{ R r

0

, }

0

 max{10, 0} 10 

새로운 목적함수의 정의 (Pshenichny의 강하 함수)

( ) ( ) ( )

( ^k ) f ( ^k ) R V _k ( ^k )

 x  x   x

V(x

^(k)

)는 최대 제약 조건 위배 값이다.

V(x

^(k)

)는 0보다 크거나 같은 값으로 제약 조건을 모두 만족하면 이 값은 0이다.

} , , ,

; , , ,

; 0 max{

)

(

⁽

^k

⁾

h

₁

h

₂

h _p g

₁

g

₂

g _m

V x     모든 제약 조건을 만족하면 이 값은 0

( ) ( )

0

1 1

max , ( )

p m

k k

k k i i

i i

R R r v u

 

 

    

   

모든 Lagrange multiplier의 합

R

_k

은 양의 상수로서 벌칙 매개 변수이다.(Penalty Parameter, 초기에 사용자에 의해 명시됨).

( ) ( ) ( )

2 2 ( )

1 2 1 2

( ) ( ) ( )

3 10 ( ),

k k k

k

f R V

x x x x V

   

    

x x x

x ^V ⁽ ^x

^{( )}

^k ⁾ ^ ^max{0, ^{g g g}

₁

^,

₂

^,

₃

^}

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

2 1 2 2 2

1

3 )

( x x x x

f x   

(k는 QP로 근사화하는 과정의 반복 회수이다.)

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

이용하여 제약 최적화 문제를

Unconstrained optimization problem로 변환.

, (k=0)

(14)

@ SDAL

CSD 알고리즘의 k번째 반복 과정 내 에서 1차원 탐색법의 반복 횟수 j표기

- CSD 알고리즘의 k번째 반복 과정 내에서

1차원 탐색법(예: 황금 분할법)을 통하여  _k 를 결정한다.

A B

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(7)

 ^{( , )}

^{k j}

  ^f ^{( , )}

^{k j}

 ^{R V}

^k

 ^{( , )}

^{k j}



 x  x   x

( ) ( ) ( )

2 2 ( )

1 2 1 2

( ) ( ) ( )

3 10 ( )

k k k

k

f R V

x x x x V

   

    

x x x

x

( )

1 2 3

(

^k

) max{0, , , }

V x  g g g

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

2 1 2 2 2

1

3 )

( x x x x

f x   

1 2 3 4

x ₁ x ₂

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

 ( x

f = -10 f = -3

d 0

0.0 

 A

B

( , ) ( ) ( )

( , )

k j k k

 k j

 

x x d

x

_(0,0)

=(1, 1) -1

x

_(0,0)

=(1, 1)

- 1차원 탐색법(예: 황금 분할법)역시 여러 번 반복하여 적용 한다.

- 따라서 CSD 알고리즘의 반복 횟수를 k로,

1차원 탐색법(황금 분할법) 내의 반복 횟수를 j로 정하고 다음과 같이 표기 한다.

1차원 탐색 내에서는 변경되지 않음

(vi) 단계 6: 1차원 탐색법(예: 황금 분할법)을 이용하여 탐색 방향(d

⁽⁰⁾

)으로 강하 함수를 최소화 하는

개선된 설계점 계산

1차원 탐색이 끝난 후

마지막 가 로

변경 된다.

( , )k j

x x

⁽^k¹⁾

,(k=0)

(15)

@ SDAL

A B

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(7)

 ^{(0, )}

^j

  ^f ^{(0, )}

^j

 ^{R V} ⁰  ^{(0, )}

^j

 ^{1 10 0} ¹

 x  x   x      

0  (1,1), d

탐색방향 :

( , ) ( , ) ( , )

2 2 ( , )

1 2 1 2

( ) ( ) ( )

3 10 ( )

k j k j k j

k

k j

f R V

x x x x V

   

    

x x x

x

( , )

1 2 3

(

^{k j}

) max{0, , , }

V x  g g g

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

2 1 2 2 2

1

3 )

( x x x x

f x   

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

1 2 3

2 3

, ( ) max{0, ( ), ( ), ( )}

max{0, , 1, 1} 0

j j j j

where V  g g g

    

x x x x

(0, ) (0) (0)

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

j

d



      

x x

1 2 3 4

x ₁ x ₂

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

 ( x

f = -10 f = -3

d 0

0.0 

(0, )

_j

0.0 

  일때

A

B

( , ) ( ) ( )

( , )

k j k k

 k j

 

x x d

( , )

k j

x CSD 알고리즘의 k번째 반복 과정

황금 분할 내의 j번째 반복 과정

x

_(0,0)

=(1, 1) -1

x

_(0,0)

=(1, 1)

(vi) 단계 6: 1차원 탐색법(예: 황금 분할법)을 이용하여 탐색 방향(d

⁽⁰⁾

)으로 강하 함수를 최소화 하는

개선된 설계점 계산

0, 0 k  j 

,(k=0)

(16)

@ SDAL

A B

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(8)

 ^{(0, )}

^j

  ^f ^{(0, )}

^j

 ^{R V} ⁰  ^{(0, )}

^j

 ^{1.21 10 0} ^1.21

 x  x   x      

0  (1,1) 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

2 1 2 2 2

1

3 )

( x x x x

f x   

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

1 2 3

, ( ) max{0, ( ), ( ), ( )}

max{0, 0.57, 1.1, 1.1} 0

j j j j

where V  g g g

    

x x x x

(0, ) (0) (0)

(0, ) (1,1) 0.1 (1,1) (1.1,1.1)

j

d



      

x x

1 2 3 4

x ₁ x ₂

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

 ( x

f = -10 f = -3

0.0 

(0, )

_j

0.1 

  **로 가정하면*,**

A

B

( , ) ( ) ( )

( , )

k j k k

 k j

 

x x d

( , )

k j

x CSD 전체 과정의 k번째 반복 과정

황금 분할 내의 j번째 반복 과정

x

_(0,0)

=(1, 1) -1

x_(0,0)=(1, 1) x_(0,1)=(1.1, 1.1)

0.1 x

_(0,1)

=(1.1, 1.1) -1.21

* 의 초기 값 0.1은 사용자가 정의한 값이며, 다른 값(예: 0.5)으로 가정할 수 있다.



^{( , )}^{k j}

( , ) ( , ) ( , )

2 2 ( , )

1 2 1 2

( ) ( ) ( )

3 10 ( )

k j k j k j

k

k j

f R V

x x x x V

   

    

x x x

x

( , )

1 2 3

(

^{k j}

) max{0, , , }

V x  g g g

(vi) 단계 6: 1차원 탐색법(예: 황금 분할법)을 이용하여 탐색 방향(d

⁽⁰⁾

)으로 강하 함수를 최소화 하는

개선된 설계점 계산

0, 1 k  j 

,(k=0)

(17)

@ SDAL

A B

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(9)

 ^{(0, )}

^j

  ^f ^{(0, )}

^j

 ^{R V} ⁰  ^{(0, )}

^j

 ^{1.592 10 0} ^1.592

 x  x   x      

0  (1,1) 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

2 1 2 2 2

1

3 )

( x x x x

f x   

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

1 2 3

, ( ) max{0, ( ), ( ), ( )}

max{0, 0.469, 1.262, 1.262} 0

where V  g g g

    

x x x x

(0, ) (0) (0)

(0, ) (1,1) 0.262 (1,1) (1.262,1.262)

j

d

       

x x

1 2 3 4

x ₁ x ₂

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

 ( x

f = -10 f = -3

0.0 

(0, )

_j

0.1 1.618(0.1) 0.2618 

    ^{일 때}

A

B

( , ) ( ) ( )

( , )

k j k k

 k j

 

x x d

( , )

k j

x CSD 전체 과정의 k번째 반복 과정

황금 분할 내의 j번째 반복 과정

x

_(0,0)

=(1, 1) -1

x_(0,0)=(1, 1) x_(0,1)=(1.1, 1.1)

0.1 x

_(0,1)

=(1.1, 1.1)

x_(0,2)=(1.262, 1.262)

0.2618

x

_(0,2)

=(1.262, 1.262) -1.592

-1.21

( , ) ( , ) ( , )

2 2 ( , )

1 2 1 2

( ) ( ) ( )

3 10 ( )

k j k j k j

k

k j

f R V

x x x x V

   

    

x x x

x

( , )

1 2 3

(

^{k j}

) max{0, , , }

V x  g g g

(vi) 단계 6: 1차원 탐색법(예: 황금 분할법)을 이용하여 탐색 방향(d

⁽⁰⁾

)으로 강하 함수를 최소화 하는

개선된 설계점 계산

0, 2 k  j 

,(k=0)

(18)

@ SDAL

A B

SQP(Sequential Quadratic Programming)방법을 이용한 풀이 예(10)

 ^{(0, )}

^j

  ^f ^{(0, )}

^j

 ^{R V} ⁰  ^{(0, )}

^j

 ^{2.321 10 0} ^2.321

 x  x   x      

0  (1,1) 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

2 1 2 2 2

1

3 )

( x x x x

f x   

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

1 2 3

, ( ) max{0, ( ), ( ), ( )}

max{0, 0.226, 1.524, 1.524} 0

j j j j

where V  g g g

    

x x x x

(0, ) (0) (0)

(0, ) (1,1) 0.524 (1,1) (1.524,1.524)

j

d

       

x x

1 2 3 4

x ₁ x ₂

g

₂

= 0

g

₃

= 0 g

₁

= x

₁²

+ x

₂²

- 6.0 = 0

) 3 , 3

*

 ( x

f = -10 f = -3

0.0 



2 (0, )

_j

0.1 1.618(0.1) 1.618 (0.1) 0.5236

     일 때

A

B

( , ) ( ) ( )

( , )

k j k k

 k j

 

x x d

( , )

k j

x CSD 전체 과정의 k번째 반복 과정

황금 분할 내의 j번째 반복 과정

x

_(0,0)

=(1, 1) -1

x_(0,0)=(1, 1) x_(0,1)=(1.1, 1.1)

0.1 x

_(0,1)

=(1.1, 1.1)

x_(0,2)=(1.262, 1.262)

0.2618

x

_(0,2)

=(1.262, 1.262) -1.592

-1.21

x_(0,3)=(1.524, 1.524)

0.5236

x

_(0,3)

=(1.524, 1.524) -2.321

( , ) ( , ) ( , )

2 2 ( , )

1 2 1 2

( ) ( ) ( )

3 10 ( )

k j k j k j

k

k j

f R V

x x x x V

   

    

x x x

x

( , )

1 2 3

(

^{k j}

) max{0, , , }

V x  g g g

(vi) 단계 6: 1차원 탐색법(예: 황금 분할법)을 이용하여 탐색 방향(d

@ 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

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

@ SDAL

Naval Architecture & Ocean Enginee ring

@ SDAL

Ch.6 Constrained Nonlinear Optimization method

6.3 Sequential Quadratic Programming;

SQP

@ SDAL

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

 순차적 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)를 사용한다.

@ SDAL

SQP 알고리즘 요약

x 1 x 2

x 1 x 2

d

x 1 x 2

d

- Penalty Function:

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

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

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

과정 2 현재 설계점에서

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

과정 1

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

과정 3

x 1 x 2

@ SDAL

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

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

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

( ) ( ) T ( ) 0.5 T

f x   x  f x   f x  x   x H x 

Minimize:

( ) ( ) f f d 0.5( )

f f d d

x x d

 

   

        

     

x d x

Minimize:

( ) ( )

( ) f f 0.5( )

f d d d d

x x

 

   

 

x x

d

탐색 방향(d

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

( ) ( ) T ( ) 0.5 T

f x   x  f x   f x  x   x H x 

Minimize: Taylor 급수의 2차항까지

고려한 목적 함수

, f



 ,

 x  d     H  I

상수 c

으로 치환 상수c

로 만든 후, 이를 해결하여 탐색 방향(search direction) d ^(k) 를 구함

 ② 제약 조건의 위배량을 원래 목적 함수에 더한 수정된 목적 함수(강 하 함수; Descent Function)를 최소화하는 최적의 이동 거리(step size) α _k 를 1차원 탐색 방법(예: 황금분할법)을 이용하여 찾아 더 나은 설계 점을 구함

x ₁ x ₂

x ₁ x ₂

x ₁ x ₂

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

x ₁ x ₂

( ) ( ) ^T ( ) 0.5 ^T

( ) ( ) ^T ( ) 0.5 ^T

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

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

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

x  ^*  ^{라고 놓으면}

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

( x f x ^* f x

 ^* '' ( ^* ) ²