In [1]:
import matplotlib.pyplot as pp
import numpy as np
In [2]:
def g( x ):
    
    return np.exp( x )

def f( x ):
    
    return np.sin( x )

x = np.linspace( -4.0, 4.0 )
pp.plot( x, f( x ) )
pp.plot( x, g( f( x ) ) )

pp.show()

Seja $\def\vect{\boldsymbol}$$\vect x^* \in \mathbb R^n$ um minimizador local de $f$, então, existe $\epsilon > 0$ tal que: $$ \|\vect y - \vect x^* \| \leq \epsilon \Rightarrow f( \vect y ) \ge f( \vect x^* ). $$

Mas, como $g$ é crescente, temos $$ f( \vect y ) \ge f( \vect x^* ) \Rightarrow g\bigl( f( \vect y ) \bigr) \ge g\bigl( f( \vect x^* ) \bigr) $$ além disso como $g$ é estritamente crescente, $$ f( \vect y ) > f( \vect x^* ) \Rightarrow g\bigl( f( \vect y ) \bigr) > g\bigl( f( \vect x^* ) \bigr). $$

Portanto: $$ \|\vect y - \vect x^* \| \leq \epsilon \Rightarrow f( \vect y ) \ge f( \vect x^* ) \Leftrightarrow g\bigl( f( \vect y ) \bigr) \ge g\bigl( f( \vect x^* ) \bigr). $$

$$ f( \vect x ) = \| A\vect x- \vect b \| = \sqrt{ \sum_{i = 1}^m\bigl( (A\vect x)_i - b_i \bigr)^2 } $$ $$ F( \vect x ) = \frac12f^2( \vect x ) =\frac12\sum_{i = 1}^m\bigl( (A\vect x)_i - b_i \bigr)^2 $$

$$ \nabla F( \vect x ) = A^T( A\vect x - \vect b ). $$

$$ A^T( A\vect x^* - \vect b ) = \vect 0 \Leftrightarrow A^TA\vect x^* = A^T\vect b. $$

$$ A \in \mathbb R^{m \times n} $$ $$ A^T \in \mathbb R^{n \times m} $$ portanto, $$ A^TA \in \mathbb R^{n \times n} $$

In [3]:
import sympy as sym
In [4]:
def f( x_1, x_2 ):
    
    return ( x_1 ** 3 + x_2 ) ** 2 + 2 * ( x_2 - x_1 - 4 ) ** 4
In [5]:
( x_1, x_2 ) = sym.symbols( 'x_1, x_2' )
print( x_1, x_2 )

x_1 x_2
In [6]:
print( f( x_1, x_2 ).subs( x_1, x_1 + x_2 ).expand().factor( x_2 ) )

x_1**6 + 2*x_1**4 + 32*x_1**3 + 192*x_1**2 + 6*x_1*x_2**5 + 512*x_1 + x_2**6 + x_2**4*(15*x_1**2 + 2) + x_2**3*(20*x_1**3 + 6*x_1) + x_2**2*(15*x_1**4 + 6*x_1**2 + 1) + x_2*(6*x_1**5 + 2*x_1**3) + 512
In [7]:
( l, d_1, d_2 ) = sym.symbols( r'\lambda, d_1, d_2' )
In [8]:
print( f( x_1 + l * d_1, x_2 + l * d_2 ) )

(\lambda*d_2 + x_2 + (\lambda*d_1 + x_1)**3)**2 + 2*(-\lambda*d_1 + \lambda*d_2 - x_1 + x_2 - 4)**4
In [9]:
import IPython
def show_expr( expr ):
    IPython.display.display( IPython.display.Math( sym.latex( expr ) ) )
In [10]:
show_expr( f( x_1 + l * d_1, x_2 + l * d_2 ) )
$$\left(\lambda d_{2} + x_{2} + \left(\lambda d_{1} + x_{1}\right)^{3}\right)^{2} + 2 \left(- \lambda d_{1} + \lambda d_{2} - x_{1} + x_{2} - 4\right)^{4}$$
In [11]:
g = f( x_1 + l * d_1, x_2 + l * d_2 ).subs( x_1, 0 )\
                                     .subs( x_2, 0 )\
                                     .subs( d_1, 1 )\
                                     .subs( d_2, 1 )
show_expr( g.simplify().diff( l, 2 ).subs( l, 0 ) )
$$2$$

$$ \min_{\vect x \in \mathbb R^n} \quad \frac12\| A \vect x - \vect b \|^2 $$ $$ A^TA\vect x = A^T\vect b $$

Seja $A \in \mathbb R^{m \times n}$, então $$ A = U\Sigma V^T, $$ onde $U\in \mathbb R^{m \times m}$ e $V \in \mathbb R^{n \times n}$ são ortonormais e $\sigma \in \mathbb R_+^{m \times n}$ é diagonal.

In [12]:
A = np.array( [ [ 10, 10, 32, 5.47 ], [ 10, 10, 32, 5.47 ], [ 10, 10, 32, 5.47 ] ] )
print( A )

[[10.   10.   32.    5.47]
 [10.   10.   32.    5.47]
 [10.   10.   32.    5.47]]
In [13]:
( U, S, V ) = np.linalg.svd( A, full_matrices = True )
print( U )
print( S )
print( V )

[[-5.77350269e-01 -8.16496581e-01  2.22044605e-16]
 [-5.77350269e-01  4.08248290e-01 -7.07106781e-01]
 [-5.77350269e-01  4.08248290e-01  7.07106781e-01]]
[6.13332104e+01 6.02391913e-15 0.00000000e+00]
[[-0.28240015 -0.28240015 -0.90368049 -0.15447288]
 [ 0.95691309 -0.03004777 -0.28877024 -0.00511986]
 [ 0.05827428 -0.95025412  0.2935168  -0.08642399]
 [-0.03422854 -0.12792339 -0.11756362  0.98419653]]
In [14]:
print( V @ V.T )

[[ 1.00000000e+00  1.23838084e-16 -4.67114000e-17  1.61659634e-17]
 [ 1.23838084e-16  1.00000000e+00 -8.65362637e-18 -5.60905669e-18]
 [-4.67114000e-17 -8.65362637e-18  1.00000000e+00  2.35693104e-18]
 [ 1.61659634e-17 -5.60905669e-18  2.35693104e-18  1.00000000e+00]]

$$ A^TA = ( U\Sigma V^T )^TU\Sigma V^T = V\Sigma^TU^T U\Sigma V^T = V \overline\Sigma V^T $$

$$ A^TA\vect x = A^T\vect b $$ $$ V \overline\Sigma V^T\vect x = V\Sigma^TU^T\vect b $$ $$ V^T V\overline\Sigma V^T\vect x = V^TV\Sigma^TU^T\vect b $$ $$ \overline\Sigma V^T\vect x = \Sigma^TU^T\vect b $$

In [15]:
s1 = np.array( [ [ 1, 0 ], [0, 0], [ 0, 0 ] ] )
print( s1 )
print( s1.T )

[[1 0]
 [0 0]
 [0 0]]
[[1 0 0]
 [0 0 0]]
  1. Calcular $\vect u = \Sigma^T U^T \vect b$
  2. Resolver $\overline\Sigma \vect y = \vect u$ (a solução é dada por componentes: $y_i = u_i / \sigma_i^2$ ou $y_i = 0$ se $\sigma_i = 0$)
  3. Calcular a solução de $V^T\vect x = \vect y$ ou seja, $\vect x = V\vect y$