Cette thèse s’inscrit dans le cadre de la conception, l’analyse et la mise en œuvre d’algorithmes efficaces et fiables pour la résolution de problèmes d’optimisation non linéaire avec contraintes. Nous présentons trois nouveaux algorithmes fortement primaux-duaux pour résoudre ces problèmes. La première caractéristique de ces algorithmes est que le contrôle des itérés s’effectue dans l’espace primal-dual tout au long du processus de la minimisation, d’où l’appellation “fortement primaux-duaux”. En particulier, la globalisation est effectuée par une méthode de recherche linéaire qui utilise une fonction de mérite primale-duale. La deuxième caractéristique est l’introduction d’une régularisation naturelle du système linéaire qui est résolu à chaque itération pour calculer une direction de descente. Ceci permet à nos algorithmes de bien se comporter pour résoudre les problèmes dégénérés pour lesquels la jacobienne des contraintes n’est pas de plein rang. La troisième caractéristique est que le paramètre de pénalisation est autorisé à augmenter au cours des itérations internes, alors qu’il est généralement maintenu constant. Cela permet de réduire le nombre d’itérations internes. Une étude théorique détaillée incluant l’analyse de convergence globale des itérations internes et externes, ainsi qu’une analyse asymptotique a été présentée pour chaque algorithme. En particulier, nous montrons qu’ils jouissent d’un taux de convergence rapide, superlinéaire ou quadratique. Ces algorithmes sont implémentés dans un nouveau solveur d’optimisation non linéaire qui est appelé SPDOPT. Les bonnes performances de ce solveur ont été montrées en effectuant des comparaisons avec les codes de références IPOPT, ALGENCAN et LANCELOT sur une large collection de problèmes. / This thesis focuses on the design, analysis, and implementation of efficient and reliable algorithms for solving nonlinearly constrained optimization problems. We present three new strongly primal-dual algorithms to solve such problems. The first feature of these algorithms is that the control of the iterates is done in both primal and dual spaces during the whole minimization process, hence the name “strongly primal-dual”. In particular, the globalization is performed by applying a backtracking line search algorithm based on a primal-dual merit function. The second feature is the introduction of a natural regularization of the linear system solved at each iteration to compute a descent direction. This allows our algorithms to perform well when solving degenerate problems for which the Jacobian of constraints is rank deficient. The third feature is that the penalty parameter is allowed to increase along the inner iterations, while it is usually kept constant. This allows to reduce the number of inner iterations. A detailed theoretical study including the global convergence analysis of both inner and outer iterations, as well as an asymptotic convergence analysis is presented for each algorithm. In particular, we prove that these methods have a high rate of convergence : superlinear or quadratic. These algorithms have been implemented in a new solver for nonlinear optimization which is called SPDOPT. The good practical performances of this solver have been demonstrated by comparing it to the reference codes IPOPT, ALGENCAN and LANCELOT on a large collection of test problems.

Abstract In our country thousands of disabled, chronically ill and other students with need for special support are living on the fringe of working life or completely outside of it. In order to improve possibilities to employ people with most minimal chances on the job market, apprenticeship training has been expanded. This term means vocational education that is based on a combination of learning on the job with theoretical learning according to the German model. This dissertation is a multidisciplinary research on the field of vocational special education and the sociology of education. The material consists of interviews, which were conducted in Finland and in Germany, with 30 students of working age with need for special support, who have already graduated or will be graduating with the help of apprenticeship. At the same time the educational systems of both countries are being analysed. The results show that in Germany apprenticeship has been continuously developed in cooperation with economy. Whereas in Finland vocational education has been built to an institutional system and the one mainly meant for students with need for special support has been conducted in a small-scaled experimental and evaluation activities. In Germany employers are required by law to employ people with an disability. This fact together with the firm position of apprenticeship gives studens with need for special support better chances than in Finland to find a full-time job on the open job market. Employing disabled people, who have completed apprenticeship training, as permanently unpaid employees poses a big problem both in Finland and in Germany. Most of the German interviewees had, however, found full-time employment after apprenticeship training, whereas in Finland part-time jobs prevail. Before and during the apprenticeship training the interviewees had been supported by families, support services and classmates. In their everyday life they perceive themselves as equal and integrated. Many of them are ambitious, successful people with an optimistic attitude towards life. Employment ensures them a structured everyday life, sufficient income and positive planning for the future. / Tiivistelmä Maassamme on tuhansia vammaisia ja pitkäaikaissairaita sekä muita erityisopiskelijoihin kuuluneita työelämän marginaalissa tai täysin ulkopuolella. Useat tahot ovat peräänkuuluttaneet vaikeimmin työllistyvien työvoiman käyttöönottoa lisäämällä oppisopimuskoulutusta eli työpaikalla oppimisen ja teoriaopiskelun yhdistelmään perustuvaa ammatillista koulutusta sen edelläkävijämaan, Saksan, malliin. Tutkimus on monitieteinen, ammatillisen erityisopetuksen ja kasvatussosiologian aloihin kuuluva. Aineiston muodostavat 30:n Suomessa ja Saksassa oppisopimuskoulutuksen avulla ammattiin valmistuneen tai valmistuvan erityisopiskelijan haastattelut sekä molempien maiden koulutusjärjestelmien kartoitukset. Haastattelut toteutettiin suomeksi, saksaksi sekä kummankin maiden viittomakielellä. Analyysimenetelmänä on sovellettu kolmivaiheista mallia sekä osittain narratiivista menetelmää. Teoreettinen viitekehys muodostuu vammaisuuden ja osallisuuden sekä hyvinvoinnin ja arjen subjektiivisten kokemusten määrittelyistä. Tulokset osoittivat, että Saksassa oppisopimuskoulutusta on kehitetty keskeytyksettä yhteistyössä maan työelämän kanssa. Ammatillinen koulutus, myös erityisopiskelijoiden osalta, tapahtuu siellä työpaikoilla. Suomessa taas ammatillista koulutusta on rakennettu laitosmaiseksi järjestelmäksi. Erityisopiskelijoiden oppisopimuskoulutus on ollut pienimuotoista kokeilu- ja kehittämistoimintaa. Saksassa työnantajien lakisääteinen velvoite työllistää vammaisia yhdessä koulutusmallin valta-aseman kanssa antaa erityisopiskelijoille paremmat mahdollisuudet kuin Suomessa työllistyä avoimille työmarkkinoille kokopäivätyöhön. Palkattoman avotyön käyttäminen oppisopimuskoulutuksen suorittaneiden vammaisten pysyvänä työllistämismuotona osoittautui molemmissa maissa ongelmaksi. Suurin osa haastatelluista oli kuitenkin sijoittunut koulutuksen jälkeen työsuhteeseen joko kokopäivä- ja erityisesti Suomessa osa-aikatyöhön. Ennen oppisopimuskoulutusta ja sen aikana haastatellut olivat saaneet tukea perheeltään ja koulutuksen tukipalveluilta sekä vertaisiltaan. He olivat arjen hyvinvoinnin kokemuksissaan yhdenvertaisia ja sosiaalisia. Monet olivat sisukkaita, valoisia onnistujia. Työ on heille tärkeä arjen jäsentäjä, tuo riittävän toimeentulon ja antaa mahdollisuuden tulevaisuuden myönteiseen suunnitteluun. / Zusammenfassung In unserem Land leben tausende von Behinderten und Langzeitkranken sowie andere der Sonderbetreuung bedürftige Auszubildende am Rande oder gänzlich außerhalb des Arbeitslebens. Viele Stimmen fordern für die schwersteinsetzbaren Gruppen verbesserte duale Ausbildungsmöglichkeiten. Dieser Begriff bezeichnet die berufliche Ausbildung, die nach dem deutschen Vorbild auf Lernen am Arbeitsplatz, kombiniert mit der theoretischen Ausbildung basiert. Die vorliegende Arbeit ist eine multidisziplinäre Studie auf dem Gebiet der beruflichen Sonderpädagogik und Bildungssoziologie. Die Materialgrundlage bilden insgesamt 30 Interviews, die sowohl in Deutschland als auch in Finnland mit Menschen mit besonderem Unterstützungsbedarf geführt wurden, deren berufliche Ausbildung im Rahmen eines dualen Ausbildungssystems stattfindet oder stattgefunden hat. Die Empirie wird mit einer Analyse der Bildungsysteme beider Länder kombiniert. Die Ergebnisse zeigen, dass in Deutschland das duale Ausbildungssystem kontinuierlich in Zusammenarbeit mit der Wirtschaft entwickelt wurde. In Finnland dagegen wurde die berufliche Ausbildung als ein institutionelles System konzipiert. Das duale Ausbildungssystem für die Auszubildenden mit besonderem Unterstützungsbedarf ist hauptsächlich kleinformatige Experimentier- und Entwicklungstätigkeit gewesen. In Deutschland sind die Arbeitgeber gesetzlich dazu verpflichtet, Behinderte zu beschäftigen. Zusammen mit der festen Verankerung des dualen Ausbildungsystems gibt dies den Auszubildenden mit besonderem Unterstützungsbedarf bessere Chancen als in Finnland, auf dem offenen Arbeitsmarkt eine Ganztagsbeschäftigung zu finden. Der größte Teil der Interviewten hat nach der dualen Ausbildung Arbeit als Ganztagsbeschäftigte gefunden, wobei in Finnland die Teilzeitbeschäftigung überwiegt. In beiden Ländern erwies sich aber der Einsatz dualausgebildeter Behinderter als unbezahlte Arbeitskräfte in Dauerbeschäftigung durchaus als Problem. Vor und während der Ausbildung erhielten die Interviewten Unterstützung von der Familie, Ausbildungsbegleitern und Mitschülern. Sie waren in ihren Alltagserfahrungen gleichwertig und integriert. Viele von ihnen waren Menschen mit positivem Lebensgefühl, strebsam und glücklich. Die Arbeit ermöglicht ihnen einen strukturierten Alltag, ausreichendes Einkommen und positive Zukunftsplanung.

Das Verbundsystem „Eliteschulen des Sports“ (EdS) wurde geschaffen, um schulpflichtige Nachwuchsathleten bei der Bewältigung ihrer „dualen Karrieren“ zu unterstützen. In aktuellen Evaluationsstudien wird den EdS diese duale Wirksamkeit jedoch teilweise abgesprochen. Festgemacht wird dies maßgeblich an outputorientierten Ergebnis-kriterien, wie der Anzahl an Schulabschlüssen oder Medaillen, die in erster Linie die Sichtweise von Geldgebern und Eigentümern repräsentieren. Dies hat zur Folge, dass die Strukturen und Prozesse, auf denen ein erfolgreicher Output basiert, genauso wenig berücksichtigt werden wie die subjektiven Anforderungen, die Nachwuchsathleten an dieses Fördersystem stellen. In der vorliegenden Arbeit wird daher im Rahmen dreier Untersuchungsabschnitte die subjektiv empfundene Zufriedenheit der jugendlichen Athleten mit den EdS in den Fokus der Betrachtung gerückt. Zur Analyse dualer Karrierebedingungen an den EdS wurden zunächst auf der Basis einer expertengestützten Delphi-Untersuchung (N = 40) 20 Qualitätskriterien dualer Unterstützungsleistungen an den EdS identifiziert. Darauf aufbauend wurde ein Erhebungsinstrument (AZ-EdS; N = 445) entwickelt und faktoranalytisch überprüft, das die individuellen Ansprüche der Athleten an die EdS in standardisierter Form erfasst. Dieses diente abschließend als Grundlage für eine Zufriedenheitsanalyse (N = 445) mit Sportschülern, in der die Schwachstellen des Fördersystems EdS aus der subjektiven Athletensicht identifiziert wurden. Es zeigte sich, dass die Athleten das Fördersystem insgesamt positiv beurteilen. Hierbei wird vor allem den Strukturen und Prozessen, die dem Ergebnis vorgelagert sind, erhöhte Wichtigkeit beigemessen. Es offenbart sich allerdings auch eine hohe Subjektivität bei der Zufriedenheitsbeurteilung, so dass durch die Athleteneinschätzung zwar kritische Handlungs-felder aufgedeckt werden können, weitergehende Analysen anhand objektiver Maßstäbe jedoch unumgänglich sind. / The German Elite Sport Schools (ESS) have been established to support the “dual career“ of junior athletes by offering school education and optimal training conditions. However, present evaluations of ESS argue that the aimed dual efficacy is not achieved. This efficacy is mainly determined by analysing output-based criteria out of a shareholder-perspective, such as completed graduations or medals won. Thus, the structures and processes, on which a high output is based, are not taken into account nor the individual demands of junior athletes regarding the dual promotional system. The present work is reacting on this situation by performing three empirical studies, which focus on the individual satisfaction of junior athletes in a holistic approach. At first, a Delphi-analysis was performed (N = 40) to identify 20 quality criteria of dual support at the ESS. These criteria were used to develop and validate a standardized questionnaire (AZ-EdS; N = 445) assessing the individual demands of junior athletes regarding the ESS. The questionnaire was used as a base to determine the athlete satisfaction with the ESS and, furthermore, to reveal the weak spots of that support system out of an athlete point of view (N = 445). The results show, that the athletes judge the support system as overall positive. An elevated importance is ascribed to the structures and processes that are a precondition for the results. However, the results also show a high subjectivity of athlete ratings. Thus, the athlete opinions can be used to reveal weak spots concerning the ESS, but further analyses using objective facts are inevitable.

Im ersten Teil der Arbeit werden die theoretischen Grundlagen zum dualen Prüfsystem in der Bundesrepublik Deutschland mit dem Schwerpunkt auf den Prüfbereich Wirtschafts- und Sozialkunde und den schriftlichen Prüfverfahren erörtert. Der anschließende empirische Teil gliedert sich in eine quantitative Dokumentenanalyse im Kapitel 3 und die qualitative Inhaltsanalyse von Experten-interviews im Kapitel 4. Durch die quantitative Datenerhebung werden einerseits Prüfungsaufgabensätze des Bereichs Wirtschafts- und Sozialkunde und anderer-seits Curricula, die dem Unterricht im Prüfbereich Wirtschafts- und Sozialkunde übergeordnet sind, hinsichtlich ihres inhaltlichen Gehaltes überprüft. Im Anschluss daran werden die Gegebenheiten im Wirtschafts- und Sozialkundeunterricht an sächsischen berufsbildenden Schulen mithilfe der Experteninterviews dargelegt. Das Kapitel fünf verbindet die erzeugten Aussagen aus den einzelnen empirischen Teilen und soll abschließend den Bezug zur These vom heimlichen Lehrplan herstellen. Im letzten Kapitel werden Empfehlungen formuliert, die die Situation der politischen Bildung in der beruflichen Bildung vor allem im Hinblick auf die schriftliche Abschlussprüfung im Bereich Wirtschafts- und Sozialkunde verbessern könnten.:Inhaltsverzeichnis 1 Einleitung 1 2 Das duale Prüfsystem der Bundesrepublik Deutschland 3 2.1 Allgemeine Rechtsgrundlagen 4 2.2 Zuständige Stellen im Prüfprozess 6 2.2.1 Neuregelungen im Berufsbildungsgesetz und deren Konsequenzen 7 2.2.2 Aufgabenerstellungseinrichtungen 8 2.3 Regularien für den Prüfungsbereich Wirtschafts- und Sozialkunde 11 2.4 Schriftliche Prüfungsdurchführungsform und ihre Aufgabentypen 7 2.4.1 Gebundene Aufgabentypen 21 2.4.2 Nichtgebundene Aufgabentypen 25 2.4.3 Qualitätskriterien der schriftlichen Prüfung 29 2.5 Schnittmengen von politischer und beruflicher Bildung 31 3 Quantitative Datenerhebung 38 3.1 Analyse der Prüfungsaufgabensätze Wirtschafts- und Sozialkunde 38 3.1.1 Prüfungsaufgabensatz Bürokaufmann/-kauffrau (Winter 2011/12) 42 3.1.2 Prüfungsaufgabensatz Koch/Köchin (Winter 2011/2012) 44 3.1.3 Prüfungsaufgabensatz Mechatroniker/-in (Winter 2011/2012) 46 3.1.4 Zusammenfassung der Aufgabenanalyse 48 3.2 Lehrplananalyse 50 3.2.1 Baden-Württemberg .. 51 3.2.2 Bayern . 55 3.2.3 Berlin und Brandenburg 57 3.2.4 Bremen 60 3.2.5 Hamburg 64 3.2.6 Mecklenburg-Vorpommern 66 3.2.7 Niedersachsen 68 3.2.8 Nordrhein-Westfalen 71 3.2.9 Rheinland-Pfalz 73 3.2.10 Saarland 76 3.2.11 Sachsen 78 3.2.12 Schleswig-Holstein 82 3.2.13 Thüringen 86 3.2.14 Zusammenfassung der Lehrplananalyse 89 4 Qualitative Datenerhebung 91 4.1 Forschungsdesign 91 4.2 Methode der qualitativen Inhaltsanalyse 92 4.3 Ergebnisse der Inhaltsanalyse 93 4.3.1 Die Abschlussprüfung als Damoklesschwert für den Lehrenden 94 4.3.2 Nomen est omen 98 4.3.3 „Und alles andere hängt vom Lehrer ab, vom Geschick des Lehrers, seinen Unterricht zu gestalten und zu sagen, das ist wichtig.“ (3/343ff.) 101 4.3.4 Berufsbildender Unterricht und Prüfungswesen – Einheit oder Dualismus? 104 5 Konklusion 109 6 Empfehlungen 114 Literaturverzeichnis 116

L’objectif principal de cette thèse est l’exploration du recalage d’images à l’aide de champs aléatoires de Markov d’ordres supérieurs, et plus spécifiquement d’intégrer la connaissance de transformations globales comme une transformation rigide, dans la structure du graphe. Notre cadre principal s’applique au recalage 2D-2D ou 3D-3D et utilise une approche hiérarchique d’un modèle de champ de Markov dont le graphe est une grille régulière. Les variables cachées sont les vecteurs de déplacements des points de contrôle de la grille.Tout d’abord nous expliciterons la construction du graphe qui permet de recaler des images en cherchant entre elles une transformation affine, rigide, ou une similarité, tout en ne changeant qu’un potentiel sur l’ensemble du graphe, ce qui assure une flexibilité lors du recalage. Le choix de la métrique est également laissée à l’utilisateur et ne modifie pas le fonctionnement de notre algorithme. Nous utilisons l’algorithme d’optimisation de décomposition duale qui permet de gérer les hyper-arêtes du graphe et qui garantit l’obtention du minimum exact de la fonction pourvu que l’on ait un accord entre les esclaves. Un graphe similaire est utilisé pour réaliser du recalage 2D-3D.Ensuite, nous fusionnons le graphe précédent avec un autre graphe construit pour réaliser le recalage déformable. Le graphe résultant de cette fusion est plus complexe et, afin d’obtenir un résultat en un temps raisonnable, nous utilisons une méthode d’optimisation appelée ADMM (Alternating Direction Method of Multipliers) qui a pour but d’accélérer la convergence de la décomposition duale. Nous pouvons alors résoudre simultanément recalage affine et déformable, ce qui nous débarrasse du biais potentiel issu de l’approche classique qui consiste à recaler affinement puis de manière déformable. / The main objective of this thesis is the exploration of higher order Markov Random Fields for image registration, specifically to encode the knowledge of global transformations, like rigid transformations, into the graph structure. Our main framework applies to 2D-2D or 3D-3D registration and use a hierarchical grid-based Markov Random Field model where the hidden variables are the displacements vectors of the control points of the grid.We first present the construction of a graph that allows to perform linear registration, which means here that we can perform affine registration, rigid registration, or similarity registration with the same graph while changing only one potential. Our framework is thus modular regarding the sought transformation and the metric used. Inference is performed with Dual Decomposition, which allows to handle the higher order hyperedges and which ensures the global optimum of the function is reached if we have an agreement among the slaves. A similar structure is also used to perform 2D-3D registration.Second, we fuse our former graph with another structure able to perform deformable registration. The resulting graph is more complex and another optimisation algorithm, called Alternating Direction Method of Multipliers is needed to obtain a better solution within reasonable time. It is an improvement of Dual Decomposition which speeds up the convergence. This framework is able to solve simultaneously both linear and deformable registration which allows to remove a potential bias created by the standard approach of consecutive registrations.

Artenübergreifende Interaktionen helfen uns, Krankheitsmechanismen zu verstehen und Targets für Therapien zu finden. Die Koexpression von Genen, gemessen an der mRNA-Häufigkeit, kann Interaktionen zwischen Wirt und Pathogen aufzeigen. Die RNA-Sequenzierung von Wirt und Pathogen wird als "duale RNA-Sequenzierung" bezeichnet. Malaria ist eine der am besten untersuchten parasitären Krankheiten, so dass eine Fülle von RNA-seq-Datensätzen öffentlich zugänglich ist. Die Autoren führen entweder duale RNA-seq durch, um den Wirt und den Parasiten gleichzeitig zu untersuchen, oder sie erhalten kontaminierende Sequenzierungs-Reads aus dem Nicht-Zielorganismus. Ich habe eine Meta-Analyse durchgeführt, bei diese beiden Arten von RNA-seq-Studien verwendet wurden, um über korrelierte Genexpression auf Wirt-Parasit-Interaktionen zu schließen. Ich habe Studien mit Homo sapiens, Mus musculus und Macaca mulatta als Wirte und ihre Plasmodium-Parasiten einbezogen. Ich benutzte orthologe Einzelkopien von Genen, um ein Repertoire von Interaktionen bei Malaria und in diesen Modellsystemen zu erstellen. Ich verknüpfte die Daten von 63 Plasmodium-Phasen-spezifischen Studien und reduzierte die Zahl der Interaktionen von potenziell 56 Millionen auf eine kleinere, relevantere Menge. Die Zentralität in den Netzwerken der Blutphasen konnte die Essentialität der Plasmodium-Gene erklären. Das aus den verketteten Daten sagte die Genessenzialität besser vor als die einzelnen Studien - ein Vorteil der Meta-Analyse. Neutrophile und Monozyten Immunmarkergene waren überrepräsentiert, was auf eine Fülle von phagozytären und respiratorischen Reaktionen hindeutet. Die Analyse der Leberphase ergab Wirts- und Parasitenprozesse in frühen und späten Entwicklungsphasen. Ich fand bekannte Wirt-Parasit-Interaktionen, die für beide Phasen gleich sind, sowie bisher unbekannte Interaktionen. Dieses Prinzip lässt sich auch auf andere Krankheiten anwenden, um Mechanismen und therapeutische Ziele zu verstehen. / Cross-species interactions help us understand disease mechanisms and find targets for therapy. Gene co-expression, measured by mRNA abundance, can identify host-pathogen interactions. The RNA-sequencing of host and pathogen is termed “dual RNA-sequencing”. Malaria is one of the most studied eukayotic parasitic diseases, making an abundance of RNA-seq data sets publicly available. Authors either perform dual RNA-seq to study the host and parasite simultaneously or acquire contaminant sequencing reads from the non-target organism. I performed a meta-analysis using these two kinds of RNA-seq studies to infer host-parasite interactions using correlated gene expression. I included studies of Homo sapiens, Mus musculus and Macaca mulatta as hosts and their corresponding Plasmodium parasites. I used single-copy orthologous genes to generate a repertoire of interactions in human malaria and in these model systems. I found 63 malaria RNA-seq studies. I concatenated sequencing runs from Plasmodium stage-specific studies and reduced the number of interactions from a potential 56 million to a smaller, more relevant set. Centrality in the blood stage networks was able to explain Plasmodium gene essentiality. The network from the concatenated data predicted gene essentiality better than the individual studies, indicating a benefit of the meta-analysis. Immune marker genes for neutrophils and monocytes were over-represented, suggesting an abundance of phagocytic and respiratory burst-related responses. The liver stage analysis revealed linked host and parasite processes at early stages until late developmental stages. I found linked host and parasite processes that are common to the two stages, e.g. parasite cell gliding and invasion and host response to hypoxia and immune response. I showed that existing data can be explored for new information. This principle can be applied to other diseases to understand mechanisms and therapeutic targets.

Die vorliegende Arbeit befasst sich mit Schnittebenenverfahren, einer Gruppe von iterativen Algorithmen zur Minimierung einer (möglicherweise nicht glatten) konvexen Funktion über einer kompakten konvexen Menge. Wir betrachten zwei prominente Beispiele, nämlich die Ellipsoidmethode und die Methode der Vaidya, und zeigen, dass ihre Konvergenzrate auch bei Verwendung eines ungenauen Orakels erhalten bleibt. Darüber hinaus zeigen wir, dass es möglich ist, diese Methoden im Rahmen der stochastischen Optimierung effizient zu nutzen. Eine andere Richtung, in der Schnittebenenverfahren nützlich sein können, sind duale Probleme. In der Regel können die Zielfunktion und ihre Ableitungen bei solchen Problemen nur näherungsweise berechnet werden. Daher ist die Unempfindlichkeit der Methoden gegenüber Fehlern in den Subgradienten von großem Nutzen. Als Anwendungsbeispiel schlagen wir eine linear konvergierende duale Methode für einen Markow-Entscheidungsprozess mit Nebenbedienungen vor, die auf der Methode der Vaidya basiert. Wir demonstrieren die Leistungsfähigkeit der vorgeschlagenen Methode in einem einfachen RL Problem. Die Arbeit untersucht auch das Konzept der Genauigkeitszertifikate für konvexe Minimierungsprobleme. Zertifikate ermöglichen die Online-Überprüfung der Genauigkeit von Näherungslösungen. In dieser Arbeit verallgemeinern wir den Begriff der Genauigkeitszertifikate für die Situation eines ungenauen Orakels erster Ordnung. Darüber hinaus schlagen wir einen expliziten Weg zur Konstruktion von Genauigkeitszertifikaten für eine große Klasse von Schnittebenenverfahren vor. Als Nebenprodukt zeigen wir, dass die betrachteten Methoden effizient mit einem verrauschten Orakel verwendet werden können, obwohl sie ursprünglich für ein exaktes Orakel entwickelt wurden. Schließlich untersuchen wir die vorgeschlagenen Zertifikate in numerischen Experimenten und zeigen, dass sie eine enge obere Schranke für das objektive Residuum liefern. / The present thesis studies cutting plane methods, which are a group of iterative algorithms for minimizing a (possibly nonsmooth) convex function over a compact convex set. We consider two prominent examples, namely, the ellipsoid method and Vaidya's method, and show that their convergence rate is preserved even when an inexact oracle is used. Furthermore, we demonstrate that it is possible to use these methods in the context of stochastic optimization efficiently. Another direction where cutting plane methods can be useful is Lagrange dual problems. Commonly, the objective and its derivatives can only be computed approximately in such problems. Thus, the methods' insensitivity to error in subgradients comes in handy. As an application example, we propose a linearly converging dual method for a constrained Markov decision process (CMDP) based on Vaidya's algorithm. We demonstrate the performance of the proposed method in a simple RL environment. The work also investigates the concept of accuracy certificates for convex minimization problems. Certificates allow for online verification of the accuracy of approximate solutions. In this thesis, we generalize the notion of accuracy certificates for the setting of an inexact first-order oracle. Furthermore, we propose an explicit way to construct accuracy certificates for a large class of cutting plane methods. As a by-product, we show that the considered methods can be efficiently used with a noisy oracle even though they were originally designed to be equipped with an exact oracle. Finally, we illustrate the work of the proposed certificates in numerical experiments highlighting that they provide a tight upper bound on the objective residual.

In this thesis, we generalize clones (as well as their relational counterparts and the relationship between them) to categories. Based on this framework, we introduce a general duality theory for clones and apply it to obtain new results for clones on finite sets.

In this thesis, we generalize clones (as well as their relational counterparts and the relationship between them) to categories. Based on this framework, we introduce a general duality theory for clones and apply it to obtain new results for clones on finite sets.

Au cours de cette thèse, nous nous sommes d'abord intéressés à l'optimisation des ressources et à la modulation adaptative dans les systèmes SC-FDMA (Single Carrier Frequency Division Multiple Access). Ce problème d'optimisation est combinatoire à complexité de calcul exponentielle. Afin de pallier à cette difficulté, nous avons utilisé la théorie de la dualité canonique, grâce à laquelle, la complexité du problème d'optimisation devient polynômiale et cela en constitue une amélioration remarquable. L'approche proposée est très proche de la solution optimale. Nous avons ensuite étudié la problématique complexe de l'allocation de ressources pour le "Streaming Vidéo" dans les réseaux sans fil, où il est nécessaire d'assurer une transmission vidéo de haute qualité en présence de canaux et de brouillages variables au cours du temps. Dans ce contexte, nous avons proposé une nouvelle méthode d'allocation de puissance conjointement à l'adaptation du débit vidéo. Pour ce faire, nous avons adopté une approche de la théorie de contrôle, intitulée "Risk-Sensitive Control". Nous avons dédié la troisième partie de la thèse à la conception d'une nouvelle stratégie "best-M" pour le renvoi du CQI (Channel Quality Indicator) pour les systèmes multi-utilisateurs et multi-porteuses. En générale, l'erreur d'estimation du CQI ainsi que son délai de renvoi sont gérés au niveau de la station de base. Notre nouvelle stratégie "best-M" suppose que la gestion de ces problèmes est confiée aux utilisateurs. De ce fait, la performance du système se trouve améliorée sans que son débit de signalisation ne soit augmenté en voix montante. / Adaptive resource allocation in wireless communication systems is crucial in order to support the diverse QoS needs of the services and optimize resource utilization. The design of resource allocation schemes should consider the service type for which it is intended. Moreover, due to feedback delay and channel estimation error, the Channel Quality Indicator (CQI) reported to the transmitter may not be a perfect measure of the channel quality and its use for resource allocation may severely degrade the systems performance. In this thesis, we study resource allocation and CQI reporting for wireless networks while taking the aforementioned factors into consideration. First, we consider resource allocation and adaptive modulation in uplink SC-FDMA systems. This is a combinatorial problem whose optimal solution is exponentially complex. We use canonical duality theory to derive a polynomial complexity resource allocation algorithm that provides a nearly optimal solution to the problem. Then, we focus on resource allocation for video streaming in wireless networks with time-varying interference. To this end, by using risk-sensitive control approach, we develop a cross-layer optimization framework that performs power control at the PHY/MAC layer and rate adaptation at the APPLICATION layer jointly and provides fairness among nodes. Finally, by using stochastic control and game theory, we design a robust best-M CQI reporting scheme for multi-carrier and multi-user systems which takes into account the impact of feedback delay and error in CQI computation. Performing resource allocation on the basis of the proposed CQI reporting can significantly improve the system performance.