\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{ textcomp }
\usepackage{ tipa }

\title{Методы Оптимизации д.з. 1}
\author{Piscenco Margarita, 797}
\date{September 2019}

\usepackage{natbib}
\usepackage{graphicx}
\pagestyle{plain} % нумерация вкл.
\usepackage{amsthm}
\usepackage{amsmath}

\renewcommand\qedsymbol{$\blacksquare$}

\begin{document}
\maketitle

\Large

\section*{\LARGE Задача 1}

\paragraph{
\Large Док-ть,что $Tr(AB) = Tr(BA)\newline $
 Док-во:\newline \large Пусть \Large $  C := AB, D := BA. \newline
Tr(AB) = Tr(C) = \sum ^n_{i = 1} c_{i, i} =  \sum ^n_{i = 1}  \sum ^n_{j = 1} a_{i, j} b_{j, i} =  \sum ^n_{j = 1} \sum ^n_{i = 1} b_{j, i} a_{i, j} =  \sum ^n_{j = 1} d_{j, j} = Tr(D) = Tr(BA)$
}

\section*{\LARGE Задача 2}
\paragraph{\Large Док-ть,что $\forall A \in R^{m*k}, B \in R^{k*n}, C\in R^{m*n} $ \newline
$<AB, C> = <B, A^TC> = <A, CB^T>$\newline
Док-во:\newline
$<AB, C> =  \sum _{i=1}^m \sum _{j=1}^n \{AB\}_{i, j} c_{i,j} =
\sum _{i=1}^m \sum _{j=1}^n \sum _{l=1}^k a_{i,l}  b_{l,j}  c_{i,j}
=   \sum _{l=1}^k \sum _{j=1}^n  b_{l,j}  \sum _{i=1}^m a_{i,l}   c_{i,j} =
\sum _{l=1}^k \sum _{j=1}^n  b_{l,j} \{A^T\}_{l,i}  c_{i,j}= \newline
 \sum _{l=1}^k \sum _{j=1}^n  b_{l,j} \{A^TC\}_{l,j} = <B, A^TC>
 $\newline
 \large Аналогично \Large $<AB, C> = \sum _{l=1}^k \sum _{j=1}^n \sum _{i=1}^m a_{i,l} b_{l,j}   c_{i,j} =  \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \sum_{j=1}^n c_{i,j} b_{l,j} =
 \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \sum_{j=1}^n c_{i,j} B^T_{j,l} =
 \sum _{i=1}^m \sum _{l=1}^k  a_{i,l}  \{ CB^T\}_{i, l}
 $
}
\newpage
\section*{\LARGE Задача 3}
\paragraph{  \Large Пусть $x,y \in R^n$. Док-ть,что $<xx^T, yy^T> = <x, y>^2$\newline
Док-во:\newline
 $<xx^T, yy^T> =$ \newline}
 {<}
 $\begin{pmatrix}
  \ x_{1}\\
  \ ...\\
  \ x_n
\end{pmatrix}
$
$
\begin{pmatrix}
  \ x_{1} &\ ... &\ x_n
\end{pmatrix}
$
{,}
 $\begin{pmatrix}
  \ y_{1}\\
  \ ...\\
  \ y_n
\end{pmatrix}
$
$
\begin{pmatrix}
  \ y_{1} &\ ... &\ y_n
\end{pmatrix}
$
{> = \newline}

{<}
 $\begin{pmatrix}
  \ x_{1}^2 &\ ... &\ x_1 x_n\\
  \ . &\ . &\ . \\
  \ x_n x_1 &\ ...&\ x_n^2
\end{pmatrix}
$
{,}
 $\begin{pmatrix}
  \ y_{1}^2 &\ ... &\ y_1 y_n\\
  \ . &\ . &\ . \\
  \ y_n y_1 &\ ...&\ y_n^2
\end{pmatrix}
$
{> =
$\sum_{i = 1}^n \sum_{j = 1}^n  x_i x_j y_i y_j$}


\paragraph{\Large $<x, y>^2 =  (\sum _{i = 1}^n x_i y_i)^2 = \sum_{i = 1}^n \sum_{j = 1}^n  x_i x_j y_i y_j $
}

\section*{\LARGE Задача 4}
\paragraph{ \Large Док-ть неравенство Коши-Буняковского.\newline
Док-во:\newline
$<x, y> \in R, \forall \lambda \in R $\newline
$0 \leq < \lambda x + y, \lambda x+y > = \newline \lambda^2<x, x> +2\lambda <x, y> + <y, y> => D\leq 0$
$D = 4<x, y>^2 - 4<x, x><y, y> \leq  0 => \newline
|<x, y>| \leq <x, x>^{1/2} <y, y>^{1/2}$ \newline
Равенство при $y = 0$ и $x= \alpha y$ очевидно. Докажем, что в других случаях равенство строгое.\newline
$D = 4<x, y>^2 - 4<x, x><y, y> < 0, \newline
<x, y>^2  < <x, x><y, y> $, что выполняется при заявленных условиях.
}
\newpage
\section*{\LARGE Задача 5}
\paragraph{ \Large Док-ть:\newline
$||x||_{\infty} \leq ||x||_2 \leq \sqrt{n} ||x||_\infty  $\newline
$ \frac{1}{\sqrt{n}}||x||_{1} \leq ||x||_2 \leq ||x||_1 $\newline
Док-во:
}
\begin{multline*}
||x||_{\infty} = max_{1\leq i \leq n}|x_i| \leq |x_{max}|  + (\sum _{i \neq i_{max}} x_i^2)^{1/2} =(\sum _{i=0} ^{n} x_i^2)^{1/2} =  ||x||_2
\\ ||x||_2 = (\sum _{i=0} ^{n} x_i^2)^{1/2} \leq (\sum _{i=0} ^{n} x_{max}^2)^{1/2} =
(n  x_{max}^2)^{1/2}   = \sqrt{n} ||x||_\infty
\\ (\frac{1}{\sqrt{n}}||x||_{1})^2 = \frac{1}{n} (\sum _{i=1}^n |x_i| )^2 =
 \frac{1}{n} <x, (1, ..., 1)^T> \leq^{ CBS \ in-ty }
\\ \leq \frac{1}{n} <x,x> <(1, ..., 1)^T, (1, ..., 1)^T> =
\frac{1}{n}\sum_{i = 1}^n x^2 \sum_{i = 1}^n 1 = \sum_{i = 1}^n x^2  = (||x||_2)^2
\\ ||x||_{1} = \sum _{i=1}^n |x_i| \geq (\sum _{i=0} ^{n} x_i^2)^{1/2} = ||x||_2
\end{multline*}
\section*{\LARGE Задача 6}
\paragraph{ \Large Упростить:\newline
1) $Det(C) \neq 0, Det(C^{-T}X^TC)\neq 0, A, B, C, X \in R^{m*n}$\newline
$Det(A X B( C^{-T} X^{T}C)^{-T}) = Det(A X B( C^TXC^{-1})^{-1}) = Det(A X B C X^{-1}C^{-T}) =
Det(A)Det(X)Det(B)*1/(Det(X)*Det(C)) = Det(A)Det(B)/Det(C)$\newline \newline
2) $||uvT-A||^2_F-||A||^2_F = \sum _{i=1}^m \sum _{j=1}^n (u_i v_j - A_{i,j})^2 - \sum _{i=1}^m \sum _{j=1}^n A_{i,j}^2  = \sum _{i=1}^m \sum _{j=1}^n (u_i^2 v_j^2 -2 A_{i j} u_i v_j)  = (\sum _{i=1}^m u_i^2 * \sum _{j=1}^n  v_j^2)  - 2 \sum _{i=1}^m \sum _{j=1}^n   A_{i,j}u_i^2 v_j^2  = \newline <u, u><v, v> - 2<A, vu^T>$\newline
% $\sum_{i = 1}^n <S^{-1}a_i, a_i> = \sum_{i = 1}^n <a_i, a_i> $
}
\section*{\LARGE Задача 7}
\paragraph{ \Large  Найти $d, d^2$:\newline
1) $A \in R^{n*n} f(t) := Det(A - tI_n) $  \newline
$  d(Det(A - tI_n)) =  Det(A - tI_n) <(A - tI_n)^{-T}, d(A - tI_n)> =
Det(A - tI_n) <(A - tI_n)^{-T}, -I_n dt_1> =  Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_1> \newline \newline
 d^2(Det(A - tI_n)) =  d(Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_1>) =
  d(Det(A - tI_n))  <(A - tI_n)^{-T}, I_n dt_1> + Det(A - tI_n) d( <(A - tI_n)^{-T}, I_n dt_1>) =
  Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> + Det(A - tI_n) <d(A - tI_n)^{-T}, I_n dt_1> =
  Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> + Det(A - tI_n) <(d(A - tI_n)^{-1})^T, I_n dt_1> =
  Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> - Det(A - tI_n) <(-(A - tI_n)^{-1}) (-I_n dt_2)(A - tI_n)^{-1})^{T}, I_n dt_1> =
  Det(A - tI_n) <(A - tI_n)^{-T}, I_n dt_2>  <(A - tI_n)^{-T}, I_n dt_1> + Det(A - tI_n) <(A - tI_n)^{-T} (I_n dt_2)(A - tI_n)^{-T}, I_n dt_1>
 \newline \newline$
 2) $ A \in S^{n}_+, b \in R^n,  f(t) := |(A+tI_n)^{-1}b|^2 \newline
 d(|(A+tI_n)^{-1}b|^2 ) = 2  |(A+tI_n)^{-1}b| * d(|(A+tI_n)^{-1}b| ) =
 2  |(A+tI_n)^{-1}b| * d(\sqrt{<(A+tI_n)^{-1}b, (A+tI_n)^{-1}b>}) =
 2  |(A+tI_n)^{-1}b| * d(\sqrt{<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>}) =
 2  |(A+tI_n)^{-1}b| * 1/2(<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} d(<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>) =
 |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} <d((A+tI_n)^{-T}(A+tI_n)^{-1})b, b> = \newline
 |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} <d((A+tI_n)^{-T}(A+tI_n)^{-1})b, b> =
 |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} <( -(A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} - (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b> = |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b>
 \newline \newline d((A+tI_n)^{-T}(A+tI_n)^{-1}) =
 d((A+tI_n)^{-T})(A+tI_n)^{-1} + (A+tI_n)^{-T}d((A+tI_n)^{-1}) =
 -(A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} - (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1}
$ \newline \newline
 $ d( |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b>) =
d( |(A+tI_n)^{-1}b|) * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2}  < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b> +
|(A+tI_n)^{-1}b| * d((<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2})  < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b> +
|(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} d( < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b>) =
 1/2 * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1} ( < (A+tI_n)^{-T}dt_1(A+tI_n)^{-T} (A+tI_n)^{-1} + (A+tI_n)^{-T}(A+tI_n)^{-1}dt_1(A+tI_n)^{-1} b, b>)^2 +
 |(A+tI_n)^{-1}b| * 1/2(<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-3/2}* <(A+tI_n)^{-T}dt_2(A+tI_n)^{-T} - (A+tI_n)^{-1}dt_2(A+tI_n)^{-1} , b> +
 2 |(A+tI_n)^{-1}b| * (<(A+tI_n)^{-T}(A+tI_n)^{-1}b, b>)^{-1/2} <(((A+tI_n)^{-T})^2dt_1dt_2(A+tI_n)^{-T} + ((A+tI_n)^{-1})^2dt_1dt_2(A+tI_n)^{-1} )b, b>
 \newline \newline
 d((C^{-T})^2) = 2C^{-T}d(C^{-T}) = 2C^{-T}(d(C^{-1}))^T =
 2C^{-T}(-C^{-1} dC C^{-1})^T =  -2C^{-T}C^{-T} dC C^{-T}\newline
 d((C{^-1})^2) =  -2C^{-1}C^{-1} dC C^{-1}
 $
}
\newpage
\section*{\LARGE Задача 8}
\paragraph{ \Large Найти $\nabla f$ и $\nabla^2 f$:\newline
1)
$f = 1/2||xx^T-A ||^2_F, A \in S^n$ \newline
$ f = 1/2||xx^T-A ||^2_F = 1/2 \sum _{i = 1}^n \sum _{j = 1}^n (x_ix_j - a_{i, j}^2) =
\newline
\frac{\partial f}{\partial x_k} = 1/2(2 x_k + 2\sum_{i \neq k} x_i) = x_k + \sum_{i \neq k} x_i = \sum _{i = 1}^n x_i \newline
\nabla f = (\sum _{i = 1}^n x_i, ..., \sum _{i = 1}^n x_i) $\newline
$H(f) = $
}
 \begin{pmatrix}
  \ \frac{\partial^2 f}{\partial x_1^2} &\ ... &\  \frac{\partial^2 f}{\partial x_1 \partial x_n }\\
  \ . &\ . &\ . \\
  \ \frac{\partial^2 f}{\partial x_1x_n} &\ ... &\  \frac{\partial^2 f}{\partial x_n^2 }\\
\end{pmatrix}
\paragraph{\Large $\frac{\partial^2 f}{\partial x_i \partial x_j } = 1 \xrightarrow{} $ $\nabla^2 f = H(f) = J_n$
\newline
2)
$f = \frac{<Ax, x>}{|x|^2}, A \in S^n$ \newline
$f = \frac{<Ax, x>}{|x|^2} = \frac{\sum _{i = 1} ^n \{Ax\}_{i} x_i}{\sum _{i = 1} ^n x_i^2} = \frac{\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j}{\sum _{i = 1} ^n x_i^2}$ \newline
$ \frac{\partial  f}{\partial x_k} = (\frac{\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j}{\sum _{i = 1} ^n x_i^2})|^/_{x_k} =  \{ (\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j)|^/_{x_k} (\sum _{i = 1} ^n x_i^2) - (\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j)(\sum _{i = 1} ^n x_i^2)|^/_{x_k}  \}/(\sum _{i = 1} ^n x_i^2)^2  = \newline
\{ (2 a_{k, k} x_k +\sum _{j\neq k}a_{k, j}x_j) (\sum _{i = 1} ^n x_i^2) - (\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j)(2 x_k)  \}/
(\sum _{i = 1} ^n x_i^2)^2 =:A/B
$\newline
$\frac{\partial^2 f}{\partial x_k \partial x_l } =(A/B)|^/_{x_l} = \{A^/_{x_l}B-AB^/_{x_l}\}/B^2$ \newline
$B^/_{x_l} = 4(\sum _{i = 1} ^n x_i^2)x_l$\newline
если l == k:\newline
$A^/_{x_k} = 2a_{k,k}x_k^2 + 2x_k(2 a_{k, k} x_k +\sum _{j\neq k}a_{k, j}x_j) - 2(\sum _{i = 1} ^n x_i \sum_{j = 1}^n a_{i, j}x_j) - 2x_k(2 a_{k, k} x_k +\sum _{j\neq k}a_{k, j}x_j)
$\newline
иначе:\newline
$A^/_{x_l} = a_{k,l}(\sum _{i = 1} ^n x_i^2) + 2x_l(2 a_{k, k} x_k +\sum _{j\neq k}a_{k, j}x_j) - 2x_k(2 a_{l, l} x_l +\sum _{j\neq l}a_{l, j}x_j)$
}
\paragraph{
\Large 3)$f = <x,x>^{<x,x>}\newline
\frac{\partial  f}{\partial x_k} = <x,x>^{<x,x>}( (<x,x>)^/_{x_k} ln(<x, x>) + <x,x>(ln(<x,x>))^/_{x_k} )\boldsymbol{=}  \newline
(<x,x>)^/_{x_k} = (\sum_{i = 1} ^n x^2)^/_{x_k} = 2x_k \newline
(ln(<x,x>))^/_{x_k}  = (ln(\sum_{i = 1} ^n x^2))^/_{x_k} = 2^n (\sqcap_{i = 1} ^n ln(x_i)) ^/_{x_k}  =  2^n (\sqcap_{i \neq k} ln(x_i)) \newline $
}
\section*{\LARGE Задача 9}
\paragraph{\Large Найти $Df$ и $D^2f$ :\newline
2) $f = <X^{-1}v, v>$ \newline
$d(<X^{-1}v, v>) = <dX^{-1}v, v> = <-X^{-T}dX_2X^{-T}v,v >\newline
d^2f = d(<-X^{-T}dX_2X^{-T}v,v >) =\newline <d(X^{-T}dX_2X^{-T})v,v > > 0, \forall X \in S^n_{++}$\newline \newline
3) $f = (Det(X))^{1/n}$\newline
$d((Det(X))^{1/n}) = 1/n Det(X)^{-\frac{n-1}{n}}d(Det(X)) = 1/n Det(X)^{-\frac{n-1}{n}}Det(X)< X^{-T}, dX_1 > = 1/n Det(X)^{\frac{1}{n}}< X^{-T}, dX_1 >$\newline \newlinelatex

$d^2 f = d(1/n Det(X)^{\frac{1}{n}}< X^{-T}, dX_1 >) =
1/n * d(Det(X)^{\frac{1}{n}})*< X^{-T}, dX_1 > + 1/n *Det(X)^{\frac{1}{n}}*d(< X^{-T}, dX_1 >) =  1/n^2 * Det(X)^{\frac{1}{n}}< X^{-T}, dX_1 > + 1/n* Det(X)^{\frac{1}{n}}*<(dX^{-1})^T, dX_1 > =
1/n^2 * Det(X)^{\frac{1}{n}}< X^{-T}, dX_1 > + 1/n* Det(X)^{\frac{1}{n}}*<-X^{-T}dX_2X^{-T}, dX_1 >$ \newline \newline
\large По условию $X \in S_{++}^n$=> DetX > 0 => D^2f > 0
}
\end{document}