Nota

Esta página fue generada a partir de docs/tutorials/05_admm_optimizer.ipynb.

Optimizador ADMM#

Introducción#

El optimizador ADMM puede resolver clases de problemas de optimización con restricciones binarias mixtas, en adelante (MBCO, mixed-binary constrained optimization problems), que a menudo aparecen en la investigación de operaciones, finanzas y logística. En particular, el optimizador ADMM diseñado aquí puede abordar el siguiente problema de optimización \((P)\):

\[\min_{x \in \mathcal{X},u\in\mathcal{U} \subseteq \mathbb{R}^l } \quad q(x) + \varphi(u),\]

sujeto a las restricciones:

\[\mathrm{sujeto a.:~} \quad G x = b, \quad g(x) \leq 0, \quad \ell(x, u) \leq 0,\]

con los supuestos funcionales correspondientes.

La función \(q: \mathbb{R}^n \to \mathbb{R}\) es cuadrática, es decir, \(q(x) = x^{\intercal} Q x + a^{\intercal} x\) para una matriz cuadrada simétrica dada \(Q \in \mathbb{R}^n \times \mathbb{R}^n, Q = Q^{\intercal}\), y el vector \(a \in \mathbb{R}^n\);
El conjunto \(\mathcal{X} = \{0,1\}^n = \{x_{(i)} (1-x_{(i)}) = 0, \forall i\}\) impone las restricciones binarias;
La matriz \(G\in\mathbb{R}^n \times \mathbb{R}^{n'}\), el vector \(b \in \mathbb{R}^{n'}\), y la función \(g: \mathbb{R}^n \to \mathbb{R}\) es convexa;
La función \(\varphi: \mathbb{R}^l \to \mathbb{R}\) es convexa y \(\mathcal{U}\) es un conjunto convexo;
La función \(\ell: \mathbb{R}^n\times \mathbb{R}^l \to \mathbb{R}\) es conjuntamente convexa en \(x, u\).

Para resolver problemas MBO, [1] propone heurísticas para \((P)\) basadas en el Método de Multiplicadores de Dirección Alterna (Alternating Direction Method of Multipliers, ADMM) [2]. ADMM es un algoritmo de división de operadores con una larga historia en la optimización convexa, y se sabe que tiene propiedades de convergencia de variables residuales, objetivas y duales, siempre que se cumplan los supuestos de convexidad.

El método de [1] (denominado 3-ADMM-H) aprovecha el procedimiento de división del operador ADMM para diseñar una descomposición de ciertas clases de MBOs en:

un subproblema QUBO que se resolverá en el dispositivo cuántico mediante algoritmos variacionales, como VQE o QAOA;
subproblema restringido convexo continuo, que se puede resolver de manera eficiente con solucionadores clásicos de optimización.

El algoritmo 3-ADMM-H funciona de la siguiente manera:

Fase de inicialización (configurar los parámetros y los solucionadores QUBO y convexos);
Para cada iteración de ADMM (\(k = 1,2,\ldots\)) hasta terminar:
- Resolver un subproblema QUBO correctamente definido (con un solucionador clásico o cuántico);
- Resolver problemas convexos correctamente definidos (con un solucionador clásico);
- Actualizar las variables duales.
Regresar optimizadores y costo.

En [1] se puede encontrar una discusión exhaustiva sobre las condiciones para la convergencia, viabilidad y optimización del algoritmo. Una variante con 2 bloques ADMM, es decir, un subproblema QUBO, y un subproblema restringido convexo continuo, también es introducido en [1].

Referencias#

[1] C. Gambella and A. Simonetto, Multi-block ADMM heuristics for mixed-binary optimization, on classical and quantum computers, arXiv preprint arXiv:2001.02069 (2020).

[2] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine learning, 3, 1–122 (2011).

Inicialización#

En primer lugar cargamos todos los paquetes que necesitamos.

[1]:

import matplotlib.pyplot as plt

from docplex.mp.model import Model

from qiskit_algorithms import QAOA, NumPyMinimumEigensolver
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import Sampler
from qiskit_optimization.algorithms import CobylaOptimizer, MinimumEigenOptimizer
from qiskit_optimization.algorithms.admm_optimizer import ADMMParameters, ADMMOptimizer
from qiskit_optimization.translators import from_docplex_mp

# If CPLEX is installed, you can uncomment this line to import the CplexOptimizer.
# CPLEX can be used in this tutorial to solve the convex continuous problem,
# but also as a reference to solve the QUBO, or even the full problem.
#
# from qiskit.optimization.algorithms import CplexOptimizer

Primero inicializamos todos los algoritmos que planeamos usar más adelante en este tutorial.

Para resolver los problemas QUBO podemos elegir entre

MinimumEigenOptimizer usando diferentes MinimumEigensolver, como SamplingVQE, QAOA o NumpyMinimumEigensolver (clásico)
GroverOptimizer
CplexOptimizer (clásico, si CPLEX está instalado)

y para resolver los problemas continuos convexos podemos elegir entre los siguientes solucionadores clásicos:

CplexOptimizer (si CPLEX está instalado)
CobylaOptimizer

En caso de que CPLEX no esté disponible, el CobylaOptimizer (para problemas continuos convexos) y el MinimumEigenOptimizer usando el NumpyMinimumEigensolver (para QUBOs) se pueden utilizar como alternativas clásicas a CPLEX para pruebas, validación, y evaluación comparativa.

[2]:

# define COBYLA optimizer to handle convex continuous problems.
cobyla = CobylaOptimizer()

# define QAOA via the minimum eigen optimizer
qaoa = MinimumEigenOptimizer(QAOA(sampler=Sampler(), optimizer=COBYLA()))

# exact QUBO solver as classical benchmark
exact = MinimumEigenOptimizer(NumPyMinimumEigensolver())  # to solve QUBOs

# in case CPLEX is installed it can also be used for the convex problems, the QUBO,
# or as a benchmark for the full problem.
#
# cplex = CplexOptimizer()

Ejemplo#

Probamos el algoritmo 3-ADMM-H en un Problema Cuadrático Binario Mixto simple con restricciones de igualdad y desigualdad (ejemplo 6 reportado en [1]). Primero construimos un problema docplex y luego lo cargamos en un QuadraticProgram.

[3]:

# construct model using docplex
mdl = Model("ex6")

v = mdl.binary_var(name="v")
w = mdl.binary_var(name="w")
t = mdl.binary_var(name="t")
u = mdl.continuous_var(name="u")

mdl.minimize(v + w + t + 5 * (u - 2) ** 2)
mdl.add_constraint(v + 2 * w + t + u <= 3, "cons1")
mdl.add_constraint(v + w + t >= 1, "cons2")
mdl.add_constraint(v + w == 1, "cons3")

# load quadratic program from docplex model
qp = from_docplex_mp(mdl)
print(qp.prettyprint())

Problem name: ex6

Minimize
  5*u^2 + t - 20*u + v + w + 20

Subject to
  Linear constraints (3)
    t + u + v + 2*w <= 3  'cons1'
    t + v + w >= 1  'cons2'
    v + w == 1  'cons3'

  Continuous variables (1)
    0 <= u

  Binary variables (3)
    v w t

Solución Clásica#

3-ADMM-H necesita un optimizador QUBO para resolver el subproblema QUBO y un optimizador continuo para resolver el subproblema restringido convexo continuo. Primero resolvemos el problema de manera clásica: usamos el MinimumEigenOptimizer con el NumPyMinimumEigenSolver como solucionador QUBO clásico y exacto y usamos el CobylaOptimizer como solucionador convexo continuo. 3-ADMM-H admite cualquier otro solucionador adecuado disponible en Qiskit Optimization. Por ejemplo, SamplingVQE, QAOA, y GroverOptimizer pueden ser usados como solucionadores cuánticos, como se demuestra más adelante. Si CPLEX está instalado, el CplexOptimizer también se puede utilizar tanto como solucionador QUBO, como solucionador convexo.

Parámetros#

Los 3-ADMM-H son parte de la clase ADMMParameters. Los valores de los parámetros personalizados se pueden establecer como argumentos de la clase. En este ejemplo, los parámetros \(\rho, \beta\) se inicializan a \(1001\) y \(1000\), respectivamente. La penalización factor_c de las restricciones de igualdad \(Gx = b\) se establece a \(900\). La tolerancia tol para la convergencia residual primaria se establece a 1.e-6. En este caso, se garantiza que la implementación de 3 bloques convergerá para el Teorema 4 de [1], porque la restricción de desigualdad con la variable continua siempre está activa. La implementación de 2 bloques se puede ejecutar configurando three_block=False y prácticamente converge a una solución factible no óptima.

[4]:

admm_params = ADMMParameters(
    rho_initial=1001, beta=1000, factor_c=900, maxiter=100, three_block=True, tol=1.0e-6
)

Llamar al algoritmo 3-ADMM-H#

Para invocar el algoritmo 3-ADMM-H, es necesario crear una instancia de la clase ADMMOptimizer. Esto toma los parámetros específicos de ADMM y los optimizadores de los subproblemas por separado en el constructor. La solución devuelta es una instancia de la clase OptimizationResult.

[5]:

# define QUBO optimizer
qubo_optimizer = exact
# qubo_optimizer = cplex  # uncomment to use CPLEX instead

# define classical optimizer
convex_optimizer = cobyla
# convex_optimizer = cplex  # uncomment to use CPLEX instead

# initialize ADMM with classical QUBO and convex optimizer
admm = ADMMOptimizer(
    params=admm_params, qubo_optimizer=qubo_optimizer, continuous_optimizer=convex_optimizer
)

[6]:

# run ADMM to solve problem
result = admm.solve(qp)

Resultado del Solucionador Clásico#

A continuación, se puede imprimir y visualizar la solución del 3-ADMM-H. El atributo x de la solución contiene, respectivamente, los valores de las variables de decisión binarias y los valores de las variables de decisión continuas. El fval es el valor objetivo de la solución.

[7]:

print(result.prettyprint())

objective function value: 1.0
variable values: v=1.0, w=0.0, t=0.0, u=2.0
status: SUCCESS

Se puede acceder a las estadísticas de la solución en el campo state y visualizarlas. Aquí mostramos la convergencia de 3-ADMM-H, en términos de residuos primarios.

[8]:

plt.plot(result.state.residuals)
plt.xlabel("Iterations")
plt.ylabel("Residuals")
plt.show()

../_images/tutorials_05_admm_optimizer_19_0.png

Solución Cuántica#

Ahora resolvemos el mismo problema de optimización con QAOA como optimizador QUBO, ejecutándolo en un dispositivo cuántico simulado. Primero, es necesario seleccionar el optimizador clásico del solucionador propio QAOA. Luego, se configura el backend de simulación. Finalmente, el solucionador propio se incluye en la clase MinimumEigenOptimizer. Una nueva instancia de ADMMOptimizer se completa con QAOA como optimizador QUBO.

[9]:

# define QUBO optimizer
qubo_optimizer = qaoa

# define classical optimizer
convex_optimizer = cobyla
# convex_optimizer = cplex  # uncomment to use CPLEX instead

# initialize ADMM with quantum QUBO optimizer and classical convex optimizer
admm_q = ADMMOptimizer(
    params=admm_params, qubo_optimizer=qubo_optimizer, continuous_optimizer=convex_optimizer
)

[10]:

# run ADMM to solve problem
result_q = admm_q.solve(qp)

Resultados de Solucionador Cuántico#

Aquí presentamos los resultados obtenidos del solucionador cuántico. Como en el ejemplo anterior, x representa la solución, el fval es el valor objetivo.

[11]:

print(result.prettyprint())

objective function value: 1.0
variable values: v=1.0, w=0.0, t=0.0, u=2.0
status: SUCCESS

[12]:

plt.clf()
plt.plot(result_q.state.residuals)
plt.xlabel("Iterations")
plt.ylabel("Residuals")
plt.show()

../_images/tutorials_05_admm_optimizer_25_0.png

[13]:

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
`qiskit-terra`	0.23.0
`qiskit-aer`	0.11.1
`qiskit-optimization`	0.5.0
`qiskit-machine-learning`	0.6.0
System information
Python version	3.9.15
Python compiler	Clang 14.0.0 (clang-1400.0.29.102)
Python build	main, Oct 11 2022 22:27:25
OS	Darwin
CPUs	4
Memory (Gb)	16.0
Tue Dec 06 21:47:54 2022 JST

This code is a part of Qiskit

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.

[ ]: