Optimality Conditions, Part II

Regularity, Second-Order Conditions, and Nonlinear Duality

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

이 장에서는 KKT condition을 적용할 수 있는 regularity assumption, constrained stationary point를 분류하는 second-order condition, 그리고 primal problem과 dual problem의 관계를 정리한다. 핵심은 전체 공간에서 objective의 Hessian을 검사하는 것이 아니라, constraint가 허용하는 방향에서 Lagrangian의 curvature를 검사하는 것이다.


KKT Conditions without Slack Variables

다음 constrained 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}\]

Lagrangian은

\[L(x,u,v) = f(x) + \sum_{i=1}^{m}u_i g_i(x) + \sum_{j=1}^{p}v_j h_j(x)\]

이다. Slack variable을 사용하지 않는 KKT system은

\[\begin{aligned} \nabla_x L(x^\star,u^\star,v^\star)&=0, \\ h_j(x^\star)&=0, \\ g_i(x^\star)&\leq0, \\ u_i^\star&\geq0, \\ u_i^\star g_i(x^\star)&=0 \end{aligned}\]

으로 쓴다. 이는 $g_i(x)+s_i^2=0$과 $u_i s_i=0$을 사용하는 formulation과 동등하지만, active set과 multiplier의 관계를 더 직접적으로 보여준다.


Regular and Irregular Points

$x^\star$에서 active inequality의 index set을

\[\mathcal{A}(x^\star) = \left\{ i:g_i(x^\star)=0 \right\}\]

이라 하자. 다음 constraint gradient들의 집합이 linearly independent이면 $x^\star$를 regular point라 한다.

\[\left\{ \nabla h_1(x^\star),\ldots,\nabla h_p(x^\star), \nabla g_i(x^\star),\ i\in\mathcal{A}(x^\star) \right\}.\]

이는 Linear Independence Constraint Qualification, 즉 LICQ이다. Active-constraint Jacobian을

\[A(x^\star) = \begin{bmatrix} \nabla h_1(x^\star)^T\\ \vdots\\ \nabla h_p(x^\star)^T\\ \nabla g_{i_1}(x^\star)^T\\ \vdots\\ \nabla g_{i_r}(x^\star)^T \end{bmatrix}\]

로 두면 regularity는

\[\operatorname{rank}A(x^\star)=p+r, \qquad r=\lvert\mathcal{A}(x^\star)\rvert\]

와 같다. 따라서 regular point에서는 active constraint의 수가 $n$을 초과할 수 없다.

LICQ가 성립하면 다음 성질을 얻는다.

  • KKT necessary theorem을 적용할 수 있다.
  • KKT multiplier가 존재하며 유일하다.
  • Constraint tangent space의 차원은 $n-p-r$이다.
  • Implicit-function argument를 사용해 국소 feasible geometry를 해석할 수 있다.

반대로 active constraint gradient가 linearly dependent이면 $x^\star$는 irregular point이다. 이 경우 local minimizer가 KKT condition을 만족하지 않을 수 있으며, KKT multiplier가 존재하더라도 유일하지 않을 수 있다. 따라서 irregular point에서 KKT system의 실패는 그 점이 minimum이 아니라는 증거가 아니다. 먼저 regularity assumption이 깨졌는지 확인해야 한다.


Why Regularity Matters

Regularity는 objective gradient를 active constraint normal의 조합으로 표현할 수 있게 하는 조건이다. Equality와 active inequality의 gradient를 열벡터로 모은 행렬을 $N(x^\star)$라 하면 stationarity는

\[\nabla f(x^\star)+N(x^\star)\lambda^\star=0\]

이다. $N(x^\star)$가 full column rank이면 동일한 $\nabla f(x^\star)$를 만드는 multiplier $\lambda^\star$는 유일하다. 실제로 두 multiplier $\lambda_1$과 $\lambda_2$가 존재한다면

\[N(x^\star)(\lambda_1-\lambda_2)=0.\]

Null space가 ${0}$이므로 $\lambda_1=\lambda_2$이다.

Irregular point에서는 $N(x^\star)$의 null space가 nontrivial하므로 multiplier가 여러 개 존재할 수 있다. 이 경우 multiplier를 constraint sensitivity로 해석할 때도 주의가 필요하다. 어떤 multiplier를 선택하는지에 따라 sensitivity value가 달라질 수 있기 때문이다.


Lagrangian Hessian

First-order KKT condition을 만족하는 $(x^\star,u^\star,v^\star)$에서 Lagrangian Hessian을

\[H_L = \nabla_{xx}^2L(x^\star,u^\star,v^\star) = \nabla^2 f(x^\star) + \sum_{i=1}^{m}u_i^\star\nabla^2g_i(x^\star) + \sum_{j=1}^{p}v_j^\star\nabla^2h_j(x^\star)\]

로 정의한다. Constrained second-order condition에서는 $\nabla^2f(x^\star)$만 검사하면 안 된다. Constraint surface의 curvature도 feasible objective variation에 기여하므로 multiplier로 가중된 $H_L$을 사용해야 한다.

Active inequality를 multiplier에 따라

\[\mathcal{A}_+ = \left\{ i\in\mathcal{A}(x^\star):u_i^\star>0 \right\}, \qquad \mathcal{A}_0 = \left\{ i\in\mathcal{A}(x^\star):u_i^\star=0 \right\}\]

으로 나눈다. $\mathcal{A}_+$의 constraint는 first order에서 boundary를 따라 움직여야 하지만, $\mathcal{A}_0$의 constraint는 feasible region 내부로 들어가는 방향을 허용할 수 있다.


Constraint Tangent Directions

모든 active constraint boundary에 tangent한 방향의 집합은

\[\mathcal{T}_A(x^\star) = \left\{ d: \nabla h_j(x^\star)^Td=0, \ \nabla g_i(x^\star)^Td=0 \ \text{for every }i\in\mathcal{A}(x^\star) \right\}\]

이다. 이는 active-constraint Jacobian의 null space와 같다.

Second-order sufficient condition에 필요한 방향집합은 weakly active inequality가 feasible interior direction을 허용한다는 점까지 반영한다.

\[\mathcal{C}(x^\star,u^\star) = \left\{ d: \begin{array}{ll} \nabla h_j(x^\star)^Td=0, & j=1,\ldots,p,\\ \nabla g_i(x^\star)^Td=0, & i\in\mathcal{A}_+,\\ \nabla g_i(x^\star)^Td\leq0, & i\in\mathcal{A}_0 \end{array} \right\}.\]

KKT stationarity에 의해 모든 $d\in\mathcal{C}(x^\star,u^\star)$는

\[\nabla f(x^\star)^Td=0\]

을 만족한다. 따라서 $\mathcal{C}$는 first-order objective change가 사라지는 feasible critical direction들의 집합이다.


Second-Order Necessary Condition

$x^\star$가 regular local minimizer이고 KKT condition을 만족한다고 하자. 그러면 모든 nonzero tangent direction $d\in\mathcal{T}_A(x^\star)$에 대하여

\[d^T H_L d\geq0\]

이어야 한다.

Derivation. Active constraint를 first order에서 유지하는 feasible curve $x(t)$를 생각하자.

\[x(0)=x^\star, \qquad x'(0)=d.\]

KKT stationarity와 feasibility를 이용하면 Lagrangian의 first-order term은 사라진다. 따라서

\[L(x(t),u^\star,v^\star)-L(x^\star,u^\star,v^\star) = \frac{t^2}{2}d^T H_Ld + o(t^2).\]

어떤 tangent direction에서 $d^TH_Ld<0$이면 충분히 작은 $t$에 대해 feasible objective가 감소하므로 local minimality와 모순이다.

이 조건을 위반한 KKT point는 local minimizer가 될 수 없다. 그러나 $d^TH_Ld\geq0$을 만족하는 것만으로는 local minimum이 보장되지 않는다.


Second-Order Sufficient Condition

KKT point $(x^\star,u^\star,v^\star)$에서

\[d^T H_Ld>0 \qquad \text{for every nonzero }d\in\mathcal{C}(x^\star,u^\star)\]

이면 $x^\star$는 isolated strict local minimizer이다. 더 정확히는 어떤 $c>0$와 $x^\star$의 neighborhood가 존재하여 feasible $x$에 대해

\[f(x) \geq f(x^\star) + c\lVert x-x^\star\rVert^2\]

형태의 quadratic growth가 성립한다.

이 조건은 $H_L$이 전체 공간에서 positive definite일 것을 요구하지 않는다. Constraint가 제거하는 방향에서 negative curvature가 존재하더라도, 모든 feasible critical direction에서 curvature가 positive이면 충분하다.

반대로

\[H_L\succ0\]

이면 모든 nonzero direction에서 quadratic form이 positive이므로 constrained second-order sufficient condition은 자동으로 성립한다. 이는 확인하기 쉬운 strong sufficient condition이지만 필요조건은 아니다.

만약 $\mathcal{C}(x^\star,u^\star)={0}$이면 검사할 nonzero critical direction이 없으므로 sufficient condition은 vacuously satisfied된다. 단순히 모든 active constraint를 equality로 취급한 tangent space가 ${0}$이라는 사실만으로는 부족하다. Zero multiplier를 갖는 active inequality는 feasible interior direction을 허용할 수 있으므로 반드시 $\mathcal{C}$를 확인해야 한다.


Reduced-Hessian Test

모든 relevant constraint가 equality처럼 작용하는 경우, $A(x^\star)$의 null space basis를 열벡터로 갖는 행렬 $Z$를 선택하자.

\[A(x^\star)Z=0, \qquad Z\in\mathbb{R}^{n\times q}.\]

모든 tangent direction은 $d=Zp$로 표현되므로

\[d^TH_Ld = p^T\left(Z^TH_LZ\right)p.\]

따라서 tangent space에서의 curvature는 reduced Hessian

\[H_R=Z^TH_LZ\]

의 definiteness로 판정할 수 있다.

\[H_R\succeq0 \quad\Longrightarrow\quad \text{restricted second-order necessary test},\] \[H_R\succ0 \quad\Longrightarrow\quad \text{second-order sufficiency on the tangent space}.\]

이 표현은 full Hessian이 indefinite이더라도 feasible subspace에서는 positive curvature를 가질 수 있음을 명확하게 보여준다.


Primal and Dual Problems

Primal problem의 Lagrangian dual function을

\[\phi(v,u) = \inf_{x\in\mathbb{R}^n}L(x,u,v), \qquad u\geq0\]

로 정의한다. Dual problem은

\[\underset{v,\,u\geq0}{\operatorname{maximize}}\quad \phi(v,u)\]

이다. Equality multiplier $v$는 unrestricted이고 inequality multiplier $u$만 nonnegative이다.

Dual function은 primal constraint를 직접 강제하지 않는다. 대신 multiplier를 고정한 unconstrained Lagrangian의 가장 작은 값을 계산한다. 따라서 dual variable은 constraint violation에 가격을 부여하고, dual maximization은 가장 강한 lower bound를 찾는다.


Weak Duality

$x$가 primal feasible이고 $(v,u)$가 $u\geq0$을 만족하는 dual-feasible multiplier라 하자. Dual function의 정의로부터

\[\phi(v,u) \leq L(x,u,v).\]

Primal feasibility와 $u\geq0$을 사용하면

\[L(x,u,v) = f(x) + \sum_i u_i g_i(x) + \sum_j v_j h_j(x) \leq f(x).\]

따라서

\[\phi(v,u)\leq f(x)\]

이다. 이를 weak duality라 한다. Primal optimal value와 dual optimal value를 각각 $p^\star$, $d^\star$라 하면

\[d^\star\leq p^\star.\]

그러므로 임의의 feasible design은 $p^\star$의 upper bound를 제공하고, 임의의 dual-feasible multiplier는 $p^\star$의 lower bound를 제공한다. 차이

\[f(x)-\phi(v,u)\geq0\]

는 현재 primal-dual pair의 optimality gap으로 해석할 수 있다.


Local Duality for Equality Constraints

Equality-constrained problem에서

\[L(x,v)=f(x)+v^Th(x)\]

라 하자. $x^\star$가 regular local minimizer이고 $v^\star$가 대응하는 multiplier이며

\[H_L = \nabla_{xx}^2L(x^\star,v^\star) \succ0\]

라고 가정한다. 그러면 $v^\star$ 근방의 각 $v$에 대해 $L(x,v)$를 국소적으로 최소화하는 differentiable mapping $x(v)$가 존재한다. Local dual function은

\[\phi(v)=L(x(v),v)\]

로 정의한다.

Constraint gradient matrix를

\[N(x) = \begin{bmatrix} \nabla h_1(x) & \cdots & \nabla h_p(x) \end{bmatrix} \in\mathbb{R}^{n\times p}\]

라 하면 envelope relation에 의해

\[\nabla\phi(v)=h(x(v))\]

이다. 실제로 chain rule을 적용하면

\[\frac{d\phi}{dv} = \frac{\partial L}{\partial v} + \frac{\partial x(v)^T}{\partial v} \nabla_xL(x(v),v),\]

이고 $x(v)$에서 $\nabla_xL=0$이므로 두 번째 항이 사라진다.

Stationarity equation을 $v$에 대해 미분하면 dual Hessian은

\[\nabla^2\phi(v) = -N(x(v))^T \left[\nabla_{xx}^2L(x(v),v)\right]^{-1} N(x(v))\]

이 된다. $H_L\succ0$이고 regularity에 의해 $N$이 full column rank이면

\[\nabla^2\phi(v^\star)\prec0.\]

또한 $\nabla\phi(v^\star)=h(x^\star)=0$이므로 $v^\star$는 local dual maximizer이고

\[\phi(v^\star) = L(x^\star,v^\star) = f(x^\star)\]

이다. 즉 이 가정 아래에서는 local duality gap이 없다.


Strong Duality and Saddle Points

Equality와 inequality가 함께 있는 problem에서도 regular local minimizer, KKT multipliers, suitable constraint qualification, 그리고 Lagrangian Hessian의 positive definiteness가 성립하면 국소적으로

\[f(x^\star)=\phi(v^\star,u^\star)\]

인 strong duality relation을 얻는다. 이 관계는 Lagrangian의 saddle-point property로 표현할 수 있다.

\[L(x^\star,u,v) \leq L(x^\star,u^\star,v^\star) \leq L(x,u^\star,v^\star), \qquad u\geq0.\]

왼쪽 부등식은 primal feasibility와 complementary slackness에서 나온다. 오른쪽 부등식은 $x^\star$가 fixed multiplier $(u^\star,v^\star)$에 대해 Lagrangian을 국소적으로 최소화한다는 뜻이다. 따라서 primal에서는 $x$에 대해 minimize하고, dual에서는 multiplier에 대해 maximize하는 saddle structure가 형성된다.

Weak duality는 convexity 없이도 성립하지만, equality of primal and dual optimal values는 추가 가정을 필요로 한다. 따라서 dual solution을 얻었다는 사실만으로 primal optimality를 주장해서는 안 되며, duality gap과 theorem의 regularity 및 curvature assumptions를 함께 확인해야 한다.


Optimality Verification Procedure

Constrained candidate point는 다음 순서로 검증한다.

  1. Primal feasibility와 active set $\mathcal{A}(x^\star)$를 확인한다.
  2. Active constraint gradient의 rank를 계산하여 regularity를 확인한다.
  3. Stationarity, dual feasibility, complementary slackness로 KKT condition을 검사한다.
  4. Lagrangian Hessian $H_L$을 계산한다.
  5. Tangent 또는 critical direction에서 $d^TH_Ld$의 부호를 검사한다.
  6. Convexity 또는 second-order sufficient condition으로 local/global minimality를 판정한다.
  7. Multiplier의 sensitivity interpretation과 primal-dual gap을 확인한다.
Test Mathematical condition Interpretation
Regularity Active constraint gradients are linearly independent KKT applicability and multiplier uniqueness
First order KKT conditions Candidate constrained stationary point
Second-order necessary $d^TH_Ld\geq0$ on active tangent directions Failure rules out a local minimum
Second-order sufficient $d^TH_Ld>0$ on every nonzero critical direction Isolated strict local minimum
Weak duality $\phi(v,u)\leq f(x)$ Dual lower bound and primal upper bound
Local strong duality $\phi(v^\star,u^\star)=f(x^\star)$ under stated assumptions Zero local duality gap

Regularity, first-order condition, second-order condition, duality는 서로 대체되는 검사가 아니다. 이들을 순서대로 결합해야 candidate point의 존재 가능성, 국소적 분류, 그리고 objective bound를 구분하여 판단할 수 있다.


Summary

  • LICQ는 KKT theorem의 적용과 multiplier의 유일성을 보장하며, irregular point에서는 KKT failure만으로 minimum을 배제할 수 없다.
  • Constrained curvature는 objective Hessian이 아니라 multiplier가 반영된 Lagrangian Hessian으로 평가한다.
  • Second-order condition은 전체 공간이 아닌 tangent 또는 critical direction에서 quadratic form의 부호를 검사한다.
  • Reduced Hessian은 feasible tangent subspace에 제한된 Lagrangian curvature를 행렬 형태로 표현한다.
  • Weak duality는 dual value가 primal optimum의 lower bound임을 보장하며 convexity 없이도 성립한다.
  • Strong duality와 saddle-point relation은 regularity와 curvature를 포함한 추가 가정 아래에서 primal-dual gap이 사라짐을 나타낸다.