Constrained Optimum Design, Part II
Active Sets, Projected Methods, and Second-Order SQP
- Potential Constraint Strategy
- Inexact Step-Size Calculation
- Descent Condition
- Bound-Constrained Problem
- Optimality Conditions for Bounds
- Projection Method
- SQP from the KKT System
- General SQP Subproblem
- Modified BFGS Hessian Update
- Basic SQP Algorithm
- SQP Merit Function
- Method of Feasible Directions
- Gradient Projection Method
- Generalized Reduced Gradient Method
- Summary
Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 13.
이 장에서는 constrained optimum design algorithm의 효율과 수렴성을 개선하는 핵심 기법을 정리한다. Potential constraint strategy로 direction subproblem에 필요한 constraints를 선택하고, inexact line search로 충분한 감소를 보장한다. 이어서 bound-constrained problem의 KKT conditions와 projection method를 살펴보고, Lagrangian curvature를 사용하는 sequential quadratic programming을 유도한다. 마지막으로 feasible directions, gradient projection, generalized reduced gradient methods의 구조를 비교한다.
Potential Constraint Strategy
Minimum에서 active인 inequalities는 일반적으로 전체 constraints의 일부뿐이지만, 그 subset은 미리 알 수 없다. $\epsilon>0$에 대하여 potential constraint index set 또는 working set을
\[\mathcal{I}_k = \left\{1,\ldots,p\right\}_{\mathrm{eq}} \cup \left\{ i: g_i\!\left(x^{(k)}\right)+\epsilon\geq0,\; i=1,\ldots,m \right\}_{\mathrm{ineq}}\]로 정의한다. 이 set에는 모든 equalities와 active, $\epsilon$-active, violated inequalities가 포함된다. $g_i(x^{(k)})+\epsilon<0$인 inactive inequality는 current direction subproblem에서 제외한다.
이 전략은 계산해야 할 constraint gradients와 subproblem dimension을 동시에 줄인다. Potential set은 optimum의 active set을 확정하는 것이 아니라 현재 iteration에서 active가 될 가능성이 있는 constraints를 보수적으로 선택한다. 따라서 $\epsilon$이 너무 작으면 곧 active가 될 constraint를 놓칠 수 있고, 너무 크면 working set을 줄이는 이점이 감소한다.
Inexact Step-Size Calculation
Exact one-dimensional minimization은 많은 function and constraint evaluations를 요구한다. 대신 Pshenichny descent function
\[\Phi_k=f_k+RV_k\]을 충분히 감소시키는 approximate step을 사용한다. 여기서
\[V_k = \max \left\{ 0,\, \left|h_1\!\left(x^{(k)}\right)\right|,\ldots, \left|h_p\!\left(x^{(k)}\right)\right|,\, g_1\!\left(x^{(k)}\right),\ldots, g_m\!\left(x^{(k)}\right) \right\}\]은 maximum constraint violation이고, $R>0$은 line search 동안 고정하는 penalty parameter이다.
$0<\mu<1$에 대하여 trial steps를
\[t_j=\mu^j, \qquad j=0,1,2,\ldots\]로 둔다. $\mu=1/2$이면 $1,1/2,1/4,\ldots$의 backtracking sequence를 얻는다. Trial design은
\[x^{(k+1,j)} = x^{(k)}+t_jd^{(k)}\]이다.
Descent Condition
$0<\gamma<1$에 대하여
\[\beta_k = \gamma\left\|d^{(k)}\right\|^2\]로 둔다. Acceptable step은
\[\Phi_{k+1,j} \leq \Phi_k-t_j\beta_k,\] \[\Phi_{k+1,j} = f\!\left(x^{(k+1,j)}\right) +RV\!\left(x^{(k+1,j)}\right)\]를 만족해야 한다. 위 inequality를 만족하는 smallest nonnegative integer $j$를 선택하고
\[\alpha_k=t_j\]로 둔다. 즉 geometric sequence에서 가장 큰 admissible trial step을 채택한다. $\gamma$가 커질수록 요구되는 감소량이 증가하여 acceptable step의 범위는 작아진다.
CSD iteration에서는 $\mathcal{I}_k$로 QP direction을 계산하고, multipliers로 $R$을 갱신한 뒤 이 line search를 적용한다. Potential set은 direction 계산 비용을 줄이지만, $V_k$에는 omitted constraint의 violation을 놓치지 않도록 모든 original constraints가 포함되어야 한다.
Bound-Constrained Problem
Bound-constrained problem은
\[\underset{x\in S}{\operatorname{minimize}} \quad f(x),\] \[S = \left\{ x\in\mathbb{R}^n: x_{iL}\leq x_i\leq x_{iU},\; i=1,\ldots,n \right\}\]으로 정의한다. Lower- and upper-bound multipliers를 각각 $V_i\geq0$와 $U_i\geq0$라 하면
\[\mathcal{L}(x,V,U) = f(x) + \sum_{i=1}^{n}V_i(x_{iL}-x_i) + \sum_{i=1}^{n}U_i(x_i-x_{iU})\]이다.
Optimality Conditions for Bounds
$c_i=\partial f/\partial x_i$라 하면 KKT conditions는
\[c_i-V_i+U_i=0,\] \[V_i(x_{iL}-x_i)=0, \qquad U_i(x_i-x_{iU})=0,\] \[x_{iL}\leq x_i\leq x_{iU}, \qquad V_i\geq0, \qquad U_i\geq0.\]따라서 각 coordinate에서
\[x_i=x_{iL} \quad\Longrightarrow\quad c_i=V_i\geq0,\] \[x_i=x_{iU} \quad\Longrightarrow\quad c_i=-U_i\leq0,\] \[x_{iL}<x_i<x_{iU} \quad\Longrightarrow\quad c_i=0.\]Lower bound에서 $c_i<0$이거나 upper bound에서 $c_i>0$이면 feasible descent direction이 존재하므로 variable을 release해야 한다. Bound에 있다는 사실만으로 active variable이 되는 것이 아니라 gradient sign까지 만족해야 한다.
Projection Method
Coordinatewise projection $P:\mathbb{R}^n\to S$를
\[P_i(z) = \begin{cases} x_{iL}, & z\leq x_{iL},\\ z, & x_{iL}<z<x_{iU},\\ x_{iU}, & z\geq x_{iU} \end{cases}\]로 정의한다. Current point 부근의 active set은 작은 $\delta_k>0$에 대하여
\[\begin{aligned} \mathcal{A}_k = \bigl\{ i:\;& x_{iL}\leq x_i^{(k)}\leq x_{iL}+\delta_k \ \text{and}\ c_i^{(k)}>0 \\ &\text{or}\quad x_{iU}-\delta_k\leq x_i^{(k)}\leq x_{iU} \ \text{and}\ c_i^{(k)}<0 \bigr\} \end{aligned}\]로 식별한다. Complement $\mathcal{F}_k={1,\ldots,n}\setminus\mathcal{A}_k$는 free-variable set이다.
Active variables는 projected step으로 bound에 머물고, free variables의 direction은 unconstrained method로 계산할 수 있다. Accepted update는
\[x^{(k+1)} = P\!\left(x^{(k)}+\alpha_kd^{(k)}\right)\]이다. Projection method는 active set을 iteration마다 다시 식별하고 free variables에 대해서만 subproblem을 푼다. 적절한 assumptions 아래에서는 correct active set을 finite iterations 안에 식별하고 local minimum으로 수렴한다.
SQP from the KKT System
SQP는 equality-constrained problem의 KKT equations에 Newton method를 적용하여 유도한다. $\mathcal{L}(x,v)=f(x)+v^Th(x)$라 하면
\[\nabla_x\mathcal{L}(x,v)=0, \qquad h(x)=0.\]$N$의 columns를 $\nabla h_j(x^{(k)})$로 두면 Newton equation은
\[\begin{bmatrix} \nabla_{xx}^2\mathcal{L}^{(k)} & N^{(k)}\\ N^{(k)T} & 0 \end{bmatrix} \begin{bmatrix} \Delta x^{(k)}\\ v^{(k+1)} \end{bmatrix} = - \begin{bmatrix} \nabla f\!\left(x^{(k)}\right)\\ h\!\left(x^{(k)}\right) \end{bmatrix}\]이 된다. 이 system은
\[\begin{aligned} \underset{d}{\operatorname{minimize}}\quad & \nabla f\!\left(x^{(k)}\right)^Td + \frac{1}{2}d^T\nabla_{xx}^2\mathcal{L}^{(k)}d \\ \text{subject to}\quad & h\!\left(x^{(k)}\right)+N^{(k)T}d=0 \end{aligned}\]인 QP의 KKT system과 같다. 따라서 SQP direction은 linearized feasibility와 Lagrangian curvature를 함께 반영하는 Newton-type direction이다.
General SQP Subproblem
Equality와 inequality constraints를 모두 포함하면
\[\begin{aligned} \underset{d}{\operatorname{minimize}}\quad & \bar f(d) = c^Td+\frac{1}{2}d^THd \\ \text{subject to}\quad & N^Td=e, \\ & A^Td\leq b \end{aligned}\]를 얻는다. 여기서 $c=\nabla f(x^{(k)})$, $e=-h(x^{(k)})$, $b=-g(x^{(k)})$이고 $H$는 $\nabla_{xx}^2\mathcal{L}$ 또는 그 approximation이다. Potential strategy를 사용하면 inequalities에는 $\mathcal{I}_k$의 constraints만 포함한다.
$H=I$이면 CSD subproblem을 얻는다. $H$가 positive definite이면 QP objective는 strictly convex이므로 feasible subproblem은 unique direction을 갖는다.
Modified BFGS Hessian Update
Exact Lagrangian Hessian 대신 gradients로 $H^{(k)}$를 갱신한다. 먼저
\[s^{(k)} = \alpha_kd^{(k)}, \qquad z^{(k)} = H^{(k)}s^{(k)}\]로 둔다. 두 점에서 동일한 current multipliers $u^{(k)}$, $v^{(k)}$를 사용하여
\[y^{(k)} = \nabla_x\mathcal{L} \!\left(x^{(k+1)},u^{(k)},v^{(k)}\right) - \nabla_x\mathcal{L} \!\left(x^{(k)},u^{(k)},v^{(k)}\right)\]를 계산하고
\[\xi_1=s^{(k)T}y^{(k)}, \qquad \xi_2=s^{(k)T}z^{(k)}\]로 둔다. Powell damping parameter는
\[\theta = \begin{cases} 1, & \xi_1\geq0.2\xi_2, \\[2mm] \dfrac{0.8\xi_2}{\xi_2-\xi_1}, & \xi_1<0.2\xi_2 \end{cases}\]이고 modified gradient difference는
\[w^{(k)} = \theta y^{(k)} + (1-\theta)z^{(k)}\]이다. Hessian approximation은
\[H^{(k+1)} = H^{(k)} + \frac{w^{(k)}w^{(k)T}} {s^{(k)T}w^{(k)}} - \frac{z^{(k)}z^{(k)T}} {s^{(k)T}z^{(k)}}\]로 갱신한다. $H^{(k)}$가 positive definite이면 damping에 의해
\[s^{(k)T}w^{(k)} \geq 0.2\,s^{(k)T}H^{(k)}s^{(k)} >0\]이므로 positive definiteness와 QP의 strict convexity를 유지한다.
Basic SQP Algorithm
Basic SQP method는 CSD algorithm에 Hessian update를 추가한 형태이다.
- $x^{(0)}$과 penalty parameter를 정하고 $H^{(0)}=I$로 둔다.
- Functions, gradients, maximum violation $V_k$를 계산하고 $k>0$이면 $H^{(k)}$를 갱신한다.
- Potential set의 SQP subproblem을 풀어 $d^{(k)}$, $u^{(k)}$, $v^{(k)}$를 구한다.
- Multipliers에 맞게 penalty parameters를 갱신하고 inexact line search를 수행한다.
- $x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}$로 갱신한다.
CSD는 QP Hessian으로 identity를 사용하지만 SQP는 Lagrangian curvature approximation을 축적하므로 solution 부근에서 더 빠른 local convergence를 기대할 수 있다.
SQP Merit Function
QP direction이 local model을 개선해도 nonlinear problem에서 cost와 feasibility가 함께 감소한다는 보장은 없다. Han–Powell exact-penalty function은
\[\Phi_H(x) = f(x) + \sum_{j=1}^{p}r_j\left|h_j(x)\right| + \sum_{i=1}^{m}\mu_i\max\left\{0,g_i(x)\right\}\]이다. Penalty parameters는 QP multipliers를 지배하도록
\[r_j\geq\left|v_j\right|, \qquad \mu_i\geq u_i\]로 선택한다. Feasible point에서는 $\Phi_H(x)=f(x)$이다. Merit function은 objective reduction과 constraint restoration을 하나의 scalar measure로 결합하고, inexact line search는 sufficient decrease를 강제한다.
Method of Feasible Directions
Current feasible design에서 improving feasible direction은
\[c^Td<0, \qquad a_i^Td<0, \quad i\in\mathcal{I}_k\]를 만족한다. 여기서 $c=\nabla f(x^{(k)})$, $a_i=\nabla g_i(x^{(k)})$이다. Direction은
\[\begin{aligned} \underset{\beta,d}{\operatorname{minimize}}\quad & \beta \\ \text{subject to}\quad & c^Td\leq\beta, \\ & a_i^Td\leq\theta_i\beta, && i\in\mathcal{I}_k, \\ & -1\leq d_j\leq1, && j=1,\ldots,n \end{aligned}\]인 LP로 구한다. $\theta_i>0$는 push-off factor이다. $\beta<0$이면 improving feasible direction을 얻고, $\beta=0$이면 current point는 KKT conditions를 만족한다. 이 방법은 feasible starting point를 요구하며 equality constraints를 유지하기 어렵다.
Gradient Projection Method
Gradient projection method는 negative cost gradient를 active-constraint tangent space에 projection한다. Active gradient matrix $N$의 columns가 linearly independent이면
\[d = - \left[ I-N\left(N^TN\right)^{-1}N^T \right]c, \qquad N^Td=0.\]Nonlinear surface에서는 tangent step 뒤 constraint-correction steps가 필요하다. Feasible active point에서 이 direction은 CSD direction과 같지만 step-size and correction procedure는 다르다. Direction 계산은 단순한 반면 correction과 convergence control은 복잡하다.
Generalized Reduced Gradient Method
GRG method는 active constraints를 equalities로 취급하고 variables를 independent $y\in\mathbb{R}^{n-p}$와 dependent $z\in\mathbb{R}^{p}$로 분할한다.
\[x = \begin{bmatrix} y\\ z \end{bmatrix}.\]First-order constraint change를
\[\Delta h = A^T\Delta y+B^T\Delta z\]로 쓰면 feasibility condition은
\[A^T\Delta y+B^T\Delta z=0.\]$B$가 nonsingular이면
\[\Delta z = -B^{-T}A^T\Delta y.\]이를 objective change에 대입하면 reduced gradient
\[\frac{df}{dy} = \frac{\partial f}{\partial y} - AB^{-1}\frac{\partial f}{\partial z}\]를 얻는다. Reduced-space direction은
\[\Delta y = -\alpha\frac{df}{dy}\]로 선택하고 $\Delta z$는 feasibility relation에서 계산한다. Active constraints가 정확히 만족되지 않으면 Newton correction으로 $z$를 조정한다.
\[\frac{df}{dy}=0\]이면 KKT stationarity가 성립한다. Potential inequalities를 equalities로 취급할 때 GRG와 gradient projection은 본질적으로 같은 tangent-space direction을 생성한다.
Summary
- Potential constraint set은 equality, active, $\epsilon$-active, violated constraints만 direction subproblem에 포함한다.
- Inexact line search는 $\Phi_{k+1,j}\leq\Phi_k-t_j\gamma|d^{(k)}|^2$를 처음 만족하는 geometric trial step을 선택한다.
- Bound-constrained KKT conditions는 lower bound에서 $c_i\geq0$, upper bound에서 $c_i\leq0$, interior에서 $c_i=0$을 요구한다.
- Projection method는 $P(x+\alpha d)$로 feasibility를 유지하면서 active/free variables를 식별한다.
- SQP subproblem은 KKT equations의 Newton step이며 Lagrangian Hessian을 통해 second-order curvature를 반영한다.
- Powell-damped BFGS update는 positive-definite Hessian approximation을 유지한다.
- Merit function과 sufficient-decrease line search는 SQP의 global behavior를 제어한다.
- Feasible directions, gradient projection, GRG는 각각 interior direction, tangent projection, variable elimination을 사용한다.