Optimality Conditions, Part I

First-Order Conditions, Lagrange Multipliers, and Global Optimality

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

이 장에서는 smooth optimum design problem의 해가 반드시 만족해야 하는 조건과, 그 조건이 실제 최적해를 보장하는 경우를 정리한다. 핵심은 feasible direction에 대한 objective의 변화율을 조사하고, 이를 gradient, Hessian, Lagrange multiplier, KKT condition으로 표현하는 것이다. Constraint qualification과 constrained second-order condition의 상세한 이론은 다음 장에서 다룬다.


Problem Setting

다음 minimization 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)\leq 0, && i=1,\ldots,m. \end{aligned}\]

Feasible set과 active set은 각각

\[\mathcal{S} = \left\{ x:h_j(x)=0,\ g_i(x)\leq0 \right\}, \qquad \mathcal{A}(x) = \left\{ i:g_i(x)=0 \right\}\]

로 정의한다. Equality constraint는 모든 feasible point에서 active하며, inactive inequality는 해당 점의 국소적인 움직임을 직접 제한하지 않는다.

이 장에서는 별도의 언급이 없으면 $f$, $h_j$, $g_i$가 필요한 차수만큼 연속 미분 가능하다고 가정한다.


Local, Global, and Existence Concepts

$x^\star\in\mathcal{S}$가 어떤 $\varepsilon>0$에 대하여

\[f(x^\star)\leq f(x) \qquad \text{for every }x\in\mathcal{S}\cap B_\varepsilon(x^\star)\]

를 만족하면 local minimizer이다. 모든 $x\in\mathcal{S}$에 대하여 같은 부등식이 성립하면 global minimizer이다. 부등호가 $x\neq x^\star$에서 엄격하면 strict local 또는 strict global minimizer라 한다.

Optimality condition은 minimizer의 성질을 판정하지만 minimizer의 존재 자체를 보장하지는 않는다. 존재성에 대한 기본 결과는 Weierstrass theorem이다.

Weierstrass theorem. 공집합이 아닌 compact feasible set $\mathcal{S}$ 위에서 $f$가 연속이면, $f$는 $\mathcal{S}$에서 global minimum과 global maximum을 갖는다.

따라서 closedness와 boundedness는 단순한 기술적 조건이 아니다. Feasible set이 열려 있거나 objective가 아래로 유계가 아니면 infimum이 존재하더라도 이를 달성하는 design은 없을 수 있다.


Differential Preliminaries

함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$의 gradient와 Hessian은

\[\nabla f(x) = \begin{bmatrix} \dfrac{\partial f}{\partial x_1} & \cdots & \dfrac{\partial f}{\partial x_n} \end{bmatrix}^{T}, \qquad \nabla^2 f(x) = \left[ \frac{\partial^2 f}{\partial x_i\partial x_j} \right]\]

로 정의한다. $d\in\mathbb{R}^n$ 방향의 first- and second-order directional derivative는

\[D f(x)[d]=\nabla f(x)^T d, \qquad D^2 f(x)[d,d]=d^T\nabla^2 f(x)d\]

이다. $f$가 두 번 연속 미분 가능하면 작은 $d$에 대하여

\[f(x+d) = f(x) + \nabla f(x)^T d + \frac{1}{2}d^T\nabla^2 f(x)d + o(\lVert d\rVert^2)\]

가 성립한다. Optimality condition은 이 Taylor expansion의 first-order term과 second-order term의 부호에서 나온다.


Unconstrained Optimality Conditions

먼저 constraint가 없는 problem을 생각하자.

\[\underset{x\in\mathbb{R}^n}{\operatorname{minimize}}\ f(x).\]

First-order necessary condition

$x^\star$가 local minimizer이고 $f$가 $x^\star$에서 미분 가능하면

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

이다.

Derivation. 임의의 $d$에 대하여 $\phi(t)=f(x^\star+td)$를 정의한다. $t=0$은 $\phi$의 local minimizer이므로

\[\phi'(0)=\nabla f(x^\star)^T d=0.\]

이 식이 모든 $d$에 대해 성립하므로 $\nabla f(x^\star)=0$이다. 이를 만족하는 점을 stationary point라 한다. Stationarity는 local minimum뿐 아니라 local maximum과 saddle point에서도 성립할 수 있으므로 충분조건이 아니다.

Second-order necessary condition

$f$가 $x^\star$에서 두 번 미분 가능하고 $x^\star$가 local minimizer이면

\[\nabla f(x^\star)=0, \qquad d^T\nabla^2 f(x^\star)d\geq0 \quad \text{for every }d,\]

즉 $\nabla^2 f(x^\star)\succeq0$이다.

Derivation. Stationarity를 Taylor expansion에 대입하면

\[f(x^\star+td)-f(x^\star) = \frac{t^2}{2}d^T\nabla^2 f(x^\star)d + o(t^2).\]

어떤 $d$에서 quadratic term이 음수라면 충분히 작은 $t\neq0$에 대해 objective가 감소하므로 local minimality와 모순이다.

Second-order sufficient condition

$x^\star$가 stationary point이고

\[\nabla^2 f(x^\star)\succ0\]

이면 $x^\star$는 strict local minimizer이다. 실제로 positive definiteness와 Hessian의 연속성에 의해 어떤 $c>0$와 $x^\star$의 neighborhood가 존재하여

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

가 충분히 작은 $d$에 대해 성립한다.

Hessian이 indefinite이면 stationary point는 local minimizer가 아니다. Hessian이 positive semidefinite이지만 singular이면 second-order test만으로는 판정할 수 없으며 higher-order term 또는 다른 분석이 필요하다.


Equality-Constrained Optimality

Equality-constrained problem

\[\begin{aligned} \underset{x}{\operatorname{minimize}}\quad & f(x) \\ \text{subject to}\quad & h(x)=0 \end{aligned}\]

을 생각하자. Jacobian을

\[J_h(x) = \begin{bmatrix} \nabla h_1(x)^T\\ \vdots\\ \nabla h_p(x)^T \end{bmatrix}\]

로 둔다. $x^\star$에서 constraint gradient가 linearly independent라면

\[\operatorname{rank}J_h(x^\star)=p\]

이고, 이 점을 regular point라 한다. First-order feasible direction은

\[\mathcal{T}(x^\star) = \left\{ d:J_h(x^\star)d=0 \right\}\]

에 속한다. 이는 equality surface의 tangent space이다.

$x^\star$가 regular local minimizer이면 모든 tangent direction $d$에 대해

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

이어야 한다. 따라서 $\nabla f(x^\star)$는 tangent space에 직교하고, constraint gradient의 span에 속한다. 즉 어떤 $v^\star\in\mathbb{R}^p$가 존재하여

\[\nabla f(x^\star) + J_h(x^\star)^T v^\star =0\]

가 성립한다. Equality multiplier $v_j^\star$의 부호에는 제한이 없다.

Lagrangian을

\[L(x,v) = f(x) + \sum_{j=1}^{p}v_jh_j(x)\]

로 정의하면 first-order necessary condition은

\[\nabla_x L(x^\star,v^\star)=0, \qquad h(x^\star)=0\]

로 간단히 쓸 수 있다. 이 조건은 feasible set 위의 stationary point를 찾지만, 그 점이 minimum인지 maximum인지까지 판정하지는 않는다.


Inequality Constraints and Feasible Directions

Inequality $g_i(x)\leq0$가 $x^\star$에서 inactive이면 충분히 작은 움직임에 대해 계속 만족되므로 first-order geometry에 나타나지 않는다. 반면 $i\in\mathcal{A}(x^\star)$이면 feasible direction은

\[\nabla g_i(x^\star)^T d\leq0\]

를 만족해야 한다. 따라서 linearized feasible cone은

\[\mathcal{L}(x^\star) = \left\{ d: J_h(x^\star)d=0, \ \nabla g_i(x^\star)^Td\leq0 \ \text{for }i\in\mathcal{A}(x^\star) \right\}\]

이다.

적절한 constraint qualification 아래에서는 실제 feasible tangent cone과 linearized cone이 일치한다. Local minimizer에서는 feasible first-order descent direction이 존재할 수 없으므로

\[\nabla f(x^\star)^T d\geq0 \qquad \text{for every }d\in\mathcal{L}(x^\star)\]

이어야 한다. 이 기하학적 조건의 multiplier 표현이 KKT condition이다.


KKT First-Order Necessary Conditions

General constrained problem의 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)\]

로 정의한다. $x^\star$가 local minimizer이고 적절한 constraint qualification이 성립하면, 다음 조건을 만족하는 multiplier $u^\star$와 $v^\star$가 존재한다.

1. Primal feasibility

\[h_j(x^\star)=0, \qquad g_i(x^\star)\leq0.\]

2. Stationarity

\[\nabla f(x^\star) + \sum_{i=1}^{m}u_i^\star\nabla g_i(x^\star) + \sum_{j=1}^{p}v_j^\star\nabla h_j(x^\star) =0.\]

3. Dual feasibility

\[u_i^\star\geq0, \qquad i=1,\ldots,m.\]

4. Complementary slackness

\[u_i^\star g_i(x^\star)=0, \qquad i=1,\ldots,m.\]

Complementary slackness에 의해 inactive constraint는 $u_i^\star=0$을 가져야 한다. Active constraint는 $u_i^\star>0$일 수도 있고 $u_i^\star=0$일 수도 있다. 후자의 경우를 weakly active constraint라 한다.

Stationarity는 기하학적으로

\[-\nabla f(x^\star) = \sum_{i\in\mathcal{A}(x^\star)}u_i^\star\nabla g_i(x^\star) + \sum_{j=1}^{p}v_j^\star\nabla h_j(x^\star)\]

를 뜻한다. 즉 objective를 가장 빠르게 감소시키는 방향이 active constraint의 outward normal과 equality normal의 선형결합으로 상쇄된다. Inequality normal의 coefficient가 nonnegative인 이유는 feasible region의 한쪽 방향만 제한하기 때문이다.

KKT condition은 일반 nonlinear problem에서 necessary condition일 뿐이다. KKT point는 local minimum, local maximum, saddle-type constrained stationary point가 될 수 있다. 또한 constraint qualification이 실패하면 local minimizer가 KKT condition을 만족하지 않거나 multiplier가 유일하지 않을 수 있다.


Active-Set Interpretation

KKT system은 어떤 inequality가 optimum에서 active인지 모르는 상태에서 equality-constrained stationarity를 찾는 문제로 해석할 수 있다.

  1. Candidate active set $\mathcal{A}$를 선택한다.
  2. $g_i(x)=0$ for $i\in\mathcal{A}$와 $h(x)=0$을 equality로 취급한다.
  3. Stationarity equation으로 $x$, $u_{\mathcal{A}}$, $v$를 계산한다.
  4. 모든 inactive inequality의 feasibility와 $u_{\mathcal{A}}\geq0$을 확인한다.

$m$개의 inequality에 대해 가능한 active set은 최대 $2^m$개이므로, 모든 조합을 직접 조사하는 방식은 큰 문제에 적합하지 않다. 그러나 이 구조는 active-set method, SQP, interior-point method가 어떤 조건을 근사적으로 만족시키는지 이해하는 기초가 된다.


Sensitivity Meaning of Lagrange Multipliers

Constraint limit이 변하는 perturbed problem을 생각하자.

\[\begin{aligned} \underset{x}{\operatorname{minimize}}\quad & f(x) \\ \text{subject to}\quad & h_j(x)=b_j, \\ & g_i(x)\leq e_i. \end{aligned}\]

Optimal value를 $f^\star(b,e)$라 하자. 해가 isolated regular local minimizer이고 active set이 안정적으로 유지되는 등 sensitivity theorem의 가정이 성립하면

\[\left. \frac{\partial f^\star}{\partial b_j} \right|_{(0,0)} = -v_j^\star, \qquad \left. \frac{\partial f^\star}{\partial e_i} \right|_{(0,0)} = -u_i^\star.\]

따라서 작은 perturbation에 대한 optimal value의 first-order 변화는

\[\Delta f^\star \approx -\sum_{j=1}^{p}v_j^\star b_j -\sum_{i=1}^{m}u_i^\star e_i\]

이다. $g_i(x)\leq e_i$에서 $e_i>0$은 constraint relaxation을 뜻한다. 그러므로 $u_i^\star$가 클수록 해당 constraint를 완화했을 때 얻을 수 있는 objective 개선의 first-order magnitude가 크다. 이 때문에 multiplier를 shadow price 또는 constraint force로 해석한다.

Multiplier의 수치는 formulation의 scale에 의존한다.

  • Objective를 $Kf$로 바꾸면 $K>0$에 대해 multiplier도 $K$배 된다.
  • Constraint를 $M g_i(x)\leq0$로 바꾸면 $M>0$에 대해 해당 multiplier는 $1/M$배 된다.
  • 따라서 multiplier의 크기는 objective와 constraint의 단위 및 scaling을 함께 고려해 해석해야 한다.


Convexity and Global Optimality

다음 조건을 만족하면 problem은 convex programming problem이다.

  • $f$가 convex이다.
  • 모든 inequality function $g_i$가 convex이다.
  • 모든 equality function $h_j$가 affine이다.

이때 feasible set은 convex이며 모든 local minimizer는 global minimizer이다. 특히 KKT condition을 만족하는 feasible point는 global minimizer이다.

Proof of KKT sufficiency. $x$를 임의의 feasible point라 하자. Convexity of $f$에 의해

\[f(x) \geq f(x^\star) + \nabla f(x^\star)^T(x-x^\star).\]

Affine equality에 대해서는

\[\nabla h_j(x^\star)^T(x-x^\star)=0\]

이고, convex inequality에 대해서는

\[\nabla g_i(x^\star)^T(x-x^\star) \leq g_i(x)-g_i(x^\star).\]

Stationarity, dual feasibility, complementary slackness를 사용하면

\[\begin{aligned} \nabla f(x^\star)^T(x-x^\star) &= -\sum_i u_i^\star \nabla g_i(x^\star)^T(x-x^\star) \\ &\geq -\sum_i u_i^\star \left(g_i(x)-g_i(x^\star)\right) \\ &\geq0. \end{aligned}\]

따라서 $f(x)\geq f(x^\star)$이고 $x^\star$는 global minimizer이다. $f$가 feasible set 위에서 strictly convex이면 global minimizer는 유일하다.

반대로 KKT condition이 convex problem에서 necessary이기 위해서는 Slater condition과 같은 적절한 constraint qualification이 추가로 필요하다. Convexity test를 통과하지 못했다는 사실은 problem이 nonconvex임을 증명하는 경우도 있지만, 단지 사용한 함수 표현으로 feasible set의 convexity를 인증하지 못했다는 뜻일 수도 있다. 서로 동등한 constraint transformation이 feasible set은 보존하면서 함수의 Hessian과 multiplier를 바꿀 수 있기 때문이다.


Summary of Optimality Tests

Problem Conditions at $x^\star$ Conclusion
Unconstrained $\nabla f(x^\star)=0$ First-order necessary
Unconstrained $\nabla f(x^\star)=0$, $\nabla^2f(x^\star)\succeq0$ Second-order necessary
Unconstrained $\nabla f(x^\star)=0$, $\nabla^2f(x^\star)\succ0$ Strict local minimum
Equality-constrained Feasibility and $\nabla_xL(x^\star,v^\star)=0$ under regularity First-order necessary
General constrained Primal feasibility, stationarity, dual feasibility, complementarity under a constraint qualification KKT first-order necessary
Convex programming A feasible KKT point Global minimum
Strictly convex objective on a convex feasible set A feasible KKT point Unique global minimum

Optimality analysis에서는 항상 세 질문을 분리해야 한다. 첫째, 해가 존재하는가. 둘째, candidate point가 necessary condition을 만족하는가. 셋째, sufficient condition 또는 convexity를 통해 그 candidate가 실제 local 또는 global minimum임을 보일 수 있는가.


Summary

  • Unconstrained optimum에서는 gradient가 zero여야 하며, Hessian의 definiteness가 stationary point의 국소적 성질을 결정한다.
  • Equality constraint는 feasible direction을 tangent space로 제한하며, Lagrange multiplier는 objective gradient와 constraint normal의 평형을 나타낸다.
  • General constrained problem의 first-order structure는 primal feasibility, stationarity, dual feasibility, complementary slackness로 구성된다.
  • KKT condition은 일반적으로 necessary condition이므로, sufficient condition이나 convexity 없이 minimum을 보장하지 않는다.
  • Lagrange multiplier는 constraint limit 변화에 대한 optimal value의 first-order sensitivity를 나타낸다.
  • Convex problem에서는 feasible KKT point가 global minimizer이며, strict convexity는 해의 유일성을 보장한다.