Constrained Optimum Design, Part I

Linearization, Sequential Programming, and Constrained Descent

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 12.

이 장에서는 smooth constrained nonlinear problem을 직접 푸는 반복 알고리즘의 기본 구조를 정리한다. Cost와 constraint functions를 현재 design에서 linearize하여 LP 또는 QP subproblem을 구성하고, 그 solution으로 design change 또는 search direction을 결정한다. 이어서 constraint violation을 포함하는 descent function으로 step size를 계산하고, 이를 constrained steepest-descent method로 통합한다.


General Constrained Problem

다음 constrained design problem을 생각하자.

\[\begin{aligned} \underset{x\in\mathbb{R}^n}{\operatorname{minimize}}\quad & f(x) \\ \text{subject to}\quad & h_j(x)=0, && j=1,\ldots,p, \\ & g_i(x)\leq0, && i=1,\ldots,m. \end{aligned}\]

Explicit bounds $x_{iL}\leq x_i\leq x_{iU}$도 inequality constraints에 포함할 수 있다. Iterative update는

\[x^{(k+1)} = x^{(k)}+\Delta x^{(k)},\] \[\Delta x^{(k)} = \alpha_kd^{(k)}\]

로 쓴다. Constrained problem에서는 direction과 step size를 결정할 때 cost뿐 아니라 equality와 inequality constraints를 함께 고려해야 한다.

일반적인 iteration은 다음 네 단계로 구성된다.

  1. 현재 design에서 cost와 constraints를 linearize한다.
  2. Linearized functions로 direction-finding subproblem을 정의한다.
  3. Subproblem을 풀어 $d^{(k)}$를 계산한다.
  4. Descent function을 감소시키는 step size $\alpha_k$를 계산한다.

Starting design은 feasible 또는 infeasible일 수 있다. Feasible point에서는 cost reduction과 feasibility 유지가 동시에 필요하고, infeasible point에서는 constraint violation을 줄이면서 optimum으로 접근해야 한다.


Constraint Status

Inequality constraint $g_i(x)\leq0$의 current point $x^{(k)}$에서의 status는 다음과 같다.

  • Active: $g_i(x^{(k)})=0$.
  • Inactive: $g_i(x^{(k)})<0$.
  • Violated: $g_i(x^{(k)})>0$.
  • $\epsilon$-active: $g_i(x^{(k)})<0$이지만 $g_i(x^{(k)})+\epsilon\geq0$.

$\epsilon$-active constraint는 feasible side에 있지만 boundary에서 $\epsilon$ 이내에 있는 constraint이다. Equality constraint $h_j(x)=0$은

\[h_j(x^{(k)})=0\]

이면 active이고, 그렇지 않으면 violated이다. 따라서 equality constraint는 모든 point에서 active 또는 violated 중 하나이다.

Active-set information은 direction subproblem에 포함할 inequality constraints를 선택하는 데 사용된다. Current point에서 충분히 떨어진 inactive constraints는 작은 local step에 영향을 주지 않지만, active·$\epsilon$-active·violated constraints는 direction 계산에 직접 포함해야 한다.


Descent Function and Convergence

Unconstrained problem에서는 $f(x)$ 자체를 descent function으로 사용할 수 있다. Constrained problem에서는 cost가 감소하더라도 constraint violation이 증가할 수 있으므로, cost와 feasibility를 함께 측정하는 function이 필요하다. 이러한 function을 descent function 또는 merit function이라 한다.

Search direction과 step size는

\[\Phi\!\left(x^{(k)}+\alpha_kd^{(k)}\right) < \Phi\!\left(x^{(k)}\right)\]

을 만들도록 선택한다. 또한 feasible optimum $x^{\star}$에서는

\[\Phi(x^{\star})=f(x^{\star})\]

가 되어야 한다.

Chapter 12에서 robust convergence를 위한 기본 requirements는 다음과 같다.

  • 매 iteration에서 감소하는 descent function이 존재한다.
  • Direction $d(x)$가 design variables의 continuous function이다.
  • Feasible set이 closed and bounded이다.

이 조건들은 algorithm의 진행을 측정하고 oscillation을 억제하며, generated sequence가 bounded region을 벗어나지 않도록 한다.


First-Order Linearization

Current design $x^{(k)}$에서 design change를 $\Delta x^{(k)}$라 하자. First-order Taylor expansions은

\[f\!\left(x^{(k)}+\Delta x^{(k)}\right) \approx f\!\left(x^{(k)}\right) + \nabla f\!\left(x^{(k)}\right)^T\Delta x^{(k)},\] \[h_j\!\left(x^{(k)}+\Delta x^{(k)}\right) \approx h_j\!\left(x^{(k)}\right) + \nabla h_j\!\left(x^{(k)}\right)^T\Delta x^{(k)},\] \[g_i\!\left(x^{(k)}+\Delta x^{(k)}\right) \approx g_i\!\left(x^{(k)}\right) + \nabla g_i\!\left(x^{(k)}\right)^T\Delta x^{(k)}\]

이다. 따라서 linearized constraints는

\[h_j\!\left(x^{(k)}\right) + \nabla h_j\!\left(x^{(k)}\right)^T\Delta x^{(k)} =0,\] \[g_i\!\left(x^{(k)}\right) + \nabla g_i\!\left(x^{(k)}\right)^T\Delta x^{(k)} \leq0\]

이다. Linearization은 current point 부근의 local model이므로 design change가 지나치게 크면 original nonlinear functions를 정확히 나타내지 못한다.


Linearized Subproblem Notation

Chapter 12의 notation을 다음과 같이 둔다.

\[c=\nabla f\!\left(x^{(k)}\right), \qquad e_j=-h_j\!\left(x^{(k)}\right), \qquad b_i=-g_i\!\left(x^{(k)}\right).\]

Design change를

\[d=\Delta x^{(k)}\]

라 하고 equality와 inequality gradient vectors를 columns로 모아

\[N = \begin{bmatrix} \nabla h_1 & \cdots & \nabla h_p \end{bmatrix}, \qquad A = \begin{bmatrix} \nabla g_1 & \cdots & \nabla g_m \end{bmatrix}\]

로 둔다. Constant $f(x^{(k)})$를 제거하면 linearized subproblem은

\[\begin{aligned} \underset{d}{\operatorname{minimize}}\quad & \bar f=c^Td \\ \text{subject to}\quad & N^Td=e, \\ & A^Td\leq b. \end{aligned}\]

여기서 $\bar f$는 original cost의 linearized change이다. Equality와 inequality의 right-hand sides는 current violations의 negative values이므로, subproblem은 current point에서 feasibility를 회복하거나 유지하는 design change를 찾는다.


Sequential Linear Programming

Linearized objective와 constraints가 모두 $d$에 대해 linear이므로 LP method를 사용할 수 있다. 이를 sequential linear programming, SLP라 한다. SLP에서는 $d$가 search direction이 아니라 current iteration의 design change 자체이다.

Linear model은 unbounded할 수 있고 큰 design change에서는 부정확해질 수 있으므로 move limits를 추가한다.

\[-\Delta_{il}^{(k)} \leq d_i \leq \Delta_{iu}^{(k)}, \qquad i=1,\ldots,n.\]

Move limits는 다음 두 역할을 한다.

  • Linearized subproblem을 bounded problem으로 만든다.
  • 별도의 line search 없이 design change의 크기를 직접 제한한다.

$d_i$는 free in sign이므로 standard LP form이 필요하면

\[d_i=d_i^+-d_i^-, \qquad d_i^+,d_i^-\geq0\]

로 분해한다.


SLP Algorithm

Constraint feasibility tolerance를 $\epsilon_1>0$, design-change tolerance를 $\epsilon_2>0$이라 하자. SLP algorithm은 다음과 같다.

  1. Starting design $x^{(0)}$과 move limits를 정한다.
  2. $f$, $h_j$, $g_i$와 모든 gradients를 current design에서 계산한다.
  3. Linearized LP subproblem과 move limits를 구성한다.
  4. LP를 풀어 design change $d^{(k)}$를 구한다.
  5. 다음 conditions을 검사한다.
\[g_i(x^{(k)})\leq\epsilon_1, \qquad \left|h_j(x^{(k)})\right|\leq\epsilon_1, \qquad \left\|d^{(k)}\right\|\leq\epsilon_2.\]
  1. 종료하지 않으면
\[x^{(k+1)}=x^{(k)}+d^{(k)}\]

로 갱신한다.

Move limits가 너무 크면 linear approximation이 부정확해지고, 너무 작으면 progress가 느려진다. Linearized constraints가 inconsistent하여 LP가 infeasible하면 move limits를 완화하거나 current point를 변경해야 할 수 있다.


Limitations of SLP

SLP는 단순하고 large design-variable problems에도 적용하기 쉽지만 다음 한계를 갖는다.

  • Move-limit selection이 algorithm의 성능과 성공 여부에 직접 영향을 준다.
  • Descent function과 line search가 없으므로 robust convergence가 보장되지 않는다.
  • Optimum이 linearized feasible set의 vertex가 아니면 두 points 사이에서 cycling할 수 있다.
  • Original nonlinear constraints는 linearized constraints를 만족한 뒤에도 violated될 수 있다.

따라서 SLP는 precise local minimum을 보장하는 general-purpose method라기보다 improved design을 빠르게 구하는 방법으로 해석하는 것이 적절하다.


Sequential Quadratic Programming

SQP는 direction-finding과 step-size determination을 분리한다.

  1. Cost와 constraints의 values 및 gradients를 이용해 QP subproblem을 구성하고 search direction $d^{(k)}$를 구한다.
  2. Descent function을 최소화하는 step size $\alpha_k$를 계산한다.

SLP와 달리 SQP에서 $d^{(k)}$는 design change 자체가 아니라 direction이다.

\[\Delta x^{(k)}=\alpha_kd^{(k)}.\]

Move limits 대신 quadratic objective가 direction norm을 제한하여 subproblem을 bounded하게 만든다. Chapter 12의 introductory SQP는 first-order problem information만 사용하며, 다음 장에서 second-order information을 포함하는 확장으로 이어진다.


QP Direction Subproblem

Linearized cost decrease와 direction length를 동시에 최소화하도록 QP subproblem을

\[\begin{aligned} \underset{d}{\operatorname{minimize}}\quad & \bar f(d)=c^Td+\frac{1}{2}d^Td \\ \text{subject to}\quad & N^Td=e, \\ & A^Td\leq b \end{aligned}\]

로 정의한다. Quadratic term의 Hessian은 identity matrix이므로 objective는 strictly convex하다. 따라서 feasible solution이 존재하면 QP direction은 global minimum이며 unique하다. Active constraint gradients가 linearly independent이면 associated multipliers도 unique하다.

Objective를

\[\bar f(d) = \frac{1}{2}\left\|d+c\right\|^2 - \frac{1}{2}\left\|c\right\|^2\]

로 쓰면 unconstrained center는 $-c$이다. 따라서 QP solution은 negative gradient를 linearized feasible set에 projection한 direction으로 해석할 수 있다.

Constraints가 없거나 direction subproblem에서 active constraints가 없으면

\[d=-c\]

가 되어 ordinary steepest-descent direction을 회복한다.


KKT System of the QP Subproblem

Inequality multipliers를 $u\geq0$, equality multipliers를 $v$라 하자. QP Lagrangian은

\[L(d,u,v) = c^Td+\frac{1}{2}d^Td + u^T(A^Td-b) + v^T(N^Td-e)\]

이다. KKT conditions은

\[d+c+Au+Nv=0,\] \[N^Td=e, \qquad A^Td\leq b,\] \[u\geq0, \qquad u_i\left(a^{(i)T}d-b_i\right)=0.\]

Stationarity에서

\[d=-(c+Au+Nv)\]

를 얻는다. 즉 constraint normals의 multiplier-weighted combination이 negative gradient를 수정하여 linearized constraints를 만족시키는 CSD direction을 만든다.

QP solution은 direction뿐 아니라 $u$와 $v$도 제공한다. 이 multipliers는 step-size calculation에 사용할 penalty parameter를 결정한다.


Pshenichny Descent Function

Chapter 12는 exact-penalty form의 Pshenichny descent function을 사용한다.

\[\Phi(x) = f(x)+RV(x), \qquad R>0.\]

Maximum constraint violation은

\[V(x) = \max \left\{ 0,\, \left|h_1(x)\right|,\ldots,\left|h_p(x)\right|,\, g_1(x),\ldots,g_m(x) \right\}.\]

따라서 feasible point에서는 $V(x)=0$이고

\[\Phi(x)=f(x).\]

Infeasible point에서는 가장 큰 equality 또는 inequality violation이 penalty로 추가된다. Equality는 sign과 관계없이 violated되므로 absolute value를 사용한다.


Penalty Parameter from Multipliers

Current QP multipliers를 $v^{(k)}$와 $u^{(k)}$라 하면

\[r_k = \sum_{j=1}^{p}\left|v_j^{(k)}\right| + \sum_{i=1}^{m}u_i^{(k)}.\]

Convergence를 위한 necessary condition은

\[R\geq r_k\]

이다. Current penalty parameter가 $R_k$이면

\[R_{k+1} = \max\left\{R_k,r_k\right\}\]

로 갱신한다. Equality multipliers는 free in sign이므로 absolute values를 사용하고, inequality multipliers는 $u_i^{(k)}\geq0$이므로 그대로 합한다.

Penalty parameter가 너무 작으면 cost decrease가 constraint violation 증가를 압도할 수 있다. Multiplier-based update는 feasibility에 충분한 weight를 부여하면서 unnecessary large penalty를 피한다.


Step-Size Subproblem

Direction $d^{(k)}$가 주어졌을 때 trial design은

\[x(\alpha) = x^{(k)}+\alpha d^{(k)}\]

이다. Constrained line-search subproblem은

\[\underset{\alpha>0}{\operatorname{minimize}} \quad \Phi(\alpha) = \Phi\!\left(x^{(k)}+\alpha d^{(k)}\right)\]

이다. 각 trial point에서 original cost와 constraints를 다시 평가하여

\[\Phi_{k,j} = f_{k,j}+R_kV_{k,j}\]

를 계산한다.

$R_k$는 current direction의 line search를 시작하기 전에 multiplier condition에 맞춰 결정하고, 해당 line search 동안에는 fixed value로 유지한다. Golden-section search와 같은 interval-reducing method를 적용할 수 있지만 function and constraint evaluations가 많아질 수 있으므로 실제 constrained algorithms에서는 inexact line search가 선호된다.


Constrained Steepest-Descent Direction

CSD method는 QP subproblem의 solution을 search direction으로 사용한다. No active constraints인 경우 QP objective의 stationarity는

\[d+c=0\]

이므로 $d=-c$이다. Constraints가 존재하면 $d$는 linearized equalities와 active inequalities를 만족하면서 $-c$에 가장 가까운 direction이다.

따라서 CSD direction은 negative gradient를 constraint tangent hyperplane에 projection한 direction으로 해석할 수 있다. QP에는 모든 inequalities를 넣을 수도 있지만, 효율을 위해 active·$\epsilon$-active·violated constraints만 포함할 수 있다.

이 QP는 first-order information만 사용한다. Second-order objective 또는 Lagrangian information을 사용하면 general SQP method로 확장된다.


CSD Algorithm

Constraint feasibility tolerance를 $\epsilon_1>0$, direction tolerance를 $\epsilon_2>0$이라 하자.

  1. $x^{(0)}$과 initial penalty parameter $R_0>0$을 정한다.
  2. Current point에서 cost, constraints, gradients와 $V_k$를 계산한다.
  3. QP subproblem을 구성하고 $d^{(k)}$, $u^{(k)}$, $v^{(k)}$를 계산한다.
  4. 다음 stopping criteria를 검사한다.
\[\left\|d^{(k)}\right\|\leq\epsilon_2, \qquad V_k\leq\epsilon_1.\]
  1. Multiplier sum $r_k$를 계산하고
\[R_{k+1} = \max\left\{R_k,r_k\right\}\]

로 penalty parameter를 갱신한다.

  1. Descent function line search로 $\alpha_k$를 구하고
\[x^{(k+1)} = x^{(k)}+\alpha_kd^{(k)}\]

로 갱신한다.

Direction norm만 작고 constraint violation이 남아 있으면 종료할 수 없다. 반대로 feasible하더라도 nonzero CSD direction이 존재하면 KKT point에 도달하지 않은 것이다.


Convergence and Limitations of CSD

Chapter 12의 CSD algorithm은 feasible 또는 infeasible starting point에서 시작할 수 있으며, 적절한 regularity와 boundedness assumptions 아래에서 generated sequence의 limit point가 KKT point가 되도록 구성된다.

Convergence argument에는 다음 요소가 사용된다.

  • QP subproblem이 cost와 feasibility를 함께 고려하는 direction을 제공한다.
  • Multiplier-based penalty update가 $\Phi$를 valid descent function으로 만든다.
  • Line search가
\[\Phi\!\left(x^{(k+1)}\right) \leq \Phi\!\left(x^{(k)}\right)\]

을 유지한다.

  • Problem functions의 second derivatives가 piecewise continuous하고 generated designs가 bounded하다.

다만 current point에서 linearized constraints가 inconsistent하면 QP subproblem이 infeasible할 수 있다. 이는 original nonlinear problem의 infeasibility를 의미하지 않는다. Inconsistent constraints를 일시적으로 제외하거나 다른 starting point 또는 feasibility-restoration strategy가 필요할 수 있다.


Summary

  • Constrained algorithms도 direction과 step size를 분리하지만 두 subproblems 모두 constraints를 고려해야 한다.
  • Active, $\epsilon$-active, violated status는 direction subproblem에 포함할 critical inequalities를 구분한다.
  • First-order Taylor expansion은 nonlinear problem을 $c^Td$, $N^Td=e$, $A^Td\leq b$인 local subproblem으로 바꾼다.
  • SLP는 move limits가 포함된 LP를 반복하며 $d$를 design change로 직접 사용하지만 robust convergence와 precise minimum을 보장하지 않는다.
  • SQP는 strictly convex QP로 search direction을 구하고 별도의 descent-function line search로 step size를 계산한다.
  • Pshenichny function $\Phi=f+RV$는 cost와 maximum constraint violation을 함께 측정하며, QP multipliers가 penalty parameter를 결정한다.
  • CSD direction은 negative gradient의 linearized feasible-set projection이며, first-order SQP의 기본 형태를 제공한다.