Vincent Zoonekynds Blog De nombreux problèmes de statistiques ou d'apprentissage automatique sont de la forme de trouver les valeurs des paramètres qui minimisent une certaine mesure d'erreur. Mais dans certains cas, des contraintes sont également imposées aux paramètres: par exemple, elles doivent résumer jusqu'à 1, ou au plus 10 d'entre elles doivent être non nulles - cela ajoute une couche combinatoire au problème, ce qui le rend Beaucoup plus difficile à résoudre. Dans cette note, je vais vous donner un guide pour (certains) des paquets d'optimisation dans R et d'expliquer (certains) des algorithmes derrière eux. Les solveurs accessibles à partir de R ont certaines limitations, comme l'incapacité à traiter des contraintes binaires ou intégrales (en problèmes non linéaires): nous verrons comment résoudre ces problèmes. Lorsque vous commencez à utiliser le logiciel d'optimisation, vous avez du mal à cibler le problème sous la forme attendue par le logiciel (vous devez souvent le reformuler pour le rendre linéaire ou quadratique, puis l'écrire sous forme matricielle). Ce n'est pas très convivial. Nous verrons qu'il est possible de spécifier des problèmes d'optimisation d'une manière parfaitement lisible. Beaucoup d'exemples seront tirés de l'optimisation des finances et des portefeuilles. Introduction L'optimisation se réfère au problème de trouver le minimum ou le maximum d'une certaine fonction, sous réserve de quelques contraintes. Les problèmes d'optimisation (parfois appelés programmes d'optimisation - le mot vient d'une époque sans ordinateurs et pas de programmes informatiques) sont souvent écrits comme où x est un vecteur et f, g, h fonctions arbitraires. Décrivons d'abord certaines des complications qui peuvent se produire lorsque vous êtes confronté à un problème d'optimisation. Extrémités locales Comme de nombreux algorithmes d'optimisation utilisent uniquement des informations locales, ils peuvent se coincer dans un extremum local. Dans l'exemple suivant, il existe de nombreuses vallées: l'ordinateur en trouvera une, mais pas nécessairement la plus basse. (Dans cet exemple, vous pouvez utiliser un algorithme d'optimisation plus robuste, comme DEoptim ou, mieux, se débarrasser des ondes et des extrema locaux en développant le sinus.) Réparamétrisation pour supprimer les contraintes La situation est souvent rendue plus compliquée par la présence Des contraintes. Heureusement, ils peuvent souvent être supprimés en reformulant le problème: si vous avez une contrainte d'égalité, vous pouvez souvent exprimer une des inconnues en fonction des autres si vous avez une contrainte d'inégalité de la forme x0, vous pouvez remplacer x par exp (Y) ou y2 ou log (1exp (y)), où y est une nouvelle inconnue. Par exemple, considérons une régression contrainte: Le problème peut être reparamétré comme suit. Malheureusement, cette approche ne fonctionne pas toujours. Considérez le problème suivant. Soit n les nombres a1. Un, nous voulons trouver x1. Xn, aussi proche que possible de l'ai, mais dans l'ordre croissant. Si l'on utilise la somme des distances au carré pour mesurer la proximité, on peut écrire le problème d'optimisation au lieu de chercher x1, x2. Xn, on peut chercher Le problème devient La contrainte est plus simple, mais nous ne nous en sommes pas complètement débarrassés. Mais nous pouvons écrire y exp (z): cela assurera qu'il reste positif. Les contraintes ont maintenant complètement disparu: nous avons une très mauvaise solution. L'un des problèmes est que la solution est sur la frontière, mais la frontière n'est plus accessible après notre reparamétrisation. Dans ce cas, la programmation quadratique est une meilleure approche. Pénalités dures et douces Dans certains cas, les contraintes sont trop irrégulières ou trop nombreuses: nous ne pouvons pas les supprimer. Au lieu de cela, nous pouvons ajouter une pénalité pour les violations de contrainte, et augmenter progressivement la pénalité. Optimisation en R Les fonctions pour résoudre des problèmes d'optimisation sont dispersées dans de nombreux paquets, chacun limité à (ou optimisé pour) des problèmes d'un certain type. Pour compliquer les choses, les interfaces sont différentes. En voici quelques uns. Il ya eu quelques tentatives pour unifier tous ces paquets, par ex. Le ROI et les paquetages optimx (ils vous permettent de décrire le problème d'optimisation, toujours de la même manière, quel que soit le type de problème et seulement ensuite de sélectionner le solveur à utiliser, le ROI pour la programmation mathématique, optimx pour l'optimisation sans ou Mais elles sont encore incomplètes et manquent de documentation. Il existe une liste plus exhaustive dans la vue des tâches d'optimisation. Si vous n'êtes pas familier avec eux, je suggère de les vérifier dans l'ordre suivant. Optim sera suffisant pour la plupart de vos besoins d'optimisation, mais vous voudrez peut-être recourir à DEoptim pour les problèmes avec de nombreux extrema locaux. Pour les problèmes non linéaires avec des contraintes non-box (c'est-à-dire des contraintes spécifiées par plusieurs fonctions, avec des égalités ou des inégalités, plutôt que des limites supérieure et inférieure), utilisez Rsolnp. Si le problème est grand et linéaire ou quadratique, vous voudrez essayer Rglpk ou quadprog à la place: ils seront beaucoup plus rapides, mais il peut être difficile d'écrire le problème sous forme matricielle. Certains de ces solveurs ont des limites. Par exemple, lpSolve impose que toutes les variables soient non négatives (c'est dans la documentation, avec un point d'exclamation, mais il est facile de négliger - Rglpk comme le même comportement par défaut, mais il peut être changé) quadprog fonctionne uniquement pour Des problèmes strictement convexes (la forme quadratique doit être positive définie, mais si vous devez ajouter des variables lentes pour transformer certaines des contraintes, vous vous retrouvez avec une matrice semi-définie positive et il ne fonctionne plus - c'est une limitation sérieuse) Les contraintes d'intégralité ne peuvent être imposées qu'à certains des solveurs linéaires. Sauf pour les solveurs non linéaires (et Rglpk, auquel vous pouvez donner un fichier texte), il n'est pas possible de spécifier les problèmes d'une manière lisible par l'homme: des matrices justes. Si votre problème n'est pas linéaire mais peut facilement être converti en un problème linéaire, vous devez effectuer vous-même la transformation. Certaines des transformations (par exemple, la séparation de la valeur positive et négative d'un nombre pour exprimer sa valeur absolue) sont faciles, mais d'autres sont plus complexes, plus longues et sujettes à erreur (par exemple, convertir le déficit attendu en une quantité linéaire ou Convertissant les contraintes quadratiques en contraintes semi-définies). Exemple: Régression La régression linéaire est un problème d'optimisation: nous recherchons la valeur de b qui minimise la somme résiduelle des carrés. Comparons le problème d'optimisation avec la régression. Exemple: régression contrainte La reformulation du problème de régression en tant que problème d'optimisation vous permet d'ajouter facilement des contraintes linéaires. Par exemple, vous pouvez demander aux coefficients de la régression de résumer jusqu'à 1. Exemple: Régression de quantile Le problème de trouver la médiane d'un ensemble de nombres x1. Xn peut être formulé comme un problème d'optimisation non linéaire: il peut être reformulé comme un problème linéaire, en remplaçant les valeurs absolues par la somme de leurs parties positive et négative. Voyons un exemple. On peut utiliser une ligne brisée asymétrique, avec pente tau si x-mu0, et 1-tau sinon, avec tau En 0,1. La médiane est obtenue pour tau12. Nous pouvons aussi utiliser cette ligne brisée asymétrique comme fonction de perte lors du calcul d'une régression: lorsque tau12 (médiane), il s'agit de la régression L1 et, en général, elle est appelée régression quantile. (Un mot de prudence: vous ne devriez pas utiliser lpSolve exactement de cette façon. Il impose que toutes les variables soient positives, y compris le quantile. Nos exemples ne fonctionne que parce que les quantiles sont positifs.) Algorithmes descente de gradient Le problème de trouver le minimum de Une fonction f (x) peut être interprétée géométriquement comme suit: si f représente l'altitude dans un paysage, minimiser f signifie trouver la vallée la plus basse. Un algorithme simple vient à l'esprit: il suffit de descendre. Plus formellement, commencez par une première estimation x de la solution calculez la dérivée (aussi appelée gradient) de f pour trouver la direction de la pente la plus abrupte (vers le bas) et prenez un pas dans cette direction lorsque vous ne pouvez plus trouver une pente direction. Vous devez d'abord choisir la taille du pas, mais vous pouvez la faire dépendre de la norme du dégradé. Nelder-Mead Si vous ne connaissez pas la dérivée de la fonction (ou si elle n'est pas différentiable), vous pouvez modifier l'algorithme de descente en gradient comme suit. Commencez par une première estimation x. Choisir une direction aléatoire, parmi les n coordonnées, aller en avant et en arrière dans cette direction, et comparer les valeurs de f: f (x), f (xh), f (x-h). Si l'une des nouvelles valeurs est meilleure que la nouvelle, passer à ce point autrement ne bouge pas. Iterer jusqu'à la convergence. L'algorithme peut être amélioré en changeant la taille du pas: augmentez-le (disons par 10) quand vous pouvez le déplacer, diminuez-le quand vous ne le faites pas (parce que quand vous ne pouvez pas bouger, le minimum est probablement proche et vous pouvez le dépasser) , Et s'arrêter lorsque la taille de pas est trop petite. Vous pouvez utiliser un pas de pas différent pour chaque coordonnée, pour éviter des problèmes si leurs échelles sont différentes. Les points xh, xh, autour de x dans toutes les directions forment une sorte de boule (carrée): l'algorithme laisse simplement la boule rouler en descente et utilise une plus petite boule, pour une meilleure précision, lorsqu'elle est coincée sur une vallée trop petite pour À explorer. Dans la dimension n, cette boule carrée a 2n points (l'hypercube a 2n sommets, mais nous n'utilisons que les points au centre des facettes). L'algorithme de Nelder-Mead utilise une idée similaire, mais avec une balle triangulaire (tétraédrique) un peu plus économique: elle n'a que n1 points. Gradient stochastique Souvent, la fonction de minimiser est une somme, avec un terme pour chaque observation. Dans ce cas, vous pouvez traiter les observations un par un (algorithme en ligne): calculez le dégradé du terme correspondant à l'observation courante, déplacez-vous dans sa direction (utilisez une taille d'échelon plus petite que pour le gradient complet) et continuez Avec le prochain terme. Gradient de conjugué Vous pouvez remarquer que la descente de gradient oscille parfois autour de la solution, ou se déplace en zigzag avant d'atteindre l'optimum. Ceci peut être remédié en se déplaçant, non dans la direction du gradient, mais dans le sens d'une certaine combinaison linéaire du gradient et de la direction précédente. Ceci peut être interprété comme une sorte d'inertie: on tourne partiellement, mais pas complètement, dans la direction du gradient, Le Hessien et ses approximations L'algorithme de descente en gradient n'a utilisé que la première dérivée (c'est-à-dire approximée la fonction de minimiser par une droite ). Au lieu de cela, nous pouvons approximer la fonction par sa seconde expansion de Taylor: l'approximation est une fonction quadratique et (à condition qu'elle soit positive définie), elle a un extremum. Cela nécessite la dérivée seconde (matrice de Hesse) et fonctionne raisonnablement bien dans de faibles dimensions. Il s'agit en fait de la méthode de Newtons, utilisée pour résoudre f (x) 0. Mais il ya un gros problème avec la hessienne: sa taille. S'il y a n paramètres à estimer, la hessienne est une matrice nn - quand n est grand, c'est ingérable. Nous avons besoin de trouver une approximation de cette matrice qui ne nécessite pas le calcul et le stockage des valeurs n2. Si la fonction de minimiser est une somme de carrés, les calculs peuvent être simplifiés par approximation du hessien (Gauss-Newton): L'étape h est choisie de sorte que S (bh) 0: Pour éviter des problèmes lors de l'inversion de la matrice, L'algorithme de Marquardt le rétrécit vers l'identité (ceci est semblable à la régression de crête): Quand lambda est grand, c'est en fait une étape dans la direction du gradient: c'est un mélange de descente de gradient et de Gauss-Newton. Dans le cas général, pour éviter de calculer, de stocker et d'inverser le Hessien, nous voulons une matrice B telle qu'il existe de nombreux choix possibles. On commence généralement par un extimate initial (par exemple, B0I), et on met à jour une estimation de la hessie à mesure que l'algorithme progresse vers l'extremum, en ajoutant une matrice facile à calculer, par ex. Une matrice de rang 1 (les matrices de rang 1 peuvent être écrites comme le produit de deux vecteurs ab). Par exemple, l'algorithme BFGS utilise deux matrices de rang 1: Il est possible de suivre une approximation de l'inverse de B en même temps. L'algorithme L-BFGS (low-memory BFGS) ne conserve que les dernières mises à jour L: il n'y a que 2L vecteurs à stocker. Optimisation contrainte: multiplicateurs de Lagrange Le problème d'optimisation contrainte peut être remplacé (la plupart du temps) par la condition de premier ordre, c'est-à-dire que l'on veut trouver (x, lambda) tel que This peut être implémenté comme suit. Minimum: il peut s'agir d'un minimum local ou, puisqu'il s'agit d'une condition de premier ordre, d'un maximum ou d'un point de selle. Regarder les conditions du second ordre donnerait plus d'informations, du moins si le Hessien est inversible. KarushKuhnTucker conditions Les multiplicateurs de Lagrange traitent des contraintes d'égalité. Lorsque nous avons des contraintes d'inégalité, les choses deviennent plus compliquées. La condition nécessaire pour un extremum devient La dernière condition est problématique: elle indique que pour chaque contrainte d'inégalité hi (x) 0, soit hi (x) 0, et la contrainte est contraignante, et hi apparaît dans la première équation ou hi (x ) 0, et la contrainte n'est pas contraignante, mui0 et hi disparaît de la première équation. Déterminer quelle contrainte lie est un problème combinatoire, mieux abordé par des algorithmes combinatoires, tels que l'algorithme simplex. Programmation linéaire, interprétation géométrique et algorithme simplex Le problème d'optimisation (x, b, c sont des vecteurs, A est une matrice) peut être interprété comme suit. Les contraintes définissent une intersection de demi-espaces, et forment un polyèdre. Les courbes de niveau (hypersurfaces) de la fonction objective sont en fait des droites (hyperplanes), parallèles entre elles, nous voulons trouver celle avec la plus haute valeur, parmi celles qui coupent le polyèdre: qui se produira sur un sommet du polyèdre. Il s'agit d'un problème combinatoire: il existe un nombre fini (mais souvent très important) de sommets, et nous devons trouver celui qui maximise l'objectif. L'algorithme simplex procède comme suit: commencez par un sommet du polyèdre, trouvez un bord dans la direction de laquelle l'objectif augmente, suivez ce bord jusqu'au prochain sommet et continuez jusqu'à ce que vous ne puissiez plus trouver un tel bord. Pour cela, nous avons besoin d'un moyen de décrire les sommets et les arêtes reliant deux sommets. Le problème d'optimisation peut être réécrit comme suit, en utilisant des variables faibles (nous remplaçons A x lt b par A x xS b, xS 0). (B, N) est une partition de la matrice (A, I) telle que B soit inversible . Les solutions avec xN0 correspondent à des sommets et sont faciles à décrire: L'objectif est également très simple: L'algorithme est alors le suivant: démarrer avec une partition (B, N) (par exemple B pourrait correspondre aux variables que nous avons ajouté) Un sommet sur le polyèdre), essayez de changer une colonne entre B et N pour augmenter l'objectif (cela correspond à se déplacer le long d'un bord du polyèdre) jusqu'à ce que vous ne puissiez plus. (En fait, vous n'avez pas à examiner toutes les paires: pour chaque variable dans N, essayez de l'inclure autant que possible, sans enfreindre les contraintes: de (), une des variables dans B sera alors 0 - c'est-à-dire Celle que vous pouvez supprimer.) Programmation linéaire et dualité Soit x une solution de. On peut trouver une limite inférieure sur l'objectif cx en considérant une combinaison linéaire des contraintes, yb, pour quelque y. Mais y b y A x, et y A x lt c x fournit y A lt c (puisque x 0, la direction de l'inégalité est préservée). En d'autres termes, toute solution réalisable de est une limite inférieure. Le problème initial est appelé le problème primitif, et le nouveau problème double. Il s'avère que ce n'est pas seulement une borne inférieure: pour les solutions optimales, la valeur de l'objectif est la même. Ceci nous permet de vérifier facilement si une solution faisable d'un problème d'optimisation linéaire est la solution optimale: si nous trouvons des solutions x et y réalistes des problèmes primal et dual, avec les mêmes valeurs objectives cxby, alors ce sont des solutions optimales . Si le dual est plus facile à résoudre, vous pouvez d'abord le résoudre, et utiliser la solution pour aider à résoudre le problème primordial. Certains algorithmes tentent de résoudre les problèmes primaires et doubles en même temps, chacun aidant à résoudre l'autre. La notion de dualité peut être généralisée aux problèmes d'optimisation d'arbitrage, mais le fait que les objectifs, aux solutions optimales, sont les mêmes, est (souvent mais) pas toujours vrai. Méthodes basées gradient gradient généralisées peuvent être utilisées pour résoudre des problèmes d'optimisation générale avec des contraintes d'égalité comme suit. Lineariser les contraintes les utiliser pour exprimer certaines des inconnues en fonction des autres (juste un système linéaire à résoudre) résoudre le problème non contraint résultant avec l'algorithme de gradient itérer jusqu'à la convergence. S'il existe également des contraintes d'inégalité, les choses deviennent plus compliquées, mais nous pouvons adapter l'algorithme simplex. Premièrement, pour simplifier le problème, utilisez des variables lâches pour remplacer les contraintes d'inégalité par des contraintes de limite inférieure ou supérieure. A chaque étape de l'algorithme, nous pouvons linéariser les contraintes d'égalité et réduire le nombre de variables: les problèmes résultants ont un objectif non linéaire mais des contraintes linéaires. En commençant par une solution réalisable, nous pouvons utiliser une méthode basée sur le gradient pour nous déplacer vers la solution et nous arrêter lorsque nous nous heurtons à la limite. Puisque nous sommes sur la frontière, certaines des contraintes d'inégalité sont actives (ou liées), c'est-à-dire des égalités. Comme pour la méthode simplex, nous pouvons essayer de trouver quelles inégalités pour rendre actif ou non pour améliorer la fonction objective. L'algorithme simplex fonctionne bien, mais il explore la surface du polyèdre définie par les contraintes - en grande dimension, la surface peut être très vaste, par rapport à l'intérieur du polyèdre (c'est ce que l'on appelle la malédiction de dimension). Les méthodes de point intérieur prennent un raccourci à l'intérieur du polyèdre. Pour le problème d'optimisation, les conditions de premier ordre (Kuhn-Tucker) sont: Nous pourrions essayer de les résoudre en suivant le gradient, qui définit un chemin d'une solution réalisable à l'extremum ou un point sur la frontière - mais quand nous nous heurtons à la Frontière du domaine, ce point n'est pas l'extremum désiré: le travail n'est pas terminé. Au lieu de cela, nous pouvons suivre un autre chemin, par exemple, les solutions de pour des valeurs progressivement plus petites de tau0. Nous n'avons pas besoin de la solution exacte de chacun de ces problèmes intermédiaires: une solution approximative suffit souvent. Programmation quadratique séquentielle (SQP) Nous pouvons produire notre propre optimiseur non linéaire et contraint. Il peut sembler un ordre élevé, mais il est en fait assez facile. Nous voulons résoudre le problème où f, g et h sont des fonctions lisses. Si nous étions dans la dimension 1, essayant de minimiser f (x) sans contraintes, nous commençons par une approximation initiale x, par approximation f par son expansion de Taylor du second ordre, la minimisons et recommençons avec la nouvelle valeur de x, jusqu'à convergence. Dans la dimension n, avec les contraintes, on peut faire la même chose: commencer par une première hypothèse x, remplacer l'objectif f par son expansion de Taylor du second ordre, remplacer les contraintes g et h par leur expansion de Taylor du premier ordre, résoudre le programme quadratique résultant , Recommencez avec la nouvelle valeur pour x, et continuez jusqu'à la convergence. C'est ce qu'on appelle la programmation quadratique séquentielle. Utilisons cette fonction pour résoudre le problème d'entropie maximum suivant. Voici un autre exemple. Nous avons une matrice nn, nous connaissons la somme des lignes, la somme des colonnes, nous connaissons certains de ses éléments. Remplir les valeurs manquantes aussi uniformément que possible, c'est-à-dire remplir les valeurs manquantes afin de maximiser l'entropie - de manière équivalente, afin de minimiser la divergence de Kullback-Leibler avec la distribution uniforme. SQP fonctionne bien pour les problèmes convexes (problèmes strictement convexes, pour cette implémentation, puisque nous nous appuyons sur quadprog). Vous pouvez préférer Rsolnp, qui fonctionnera aussi bien reasobaly sur de nombreux problèmes non convexes. Algorithmes stochastiques Les algorithmes précédents sont limités à des problèmes de comportement: ils fonctionnent bien pour des problèmes convexes, pour lesquels il n'existe pas d'extrémités locales qui nous induisent en erreur. Voici quelques algorithmes d'optimisation plus robustes aux extrema locaux. Puisqu'ils ne peuvent pas traiter des contraintes, vous pouvez les convertir en pénalités (contraintes douces). Le recuit simulé explore l'espace réalisable, aléatoirement, contrairement à la descente en gradient, mais pas toujours en descente: pour éviter les extrêmes locaux, il accepte parfois des solutions pires que l'actuelle. La probabilité d'accepter une solution pire que celle actuelle dépend de la gravité de cette solution et la probabilité diminue progressivement à mesure que l'algorithme progresse. Il peut être très lent. La recherche d'acceptation de seuil est similaire, mais la décision d'accepter une solution pire que la présente est déterministe, sur la base d'un seuil qui diminue à mesure que l'algorithme progresse. L'évolution différentielle est un algorithme basé sur la population: nous suivons une population de solutions potentielles et la mélangons, à chaque étape, pour créer la prochaine génération. Si x1, x2, x3 sont des éléments de la population courante, les rejetons sont de la forme. L'optimisation des essaims de particules est un autre algorithme basé sur la population, dans lequel les solutions se déplacent à la fois dans la direction du gradient et l'une vers l'autre. Les algorithmes génétiques peuvent également être utilisés, mais la façon dont ils combinent les solutions (crossover) fonctionne mieux si les coordonnées sont indépendantes ou dans un ordre significatif. Ils peuvent être améliorés en ajoutant une recherche locale après chaque étape. Vers une interface plus conviviale Réécrire un problème d'optimisation en un problème quadratique (par exemple, se débarrasser des valeurs absolues, comme dans notre exemple de régression quantile), puis écrire les matrices correspondantes est facile mais extrêmement encombrant. La situation n'est pas différente de celle des modèles de régression: les logiciels archaïques incapables de traiter les variables qualitatives obligent l'utilisateur à créer manuellement la matrice du modèle, avec des variables fictives. Les utilisateurs de Matlab peuvent déjà spécifier des problèmes d'optimisation de manière conviviale. Pourrions-nous avoir quelque chose de similaire pour R? Nous voulons être en mesure de spécifier des problèmes d'optimisation, par ex. comme suit. Ce n'est pas aussi difficile qu'il paraît. (Le code ci-dessous est juste une preuve de concept: il n'a pas été fortement testé, est connu pour échouer dans certains cas, est limité à quelques types de problèmes, et il est très lent.) Les inconnues ne sont que des cordes, avec un Spécifique, afin que nous puissions surcharger les fonctions et les opérateurs dont nous avons besoin. Les fonctions - somme construisent des expressions de plus en plus complexes, comme des chaînes. Les fonctions maximiser et minimiser, et les opérateurs lt, prennent une expression (une chaîne), l'analysent (en utilisant yacas), extraient les parties linéaires et quadratiques (dans le cas d'un problème linéaire ou quadratique) et les stockent dans des variables globales, Qui sont finalement utilisés par la fonction de résolution. Des fonctions comme abs ou CVaR ajoutent de nouvelles variables et sont remplacées par des expressions linéaires. Cela est valable tant que le problème reste convexe, mais je ne vérifie pas que c'est le cas. La partie délicate est de convertir les expressions que nous avons (comme chaînes) dans les matrices attendues par quadprog ou Rglpk. Je m'appuie sur Maxima pour cette tâche (vous devrez peut-être l'installer en premier) et communiquer avec lui via des canaux nommés (vous avez besoin d'un système d'exploitation qui fournit des canaux nommés). Exemples d'optimisation de portefeuille Pour les exemples, nous utiliserons les rendements hebdomadaires pour une poignée d'actions. Pour vérifier comment les choses s'échelonnent lorsque l'univers est plus grand, voici un ensemble de données plus réaliste. Le problème d'optimisation du portefeuille est le problème de trouver les pondérations optimales d'un portefeuille, c'est-à-dire combien vous devriez investir dans chaque actif pour maximiser une quantité souhaitable (souvent, une mesure du rendement ajusté au risque). Si vous ne disposez d'aucune information sur les actifs (ou, de manière plus réaliste, sur des informations fiables), vous pouvez affecter le même poids à chaque actif: cela maximise l'entropie (une mesure de la diversité) des poids. Variance moyenne Les portefeuilles de moyenne-variance maximisent les rendements attendus ajustés au risque du portefeuille. L'ajustement du risque dépend de l'aversion pour le risque de l'investisseur (informellement, cela correspond à lambda, dans la formule). Comme mesure du risque, nous pouvons utiliser la variance des rendements du portefeuille, mais il existe de nombreux autres choix. Variance minimale Au lieu de regarder les rendements corrigés du risque, nous pouvons simplement regarder le risque - il est beaucoup plus facile de prédire le risque futur que les rendements futurs. Frontière efficace Il existe plusieurs manières d'identifier les portefeuilles sur la frontière efficace: Elles correspondent à la minimisation du risque pour un rendement cible fixé, à la maximisation des rendements d'un budget à risque fixe et à la maximisation des rendements ajustés au risque. Malheureusement, comme vous ajoutez plus de contraintes (entièrement investi, pas de ventes à découvert, les limites de poids pour chaque secteur, les limites de poids pour chaque actif, la limite sur le nombre d'actifs, les tailles de lot, etc), la forme de la région faisable change et besoin Ne restent pas convexes: ces problèmes ne sont plus garantis équivalents. Des portefeuilles aléatoires Une façon très naïve de trouver un portefeuille (presque) optimal pour une fonction objective arbitraire serait de prendre de nombreux portefeuilles au hasard et de garder le meilleur. Tout d'abord, il semble une très mauvaise idée: nous sommes apparemment juste échantillon de portefeuilles autour du portefeuille à pondération égale. Mais il y a beaucoup de choses que nous faisons mal. Tout d'abord, si nous prenons des nombres uniformément distribués et les divisons par leur somme, nous n'avons pas de nombres uniformément répartis dans la somme simple (w) 1: il ya un biais vers le centre du simplexe. Elle disparaît si nous utilisons plutôt une distribution exponentielle: nous sommes maintenant beaucoup plus près de la frontière efficace. Nous ne voulons pas vraiment échantillonner uniformément à partir du simplex: les portefeuilles optimaux ont tendance à être quelque part sur la frontière. Prenant une certaine puissance des poids polarisera les données vers les sommets et les bords. (La valeur est un peu trop élevée, de sorte que nous pouvons voir sur l'intrigue ce qui se passe réellement.) Nous pourrions améliorer les choses encore en utilisant des séquences faible discordance. Avec plus de stocks, vous pouvez vouloir augmenter l'exposant, mais pas trop, sinon la plupart des portefeuilles sont concentrés sur un seul stock. Contraintes de courte durée Le portefeuille long-court non contraint a un effet de levier excessif. Nous pouvons contrôler l 'effet de levier de la même façon que nous avons mis en œuvre la régression quantile: écrire les poids du portefeuille comme wi ai - bi, avec a et b positifs. Coûts de transaction Les coûts de transaction peuvent être ajoutés comme une pénalité à la fonction objectif. Le plus facile à résoudre est une pénalité L2: le problème reste quadratique. Mais une pénalité linéaire est plus réaliste. On peut se débarrasser de la valeur absolue comme d'habitude, en écrivant son argument comme une différence de deux nombres. Portefeuille tangent (ratio de Sharpe maximum) Nous pourrions d'abord calculer tous les portefeuilles sur la frontière efficace, puis trouver la tangente l'un d'entre eux. Mais c'est beaucoup de calculs si vous voulez seulement un portefeuille (d'autant plus quand il ya beaucoup d'actifs). Alternativement, nous pouvons utiliser un optimiseur non linéaire (à première vue, la maximisation du ratio de Sharpe ne ressemble pas à un problème quadratique). Mais ce n'est pas un problème convexe: il n'y a aucune garantie que la solution que nous obtenons est un maximum global. Il s'avère que le problème de trouver le portefeuille tangent peut être reformulé comme un problème quadratique, comme suit. Le portefeuille tangent est également le portefeuille maximal de ratio de Sharpe, où le ratio de Sharpe est égal à wrt (w V w), parmi les portefeuilles entièrement investis (les pondérations devraient se résumer à 1). Supprions la contrainte que les poids résument à 1. Il n'y a plus de solution unique au problème: puisque le rapport d'action est inchangé quand on multiplie les poids par un nombre non nul (homogène de degré 0) Les portefeuilles de ratio Sharpe maximum forment une ligne - une fois que nous connaissons un portefeuille, nous pouvons obtenir les autres en le multipliant par un scalaire. Pour avoir une seule solution, nous pouvons imposer une condition sur les poids. Par exemple, on peut demander que le numérateur du ratio de partage soit 1. On doit alors maximiser 1sqrt (w V w), c'est-à-dire minimiser w Vw: c'est un problème quadratique. Optimisation basée sur le scénario: CVaR minimum La valeur conditionnelle à risque (CVaR), également appelée déficit attendu (ES), est la perte attendue, étant donné que la perte dépasse un certain seuil. Le seuil est habituellement un certain quantile de la distribution des rendements, par ex. Le quantile 5, ou le quantile 1. Nous pouvons utiliser le déficit attendu comme mesure du risque. Si nous connaissions la distribution des rendements, ce serait simplement un problème d'optimisation non linéaire. Cependant, les retours ne sont pas gaussiens. (Nous pourrions utiliser d'autres distributions paramétriques.) Au lieu d'une distribution paramétrique, nous pouvons utiliser la distribution empirique des rendements. Premièrement, nous devons exprimer le déficit attendu (échantillon) comme un problème d'optimisation. Le problème d'optimisation devient un peu désordonné (si vous commettez une erreur quelque part, par exemple avec le signe des variables lâches, le bogue est extrêmement long à traquer). Pour s'assurer que nous réduisons effectivement le déficit attendu, comparons avec une optimisation plus directe. De la même façon, nous pourrions ajouter une contrainte sur le CVaR. Optimisation basée sur le scénario: VaR La valeur à risque (VaR) est juste un quantile de la distribution des rendements - mais elle est exprimée comme une perte, donc le signe est différent. Il peut être exprimé comme suit: Puisqu'il s'agit d'un minimum, il peut être utilisé dans la fonction objective d'un problème d'optimisation, comme nous l'avons fait pour le CVaR. Malheureusement, les fonctions d'indicateur (qui peuvent être codées avec des variables binaires) rendent le problème d'optimisation (non convexe et) plutôt difficile à résoudre. Nous pouvons utiliser un optimiseur robuste, p. Ex. DEoptim. Branch-and-bound: Variables binaires et contraintes de cardinalité Ajout de la contrainte que certaines des variables sont binaires, c'est-à-dire ne peut prendre que deux valeurs, 0 ou 1, rend le problème encore plus combinatoire. S'il existe n telles variables binaires, on peut résoudre les 2n problèmes correspondant à toutes leurs valeurs possibles. C'est trop, bien sûr, mais nous pouvons réduire le nombre de problèmes à résoudre en les arrangeant dans un arbre, en trouvant une limite sur la valeur de chaque sous-arbre et en taillant tous les sous-arbres comme suit. La racine de l'arbre correspond au problème non contraint: les variables binaires ne sont contraintes qu'à 0,1, mais elles ne doivent pas être des entiers. Il y a deux noeuds enfants, chacun ajoutant une contrainte à la première variable binaire: c'est 0 ou 1 (les autres variables restent dans 0,1). La couche suivante de l'arbre (4 nœuds) ajoute des contraintes à la deuxième variable, et ainsi de suite. Nous recherchons la feuille avec la meilleure solution. Comme les nœuds ont des contraintes moins strictes que les feuilles, leur solution est meilleure, mais jamais pire, que les feuilles en dessous: si la valeur d'un nœud est pire que la meilleure solution foliaire trouvée jusqu'à présent, il n'est pas nécessaire d'explorer les Sous-arbre, et il peut être élagué. Dans l'exemple suivant, nous considérons le problème de la détermination du portefeuille à écart minimum, à long seulement, avec au plus 5 actifs. The problem can be written as Let us first write functions to add constraints and solve the problem (so that the code can be reused with other solvers). Branch-and-bound: Integer variables and lot sizes The same idea can be used to handle integrality constants: at each node, we split the tree into 3 subtrees, corresponding to the constraints xiv (where v is some integer value, e. g. the integer closest to the solution of the unconstrained problem), xi v1 and xi lt v-1. The tree can be much larger than in the binary case: only when we add an equality constraint does the number of variables to decide on decrease. (In most cases, the xi are bounded, so that the tree is finite.) The algorithm can be improved: you can split the nodes in 2 rather than 3, you can carefully choose the variable to split on, you can use better heuristics to find a good upper bound on the minimum, you can add constraints to shrink the set of feasible solutions (branch-and-cut). Equal contribution to risk The risk of a portfolio, is homogeneous of degree 1, and can therefore be decomposed as where the marginal contribution to risk (MCTR) of asset i can be computed as Let us check on an example: It is easy to find portfolios with equal marginal contribution to risk. It is not really an optimization problem, but just a system of equations to solve. If r is the vector of desired marginal contributions to risk (up to a multiplicative constant), we want w (and lambda) such that In a risk parity portfolio, the assets have the same contribution to risk (the contribution to risk is wMCTR). They are a special case of risk budgeting portfolios, where the contribution to risk of each asset is imposed. It is still a system of equations to solve, but it is not linear: if ri is the desired contribution to risk of asset i, we want to find w so that where the risk is the sum of the contributions to risk. This can be written as where. is the elementwise product. (It is a quadratic equation: no easy solution.) We can use a non-linear solver. Since the problem is not convex, you may want to try other optimizers (e. g. DEoptim). Conclusion What we talked about We have presented the algorithms behind commonly-used optimization routines. They fall into three broad categories: gradient-like methods, that try to find a direction in which the objective function is better (with many variants, some eschewing the gradient (Nelder-Mead), some using a biased gradient (conjugate gradient), some using the hessian, some approximating the hessian (L-BGFS), some using the specific form of the objective function to simplify the computations (Gauss-Newton, Levenberg-Marquardt)) combinatorial methods, that explore on the frontier of the feasible set, from vertex to vertex (or from facet to facet), to improve the objective function (simplex, generalized reduced gradient) interior point methods, that regularize the Kuhn-Tucker conditions g lambda 0 into g lambda tau, and let the regularization parameter tau decrease. We have presented some code to add binary or integral constraints to an arbitrary optimization problem and code to allow us to enter optimization problems in a human-readable form. We have given a few portfolio optimization examples: minimum variance, mean-variance, CVaR, VaR, prescribed contribution to risk, using a variety of optimization algorithms, including random portfolios. We saw that, for real-world problems, different optimizers may give different results: it is safer to use several optimizers (some lack robustness, some lack speed, some are user-unfriendly and their use is therefore bug-prone), check that the constraints are satisfied (especially if you have to transform the problem by hand to give it to the optimizer) and compare with some base-line algorithm (e. g. random portfolios). What we did not talk about I focused on the algorithms, without stressing how careful one should be when using them in a financial context. You need to check if the purportedly optimal portfolios are indeed close to optimal, out-of-sample -- and you need to clearly define what you mean by optimal. This will not only depend on the optimization problems, but also on the estimators of variance and returns used. You should check how sensitive those optimization problems are to their inputs. You should also carry out a complete backtest, to check how consistent the resulting portfolios are over time: is their out-of-sample performance independent of the market regime do they generate an excessive turnover I did not mention the use of copulas, volatility models, (semi-)parametric estimators of VaR and CVaR, spectral risk measures, drawdown. I intended to but did not mention second order cone programming and semi-definite programming, which generalize quadratic programming, and can be used for quadratic constraints and robust optimization (i. e. situations where you do not have a single number for the variances and expected returns, but intervals). There is an Rcsdp package, but the documentation is scarce (only one example), the error messages cryptic, and the licence non-standard.
No comments:
Post a Comment