Note

Cette page a été générée à partir de tutorials/optimization/5_admm_optimizer.ipynb.

Exécuter en mode interactif dans le ` IBM Quantum lab <https://quantum-computing.ibm.com/jupyter/tutorial/optimization/5_admm_optimizer.ipynb>` _.

Optimiseur ADMM

Introduction

L’optimiseur ADMM permet de résoudre des classes de problèmes d’optimisation à contraintes binaires mixtes (MBCO), qui apparaissent souvent dans les domaines de la logistique, les finances et la recherche opérationnelle. En particulier, l’optimiseur ADMM conçu ici peut résoudre le problème d’optimisation suivant \((P)\) :

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

soumis aux contraintes :

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

avec les hypothèses suivantes :

1. La fonction \(q: \mathbb{R}^pf \to \mathbb{R}\) est quadratique, donc \(q(x) = x^{\intercal} Q x + a^{\intercal} x\) pour une matrice carrée symétrique donnée \(Q \in \mathbb{R}^ \times \mathbb{R}^n, Q = Q^{\intercal}\), et un vecteur \(a \in \mathbb{R}^n\);

2. L’ensemble \(\mathcal{X} = \{0,1\}^M = \{x_{(i)} (1-x_{(i)}) = 0, \forall i\}\) impose les contraintes binaires ;

3. La matrice \(G\in\mathbb{R}^f \times \mathbb{R}^{n'}\), le vecteur \(b \in \mathbb{R}^{n'}\), et la fonction \(g: \mathbb{R}^ \to \mathbb{R}\) sont convexes;

4. La fonction \(\varphi: \mathbb{R}^l \to \mathbb{R}\) est convexe et \(\mathcal{U}\) est un ensemble convexe ;

5. La fonction \(\ell: \mathbb{R}^pf\times \mathbb{R}^l \to \mathbb{R}\) est jointivement convexe en \(x, u\).

Afin de résoudre les problèmes MBO, [1] a proposé une méthode heuristique pour \((P)\) basée sur la méthode de direction alternée des multiplicateurs (ADMM) [2]. ADMM est un algorithme de fractionnement d’opérateurs utilisé depuis longtemps dans l’optimisation convexe. Cette méthode est connue pour avoir des propriétés de convergence résiduelle, objective et à double variable, à condition que les hypothèses de convexité soient vérifiées.

La méthode décrite en [1] (appelée 3-ADMM-H) repose sur la procédure de décomposition des opérateurs pour découper certaines classes de problèmes MBO en: - un sous-problème QUBO qui peut être solutionné par un ordinateur quantique via des algorithmes tels que VQE (Variational-Quantum-Eigensolver) ou QAOA (Quantum Approximate Optimization Algorithm); - des sous-problèmes à contraintes continues convexes qui peuvent être résolus efficacement par des optimisations classiques.

L’algorithme 3-ADMM-H fonctionne ainsi :

0. Phase d’initialisation (positionne les paramètres, la QUBO -Quadratic Unconstrained Binary Optimization- et les solveurs convexes);

1. For each ADMM iterations ($k = 1, 2, \ldots, $) until termination:

   • Résoudre un sous-problème QUBO défini complètement (avec une machine classique ou quantique);

   • Résoudre des problèmes convexes correctement définis (avec une machine classique);

   • Mettre à jour les variables duales.

2. Retourner les optimiseurs et le coût.

Une discussion accessible sur les conditions de convergence, la faisabilité et l’optimisation de l’algorithme peut être trouvé dans [1]. Une variante avec deux blocs ADMM, de fait un problème QUBO, et un sous-problème contraint continu convexe est aussi présenté en [1].

Références

[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).

Initialisation

On commence ici par charger tous les packages nécessaires.

import time
from typing import List, Optional, Any
import numpy as np
import matplotlib.pyplot as plt

from docplex.mp.model import Model

from qiskit import BasicAer
from qiskit.aqua.algorithms import QAOA, NumPyMinimumEigensolver
from qiskit.optimization.algorithms import CobylaOptimizer, MinimumEigenOptimizer
from qiskit.optimization.problems import QuadraticProgram
from qiskit.optimization.algorithms.admm_optimizer import ADMMParameters, ADMMOptimizer

# 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

On initialise ensuite tous les algorithmes prévus pour ce tutoriel.

Pour résoudre les problèmes QUBO, on peut choisir entre - MinimumEigenOptimizer utilisant des MinimumEigensolver, tels que VQE, QAOA ou NumpyMinimumEigensolver (classique) - GroverOptimizer - CplexOptimizer (classique, nécessite CPLEX installé)

et pour résoudre les problèmes convexes continus on peut choisir l’un des choisir classiques suivants : - CplexOptimizer (nécessite CPLEX installé) - CobylaOptimizer

Si CPLEX n’est pas disponible, la classe CobylaOptimizer (pour les problèmes continus convexes) ainsi que MinimumEigenOptimizer reposant sur NumpyMinimumEigensolver (pour QUBO) peuvent être utilisées comme alternatives à CPLEX pour tester, valider et mesurer les performances.

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

# define QAOA via the minimum eigen optimizer
qaoa = MinimumEigenOptimizer(QAOA(quantum_instance=BasicAer.get_backend('statevector_simulator')))

# 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()

Exemple

Nous testons maintenant l’algorithme 3-ADMM-H sur un problème simple quadratique binaire mixte avec des contraintes d’égalités et d’inégalités (Exemple 6 décrit dans [1]). Nous commençons par construire un problème docplex puis nous le chargeons dans un QuadraticProgram.

# 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 = QuadraticProgram()
qp.from_docplex(mdl)
print(qp.export_as_lp_string())

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: ex6

Minimize
 obj: v + w + t - 20 u + [ 10 u^2 ]/2 + 20
Subject To
 cons1: v + 2 w + t + u <= 3
 cons2: v + w + t >= 1
 cons3: v + w = 1

Bounds
 0 <= v <= 1
 0 <= w <= 1
 0 <= t <= 1

Binaries
 v w t
End

Solution classique

L’algorithme 3-ADMM-H repose sur l’utilisation d’un optimiseur QUBO (pour adresser les sujets QUBO) et d’un optimiseur continu (pour adresser les problèmes contraints continus convexes). En premier lieu, nous résolvons ce problème de manière classique: Nous utilisons la classe MinimumEigenOptimizer avec un NumPyMinimumEigenSolver comme solution QUBO classique exacte et nous utilisons la classe CobylaOptimizer comme solution du problème continu convexe. 3-ADMM-H supporte tout solveur disponible dans Qiskit. Par exemple VQE, QAOA, et GroverOptimizer peuvent être invoqués comme solveurs quantiques comme nous le verrons plus tard. Si CPLEX est installé, le CplexOptimizer peut être utilisé à la fois comme solveur QUBO et comme solveur continu convexe.

Paramètres

Le 3-ADMM-H est associé à la classe ADMMParameters. Des valeurs particulières de certains paramètres doivent être définis comme arguments de la classe. Dans notre exemple, les paramètres \(\rho, \beta\) sont initialisés à \(1001\) et \(1000\) , respectivement. La pénalisation factor_c associée aux contraintes d’égalité \(Gx = b\) . La tolérance tol de la convergence résiduelle primaire est définie à 1.e-6. Dans ce cas, l’implémentation 3-block converge forcément en accord avec le théorème 4 de [1], car la contrainte d’inégalité sur la variable continue est toujours active. L’implémentation 2-block est réalisée en posant three_block=False, et converge vers une solution possible mais non optimale.

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

Appel de l’algorithme 3-ADMM-H

Pour invoquer l’algorithme 3-ADMM-H, une instance de la classe ADMMOptimizer doit être créée. Cette instance accepte des paramètres spécifiques ADMM et les différents optimiseurs dans un constructeur. La solution retournée est une instance de la classe OptimizationResult.

# 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)

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

Résultats avec un solveur classique

La solution 3-ADMM-H peut alors être imprimée et visualisée. L’attribut x de la solution contient respectivement, les valeurs des variables binaires de décision et les valeurs des variables de décision continues. L’objet fval est une valeur objective de la solution.

print("x={}".format(result.x))
print("fval={:.2f}".format(result.fval))

x=[1. 0. 0. 2.]
fval=1.00

Les statistiques sur la solution sont accessibles via le champ state. On affiche ici la convergence du 3-ADMM-H, en termes de résidus primaires.

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

Solution Quantique

Nous allons maintenant résoudre le même problème d’optimisation avec QAOA comme optimiseur QUBO via une exécution sur un système quantique simulé. Nous devons, en premier, sélectionner l’optimiseur classique eigensolver QAOA. Ensuite le backend de simulation doit être choisi. Enfin, le eigensolver est associé à la classe MinimumEigenOptimizer. Une nouvelle instance de ADMMOptimizer est créée avec QAOA comme optimiseur QUBO.

# 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)

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

Résultats du solveur quantique

Nous présentons ici les résultats obtenus avec le solveur quantique. Comme précédemment, x est la solution, fval est une valeur objective de la solution.

print("x={}".format(result_q.x))
print("fval={:.2f}".format(result_q.fval))

x=[1. 0. 0. 2.]
fval=1.00

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

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	None
Terra	0.15.1
Aer	0.6.1
Ignis	0.4.0
Aqua	0.7.5
IBM Q Provider	0.8.0
System information
Python	3.7.4 (default, Aug 13 2019, 15:17:50) [Clang 4.0.1 (tags/RELEASE_401/final)]
OS	Darwin
CPUs	2
Memory (Gb)	12.0
Fri Aug 28 09:24:00 2020 EDT

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

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.