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.0

password para jupyterlab: qwerty

Detener el contenedor de docker:

docker stop jupyterlab_numerical

Documentación de la imagen de docker palmoreck/jupyterlab_numerical:1.1.0 en liga.


Nota generada a partir de liga1, liga2.


In [1]:
!pip3 install --user -q cvxpy


  WARNING: The scripts futurize and pasteurize are installed in '/home/miuser/.local/bin' which is not on PATH.
  Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.
WARNING: You are using pip version 19.3.1; however, version 20.1.1 is available.
You should consider upgrading via the 'pip install --upgrade pip' command.

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 utils import compute_error

from algorithms_for_cieco import path_following_method_feasible_init_point

Primer ejemplo

$$ \min \quad x_1^2 + x_2^2 + x_3^2 + x_4^2 -2x_1-3x_4$$
$$\text{sujeto a: } $$
$$ \begin{array}{c} 2x_1 + x_2 + x_3 + 4x_4 = 7 \\ x_1 + x_2 + 2x_3 + x_4 = 6 \end{array} $$
$$x_1, x_2, x_3, x_4 \geq 0$$

In [6]:
fo = lambda x: x[0]**2 + x[1]**2 + x[2]**2 + x[3]**2-2*x[0]-3*x[3]

In [7]:
const = {0: lambda x: -x[0],
         1: lambda x: -x[1],
         2: lambda x: -x[2],
         3: lambda x: -x[3]
        }

In [8]:
A= np.array([[2,1,1,4],
             [1,1,2,1]])

In [9]:
b=np.array([7,6])

In [10]:
x_ast=np.array([1.1232876712328763,0.6506849315068493,
                1.8287671232876714,0.5684931506849317])

In [11]:
x_0 = np.array([8.082191780821915e-01,
                8.767123287671235e-01,
                1.821917808219178e+00,
                6.712328767123281e-01])

In [12]:
x_0


Out[12]:
array([0.80821918, 0.87671233, 1.82191781, 0.67123288])

In [13]:
p_ast=fo(x_ast)

In [14]:
p_ast


Out[14]:
1.4006849315068495

In [15]:
tol_outer_iter = 1e-6
tol=1e-8
tol_backtracking=1e-12
maxiter=30
mu=10

In [16]:
[x,iter_barrier,t] = path_following_method_feasible_init_point(fo, A, const,
                                                               x_0, tol,
                                                               tol_backtracking, x_ast, p_ast, maxiter,
                                                               mu, tol_outer_iter = tol_outer_iter 
                                                               )


Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
1		3.87e+01	2.49e+01	1.61e-01
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+02		7.74e+00	1.73e-01	1.15e-01	---		1.04e+00
1		1.09e+02		3.10e-04	7.71e-03	2.27e-04	1.00e+00	1.04e+00
2		1.09e+02		3.10e-04	7.71e-03	2.27e-04	2.27e-13	1.04e+00
Error of x with respect to x_ast: 7.71e-03
Approximate solution: [1.11865825 0.66695832 1.8231155  0.56815242]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[1.11865825 0.66695832 1.8231155  0.56815242]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
2		3.48e+02	2.49e+02	1.61e-02
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+03		7.97e+01	1.73e-01	1.15e-01	---		1.00e+00
1		1.09e+03		9.56e-05	8.05e-04	2.48e-06	1.00e+00	1.00e+00
2		1.09e+03		9.56e-05	8.05e-04	2.48e-06	5.82e-11	1.00e+00
3		1.09e+03		9.56e-05	8.05e-04	2.48e-06	4.66e-10	1.00e+00
4		1.09e+03		9.56e-05	8.05e-04	2.48e-06	9.09e-13	1.00e+00
Error of x with respect to x_ast: 8.05e-04
Approximate solution: [1.12264501 0.65235043 1.82823695 0.56853065]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[1.12264501 0.65235043 1.82823695 0.56853065]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
3		3.48e+03	2.49e+03	1.61e-03
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+04		7.99e+02	1.73e-01	1.15e-01	---		1.00e+00
1		1.09e+04		2.59e-04	1.28e-04	6.26e-08	1.00e+00	1.00e+00
2		1.09e+04		9.42e-12	8.44e-05	2.72e-08	1.00e+00	1.00e+00
Error of x with respect to x_ast: 8.44e-05
Approximate solution: [1.12325838 0.65086494 1.82869835 0.56847999]
Inner iterations
[1.12325838 0.65086494 1.82869835 0.56847999]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
4		3.48e+04	2.49e+04	1.61e-04
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+05		8.00e+03	1.73e-01	1.15e-01	---		1.00e+00
1		1.09e+05		2.18e-03	9.11e-05	3.17e-08	1.00e+00	1.00e+00
2		1.09e+05		4.72e-10	8.40e-06	2.70e-10	1.00e+00	1.00e+00
Error of x with respect to x_ast: 8.40e-06
Approximate solution: [1.12328471 0.65070284 1.82876029 0.56849186]
Inner iterations
[1.12328471 0.65070284 1.82876029 0.56849186]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
5		3.48e+05	2.49e+05	1.61e-05
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+06		8.00e+04	1.73e-01	1.15e-01	---		1.00e+00
1		1.09e+06		2.14e-02	8.97e-05	3.07e-08	1.00e+00	1.00e+00
2		1.09e+06		3.90e-10	8.33e-07	2.65e-12	1.00e+00	1.00e+00
Error of x with respect to x_ast: 8.33e-07
Approximate solution: [1.12328736 0.65068671 1.82876645 0.56849303]
Inner iterations
[1.12328736 0.65068671 1.82876645 0.56849303]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
6		3.48e+06	2.49e+06	1.61e-06
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.09e+07		8.00e+05	1.73e-01	1.15e-01	---		1.00e+00
1		1.09e+07		2.13e-01	8.96e-05	3.07e-08	1.00e+00	1.00e+00
2		1.09e+07		2.78e-08	1.14e-07	5.26e-14	1.00e+00	1.00e+00
3		1.09e+07		1.54e-08	9.03e-08	3.65e-14	1.00e+00	1.00e+00
Error of x with respect to x_ast: 9.03e-08
Approximate solution: [1.12328763 0.65068512 1.82876705 0.56849314]
Inner iterations
[1.12328763 0.65068512 1.82876705 0.56849314]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
7		3.48e+07	2.49e+07	1.61e-07
----------------------------------------------------------------------------------------

In [17]:
[x,iter_barrier,t]


Out[17]:
[array([1.12328763, 0.65068512, 1.82876705, 0.56849314]),
 174,
 24851063.829786982]

In [18]:
compute_error(x_ast,x)


Out[18]:
9.029491544987291e-08

Comparación con cvxpy


In [19]:
import cvxpy as cp

In [20]:
x1 = cp.Variable()
x2 = cp.Variable()
x3 = cp.Variable()
x4 = cp.Variable()

In [21]:
# Create two constraints.
constraints = [2*x1+x2+x3+4*x4-7 == 0,x1+x2+2*x3+x4-6 == 0,x1>=0,x2>=0,x3>=0,x4>=0]

# Form objective.

obj = cp.Minimize(x1**2+x2**2+x3**2+x4**2-2*x1-3*x4)

In [22]:
# Form and solve problem.
prob = cp.Problem(obj, constraints)
prob.solve()  # Returns the optimal value.


Out[22]:
1.4006849315068515

In [23]:
print("status:", prob.status)
print("optimal value", prob.value)
print("optimal var", x1.value, x2.value, x3.value,x4.value)


status: optimal
optimal value 1.4006849315068515
optimal var 1.1232876712328763 0.6506849315068494 1.8287671232876717 0.5684931506849316

Segundo ejemplo

$$\min 2x_1 + 5x_2$$
$$\text{sujeto a: }$$
$$ \begin{array}{c} 6-x_1-x_2 \leq 0 \\ -18 + x_1 +2x_2 \leq 0\\ x_1, x_2 \geq 0 \end{array} $$

In [24]:
fo = lambda x: 2*x[0] + 5*x[1]

In [25]:
const = {0: lambda x: 6-x[0]-x[1],
         1: lambda x: -18+x[0]+2*x[1],
         2: lambda x: -x[0],
         3: lambda x: -x[1]
        }

In [26]:
A=np.array([0,0],dtype=float)
b = 0

In [27]:
x_ast = np.array([6,0], dtype=float)

In [28]:
x_0 = np.array([4,4], dtype=float)

In [29]:
p_ast=fo(x_ast)

In [30]:
p_ast


Out[30]:
12.0

In [31]:
tol_outer_iter = 1e-3
tol=1e-8
tol_backtracking=1e-12
maxiter=30
mu=10

In [32]:
[x,iter_barrier,t] = path_following_method_feasible_init_point(fo, A, const,
                                                               x_0, tol,
                                                               tol_backtracking, x_ast, p_ast, maxiter,
                                                               mu, tol_outer_iter=tol_outer_iter
                                                               )


Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
1		1.23e+01	2.50e-01	1.60e+01
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		8.37e-01		5.59e+00	7.45e-01	1.33e+00	---		9.46e+00
1		8.37e-01		2.61e-02	2.15e-01	5.37e-01	5.00e-01	9.46e+00
2		8.37e-01		2.61e-02	2.15e-01	5.37e-01	1.78e-15	9.46e+00
Error of x with respect to x_ast: 2.15e-01
Approximate solution: [6.88318309 0.93672033]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[6.88318309 0.93672033]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
2		5.08e+01	2.50e+00	1.60e+00
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.29e+01		5.12e+02	7.45e-01	1.33e+00	---		1.00e+01
1		1.29e+01		1.82e+01	1.05e-01	2.66e-01	6.25e-02	1.00e+01
2		1.29e+01		1.39e-01	2.70e-02	6.48e-02	2.50e-01	1.00e+01
3		1.29e+01		9.73e-03	2.30e-02	6.15e-02	1.00e+00	1.00e+01
4		1.29e+01		9.73e-03	2.30e-02	6.15e-02	7.11e-15	1.00e+01
Error of x with respect to x_ast: 2.30e-02
Approximate solution: [6.06671215 0.120975  ]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[6.06671215 0.120975  ]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
3		3.19e+02	2.50e+01	1.60e-01
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.34e+02		8.98e+04	7.45e-01	1.33e+00	---		3.29e+01
1		1.34e+02		2.34e+04	2.79e-01	7.50e-01	1.95e-03	3.29e+01
2		1.34e+02		9.87e+03	1.84e-01	4.43e-01	3.91e-03	3.29e+01
3		1.34e+02		1.42e+03	7.07e-02	1.83e-01	7.81e-03	3.29e+01
4		1.34e+02		4.19e+01	2.22e-02	2.94e-02	3.12e-02	3.29e+01
5		1.34e+02		2.72e-01	3.45e-03	9.07e-03	1.25e-01	3.29e+01
6		1.34e+02		4.23e-02	2.14e-03	5.76e-03	1.00e+00	3.29e+01
7		1.34e+02		4.23e-02	2.14e-03	5.76e-03	1.14e-13	3.29e+01
Error of x with respect to x_ast: 2.14e-03
Approximate solution: [6.00409637 0.01217541]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[6.00409637 0.01217541]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
4		3.01e+03	2.50e+02	1.60e-02
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.35e+03		3.48e+06	7.45e-01	1.33e+00	---		1.24e+00
1		1.35e+03		-3.78e+05	5.92e-01	7.67e-01	4.88e-04	1.24e+00
Error of x with respect to x_ast: 5.92e-01
Approximate solution: [3.74466343 2.74382753]
Inner iterations
[3.74466343 2.74382753]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
5		5.30e+04	2.50e+03	1.60e-03
----------------------------------------------------------------------------------------
I	Norm gfLogBarrier 	Newton Decrement	Error x_ast	Error p_ast	line search	CondHf
0		1.35e+04		3.67e+08	7.45e-01	1.33e+00	---		1.97e+01
1		1.35e+04		2.04e+08	5.01e-01	5.87e-01	6.10e-05	1.97e+01
2		1.35e+04		1.86e+07	1.14e-01	1.71e-01	6.10e-05	1.97e+01
3		1.35e+04		4.90e+06	5.01e-02	9.54e-02	1.22e-04	1.97e+01
4		1.35e+04		1.46e+06	2.29e-02	5.54e-02	2.44e-04	1.97e+01
5		1.35e+04		4.54e+05	1.18e-02	3.17e-02	4.88e-04	1.97e+01
6		1.35e+04		3.91e+03	2.11e-03	2.13e-03	1.95e-03	1.97e+01
7		1.35e+04		7.20e-01	4.35e-05	6.02e-05	1.56e-02	1.97e+01
8		1.35e+04		2.85e-01	1.78e-05	4.27e-05	1.00e+00	1.97e+01
9		1.35e+04		2.85e-01	1.78e-05	4.27e-05	1.82e-12	1.97e+01
10		1.35e+04		2.85e-01	1.78e-05	4.27e-05	9.09e-13	1.97e+01
Error of x with respect to x_ast: 1.78e-05
Approximate solution: [6.00008070e+00 7.00989697e-05]
Backtracking value less than tol_backtracking, check approximation
Inner iterations
[6.00008070e+00 7.00989697e-05]
----------------------------------------------------------------------------------------
Outer iterations of path following method
Mu value: 1.00e+01
Outer iteration	LogBarrier 	t_log_barrier	Stopping criteria
6		3.00e+05	2.50e+04	1.60e-04
----------------------------------------------------------------------------------------
/datos/MNO_desde_2018/ramas_repo/mno-master/temas/IV.optimizacion_convexa_y_machine_learning/algoritmos/Python/utils.py:55: RuntimeWarning: invalid value encountered in log
  eval_f_const_inequality = np.log(-eval_f_const_inequality)

In [33]:
[x,iter_barrier,t]


Out[33]:
[array([6.00008070e+00, 7.00989697e-05]), 106, 25000.0]

In [34]:
compute_error(x_ast,x)


Out[34]:
1.7815100934694886e-05

Comparación con cvxpy


In [35]:
x1 = cp.Variable()
x2 = cp.Variable()

In [36]:
# Create two constraints.
constraints = [6-x1-x2 <= 0,-18+x1+2*x2<=0,x1>=0,x2>=0]

# Form objective.

obj = cp.Minimize(2*x1+5*x2)

In [37]:
# Form and solve problem.
prob = cp.Problem(obj, constraints)
prob.solve()  # Returns the optimal value.


Out[37]:
12.0000000016275

In [38]:
print("status:", prob.status)
print("optimal value", prob.value)
print("optimal var", x1.value, x2.value)


status: optimal
optimal value 12.0000000016275
optimal var 6.000000000175689 2.552244387851183e-10

Referencias:

  • S. P. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2009.