[Optimal Design] 12. Numerical method for constrained optimum design

On this page

• Introduction to Optimum Design
  • 12. Numerical Method for Constrained Optimum Design

Introduction to Optimum Design

12. Numerical Method for Constrained Optimum Design

---

- 이 장의 주요내용:

• 평탄 제약조건 비선형 최적화 문제를 풀기 위한 수치 알고리즘의 기본적인 단계 설명

• 평탄 제약조건 비선형 최적화 문제에서 강하 방향과 강하 단계의 개념 설명

• 제약조건 비선형 최적화 문제의 선형화와 선형계획법 부문제 정의

• 제약조건 비선형 최적화 문제를 풀기 위한 순차 선형계획법(SLP) 사용

• 제약조건 비선형 최적화 문제에 대하여 2차식 계획법 부문제의 정의와 탐색방향을 위한 풀이

• 비선형 제약조건 최적화 문제를 풀기 위한 최적화 알고리즘 사용

---

Optimal design과 Constrained Optimization 개념

1. Unconstrained Optimization

   • 제약 조건 없이 목표 함수를 최적화 하는 문제를 다룸

   • 대표적인 방법: Steepest Desent Method, Conjugate Gradient Method, Newton Method, DFP(Davidon-Fletcher-Powell), BFGS(Broyden-Fletcher-Goldfarb-Shanno) 등

   • 목표는 반복적으로 설계 포인트(Design point)를 업데이트하여 최적의 해에 도달하는 것.

2. Constrained Optimization

   • 제약 조건이 추가된 상황에서 최적화 문제를 해결

   • 제약 조건의 만족 여부를 각 반복 단계(Iteration)마다 확인 필요

   • 문제 해결 방법

     • 목표 함수와 제약 조건 함수를 선형화(Linearization)하여 단순화

     • 제약 조건 위반 시 설계 포인트를 수정하여 제약 조건을 만족하도록 조정

   • 수치적(Numerical) 접근 방식이 사용되며, 높은 차원(N-Dimensional Space)에서는 시각적 방법이 불가능하므로 반복적 계산에 의존

3. Linearization

   • Taylor Series Expansion을 통해 목표 함수와 제약 조건을 1차 도함수 기반으로 선형화

   • 2차 이상의 고차항(Higher-Order Terms)은 무시, 반복적으로 업데이트를 통해 정확도를 높임

   • 목표는 선형화된 방정식을 이용하여 현재 설계 포인트에서 다음 포인트로 이동

4. Iteration Process

   • 초기 점(Start Point)에서 시작하여 선형화된 문제를 반복적으로 해결

   • 제약 조건 영역(Feasible Region) 내에서 최적 해를 찾는 과정

   • 오차(Tolerance) 허용 범위 내에 도달하면 수렴(Convergence)으로 간주

5. 예제

   • 목적 함수: \(f(x_1, x_2) = x_1^2 + x_2^2 - 3x_1x_2\)

   • 제약 조건

     • \(g_1(x)=\frac{1}{6}x_1^2+\frac{1}{6}x_2^2-1\le 0\)

     • \(g_2(x)=-x_1\le 0\)

     • \(g_3(x)=-x_2\le 0\)

   • 초기 점: \((x_1, x_2) = (1, 1)\)

   • 선형화 후 각 반복 단계에서 제약 조건을 만족하는 새로운 설계 포인트 계산

6. 결론

   • Constraint Optimization은 실제 공학 문제에서 필수적인 과정이며, 일반적으로 수학적 접근과 수치적 방법의 조합이 필요

   • 반복적인 선형화와 업데이트를 통해 최적 해에 가까워짐

교재 TF 문제

Section 12.1 Basic Concepts Related to Numercal Methods

1. The basic numerical iterative philosophy for solving constrained and unconstrained problems is the same. (F) - unconstrained 최적화에서는 단순히 목적 함수 값을 줄이는 방향을 찾으면 되지만, 제약 조건이 있는(constrained) 문제에서는 제약 조건을 만족시키면서 최적화를 진행해야 한다. 따라서 기본 철학이 다르다.

2. Step size determination is a 1D problem for unconstrained problems. (T) - 탐색 방향이 주어진 경우, 스텝 크기를 결정하는 것은 1차원 문제로 축소된다. 이는 제약 조건이 없는 경우에 적용된다.

3. Step size determination is a multidimensional problem for constrained problems. (T) - 제약 조건이 있는 문제에서는 스텝 크기를 결정할 때 탐색 방향뿐만 아니라 제약 조건을 고려해야 한다. 이는 다차원적인 문제로 이어질 수 있다.

7. An equality constraint is always active at the optimum. (T) - 최적화 문제에서 equality constraint는 항상 active 상태이다. 이는 최적 조건에서 등식 제약이 만족되어야 하기 때문이다.

8. In constrained optimization problems, search direction is found using the cost gradient only. (F) - 제약 조건이 있는 문제에서는 목적 함수의 gradient 뿐만 아니라 제약 조건의 gradient도 사용된다. 예를 들어, Lagrange 승수를 사용하는 방법에서는 제약 조건의 정보가 필수적이다.

9. In constrained optimization problems, search direction is found using the constraint gradients only. (F) - 탐색 방향은 목적 함수의 gradient와 제약 조건의 gradient를 조합하여 계산된다. 한개만 고려하는게 아님

10. In constrained problems, the descent function is used to calculate the search direction. (T) - 하강 함수는 목적 함수와 제약 조건을 결합한 형태로, 탐색 방향 계산에 사용된다.

11. In constrained problems, the descent function is used to calculate a feasible point. (F) - 하강 함수는 탐색 방향을 결정하는 데 사용되며, 직접적으로 가능(feasible)한 점을 계산하지는 않는다.

12. Cost function can be used as a descent function in unconstrained problems. (T) - 제약 조건이 없는 경우, 목적 함수 자체를 하강 함수로 사용하여 탐색 방향을 결정할 수 있다.

13. A 1D search on a descent function is needed for convergence of algorithms. (F) - 1D 탐색은 스텝 크기 결정에서 중요하지만, 모든 알고리즘의 수렴에 필수적인 것은 아니다. 예를 들어, 고정 스텝 크기를 사용하는 알고리즘도 존재한다.

14. A robust algorithm guarantees convergence. (F) - robust algorithm은 다양한 초기 조건에서 작동할 가능성이 높지만, 모든 상황에서 수렴을 보장하지는 않는다. 문제의 성질(예: 비볼록성, 불완전한 제약 처리 등)에 따라 실패할 수 있다.

15. A feasible set must be closed and bounded to guarantee convergence of algorithms. (T) - 수렴성을 보장하려면 가능 집합(feasible set)이 닫히고 유계(bounded)여야 한다. 그렇지 않으면 최적해가 무한대 또는 집합 밖으로 벗어날 수 있다.

Section 12.2 Linearization of the Constrained Problem

1. Linearization of cost and constraint functions is a basic step for solving nonlinear optimization problems. (T) - 비선형 최적화 문제는 선형화(linearization)를 통해 단순화된 하위 문제를 반복적으로 해결하는 방식으로 접근. 목적 함수와 제약 조건을 선형화하면 각 반복에서 선형 문제로 변환할 수 있다.

2. General constrained problems cannot be solved by solving a sequence of linear programming subproblems. (F) - 일반적인 constrained problem는 연속적인 선형 프로그래밍(subproblems)을 해결하여 근사적으로 풀 수 있다. 이 방법은 Sequential Linear Programming (SLP) 알고리즘의 핵심 원리이다.

3. In general, the linearized subproblem without move limits may be unbounded. (T) - 선형화된 하위 문제에서 이동 제한(move limit)이 없으면, 선형 문제의 특성상 해가 무한대로 발산하거나 제한되지 않을 수 있다. 따라서 이동 제한이 필요하다.

4. The SLP method for general constrained problems is guaranteed to converge. (F) - SLP 방법은 항상 수렴을 보장하지 않는다. 이동제한, 초기 조건, 문제의 비선형성 등에 따라 발산하거나 적절한 해를 찾지 못할 수 있다.

5. Move limits are essential in the SLP procedure. (T) - move limit은 선형화의 유효성을 보장하고, 하위 문제에서 무한 발산(unbounded)을 방지하기 위해 필수적이다. 이를 통해 적절한 지역 근사를 유지할 수 있다.

6. Equality constraints can be treated in the SLP algorithm. (T) - 등식 제약 조건은 SLP 알고리즘에서 Lagrange 승수 또는 기타 선형화 기법을 사용하여 다룰 수 있다. 이는 제약 조건을 만족시키면서 최적화를 수행하는 데 사용된다.

Section 12.7 The CSD Method - 생략

---

기말대비

Quiz 2

1. Unconstrained optimization problems are classfied as 1D (or line search) problems and multidimensional problems. (T)*

2. 1D minimization problem can be solved by interval halving method, golden section method, or polynomial interpolation method. (T) - 1D line search?

3. After initial bracketing, the interval halving method requires three additional function evaluations to reduce the interval of uncertainty (F)* - 3이 아닌 2

4. After initial bracketing, the golden section method require one additional function evaluations to reduce the interval of uncertainty (T)

5. “Robust quadratic fit-sectioning algorithm” by Brent uses a golden section method whenever possible. Otherwise, use quadratic polynomial approximation. (F) - Poly 쓸 수 있으면 무조건 Poly 먼저 쓴 뒤 골든섹션

6. Steepest descent directions are orthogonal to each other. Moreover, the steepest descent direction is orthogonal to the iso-cost surface. (T)

7. Conjugate directions are orthogonal to each other. The conjugate direction at the \(k^{th}\) point is orthogonal to the gradient of the cost function at the \((k-1)^{th}\) point. (F)* - 각 방향끼린 직교하지 않음, 목적함수의 k+1과는 직교, k-1과는 직교 x

8. The conjugate gradient method can converge to the optimal point with n iterations or less for a quadratic function of n design variables. (T)

9. The condition number of Hessian matrix (symmetric and positive definite) is defined as the ratio of the smallest to the largest eigenvalue. (F)* \(\frac{\lambda_{max}}{\lambda_{min}}\) 이다.

10. The minimum value of the condition number is zero. (F) - 최소는 1이다.

• 그림 주어지고 steepest descent direction \(\tilde{d}^0\), the fastest function increasing direction \(\tilde{g}^0\) at the point \(x^0\) 그리는 문제 나옴.

• 알고리즘 주어지고 빈칸 채워넣는 문제 나옴.