Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

La géométrie symplectique et la géométrie complexe sont intimement liées, en particulier par les techniques asymptotiquement holomorphes de Donaldson et Auroux d'une part et par les travaux d’Eliashberget et Cieliebak sur la pseudoconvexité d'autre part. Les travaux présentés dans cette thèse sont motivés par ces deux liens. On donne d’abord la caractérisation symplectique suivante des constantes de Seshadri. Dans une variété complexe, la constante de Seshadri d’une classe de Kähler entière en un point est la borne supérieure des capacités de boules standard admettant, pour une certaine forme de Kähler dans cette classe, un plongement holomorphe et iso-Kähler de codimension 0 centré en ce point. Ce critère était connu de Eckl en 2014 ; on en donne une preuve différente. La deuxième partie est motivée par la question suivante de Donaldson : <<Toute sphère lagrangienne d'une variété projective complexe est-elle un cycle évanescent d'une déformation complexe vers une variété à singularité conique ?>> D'une part, on présente toute sous-variété lagrangienne close d’une variété symplectique/kählérienne close dont les périodes relatives sont entières comme lieu des minima d’une exhaustion <<convexe>> définie sur le complémentaire d'une section hyperplane symplectique/complexe. Dans le cadre kählérien, <<convexe>> signifie strictement plurisousharmonique tandis que dans le cadre symplectique, cela signifie de Lyapounov pour un champ de Liouville. D'autre part, on montre que toute sphère lagrangienne d'un domaine de Stein qui est le lieu des minima d’une fonction <<convexe>> est un cycle évanescent d'une déformation complexe sur le disque vers un domaine à singularité conique. / Symplectic geometry and complex geometry are closely related, in particular by Donaldson and Auroux’s asymptotically holomorphic techniques and by Eliashberg and Cieliebak’s work on pseudoconvexity. The work presented in this thesis is motivated by these two connections. We first give the following symplectic characterisation of Seshadri constants. In a complex manifold, the Seshadri constant of an integral Kähler class at a point is the upper bound on the capacities of standard balls admitting, for some Kähler form in this class, a codimension 0 holomorphic and iso-Kähler embedding centered at this point. This criterion was known by Eckl in 2014; we give a different proof of it. The second part is motivated by Donaldon’s following question: ‘Is every Lagrangian sphere of a complex projective manifold a vanishing cycle of a complex deformation to a variety with a conical singularity?’ On the one hand, we present every closed Lagrangian submanifold of a closed symplectic/Kähler manifold whose relative periods are integers as the lowest level set of a ‘convex’ exhaustion defined on the complement of a symplectic/complex hyperplane section. In the Kähler setting ‘complex’ means strictly plurisubharmonic while in the symplectic setting it refers to the existence of a Liouville pseudogradient. On the other hand, we prove that any Lagrangian sphere of a Stein domain which is the lowest level-set of a ‘convex’ function is a vanishing cycle of some complex deformation over the disc to a variety with a conical singularity.

No description available.

We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show that the resolutions of all these ideals are closely related and that their Z-graded Betti tables coincide. As corollaries, we give conceptual proofs of conjectures and questions posed by Postnikov and Shapiro, by Manjunath and Sturmfels, and by Perkinson, Perlman, and Wilmes. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.

abstract: Many products undergo several stages of testing ranging from tests on individual components to end-item tests. Additionally, these products may be further "tested" via customer or field use. The later failure of a delivered product may in some cases be due to circumstances that have no correlation with the product's inherent quality. However, at times, there may be cues in the upstream test data that, if detected, could serve to predict the likelihood of downstream failure or performance degradation induced by product use or environmental stresses. This study explores the use of downstream factory test data or product field reliability data to infer data mining or pattern recognition criteria onto manufacturing process or upstream test data by means of support vector machines (SVM) in order to provide reliability prediction models. In concert with a risk/benefit analysis, these models can be utilized to drive improvement of the product or, at least, via screening to improve the reliability of the product delivered to the customer. Such models can be used to aid in reliability risk assessment based on detectable correlations between the product test performance and the sources of supply, test stands, or other factors related to product manufacture. As an enhancement to the usefulness of the SVM or hyperplane classifier within this context, L-moments and the Western Electric Company (WECO) Rules are used to augment or replace the native process or test data used as inputs to the classifier. As part of this research, a generalizable binary classification methodology was developed that can be used to design and implement predictors of end-item field failure or downstream product performance based on upstream test data that may be composed of single-parameter, time-series, or multivariate real-valued data. Additionally, the methodology provides input parameter weighting factors that have proved useful in failure analysis and root cause investigations as indicators of which of several upstream product parameters have the greater influence on the downstream failure outcomes. / Dissertation/Thesis / Ph.D. Electrical Engineering 2011

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)

<p>U disertaciji su posmatrani projektivni postupci tipa konjugovanih gradijenata za re&scaron;avanje nelinearnih monotonih sistema velikih dimenzija. Ovi postupci kombinuju projektivnu metodu sa pravcima pretraživanja tipa konjugovanih gradijenata. Zbog osobine monotonosti sistema, projektivna metoda omogućava jednostavnu globalizaciju, a pravci pretraživanja tipa konjugovanih gradijenata zahtevaju malo<br />računarske memorije pa su pogodni za re&scaron;avanje sistema velikih dimenzija. Projektivni postupci tipa konjugovanih gradijenata ne koriste izvode niti funkciju cilja i zasnovani su samo na izračunavanju vrednosti funkcije sistema, pa su pogodni i za re&scaron;avanje neglatkih monotonih sistema. Po&scaron;to se globalna konvergencija dokazuje bez pretpostavki o regularnosti, ovi postupci se mogu koristiti i za re&scaron;avanje sistema sa singularnim re&scaron;enjima. U disertaciji su definisana tri nova tročlana pravca pretraživanja<br />tipa Flečer-Rivs i dva nova hibridna pravca tipa Hu-Stori. Formulisani su projektivni postupci sa novim pravcima pretraživanja i dokazana je njihova globalna konvergencija. Numeričke performanse postupaka testirane su na relevantnim primerima i poređene sa poznatim postupcima iz literature. Numerički rezultati potvrđuju da su novi postupci robusni, efikasni i uporedivi sa postojećim postupcima.</p> / <p>Projection based CG methods for solving large-scale nonlinear monotone systems are considered in this thesis. These methods combine hyperplane projection technique with conjugate gradient (CG) search directions. Hyperplane projection method is suitable for monotone systems, because it enables simply globalization, while CG directions are efficient for large-scale nonlinear systems, due to low memory. Projection based CG methods are funcion-value based, they don&rsquo;t use merit function and derivatives, and because of that they are also suitable for solving nonsmooth monotone systems. The global convergence of these methods are ensured without additional regularity assumptions, so they can be used for solving singular systems.Three new three-term search directions of Fletcher-Reeves type and two new hybrid search directions of Hu-Storey type are defined. PCG algorithm with five new CG type directions is proposed and its global convergence is established. Numerical performances of methods are tested on relevant examples from literature. These results point out that new projection based CG methods have good computational performances. They are efficient, robust and competitive with other methods.</p>

Les institutions financières sont, dans l’exercice de leurs fonctions, confrontées à divers risques, entre autres le risque de crédit, le risque de marché et le risque opérationnel. L’instabilité de ces facteurs fragilise ces institutions et les rend vulnérables aux risques financiers qu’elles doivent, pour leur survie, être à même d’identifier, analyser, quantifier et gérer convenablement. Parmi ces risques, celui lié au crédit est le plus redouté par les banques compte tenu de sa capacité à générer une crise systémique. La probabilité de passage d’un individu d’un état non risqué à un état risqué est ainsi au cœur de nombreuses questions économiques. Dans les institutions de crédit, cette problématique se traduit par la probabilité qu’un emprunteur passe d’un état de "bon risque" à un état de "mauvais risque". Pour cette quantification, les institutions de crédit recourent de plus en plus à des modèles de credit-scoring. Cette thèse porte sur les techniques actuelles de credit-scoring adaptées aux besoins d’une institution de crédit, le CFCAL-banque, spécialisé dans les prêts garantis par hypothèques. Nous présentons en particulier deux modèles non paramétriques (SVM et GAM) dont nous comparons les performances en termes de classification avec celles du modèle logit traditionnellement utilisé dans les banques. Nos résultats montrent que les SVM sont plus performants si l’on s’intéresse uniquement à la capacité de prévision globale. Ils exhibent toutefois des sensibilités inférieures à celles des modèles logit et GAM. En d’autres termes, ils prévoient moins bien les emprunteurs défaillants. Dans l’état actuel de nos recherches, nous préconisons les modèles GAM qui ont certes une capacité de prévision globale moindre que les SVM, mais qui donnent des sensibilités, des spécificités et des performances de prévision plus équilibrées. En mettant en lumière des modèles ciblés de scoring de crédit, en les appliquant sur des données réelles de crédits hypothécaires, et en les confrontant au travers de leurs performances de classification, cette thèse apporte une contribution empirique à la recherche relative aux modèles de credit-scoring. / Financial institutions face in their functions a variety of risks such as credit, market and operational risk. These risks are not only related to the nature of the activities they perform, but also depend on predictable external factors. The instability of these factors makes them vulnerable to financial risks that they must appropriately identify, analyze, quantify and manage. Among these risks, credit risk is the most prominent due to its ability to generate a systemic crisis. The probability for an individual to switch from a risked to a riskless state is thus a central point to many economic issues. In credit institution, this problem is reflected in the probability for a borrower to switch from a state of “good risk” to a state of “bad risk”. For this quantification, banks increasingly rely on credit-scoring models. This thesis focuses on the current credit-scoring techniques tailored to the needs of a credit institution: the CFCAL-banque specialized in mortgage credits. We particularly present two nonparametric models (SVM and GAM) and compare their performance in terms of classification to those of logit model traditionally used in banks. Our results show that SVM are more effective if we only focus on the global prediction performance of the models. However, SVM models give lower sensitivities than logit and GAM models. In other words the predictions of SVM models on defaulted borrowers are not satisfactory as those of logit or GAM models. In the present state of our research, even GAM models have lower global prediction capabilities, we recommend these models that give more balanced sensitivities, specificities and performance prediction. This thesis is not completely exhaustive about the scoring techniques for credit risk management. By trying to highlight targeted credit scoring models, adapt and apply them on real mortgage data, and compare their performance through classification, this thesis provides an empirical and methodological contribution to research on scoring models for credit risk management.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-24T19:36:29Z No. of bitstreams: 1 lucascorreanettomachado.pdf: 1851458 bytes, checksum: 2a8b67f0adf8343c28d4e1121a757f6d (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-25T15:23:10Z (GMT) No. of bitstreams: 1 lucascorreanettomachado.pdf: 1851458 bytes, checksum: 2a8b67f0adf8343c28d4e1121a757f6d (MD5) / Made available in DSpace on 2017-04-25T15:23:10Z (GMT). No. of bitstreams: 1 lucascorreanettomachado.pdf: 1851458 bytes, checksum: 2a8b67f0adf8343c28d4e1121a757f6d (MD5) Previous issue date: 2013-11-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta uma técnica para treinamento de Redes Neurais Artificiais (RNA), capaz de obter os parâmetros da rede através dos dados disponíveis para treinamento, sem necessidade de estabelecer a arquitetura da rede a priori, denominado Método de Segmentações Geométricas Sucessivas (MSGS). O MSGS agrupa os dados de cada classe em Hipercaixa (HC) onde cada caixa é alinhada de acordo com os eixos de maior distribuição de seu conjunto de pontos. Sendo as caixas linearmente separáveis, um hiperplano de separação é identificado originando um neurônio. Caso não seja possível a separação por um único hiperplano, uma técnica de quebra é aplicada para dividir os dados em classes menores para obter novas HCs. Para cada subdivisão novos neurônios são adicionados à rede. Os resultados dos testes realizados apontam para um método rápido e com alta taxa de sucesso. / This work presents a technique for Artificial Neural Network (ANN) training, able to get the network parameters from the available data for training, without establishing the network architecture a priori, called Successive Geometric Segmentation Method (SGSM). The SGSM groups the data of each class into hyperboxes (HB) aligned in accordance with the largest axis of its points distribution. If the HB are linearly separable, a separating hyperplane may be identified resulting a neuron. If it is not, a segmentation technique is applied to divide the data into smaller classes for new HB. For each subdivision new neurons are added to the network. The tests show a rapid method with high success rate.

We study a multivariate version of the Bernstein–Sato polynomial, the so-called Bernstein–Sato ideal, associated to an arbitrary factorization of an analytic germ <i>f - f</i>₁···<i>f</i>_r. We identify a large class of geometrically characterized germs so that the <i>D</i>_X,x[<i>s</i>₁,...,<i>s</i>_r]-annihilator of <i>f</i>^s₁¹···<i>f</i>^s_r^r admits the simplest possible description and, more-over, has a particularly nice associated graded object. As a consequence we are able to verify Budur’s Topological Multivariable Strong Monodromy Conjecture for arbitrary factorizations of tame hyperplane arrangements by showing the zero locus of the associated Bernstein–Sato ideal contains a special hyperplane. By developing ideas of Maisonobe and Narvaez-Macarro, we are able to find many more hyperplanes contained in the zero locus of this Bernstein–Sato ideal. As an example, for reduced, tame hyperplane arrangements we prove the roots of the Bernstein–Sato polynomial contained in [−1,0) are combinatorially determined; for reduced, free hyperplane arrangements we prove the roots of the Bernstein–Sato polynomial are all combinatorially determined. Finally, outside the hyperplane arrangement setting, we prove many results about a certain <i>D</i>_X,x-map ∇_<i>A</i> that is expected to characterize the roots of the Bernstein–Sato ideal.