Skip to main content
MathOverflow

Return to Answer

added 6 characters in body
Source Link
Cristóbal Guzmán
Cristóbal Guzmán
  • 980
  • 5
  • 15

Note that $f(t)=g(A(t))$, where $A(t_1,t_2)=A_0+t_1A_1+t_2A_2$ is affine and $g(B)=\lambda_{min}(B)$ which is concave on $B$. Now, to obtain the supergradient of this function you just need to use the chain rule of convex analysis.

First, it is easy to see that the Jacobian of $A$ is $$ D A(t) = A^{\ast} = [A_1^T;A_2^T]. $$

The maximum eigenvalue $g$ can be described by $$ \lambda_{min}(B) = \min\{u^TBu:\,\, \|u\|_2=1 \}. $$ So its superdifferential is given by the convex hull of rank one matrices given by eigenvectors associated to the minimum eigenvalue, i.e. $$ \partial \lambda_{min}(B) = \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}.$$

Finally, by the chain rule, $$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}\}.$$$$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,A(t)u=\lambda_{min}(A(t)) u \}\}.$$ (the inner product above is the trace inner product) Which is a set of linear operators from $\mathbb{R}^2$ to $\mathbb{R}$, as it should be.

You can derive chain rules for general affine maps: see Hiriart-Urruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).

Note that $f(t)=g(A(t))$, where $A(t_1,t_2)=A_0+t_1A_1+t_2A_2$ is affine and $g(B)=\lambda_{min}(B)$ which is concave on $B$. Now, to obtain the supergradient of this function you just need to use the chain rule of convex analysis.

First, it is easy to see that the Jacobian of $A$ is $$ D A(t) = A^{\ast} = [A_1^T;A_2^T]. $$

The maximum eigenvalue $g$ can be described by $$ \lambda_{min}(B) = \min\{u^TBu:\,\, \|u\|_2=1 \}. $$ So its superdifferential is given by the convex hull of rank one matrices given by eigenvectors associated to the minimum eigenvalue, i.e. $$ \partial \lambda_{min}(B) = \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}.$$

Finally, by the chain rule, $$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}\}.$$ (the inner product above is the trace inner product) Which is a set of linear operators from $\mathbb{R}^2$ to $\mathbb{R}$, as it should be.

You can derive chain rules for general affine maps: see Hiriart-Urruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).

Note that $f(t)=g(A(t))$, where $A(t_1,t_2)=A_0+t_1A_1+t_2A_2$ is affine and $g(B)=\lambda_{min}(B)$ which is concave on $B$. Now, to obtain the supergradient of this function you just need to use the chain rule of convex analysis.

First, it is easy to see that the Jacobian of $A$ is $$ D A(t) = A^{\ast} = [A_1^T;A_2^T]. $$

The maximum eigenvalue $g$ can be described by $$ \lambda_{min}(B) = \min\{u^TBu:\,\, \|u\|_2=1 \}. $$ So its superdifferential is given by the convex hull of rank one matrices given by eigenvectors associated to the minimum eigenvalue, i.e. $$ \partial \lambda_{min}(B) = \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}.$$

Finally, by the chain rule, $$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,A(t)u=\lambda_{min}(A(t)) u \}\}.$$ (the inner product above is the trace inner product) Which is a set of linear operators from $\mathbb{R}^2$ to $\mathbb{R}$, as it should be.

You can derive chain rules for general affine maps: see Hiriart-Urruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).

Source Link
Cristóbal Guzmán
Cristóbal Guzmán
  • 980
  • 5
  • 15

Note that $f(t)=g(A(t))$, where $A(t_1,t_2)=A_0+t_1A_1+t_2A_2$ is affine and $g(B)=\lambda_{min}(B)$ which is concave on $B$. Now, to obtain the supergradient of this function you just need to use the chain rule of convex analysis.

First, it is easy to see that the Jacobian of $A$ is $$ D A(t) = A^{\ast} = [A_1^T;A_2^T]. $$

The maximum eigenvalue $g$ can be described by $$ \lambda_{min}(B) = \min\{u^TBu:\,\, \|u\|_2=1 \}. $$ So its superdifferential is given by the convex hull of rank one matrices given by eigenvectors associated to the minimum eigenvalue, i.e. $$ \partial \lambda_{min}(B) = \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}.$$

Finally, by the chain rule, $$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}\}.$$ (the inner product above is the trace inner product) Which is a set of linear operators from $\mathbb{R}^2$ to $\mathbb{R}$, as it should be.

You can derive chain rules for general affine maps: see Hiriart-Urruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).