Notas para contenedor de docker:
Comando de docker para ejecución de la nota de forma local:
nota: cambiar <ruta a mi directorio> por la ruta de directorio que se desea mapear a /datos dentro del contenedor de docker.
docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0password para jupyterlab: qwerty
Detener el contenedor de docker:
docker stop jupyterlab_numericalDocumentación de la imagen de docker palmoreck/jupyterlab_numerical:1.1.0 en liga.
In [1]:
!pip3 install --user -q cvxpy
En esta nota se consideran resolver problemas de optimización con restricciones lineales de igualdad de la forma:
$$\min f_o(x)$$con variable de optimización $x \in \mathbb{R}^{n}$ y $A \in \mathbb{R}^{p \times n}, b \in \mathbb{R}^p$ conocidos.
Se asume lo siguiente:
$f:\mathbb{R}^n \rightarrow \mathbb{R}$ convexa y $\mathcal{C}^2(\text{dom}f_o)$.
$rank(A) = p < n$: tenemos menos restricciones que variables y los renglones de $A$ son linealmente independientes.
Existe un punto óptimo $x^*$ por lo que el problema tiene solución y el valor óptimo se denota por $p^* = f_o(x^*) = \inf f_o(x)$.
Los puntos iniciales $x^{(0)}$ de los métodos iterativos están en $\text{dom}f_o$ y los conjuntos $f_o(x^{(0)})$-subnivel son conjuntos cerrados.
Algoritmo de Newton con punto inicial factible para problemas de optimización con restricciones de igualdad lineales
Dados un punto inicial $x$ en $\text{dom}f_o$ con $Ax=b$ y una tolerancia $\epsilon >0$.
Repetir el siguiente bloque para $k=0,1,2,...$
- Calcular la dirección de descenso de Newton $\Delta x_{\text{nt}}$ y el decremento de Newton al cuadrado: $\lambda^2 (x)$.
- Criterio de paro: finalizar el método si $\frac{\lambda^2(x)}{2} \leq \epsilon$.
- Búsqueda de línea. Elegir un tamaño de paso $t > 0$ (usar el cálculo de $\lambda^2 (x)$ del paso anterior).
- Hacer la actualización: $x = x + t\Delta x_{\text{nt}}$.
hasta convergencia (satisfacer criterio de paro).
Se comparan los resultados del paquete cvxpy con los obtenidos en la implementación hecha por el prof en algoritmos/Python, en específico algoritmos/Python/algorithms_for_ceco.py para problemas tipo CECO (Constrained Equality Convex Optimization)
In [1]:
import os
In [2]:
cur_directory = os.getcwd()
In [3]:
dir_alg_python = '/algoritmos/Python'
In [4]:
os.chdir(cur_directory + dir_alg_python)
In [5]:
import math
import numpy as np
from algorithms_for_ceco import Newtons_method_feasible_init_point
from line_search import line_search_for_residual_by_backtracking
from utils import compute_error
In [6]:
fo = lambda x: x[0]**2 + 2*x[0]*x[1]+x[1]**2-2*x[1]
In [7]:
A = np.array([1,0],dtype=float)
In [8]:
b = np.array([0])
In [9]:
x_ast=np.array([0,1], dtype=float)
In [10]:
x_0 = np.array([0,-2],dtype=float)
In [11]:
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)
In [12]:
x
Out[12]:
In [13]:
total_of_iterations
Out[13]:
In [14]:
x_plot.shape
Out[14]:
In [15]:
x_plot
Out[15]:
In [16]:
compute_error(x_ast,x)
Out[16]:
In [17]:
x_0 = np.array([1,-2],dtype=float)
In [18]:
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)
In [19]:
compute_error(x_ast,x)
Out[19]:
Error relativo muy alto
In [20]:
fo = lambda x: 1/2*(x[0]**2 + x[1]**2)
In [21]:
A = np.array([2,-1],dtype=float)
In [22]:
b=5
In [23]:
x_ast = np.array([2,-1],dtype=float)
In [24]:
x_0 = np.array([0,-5],dtype=float)
In [25]:
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)
In [26]:
x
Out[26]:
In [27]:
x_ast
Out[27]:
In [28]:
compute_error(x_ast,x)
Out[28]:
In [29]:
fo = lambda x: x[0]**2+x[1]**2
In [30]:
x_ast = np.array([.5,.5],dtype=float)
In [31]:
A = np.array([1,1],dtype=float)
In [32]:
b=1
In [33]:
x_0 = np.array([2,-1],dtype=float)
In [34]:
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)
In [35]:
compute_error(x_ast,x)
Out[35]:
In [36]:
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)
In [37]:
x_ast = np.array([-0.23104907880100917,0.0770163596518852],dtype=float)
In [38]:
A = np.array([1,3],dtype=float)
In [39]:
b=0
In [40]:
x_0 = np.array([0,0],dtype=float)
In [41]:
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)
In [42]:
compute_error(x_ast, x)
Out[42]:
Resolver: $$\displaystyle \min_{x \in \mathbb{R}^3} \quad ||x||_2^2$$
In [43]:
fo = lambda x: x.dot(x)
In [44]:
x_ast = np.array([-0.5,-0.5,2. ], dtype=float)
In [45]:
A = np.array([[1, 1, 1],
[1, 1, 2]],dtype=float)
In [46]:
b = np.array([1,3])
In [47]:
x_0 = np.array([3,-4,2], dtype=float)
#x_0 = np.array([2,-3,2], dtype=float) #este es otro punto factible
In [48]:
tol=1e-8
tol_backtracking=1e-14
p_ast=fo(x_ast)
In [49]:
[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)
In [50]:
compute_error(x_ast,x)
Out[50]:
In [51]:
import cvxpy as cp
In [52]:
x = cp.Variable(3)
A = np.array([[1, 1, 1],
[1, 1, 2]])
b = np.array([1,3])
In [53]:
obj = cp.Minimize(cp.norm(x,2))
constraints = [A@x == b]
In [54]:
prob = cp.Problem(obj, constraints)
In [55]:
prob.solve()
Out[55]:
In [56]:
print("optimal value", prob.value)
In [57]:
print("optimal var", x.value)
In [58]:
A@x.value
Out[58]:
In [59]:
np.linalg.norm(x.value)
Out[59]:
In [60]:
vec = [1,-2,2]
A@vec
Out[60]:
In [61]:
np.linalg.norm(vec)
Out[61]:
In [62]:
vec = [2,-3,2]
A@vec
Out[62]:
In [63]:
np.linalg.norm(vec)
Out[63]:
In [64]:
vec = [3,-4,2]
A@vec
Out[64]:
In [65]:
np.linalg.norm(vec)
Out[65]:
Referencias: