<jupyter_start><jupyter_text>**Notas para contenedor de docker:** Comando de docker para ejecución de la nota de forma local:nota: cambiar `` por la ruta de directorio que se desea mapear a `/datos` dentro del contenedor de docker.```docker run --rm -v :/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0```password para jupyterlab: `<PASSWORD>`Detener el contenedor de docker:```docker stop jupyterlab_numerical``` Documentación de la imagen de docker `palmoreck/jupyterlab_numerical:1.1.0` en [liga](https://github.com/palmoreck/dockerfiles/tree/master/jupyterlab/numerical). --- Nota generada a partir de [liga1](https://drive.google.com/file/d/1zCIHNAxe5Shc36Qo0XjehHgwrafKSJ_t/view), [liga2](https://drive.google.com/file/d/12L7rOCgW7NEKl_xJbIGZz05XXVrOaPBz/view). **Dando click en: [![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/palmoreck/dockerfiles-for-binder/jupyterlab_numerical?urlpath=lab/tree/analisis-numerico-computo-cientifico/temas/IV.optimizacion_convexa_y_machine_learning/4.4.Metodo_de_Newton_para_puntos_iniciales_no_factibles_Python.ipynb) se ejecuta la nota de forma interactiva**.<jupyter_code>!pip3 install --user -q cvxpy
import os
cur_directory = os.getcwd()
dir_alg_python = '/algoritmos/Python'
os.chdir(cur_directory + dir_alg_python)
import math

import numpy as np

from algorithms_for_ceco import Newtons_method_feasible_init_point, \
                                Newtons_method_infeasible_init_point, \
                                Newtons_method_infeasible_init_point_2nd_version
from line_search import line_search_for_residual_by_backtracking
from utils import compute_error<jupyter_output><empty_output><jupyter_text>Primer ejemplo $$\displaystyle \min_{x \in \mathbb{R}^2} \quad x_1^2 + 2x_1x_2 + x_2^2-2x_2$$ $$\text{sujeto a: } x_1 = 0$$<jupyter_code>fo = lambda x: x[0]**2 + 2*x[0]*x[1]+x[1]**2-2*x[1]
A = np.array([1,0],dtype=float)
b = np.array([0])
x_ast=np.array([0,1], dtype=float)<jupyter_output><empty_output><jupyter_text>En el siguiente ejemplo si usamos el algoritmo anterior para punto inicial no factible ($Ax^{(0)} \neq b$) obsérvese que no funciona<jupyter_code>x_0 = np.array([1,-2],dtype=float)
tol=1e-8
tol_backtracking=1e-14
maxiter=50
p_ast=fo(x_ast)
[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_feasible_init_point(fo,A, x_0,tol, 
                                                       tol_backtracking, x_ast, p_ast, maxiter)
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Error relativo muy alto**  Método de Newton para puntos iniciales no factibles  Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([1,-2], dtype=float)
nu_0 = 5<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast, maxiter
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast, maxiter
                                                                     )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>Segundo ejemplo $$\displaystyle \min_{x \in \mathbb{R}^2} \quad \frac{1}{2}(x_1^2 + x_2^2)$$ $$\text{sujeto a: } 2x_1 -x_2 = 5$$<jupyter_code>fo = lambda x: 1/2*(x[0]**2  + x[1]**2)
A = np.array([2,-1],dtype=float)
b=5
x_ast = np.array([2,-1],dtype=float)<jupyter_output><empty_output><jupyter_text>Método de Newton para puntos iniciales no factibles  Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([1,1],dtype=float)
nu_0 = 4<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast, maxiter
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast, maxiter
                                                                     )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>Tercer ejemplo $$\displaystyle \min_{x \in \mathbb{R}^2} \quad x_1^2 + x_2^2$$ $$\text{sujeto a :} x_1+x_2 = 1$$<jupyter_code>fo = lambda x: x[0]**2+x[1]**2
x_ast = np.array([.5,.5],dtype=float)
A = np.array([1,1],dtype=float)
b=1<jupyter_output><empty_output><jupyter_text>Método de Newton para puntos iniciales no factibles  Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([1,1],dtype=float)
nu_0 = 4<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast, maxiter
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast, maxiter
                                                                     )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>Cuarto ejemplo $$\displaystyle \min_{x \in \mathbb{R}^2} \quad e^{x_1+3x_2-0.1} + e^{x_1 -3x_2-0.1} + e^{-x_1-0.1}$$ $$\text{sujeto a:} x_1 + 3x_2 = 0$$<jupyter_code>fo = lambda x: math.exp(x[0] + 3*x[1]-0.1) + math.exp(x[0]  -3*x[1]-0.1) + math.exp(-x[0]-0.1)
x_ast = np.array([-0.23104907880100917,0.0770163596518852],dtype=float)
A = np.array([1,3],dtype=float)
b=0<jupyter_output><empty_output><jupyter_text>Método de Newton para puntos iniciales no factibles  Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([1,1],dtype=float) #with 1,1 doesn't work
nu_0 = 1<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast,maxiter
                                                        )<jupyter_output>I	||res_primal||	||res_dual|| 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0	4.00e+00	1.59e+02	1.97e+02	6.32e+00	5.09e+01	---		6.62e+02
1	4.00e+00	1.59e+02	1.97e+02	6.32e+00	5.09e+01	2.78e-17	6.62e+02
Backtracking value less than tol_backtracking, try other initial point<jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast,maxiter
                                                                     )<jupyter_output>I	||res_primal||	||res_dual|| 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0	4.00e+00	1.59e+02	1.97e+02	6.32e+00	5.09e+01	---		6.62e+02
1	4.00e+00	1.59e+02	1.97e+02	6.32e+00	5.09e+01	2.78e-17	6.62e+02
Error of x with respect to x_ast: 6.32e+00
Approximate solution: [1. 1.]
Backtracking value less than tol_backtracking, check approximation<jupyter_text>(Probando el comportamiento con punto inicial factible ($Ax^{(0)} = b$))<jupyter_code>x_0 = np.array([0,0],dtype=float) 
nu_0 = 1<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast,maxiter
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast,maxiter
                                                                     )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([-.1,.1],dtype=float) 
nu_0 = 1<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast,maxiter
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot]= Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                    tol_backtracking, x_ast, p_ast,maxiter
                                                                    )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>Quinto ejemplo: con más restricciones de igualdad Resolver: $$\displaystyle \min_{x \in \mathbb{R}^3} \quad ||x||_2^2$$ $$\text{sujeto a: }\begin{array}{l}\begin{array}{c}x_1 + x_2 + x_3 = 1 \\x_1 + x_2 + 2x_3 = 3\end{array}\end{array}$$<jupyter_code>fo = lambda x: x.dot(x)
x_ast = np.array([-0.5,-0.5,2. ], dtype=float)
A = np.array([[1, 1, 1],
              [1, 1, 2]],dtype=float)
b = np.array([1,3])<jupyter_output><empty_output><jupyter_text>Método de Newton para puntos iniciales no factibles  (Probando el comportamiento con un punto inicial factible ($Ax^{(0)} = b$))<jupyter_code>x_0 = np.array([3,-4,2], dtype=float) #Ax_0 = b
#x_0 = np.array([2,-3,2], dtype=float)
nu_0 = np.array([0,0],dtype=float)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast
                                                         )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast
                                                                     )
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Hay que aumentar el número de iteraciones...**  Punto inicial no factible ($Ax^{(0)} \neq b$)<jupyter_code>x_0 = np.array([3,-4,0], dtype=float) #Ax_0 different to b
#x_0 = np.array([2,-3,1], dtype=float) #Ax_0 different to b
                                       #Compare different versions of
                                       #Newtons method infeasible initial points
nu_0 = np.array([0,0],dtype=float)<jupyter_output><empty_output><jupyter_text>**Versión del método de Newton para puntos iniciales no factibles que se apoya del método de Newton para puntos iniciales factibles**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point(fo, A, b,x_0, nu_0, tol, 
                                                         tol_backtracking, x_ast, p_ast)
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Hay que aumentar el número de iteraciones...** **Versión del método de Newton para puntos iniciales no factibles (2o versión)**<jupyter_code>[x,total_of_iterations,
 Err_plot,x_plot] = Newtons_method_infeasible_init_point_2nd_version(fo, A, b,x_0, nu_0, tol, 
                                                                     tol_backtracking, x_ast, p_ast)
compute_error(x_ast,x)<jupyter_output><empty_output><jupyter_text>**Hay que aumentar el número de iteraciones...**  Comparación del quinto ejemplo con [cvxpy](https://github.com/cvxgrp/cvxpy)<jupyter_code>import cvxpy as cp
x = cp.Variable(3)
A = np.array([[1, 1, 1],
              [1, 1, 2]])
b = np.array([1,3])
obj = cp.Minimize(cp.norm(x,2))

constraints = [A@x == b]
prob = cp.Problem(obj, constraints)
prob.solve()
print("optimal value", prob.value)

print("optimal var", x.value)
A@x.value
np.linalg.norm(x.value)<jupyter_output><empty_output><jupyter_text>Otros puntos iniciales<jupyter_code>vec = [1,-2,2]
A@vec
np.linalg.norm(vec)
vec = [2,-3,2]
A@vec
np.linalg.norm(vec)
vec = [3,-4,2]
A@vec
np.linalg.norm(vec)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11724993111049876, 'fraction_numerical': 0.032791402590245246, 'mean_word_length': 3.099689353290031, 'pattern_counts': {'":': 0, '<': 132, '<?xml version=': 0, '>': 132, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 72, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '33', 'dir': 'jupyter-structured-clean-dedup', 'id': '29286', 'license': 'Apache-2.0', 'n_tokens_mistral': 5481, 'n_tokens_neox': 5222, 'n_words': 992, 'path': 'temas/IV.optimizacion_convexa_y_machine_learning/4.4.Metodo_de_Newton_para_puntos_iniciales_no_factibles_Python.ipynb', 'repo_name': 'Danahirmt/analisis-numerico-computo-cientifico', 'size': '14512'}