Allmän information om examensarbetet på studentwebben

Specifik information för ämnesvalet matematik

Optimeringslära och systemteori

Optimeringslära och systemteori är ett tillämpat matematiskt ämne som omfattar teori, modeller och metoder för optimering samt systemteoretiska aspekter inom ämnen som biologi, maskinteknik, reglerteknik, robotik, signalbehandling, maskininlärning och AI.

Vårens projektarbete i optimeringslära och systemteori

I VT25 kommer vi att erbjuda följande projekt (OBS listan håller på att uppdateras och det kan komma ett/två projekt till)

• Handelsresandeproblemet
En handelsresande ska besöka ett antal städer men vill minimera den totala sträckan för att besöka alla städer och komma tillbaka hem. Problemet kallas handelsresandeproblemet och är en klassiker inom optimering. Det finns många metoder för att lösa problemet exakt eller approximativt. Projektet går ut på att jämföra olika sådana metoder. Utgångspunkten skulle vara två vanliga formuleringar av problemet och även använda plansnittsmetoder i en modern optimeringslösare. Det går att utöka projektet genom att titta på heuristiker eller mer avancerade exakta lösningsmetoder. 
Rekommenderade förkunskaper: SF1811/SF1861 Optimeringslära


• Hur kan optimering användas för att bidra till klimatomställningen?
Optimering används inom många områden. Ett särskilt aktuellt område just nu är klimatomställning. Arbetet syftar till att hitta konkreta exempel där optimering används för klimatomställning. Eventuellt kan någon enkel egen modell sättas upp.

Förra året gjordes ett projekt inriktat mot vattenkraftoptimering under detta tema.


• Platsallokering på tåg
Tänk dig att du driver en tåglinje där resenärerna måste reservera sin plats. Resenärerna kan resa olika sträckor, vilket gör att du behöver kunna placera de på ett sätt i tåget så alla kan få en sittplats. Om man vet hur många som vill resa mellan varje station kan man formulera platsallokeringen som ett optimeringsproblem och lösa det för att hitta sättet som gör att flest personer kan resa med tåget (eller någon annan målfunktion). Projektet skulle alltså gå ut på att formulera en modell för ett sådant problem, lösa problemet med lämplig programvara och redovisa lösningen. Projektet kan utökas genom att till exempel jämföra olika formuleringar av problemet, göra modellen mer verklighetstrogen eller försöka hitta bra lösningar till stora instanser av problemet som inte kan lösas exakt.
Rekommenderade förkunskaper: SF1811/SF1861 Optimeringslära


• Formation control based on agents inherent interaction
Formation control in multi-agent system which aims to achieve various formation patterns by designing control strategy attracts more and more researchers' attention. Most formation control strategies use position error in the performance index. Howevr, in many cases the position error is not measurable. Thus we aim to design a formation control strategy that does not rely on position error, but use the inherent interaction of agents. In this project, we will: 1)introduce quadratic optimal control and review formation control, 2 build the control model using quadratic optimal control, 3 simulate different formation by changing the parameters


• Forward and Inverse Optimal Control: From Defining Objectives to Learning from Behavior
Inverse optimal control (IOC) is a mathematical approach aimed at determining the underlying objective or cost function that governs an agent's observed behavior, particularly in dynamical systems. In contrast to traditional optimal control, where the goal is to minimize or maximize a predefined cost function, IOC works in reverse, inferring the cost function based on observed optimal behavior. In many real-world applications, such as robotics, the true objective driving an agent's actions is often unknown or difficult to model. By observing the actions taken by an autonomous system, IOC seeks to uncover this hidden objective. In this project, we will: (1) introduce the traditional optimal control; (2) learn the mathematical principles behind Inverse Optimal Control; (3) apply them to simple control systems, such as a wheeled robot.


• Optimal strategies for the pursuit-evasion problem of robots
Pursuit-evasion is ubiquitous in nature with great appeal to researchers for a long history from many disciplines, e.g., mathematics, engineering, and biology. It has received much attention from perspectives of, for instance, game theory, area defense, sport, and aircraft control. In this project, we study the pursuit-evasion problem of multiple robots and try to find the optimal strategies for both the pursuers and the evaders. Then, we analyze how the parameters of the strategies impact the result. We then use simulation to verify the effectiveness of the strategies.


• Breaking Feedback Loops in Recommender Systems
Recommender systems play an increasingly important role in modern web ecosystems. These systems are deployed in dynamic environments, where at each step, the recommender system first provides recommendations to users and collects their feedback data. In the next step, it re-learns user preferences based on this feedback and provides new recommendations. Throughout this process, these two steps alternate, creating a feedback loop. The existence of this feedback loop means that the user data used for learning exhibits non-independent stationary properties, which may lead to biased estimates of user preferences by traditional learning algorithms, thereby affecting the quality of recommendations. In this project, we focus on utilizing causal inference methods to break this feedback loop, developing learning algorithms for recommendation systems under non-independent stationary data, and evaluating the recommendation quality of these algorithms.


• On the simplex method and the interior-point method for linear programming
A classical method for solving linear programming problems is the simplex method. This method has the drawback that there is (yet) no variant known that does not admit exponential running time in the worst case even if it usually runs in polynomial time. An efficient competitor for the simplex method, whose generalization is also used for non-linear programming, is the interior-point method, with a proven (weakly-)polynomial worst-case running time. Both methods have their strengths, and they generate their solution in an inherently different way, with the simplex method traveling through potential optimal solutions and the interior-point method aggregating the whole global picture and traveling through the interior of the feasible set.

In this project, you will study both methods and compare their behavior from both a theoretical and a practical point of view using your own implementation of the two methods in a suitable programming language. Suggested directions are to study the 'crossover' between the simplex method and the interior-point method to get a vertex solution for the latter as well, to explore different variations of the method (pivoting rules and primal versus primal-dual) on a dataset of test problems or to look at pathological examples for one method and see if the other method can handle this better. It is strongly advised to have taken a basic course in optimization (e.g. SF1811 or SF1861).


• Optimering av lagerhållningssystem för varor med bäst före datum
Om man vill hålla nere kostnaderna för lagerhållning och minska svinnet så krävs planering vid beställning av nya varor och en god kännedom om efterfrågan.    Vi vill studera en enkel modell och se på effekterna av kundbeteende och prissättning.  


• Hybrid Modeling for Parameters Tuning and Optimizing 
Hybrid modeling refers to integrating the physical principles of a system with data-driven models to more accurately describe its behavior in different scenarios. In many industrial applications, such as the comfort stopping of electric vehicles, parameters are often grounded in practical physical realities. Additionally, system dynamics frequently involve multiple interrelated factors, and the behavior of these factors often exhibits high complexity and nonlinear characteristics. Therefore, it is essential to develop parameter tuning and optimizing methods that are both interpretable and adaptable. In this project, we first analyze key parameters influencing comfort stopping, such as suspension stiffness, road conditions, vehicle load, etc., and then use basis function interpolation or machine learning methods like CNN and MLP to establish the relationship between these parameters and the output variable. Finally, we can verify the results of parameter tuning and optimize through simulation.


• Replication-robust Profit Allocation for Data Exchange in ML
The increasing prevalence of ML models in industry applications has necessitated the formation of Data Markets that can facilitate the exchange of high-quality data between data sellers and buyers. These markets must in turn evaluate the importance of a particular seller's data in order to allocate a proportional reward to each seller. Methods that allocate rewards based on cooperative game theory (such as the Shapley value) have been proposed as a measure of a dataset's contribution toward a model's performance, but it is not clear whether they remain suitable in the presence of malicious participants. This project will examine a more general family of solution concepts, collectively known as semivalues, and will characterize those semivalues that are robust toward strategic participants that can decide to replicate their data. Specifically, you will focus on (1) sufficient and necessary conditions for semivalues to be robust against replication, (2) design an optimal semivalue for data exchange markets, and (3) implement established and designed solution concepts in the programming language of your choice.


• Cluster detection in the neuronal network of a worm
Various complex systems can be represented using graphs, which then can be analyzed to further explore their properties. One of such systems is a nervous system of the nematode worm C. elegans. In this project, the aim is to investigate the network representation of C. elegans worm and its structural properties. To do that we focus on detecting subgraphs with properties interesting in relation to nervous systems. 


• Formation control of unicycles
One of the fundamental tasks in multi-agent systems is formation control. The local interactions among individual agents, along with their prior knowledge of the desired formation, largely determine the formations that can ultimately be achieved. In this project, we investigate how to achieve certain formations for wheeled robots, which are described by a nonlinear unicycle model.


• Color transfer using optimal transport
The optimal transport problem consists of finding the most efficient way to move mass from one distribution into another, while minimizing a cost. This project aims to study its application to color transfer, a technique used in image processing where the color palette of one image (represented as a histogram in the three-dimensional RGB space), is adjusted to match the color distribution of another image. The resulting transportation problem is a large linear program, and different techniques based on linear and nonlinear programming can be examined to improve both the efficiency and the qualitative result of the solution.


• Network Flow Modeling for Multi-Class Vehicle Traffic
This project aims to study the network flow problem where the traffic of multiple vehicle types is modeled and efficiently routed from origin to destination. Each vehicle class may have distinct characteristics, such as speed, size, and road restrictions, leading to more challenging flow dynamics. The project will investigate different methods for solving this flow problem using linear and nonlinear programming, focusing on optimizing the traffic flow while considering vehicle class-specific constraints.


• Feature selection for cell development via sparsity promoting methods
Cell differentiation is a fundamental biological process. In this process immature stem cells are developed into specialized mature cells, and this process is determined by changes in the gene expression levels. Modern single-cell technologies can capture snapshots of the gene expression levels of developing cells. In this project we will explore sparsity promoting methods for identifying genes that are important for predicting cell fates of developing immune cells.


• Color transfer using optimal transport
The optimal transport problem consists of finding the most efficient way to move mass from one distribution into another, while minimizing a cost. This project aims to study its application to color transfer, a technique used in image processing where the color palette of one image (represented as a histogram in the three-dimensional RGB space), is adjusted to match the color distribution of another image. The resulting transportation problem is a large linear program, and different techniques based on linear and nonlinear programming can be examined to improve both the efficiency and the qualitative result of the solution.


• Network Flow Modeling for Multi-Class Vehicle Traffic
This project aims to study the network flow problem where the traffic of multiple vehicle types is modeled and efficiently routed from origin to destination. Each vehicle class may have distinct characteristics, such as speed, size, and road restrictions, leading to more challenging flow dynamics. The project will investigate different methods for solving this flow problem using linear and nonlinear programming, focusing on optimizing the traffic flow while considering vehicle class-specific constraints.

För att välja ett projekt med oss, maila jankr@kth.se, och skriv vilka projekt ni helst vill jobba med (första val, andra val, och tredjeval). Vi försöker alltid ge er ert första val (det lyckas ofta). Deadline för att skicka in önskemål om projekt är December 5:e.

Flera av projekten relaterar till befintlig forskning inom avdelningen och det finns i Stockholmsområdet ledande industri och forskningsföretag inom dessa tillämpningsområden. Andra projekt behandlar grundläggande matematiska problem inom ämnet vilka kan tillämpas inom många områden.

Projekten skall normalt genomföras i grupper om två studenter men det är även möjligt att arbeta individuellt. Vi kan också hjälpa er att hitta nån att jobba med. I en del projekt kan det finnas flera (2 eller 3) delprojekt. Samtliga projekt har en inläsningsdel och en problemlösningsdel. Inläsningsdelen är gemensam för alla grupperna i varje projekt medan problemlösningsdelen skall utföras självständigt inom de olika delprojekten.

Inläsningsdel

Projekten inleds med en inläsningsdel under LP3. Inläsningen av ämnet sker i form av en informell lärarledd studiecirkel, där deltagarna hjälps åt att lära sig den nödvändiga teorin. Denna delen av kursen avslutas med att studenterna i varje delprojekt presenterar sitt delproblem och sin arbetsplan för projektet. Detaljerna kring upplägget varierar lite grand mellan de olika projekten.

Problemlösningsdel

Problemlösningen utförs i huvudsak under LP4. Här skall grupperna självständigt arbeta med sina problem. Normalt träffas gruppen och lärarna en gång per vecka för att diskutera projektens status.

Kontaktpersoner

För frågor angående inriktningen mot optimeringslära och systemteori: Jan Kronqvist

Ungefärlig tidsplan för projektarbetet

• Januari: Arbetetet påbörjas med inläsning.
• Början av mars: Projektformuleringar och arbetsplan ska finnas färdiga.
• Mitten/slutet av mars: Studenten lämnar disposition och skelett till handledaren.
• Början av maj: Rapport lämnas till handledaren för granskning.
• Mitten/slutet av maj: Redovisning, plagiatgranskning och betygssättning.