FCT: DM - Teses de Doutoramento
URI permanente para esta coleção:
Navegar
Entradas recentes
- AITP Methods for Maximizing Generality and Tractability of Classes of AlgebrasPublication . Araújo, Gonçalo Gomes; Araújo, JoãoThis thesis was motivated by the search for new classes of algebras that maximize both generality (the class contains many important examples) and tractability (the class allows for deep structural theorems), combining algebra, automated reasoning, and large-scale computation. A database of nearly 500 classes of algebras was autoformalized from the literature and organized as a partially ordered set of inclusions. More than 80,000 theorems were proved with automated theorem provers, many requiring non-trivial proofs. The work also produced dozens new GAP packages. In the process, group-theoretic constructions such as verbal and marginal subgroups were extended to inverse semigroups and related structures, yielding new theorems. The methods developed show how autoformalization and database techniques can generate new algebraic classes and enable property transfer between them. The work toward the original goal—identifying classes that maximize generality and depth—is more than half complete, and we expect that this goal will soon be achieved, opening one or more new areas of mathematics.
- A CLASSIFICATION METHOD BASED ON A CLOUD OF SPHERESPublication . Dias, Tiago Melo; Amaral, PaulaThe contemporary landscape of machine learning is defined by a persistent trade-off between the predictive power of complex, opaque models and the transparency of simpler, often less flexible ones. While deep neural networks and large ensemble methods achieve state-of-the-art performance, their "black-box" nature presents a significant barrier to their adoption in high-stakes domains such as finance, medicine, and autonomous systems, where trust, fairness, and accountability are paramount. This thesis confronts this chal- lenge directly, proposing, formalising, and evaluating a novel geometric classifier – the Connected Cloud of Spheres Problem (CCSP) – as a method that intrinsically balances predictive power with structural transparency. The core philosophy is that it is possible to construct a classifier that is both sufficiently flexible to model complex, non-linear decision boundaries and sufficiently simple to be inherently interpretable, without resorting to post-hoc explanation techniques. The research begins by situating the CCSP within the broader context of supervised classi- fication, identifying a conceptual gap for models that can provide non-linear separability directly in the original feature space. The fundamental idea of the CCSP is to distinguish a target class by enclosing all of its data points within a collection of overlapping hyper- spheres. This "cloud" must form a single, connected geometric object, ensuring the model learns a coherent region for the target class. This approach provides a transparent and intuitive representation of the class boundary, where the final model is simply the set of centres and radii of the constituent hyperspheres. The theoretical foundations of the CCSP are established through a rigorous mathematical treatment. We develop three distinct mixed-integer non-linear programming (MINLP) formulations to capture the problem’s logic. The baseline model enforces the three core principles of coverage, exclusion, and connectedness. This is extended to a hard-margin (HM-CCSP) formulation, which integrates the principle of margin maximisation from Support Vector Machines (SVM) to create a more robust and generalisable classification boundary. Recognising that real-world data is rarely perfectly separable, we further de- velop a soft-margin (SM-CCSP) model, which introduces slack variables to provide the necessary flexibility to handle noisy datasets and class overlap, making the approach viable for practical applications. A key theoretical contribution of this work is the formal proof that the CCSP is a universal classifier. Through a constructive proof by mathematical induction, we demonstrate that a feasible CCSP solution is guaranteed to exist for any finite, disjoint sets of points. This result provides a strong theoretical assurance that the method’s hypothesis space is sufficiently expressive to model arbitrarily complex decision boundaries. Furthermore, we explore the unique properties of the CCSP as a model-intrinsic outlier detection method, proposing a set of formal conditions based on intra-hypersphere population density and inter-hypersphere distances to signal po- tential anomalous data points within the training set, thereby enhancing the model’s interpretability. While the MINLP formulations provide a precise definition of the problem, their hard nature makes them computationally intractable for datasets of realistic size. The second major contribution of this thesis is therefore the development and evaluation of practical solution methods. We address the computational bottleneck by designing and testing three constructive heuristic algorithms. The first, a Greedy Local Connectivity (GLC) heuristic, preserves the cloud’s connectedness property at every step. We then introduce two more effective variants: a Greedy Global Connectivity (GGC) heuristic that prioritises global coverage before enforcing connectivity at the end of the process, and a Furthest Point Seeding (FPS) heuristic that simplifies the search for new hyperspheres. To validate these practical approaches, we conducted a computational study on twelve benchmark datasets from the machine learning literature. The performance of the three heuristics was compared against established classification algorithms, including Logistic Regression, Support Vector Machines, and Random Forest. The empirical results demon- strate the viability and competitiveness of the CCSP framework. The novel heuristics, particularly the GGC, achieve performance comparable to the benchmark models. These findings validate the heuristic design principle that delaying the enforcement of the con- nectivity constraint can lead to more effective and parsimonious geometric solutions. Finally, this thesis critically reflects on the limitations of the proposed methods and outlines prioritised directions for future research. The primary debility of the exact MINLP models is their computational complexity, which could be addressed by exploring advanced techniques such as symmetry-breaking constraints. The proposed heuristics, while effective, are not guaranteed to be optimal, suggesting an opportunity for more sophisticated meta-heuristic search strategies. Key avenues for future work include a deeper, formal analysis of the CCSP’s interpretability; the generalisation of the model to use ellipsoids, which could provide a better fit for anisotropic data distributions; and the development of a formal method to identify the CCSP’s equivalent of "support vectors" – the critical data points that define the final decision boundary. In conclusion, this thesis introduces, rigorously defends, and evaluates the Connected Cloud of Spheres Problem as a novel and powerful paradigm for supervised classifi- cation. By grounding the classification task in intuitive computational geometry, the CCSP provides a compelling alternative to opaque, black-box models. The mathematical formulations, theoretical proofs, and heuristic evaluations presented herein collectively demonstrate that it is possible to build a classifier that is both flexible enough to model complex data and transparent enough to be understood. It is our hope that the work and future research directions outlined in this thesis will contribute to the ongoing and critical effort to build more trustworthy, accountable, and interpretable artificial intelligence.
- Commuting graphs of semigroupsPublication . Paulista, Tânia Patrícia Lopes; Malheiro, António; Cain, AlanGrafos comutativos são grafos simples construídos a partir de semigrupos e que descrevem a comutatividade de elementos. Estes grafos têm sido úteis em teoria de grupos, o que se deve à relação entre a estrutura combinatória do grafo comutativo de um grupo e a estrutura algébrica do grupo. Apesar de grafos comutativos de grupos terem sido amplamente estudados, o mesmo não tem acontecido com grafos comutativos de semigrupos (não-grupos) — desta forma, o objetivo desta tese é aprofundar o conhecimento destes grafos. Consideramos três perspetivas diferentes no estudo de grafos comutativos de semigrupos. Primeiro, investigamos os grafos comutativos de três importantes semigrupos (nãogrupos) — nomeadamente, o semigrupo de transformações, o semigrupo de transformações parciais e o semigrupo de relações binárias — e determinamos algumas das suas propriedades (tais como diâmetro, número de clique, cintura, grau de malha). Também descrevemos os maiores subsemigrupos comutativos de certos tipos do semigrupo de transformações (respetivamente, semigrupo de transformações parciais). De seguida passamos para construções de semigrupos: consideramos uniões-zero, produtos diretos, semigrupos de matrizes de Rees sobre grupos e semigrupos de matrizes de Rees com 0 sobre grupos. Determinamos várias propriedades dos grafos comutativos destas construções de semigrupos (diâmetro, número de clique, cintura, número cromático, grau de malha) e estabelecemos, quando possível, relações entre as propriedades do grafo comutativo da construção de semigrupos e as propriedades dos grafos comutativos dos semigrupos originais. Finalmente, focamo-nos nas propriedades de grafos comutativos de semigrupos de diferentes classes. Investigamos os valores possíveis para o diâmetro, número de clique, cintura, número cromático e grau de malha do grafo comutativo de um semigrupo completamente simples, de um semigrupo completamente 0-simples, de um semigrupo inverso ou de um semigrupo completamente regular.
- Constrained Multiobjective Derivative-free OptimizationPublication . Silva, Everton José da; Custódio, AnaThe present work focus on multiobjective derivative-free optimization, proposing strate- gies to address constrained problems. For that, a direct multisearch method that combines a filter-based strategy with an inexact restoration phase, DMS-FILTER-IR, was developed. In this approach, feasibility is treated as an additional component of the objective function that must be minimized. The inexact restoration step attempts to generate new feasible points, thereby prioritizing feasibility, a requirement for the strong performance of any filter approach. Theoretical results are provided, analyzing the different types of sequences of points generated by the new algorithm, and numerical experiments on a set of nonlinearly constrained biob- jective problems are reported, stating the good algorithmic performance of the proposed approach. The filter approach reformulates the original problem by aggregating the constraint violations into an additional objective function component, thereby increasing the number of objectives by one. From a theoretical point of view, DMS-FILTER-IR was developed for continuous constrained multiobjective optimization with an arbitrary number of objectives. However, when the original problem has three or more objectives, the increase of this number caused by the use of the filter, originates a many-objective optimization problem. Thus, strategies to address many-objective optimization problems are also investigated. Based on reduction approaches, employing correlation or sketching techniques, we propose a new variant of DMS, namely DMS-Reduction. This reduction method aims to tackle large problems by decreasing both the number of objective function components and the number of problem variables. Reducing the number of components of the objective function to be optimized at each iteration, has the additional benefit of potentially conducting to a reduction in the number of variables to be optimized, since there could be the case that not all variables are related to the objective function components selected. We detail the proposed algorithm and report a large set of numerical experiments that demonstrate the potential of this approach in addressing many-objective optimization problems. A different way of addressing constraints is resorting to penalization techniques. We investigate the use of a logarithmic barrier technique, both in single and multiobjective derivative-free optimization. For single-objective optimization, we propose the joint use of a mixed penalty-logarithmic barrier method and direct search. A merit function is employed in which the set of inequality constraints is divided into two groups: one is treated with a logarithmic barrier approach, while the other, together with the equality constraints, is addressed using a penalization term. This strategy is incorporated into a generalized pattern search method, enabling the effective handling of general nonlinear constraints. Convergence to KKT-stationary points is established under continuous differ- entiability assumptions, without requiring any form of convexity. Numerical experiments demonstrate the robustness, efficiency, and overall effectiveness of the proposed method, when compared with state-of-the-art solvers. The logarithmic barrier approach is then ex- tended to the multiobjective setting via LOG-DMS, demonstrating improved exploration of the Pareto front under inequality constraints. Comparative experiments indicate that LOG-DMS outperforms traditional DMS and DMS-FILTER-IR in terms of hypervolume metrics. Overall, the contributions of this thesis not only advance the theoretical understanding of constrained derivative-free optimization methods but also provide practical, competitive algorithms for solving optimization problems.
- A Spherical Support Vector Machine for Classical and Interval-valued DataPublication . Malha, Rui Jorge Fernandes; Amaral, PaulaThe application of automatic classification methods has significantly advanced real-time fraud detection and anomaly monitoring, streamlined and modernized administrative pro- cesses, and supported decision-making across various domains. Despite these advantages, it is crucial to acknowledge the inherent risks of using these methods as "black boxes" that operate without sufficient scrutiny or interpretability. Support Vector Machines (SVM) offer a more transparent alternative compared to techniques like deep neural networks and random forests. This study aims to harness the potential of SVMs while avoiding the complexity introduced by kernel functions, thus preserving the classification model within the original feature space and minimizing excessive parameter tuning. In the classical SVM approach, the separation between classes is determined by a hyperplane. Recently, generalizations of this concept have emerged, incorporating non- linear separations through kernel functions or alternative schemes, such as non-linear functions and polytopes. In this work, we propose a generalization of the SVM method, where the separator is a curve with a spherical shape. However, key SVM principles, such as margin maximization and the use of soft margins, are retained. We model this spherical classification method as a quadratic optimization problem and introduce a linear relaxation. These models were applied to classical data sets available from a benchmark repository. Furthermore, we extend this approach to interval-valued data, within the framework of Symbolic Data Analysis (SDA). In Symbolic Data, features are represented by sets, intervals, or histograms, rather than conventional data arrays, an approach that has gained increasing relevance, particularly in the era of Big Data. As with the classical case, a relaxation is also presented for interval-value data. The performance of these formulations was tested against traditional classification methods, yielding highly positive results. This demonstrates the potential of the proposed approach for enhancing classification accuracy and interpretability, particularly in complex data scenarios.
- Therapeutic deep eutectic systems as promising selective therapeutic agents in the anticancer battlePublication . Oliveira, Filipe Silva Nunes de; Duarte, Ana; Chan, AlanIn the pursuit of overcoming modern medicine most highly demanding challenges, we keep on seeking innovative therapeutics to unravel the complexity lying at the intersection of sci- ence, health, and sustainability. Considering cancer is the second leading cause of death world- wide, and colorectal cancer (CRC) is among the most incident and deadliest, while conventional therapeutics lack on selectiveness with consequent undesired side-effects. It was the main aim of this thesis to design a selective anti-CRC agent which could also be aligned with pharma- ceutical industry sustainable goals. Following eutectic systems spotlight from their remarkable physicochemical and biological properties, it was herein sought to push forward their reported promising cytotoxicity towards cancer cells, by unravelling eutectics specific interaction with CRC cells. For that, a library of therapeutic deep eutectic systems (THEDES) based on the com- bination of a terpene with an anti-inflammatory drug, was created embodying liquid formula- tions that could leverage both individual components inherent therapeutical traits. Subse- quently, an integrated approach was employed for evaluating THEDES effect on several indi- cators of potential therapeutic value towards CRC. In a first step, combining Me:Ibu (3:1), Thy:Ibu (3:1), POH:Ibu (3:1), POH:Ibu (8:1), Lim:Ibu (4:1) and Lim:Ibu (8:1), revealed promising anti-CRC effect since eutecticity promoted an increase in API bioavailability, control of ROS production, and cell dead induction via apoptosis. Secondly, THEDES specific interaction with CRC cellular endo and exometabolome, revealed alterations on their metabolite landscape with deleterious effect on essential metabolic pathways, as lipid and anaerobic glycolysis energy production pathways. Subsequently, from an in vivo systemic toxicity preliminary assessment considering a Zebrafish animal model, was observed non-relevant toxicity of these THEDES within their therapeutic window concentration range. Finally, a controlled drug delivery system based on liposomes (LPS) was developed foreseeing THEDES therapeutic further application. LPS with particle size within the range of 200 nm, monodispersed and with negative homoge- neous zeta potentials were obtained, revealing 27% of Me:Ibu (3:1) encapsulation efficiency. In summary, this work aimed to provide a better understanding on THEDES, combining Ibu with terpenes, specific anticancer activity, while deploying optimized methodologies for an overall better understanding of eutectics anticancer activity, attempting to push forward the estab- lishment of such systems as an alternative or complementary therapeutic agent towards CRC.
- Trust-region Methods for Multiobjective Derivative-free OptimizationPublication . Mohammadi, Aboozar; Custódio, Ana LuísaMultiobjective optimization is an interdisciplinary field with diverse applications in science, engineering, environment, finance, medicine, and many other domains. As objective function components often conflict with each other, finding a single point that simultaneously minimizes all function components becomes impossible. Instead, the solution lies in the Pareto front, which represents a set of nondominated points. This thesis proposes an algorithmthatemploys a trust-region approach to approximate the set of Pareto critical points in multiobjective optimization problems. Initially, the algorithm utilizes derivative information from the objective function to compute Taylor models that provide approximations for the different components of it. Subsequently, the algorithm will be adapted to handle multiobjective derivative-free optimization problems, where derivative information is not accessible. The primary objective of this algorithm is to achieve a comprehensive, densely populated, and uniformly distributed approximation of the complete Pareto front. This is accomplished through an iterative process consisting of two main steps: the extreme point step and the scalarization step. These steps are performed alternately throughout the algorithm’s execution. During the extreme point step, the algorithm expands the approximation to the Pareto front by moving towards its extreme points. These extreme points correspond to the individual minimization of each objective function component. On the other hand, the scalarization step focuses on reducing gaps along the Pareto front by solving suitable scalarization problems. The scalarization step incorporates a pivotal additional step, referred to as the middle point step. This step plays an important role in determining the initial points for solving the scalarization problems. The significance of this step in ensuring the high performance of the algorithm is substantiated through numerical results. The algorithm proposed in this thesis incorporates a meticulous approach to managing the limited evaluations of objective functions. It is specifically designed to address scenarios where the evaluation of objective functions is computationally expensive and the budget for such evaluations is restricted. This approach maximizes the quality of the obtained approximation to the Pareto front, allowing for a more accurate representation of the optimal trade-off solutions in multiobjective optimization problems with expensive and limited function evaluations. The thesis provides a detailed and comprehensive analysis of the convergence properties of the proposed method under the scenario where derivative information of the objective function is available and utilized. The analysis aims to thoroughly understand and evaluate the behavior of the algorithm as it iteratively advances toward the Pareto critical points during the optimization process. The results of numerical experiments are reported, to illustrate the effectiveness and robustness of the proposed approach. These experiments are designed with two main purposes. The first goal is to demonstrate the essentiality of each key algorithmic feature in achieving optimal performance by this approach. Secondly, the performance of this algorithm is compared against a state-of-the-art multiobjective derivative-based optimization solver, which inherently attempts to generate approximations of the complete Pareto front for a given problem. In the second phase of the thesis, following the initial algorithm, we further modify it to compute an approximation of the complete Pareto front in multiobjective derivativefree optimization problems. In this scenario, the objective functions are assumed to be expensive black-box functions, where derivatives are not available and cannot be estimated. The modified algorithm is specifically adapted to fully accommodate the absence of derivatives. To approximate the objective function components, the modified algorithm incorporates various strategies to navigate the challenges posed by the absence of derivatives. It employs a technique based on polynomial interpolation and minimum Frobenius norm approaches to compute high-quality models that approximate the objective function components. The convergence analysis for the derivative-free version of the algorithm is conducted. Extensive efforts are devoted to examining the convergence properties of the algorithm, specifically considering the challenge of lacking derivative information. Detailed numerical results are presented, demonstrating the notable performance of the modified algorithm compared to state-of-the-art multiobjective derivative-free optimization solvers, which also aim to approximate complete Pareto fronts.
- On Voevodsky and Farrell-Jones conjecturesPublication . Reis, José Francisco de Vasconcelos Teodósio Nunes dos; Tabuada, GonçaloThis thesis consists of two parts. In the first part we improve the Voevodsky nilpotence conjecture, a problem on algebraic geometry. In the second part we improve the Farrell- Jones isomorphism conjecture, a problem on algebraic topology. The Voevodsky nilpotence conjecture claims that the nilpotence and the numerical equivalence relations on the algebraic cycles of a smooth proper scheme agree. Bernardara- Marcolli-Tabuada generalized this problem to the setting of differential graded categories and showed that this conjecture holds for certain quadric fibrations, intersections of quadrics, linear sections of Grassmannians and of determinantal varietie and Moishezon manifolds. Later on, Ornaghi-Pertusi showed that the conjecture holds for cubic fourfolds and for Gushel-Mukai fourfolds. Working on this setting of differential graded categories, we refine these results by showing that the algebraic and the numerical equivalence relations also agree for those cases. Moreover,wework withquotients between equivalence relations. This allows us not only to obtain a refinement of the aforementioned results but also to compute, for example, the quotient between the rational and the algebraic equivalence relations of certain five-folds. These results lead to preprint [74]. The Farrell-Jones isomorphism conjecture is a local-to-global statement that claims that the algebraic 𝐾-theory of a group ring 𝑅𝐺, where 𝑅 stands for a commutative ring, is completely determined by the algebraic 𝐾-theory of the group rings 𝑅𝑉 with 𝑉 a virtually cyclic subgroup of 𝐺. This important conjecture simplifies the computation of the algebraic 𝐾-theory of a group ring. Following the approach of Bunke-Kasprowski-Winges, we work on a generalized version of the Farrell-Jones isomorphism conjecture that is stated in the setting of ∞-categories. Using tools from the theory of noncommutative motives we were able to show that the Farrell-Jones isomorphism conjecture holds, under certain conditions, for finitary localising invariants. This result lead to the publication [75].
- On Notions of ProvabilityPublication . Santos, Paulo Guilherme Domingos Canha Moreira dos; Kahle, Isabel; Kahle, ReinhardIn this thesis, we study notions of provability, i.e. formulas B(x,y) such that a formula ϕ is provable in T if, and only if, there is m ∈ N such that T ⊢ B(⌜ϕ⌝,m) (m plays the role of a parameter); the usual notion of provability, k-step provability (also known as k-provability), s-symbols provability are examples of notions of provability. We develop general results concerning notions of provability, but we also study in detail concrete notions. We present partial results concerning the decidability of kprovability for Peano Arithmetic (PA), and we study important problems concerning k-provability, such as Kreisel’s Conjecture and Montagna’s Problem: (∀n ∈ N.T ⊢k steps ϕ(n)) =⇒ T ⊢ ∀x.ϕ(x), [Kreisel’s Conjecture] and Does PA ⊢k steps PrPA(⌜ϕ⌝)→ϕ imply PA ⊢k steps ϕ? [Montagna’s Problem] Incompleteness, Undefinability of Truth, and Recursion are different entities that share important features; we study this in detail and we trace these entities to common results. We present numeral forms of completeness and consistency, numeral completeness and numeral consistency, respectively; numeral completeness guarantees that, whenever a Σb 1(S12 )-formula ϕ(⃗x ) is such that ⃗Q ⃗x .ϕ(⃗x ) is true (where ⃗Q is any array of quantifiers), then this very fact can be proved inside S12 , more precisely S12 ⊢ ⃗Q ⃗x .Prτ (⌜ϕ( •⃗ x )⌝). We examine these two results from a mathematical point of view by presenting the minimal conditions to state them and by finding consequences of them, and from a philosophical point of view by relating them to Hilbert’s Program. The derivability condition “provability implies provable provability” is one of the main derivability conditions used to derive the Second Incompleteness Theorem and is known to be very sensitive to the underlying theory one has at hand. We create a weak theory G2 to study this condition; this is a theory for the complexity class FLINSPACE. We also relate properties of G2 to equality between computational classes.
- Iberian Energy Market: Spot Price Forecast by Modelling Market OffersPublication . Pinhão, Miguel Filipe de Sousa Varinhos; Fonseca, Miguel; Covas, RicardoElectricity is a very special commodity since it is economically non-storable, and thus requiring a constant balance between production and consumption. At the corporate level, electricity price forecasts have become a fundamental input to energy companies’ decision making mechanisms [22, 45]. Electric utilities are higly vulnerable to economical crisis, since they generally cannot pass their excess costs on the wholesale market to the retail consumers [77] and, since the price depends on variables like weather (temperature, wind speed, precipitation, etc.) and the intensity of business and everyday activities (on-peak vs. off-peak hours, weekdays vs. weekends, holidays and near-holidays, etc.) it shows specific dynamics not observed in any other market, exhibiting seasonality at the daily, weekly and annual levels, and abrupt, short-lived and generally unanticipated price spikes. These extreme price volatility make price forecasts from a few hours to a few months ahead to become of particular interest to power portfolio managers. An utility company or large industrial consumer who is able to accurately forecast the wholesale prices and it’s volatility, can adjust its bidding strategy and its own production/consumption schedule in order to reduce the risk or maximize the profits in day-ahead trading. In this work I discuss the dynamics of the Iberian electricity day-ahead market (OMIE), review the state-of-the-art forecasting techniques and introduce a new approach to Electricity Price Forecasting, by forecasting the underlying dynamics, the market demand/supply curves. With this method it is possible to predict not only the electricity prices for the next hours, but also the market curves, which can then be used for risk management and a more accurate schedule of generation units. I analyze the model results and benchmark them against other models in the industry.