In a series of work initiated by Nemirovsky and Yudin, and later extended by Nesterov, first-order algorithms for unconstrained minimization with optimal theoretical complexity bound have been proposed. On the other hand, conjugate gradient algorithms as one of the widely used first-order techniques suffer from the lack of a finite complexity bound. In fact their performance can possibly be quite poor. This dissertation is partially on tightening the gap between these two classes of algorithms, namely the traditional conjugate gradient methods and optimal first-order techniques. We derive conditions under which conjugate gradient methods attain the same complexity bound as in Nemirovsky-Yudin's and Nesterov's methods. Moreover, we propose a conjugate gradient-type algorithm named CGSO, for Conjugate Gradient with Subspace Optimization, achieving the optimal complexity bound with the payoff of a little extra computational cost. We extend the theory of CGSO to convex problems with linear constraints. In particular we focus on solving $l_1$-regularized least square problem, often referred to as Basis Pursuit Denoising (BPDN) problem in the optimization community. BPDN arises in many practical fields including sparse signal recovery, machine learning, and statistics. Solving BPDN is fairly challenging because the size of the involved signals can be quite large; therefore first order methods are of particular interest for these problems. We propose a quasi-Newton proximal method for solving BPDN. Our numerical results suggest that our technique is computationally effective, and can compete favourably with the other state-of-the-art solvers.

La détermination des paramètres d'un milieu poreux, notamment de la porosité, de la perméabilité et des propriétés du fluide saturant est un enjeu important pour des problèmes hydrologiques, pétroliers ou de risques naturels. L'objectif principal de ce travail est d'estimer ces propriétés à partir des ondes sismiques réfléchies.<br />Les théories poro-élastiques (Biot,1956) nécessitent de nombreux paramètres pour caractériser les milieux poreux et conduisent à des propriétés particulières des ondes sismiques (deux ondes de compression, atténuation intrinsèquement définies,...). Ces équations sont résolues pour un milieu poreux stratifié plan saturé par un fluide homogène par une méthode de réflectivité associée à une intégration en nombre d'ondes discrets. Ce programme de simulation est tout d'abord utilisé pour estimer la sensibilité des ondes réfléchies à la localisation et à la concentration du dioxyde de carbone dans le cas d'un stockage dans un aquifère marin profond. La sensibilité de la réponse sismique aux différents paramètres du milieu poreux est ensuite établie de manière plus systématique par le calcul analytique des dérivées de Fréchet des sismogrammes et leur mise en oeuvre numérique. Les applications numériques réalisées indiquent que les paramètres primordiaux à déterminer sont la porosité et la consolidation.<br />Ces opérateurs de sensibilité ont ensuite été intégrés dans un code d'inversion de formes d'ondes complètes (algorithme de Quasi-Newton). Les calculs d'inversion réalisés à partir de données synthétiques indiquent que les distributions de porosité et les paramètres caractérisant le solide et le fluide (densité et modules mécaniques) peuvent être correctement reconstruits lorsque les autres paramètres sont bien déterminés.<br />Cependant, l'inversion de plusieurs paramètres reste un problème difficile du fait des couplages sismiques existant entre eux. Il est cependant possible de résoudre des problèmes complexes en ne considérant qu'un seul paramètre pour le fluide (saturation) et un pour les minéraux (lithologie), ou en effectuant des inversions différentielles pour suivre des variations du fluide.<br />La méthode d'inversion est finalement appliquée à un jeu de données réelles acquis sur le site côtier de Maguelonne dans l'Hérault. Les variations du milieu peuvent être reconstruites en utilisant de l'information a priori venant de forages.

Ce travail est divisé en deux axes de recherches. Le premier axe concerne l'étude de quelques systèmes d'équations aux dérivées partielles non linéaires issus de la modélisation macroscopique des composants semi-conducteurs. Le deuxième axe de recherche est consacré à l'étude de quelques problèmes d'identification. Nous nous intéressons en particulier à deux types de problèmes d'identification. Le premier concerne la reconstruction des données sur le bord pour des problèmes elliptiques. Le deuxième type de problèmes auquel nous nous sommes intéressés est celui de l'identification des frontières dans des problèmes gouvernés par des équations elliptiques.

In this thesis, optimization approaches for intensity-modulated radiation therapy are developed and evaluated with focus on numerical efficiency and treatment delivery aspects. The first two papers deal with strategies for solving fluence map optimization problems efficiently while avoiding solutions with jagged fluence profiles. The last two papers concern optimization of step-and-shoot parameters with emphasis on generating treatment plans that can be delivered efficiently and accurately. In the first paper, the problem dimension of a fluence map optimization problem is reduced through a spectral decomposition of the Hessian of the objective function. The weights of the eigenvectors corresponding to the p largest eigenvalues are introduced as optimization variables, and the impact on the solution of varying p is studied. Including only a few eigenvector weights results in faster initial decrease of the objective value, but with an inferior solution, compared to optimization of the bixel weights. An approach combining eigenvector weights and bixel weights produces improved solutions, but at the expense of the pre-computational time for the spectral decomposition. So-called iterative regularization is performed on fluence map optimization problems in the second paper. The idea is to find regular solutions by utilizing an optimization method that is able to find near-optimal solutions with non-jagged fluence profiles in few iterations. The suitability of a quasi-Newton sequential quadratic programming method is demonstrated by comparing the treatment quality of deliverable step-and-shoot plans, generated through leaf sequencing with a fixed number of segments, for different number of bixel-weight iterations. A conclusion is that over-optimization of the fluence map optimization problem prior to leaf sequencing should be avoided. An approach for dynamically generating multileaf collimator segments using a column generation approach combined with optimization of segment shapes and weights is presented in the third paper. Numerical results demonstrate that the adjustment of leaf positions improves the plan quality and that satisfactory treatment plans are found with few segments. The method provides a tool for exploring the trade-off between plan quality and treatment complexity by generating a sequence of deliverable plans of increasing quality. The final paper is devoted to understanding the ability of the column generation approach in the third paper to find near-optimal solutions with very few columns compared to the problem dimension. The impact of different restrictions on the generated columns is studied, both in terms of numerical behaviour and convergence properties. A bound on the two-norm of the columns results in the conjugate-gradient method. Numerical results indicate that the appealing properties of the conjugate-gradient method on ill-conditioned problems are inherited in the column generation approach of the third paper. / QC 20100709

There is a growing demand for the high quality TV programs such as High Definition TV (HDTV). The CATV network is often a suitable solution to address this demand using a CATV modem delivering high data rate digital signals in a cost effective manner, thereby, utilizing a complex digital modulation scheme is inevitable. Exploiting complex modulation schemes, entails a more sophisticated modulator and distribution system with much tighter tolerances. However, there are always distortions introduced to the modulated signal in the modulator degrading signal quality.<p> In this research, the effect of distortions introduced by the RF band pass filter in the modulator will be considered which cause degradations on the quality of the output Quadrature Amplitude Modulated (QAM) signal. Since the RF filter's amplitude/group delay distortions are not symmetrical in the frequency domain, once translated into the base band they have a complex effect on the QAM signal. Using Matlab, the degradation effects of these distortions on the QAM signal such as Bit Error Rate (BER) is investigated.<p> In order to compensate for the effects of the RF filter distortions, two different methods are proposed. In the first method, a complex base band compensation filter is placed after the pulse shaping filter (SRRC). The coefficients of this complex filter are determined using an optimization algorithm developed during this research. The second approach, uses a pre-equalizer in the form of a Feed Forward FIR structure placed before the pulse shaping filter (SRRC). The coefficients of this pre-equalizer are determined using the equalization algorithm employed in a test receiver, with its tap weights generating the inverse response of the RF filter. The compensation of RF filter distortions in base band, in turn, improves the QAM signal parameters such as Modulation Error Ratio (MER). Finally, the MER of the modulated QAM signal before and after the base band compensation is compared between the two methods, showing a significant enhancement in the RF modulator performance.

There is a growing demand for the high quality TV programs such as High Definition TV (HDTV). The CATV network is often a suitable solution to address this demand using a CATV modem delivering high data rate digital signals in a cost effective manner, thereby, utilizing a complex digital modulation scheme is inevitable. Exploiting complex modulation schemes, entails a more sophisticated modulator and distribution system with much tighter tolerances. However, there are always distortions introduced to the modulated signal in the modulator degrading signal quality.<p> In this research, the effect of distortions introduced by the RF band pass filter in the modulator will be considered which cause degradations on the quality of the output Quadrature Amplitude Modulated (QAM) signal. Since the RF filter's amplitude/group delay distortions are not symmetrical in the frequency domain, once translated into the base band they have a complex effect on the QAM signal. Using Matlab, the degradation effects of these distortions on the QAM signal such as Bit Error Rate (BER) is investigated.<p> In order to compensate for the effects of the RF filter distortions, two different methods are proposed. In the first method, a complex base band compensation filter is placed after the pulse shaping filter (SRRC). The coefficients of this complex filter are determined using an optimization algorithm developed during this research. The second approach, uses a pre-equalizer in the form of a Feed Forward FIR structure placed before the pulse shaping filter (SRRC). The coefficients of this pre-equalizer are determined using the equalization algorithm employed in a test receiver, with its tap weights generating the inverse response of the RF filter. The compensation of RF filter distortions in base band, in turn, improves the QAM signal parameters such as Modulation Error Ratio (MER). Finally, the MER of the modulated QAM signal before and after the base band compensation is compared between the two methods, showing a significant enhancement in the RF modulator performance.

Le système étudié durant cette thèse est un véhicule électrique hybride avec deux sources d'énergies (pile à combustible et supercondensateurs). L'objectif fixé est de minimiser la consommation du carburant tout en satisfaisant la demande instantanée en puissance sous des contraintes de puissance, de capacité et de stockage. Le problème a été modélisé sous la forme d'un problème d'optimisation globale. Nous avons développé de nouvelles méthodes heuristiques pour le résoudre et proposé le calcul d'une borne inférieure de consommation, en apportant de meilleurs résultats que ceux trouvés dans la littérature. En plus, une étude de robustesse a été réalisée afin de minimiser la consommation de pire-cas suite à une perturbation ou du fait d'incertitudes sur les données d'entrée, précisément sur la puissance demandée. Le but de cette étude est de prendre en compte les perturbations dès la construction des solutions afin d'éviter l'infaisabilité des solutions non robustes en situation perturbée. Les heuristiques de résolution du problème robuste modélisé sous la forme d'un problème de Minimax ont fourni des solutions moins sensibles aux perturbations que les solutions classiques.

Optimal control problems for finite-strain elasticity are considered. An inner pressure or an inner fiber tension is acting as a driving force. Such internal forces are typical, for instance, for the motion of heliotropic plants, and for muscle tissue. Non-standard objective functions relevant for elasticity problems are introduced. Optimality conditions are derived on a formal basis, and a limited-memory quasi-Newton algorithm for their solution is formulated in function space. Numerical experiments confirm the expected mesh-independent performance.

Les calculs d'équilibres à triphasiques et quadriphasiques sont au cœur des simulations de réservoirs impliquant des processus de récupérations tertiaires. Dans les procédés d'injection de gaz ou de vapeur, le système huile-gaz est enrichi d'une nouvelle phase qui joue un rôle important dans la récupération de l'huile en place. Les calculs d'équilibres représentent la majeure partie des temps de calculs dans les simulations de réservoir compositionnelles où les routines thermodynamiques sont appelées un nombre conséquent de fois. Il est donc important de concevoir des algorithmes qui soient fiables, robustes et rapides. Dans la littérature peu de simulateurs basés sur des équations d'état sont applicables aux procédés de récupération thermique. A notre connaissance, il n'existe pas de simulation thermique complètement compositionnelle de ces procédés pour des cas d'applications aux huiles lourdes. Ces simulations apparaissent essentielles et pourraient offrir des outils améliorés pour l’étude prédictive de certains champs. Dans cette thèse, des algorithmes robustes et efficaces de calculs d’équilibre multiphasiques sont proposés permettant de surmonter les difficultés rencontrés durant les simulations d'injection de vapeur pour des huiles lourdes. La plupart des algorithmes d'équilibre de phases sont basés sur la méthode de Newton et utilisent les variables conventionnelles comme variables indépendantes. Dans un premier temps, des améliorations de ces algorithmes sont proposées. Les variables réduites permettent de réduire la dimensionnalité du système de nc (nombre de composants) dans le cas des variables conventionnelles, à M (M<<nc), et sont déjà utilisées dans certains simulateurs de réservoirs commerciaux. La méthode de réduction proposée par Nichita and Graciaa (Fluid Phase Equil. 302 (2011) 226-233) est étendue à l'analyse de stabilité et aux calculs d'équilibres multiphasiques. A l'inverse des précédentes méthodes de réduction, les variables ne sont pas bornées. La méthode de Newton nécessite une Hessienne définie positive pour pouvoir être utilisée. D'autres méthodes de minimisations sont testées permettant de s'affranchir de cette contrainte; les méthodes Quasi-Newton et Trust-Region qui garantissent une direction de descente à chaque itération. Ces dernières présentent un grand intérêt puisqu'elles permettent de réaliser des pas supra-linéaires (même lorsque la Hessienne n'est pas définie positive) et quadratiques (Trust-Region) ou proches de quadratiques (Quasi-Newton) dans le cas contraire. Un nouveau vecteur de variables indépendantes est proposé (construit afin d'obtenir une meilleure mise échelle du problème) et utilisé au sein d'un algorithme BFGS modifié. De même, une méthode de Trust-Region est développée pour les problèmes de tests de stabilités et d'équilibres multiphasiques. Ensuite, considérant le fluide comme semi-continu, une méthodologie basée sur une procédure de quadrature Gaussienne est proposée pour calculer mathématiquement les pseudo-composants capables de représenter le comportement du fluide. La méthodologie peut être vue comme une procédure de groupement/dégroupement, applicable pour tout nombre de points de quadratures et toute composition de mélange. Dans une dernière partie, un algorithme général pour le calcul d’équilibre multiphasique est présenté incluant tous les algorithmes développés. Ce dernier est testé et validé contre des données expérimentales et de la littérature. Des simulations triphasiques et quadriphasiques d'injection de CO2 démontrent la capacité du programme à traiter un nombre arbitraire de phases. Des simulations de balayages par la vapeur sont réalisées pour des réservoirs montrant d'importantes hétérogénéités. Finalement, une simulation complètement compositionnelle du processus de Steam Assisted Gravity Drainage est réalisée. A notre connaissance, il s'agit de la première simulation de la sorte pour des cas d'applications d'huiles lourdes. / Three to four phase equilibrium calculations are in the heart of tertiary recovery simulations. In gas/steam injection processes, additional phases emerging from the oil-gas system are added to the set and have a significant impact on the oil recovery. The most important computational effort in many chemical process simulators and in petroleum compositional reservoir simulations is required by phase equilibrium and thermodynamic property calculations. In field scale reservoir simulations, a huge number of phase equilibrium calculations is required. For all these reasons, the algorithms must be robust and time-saving. In the literature, few simulators based on equations of state (EoS) are applicable to thermal recovery processes such as steam injection. To the best of our knowledge, no fully compositional thermal simulation of the steam injection process has been proposed with extra-heavy oils; these simulations are essential and will offer improved tools for predictive studies of the heavy oil fields. Thus, in this thesis different algorithms of improved efficiency and robustness for multiphase equilibrium calculations are proposed, able to handle conditions encountered during the simulation of steam injection for heavy oil mixtures. Most of the phase equilibrium calculations are based on the Newton method and use conventional independent variables. These algorithms are first investigated and different improvements are proposed. Michelsen’s (Fluid Phase Equil. 9 (1982) 21-40) method for multiphase-split problems is modified to take full advantage of symmetry (in the construction of the Jacobian matrix and the resolution of the linear system). The reduction methods enable to reduce the space of study from nc (number of components) for conventional variables to M (M<<nc) and are already used in some commercial reservoir simulators. The reduction method proposed by Nichita and Graciaa (Fluid Phase Equil. 302 (2011) 226-233) is extended to phase stability analysis and multiphase-split calculations. Unlike previous reduction methods, the set of variables is unbounded and the convergence path is the same as in conventional methods using the logarithm of equilibrium constants as variables. The Newton method requires a positive definite Hessian for convergence. Other kinds of minimization methods are investigated which overcome this constraint; the Quasi-Newton and Trust-region methods always guarantee a descent direction. These methods represent an interesting alternative since they can reach supra-linear steps even when the Hessian is non-positive definite, and can reach quadratic steps (Trust-Region) or nearly quadratic steps (Quasi-Newton) otherwise. A new set of independent variables is proposed (designed to ensure a better scaling of the problem) for a modified BFGS (which ensures the positive definiteness of the approximation of the Hessian matrix) algorithm and a Trust-Region method is also proposed for the stability-testing and phase-split problems. Subsequently, by assuming the fluid composition as semi-continuous, a methodology based on a Gaussian quadrature is proposed to mathematically compute a set of pseudo-components capable of representing the fluid behavior. The methodology can be seen as a lumping-delumping procedure, applicable to any number of quadrature points and to any feed distribution. In a last part, a general multiphase flash procedure implementing all the developed algorithms is presented, and tested against experimental and literature data. Three- and four phase CO2 injection simulations demonstrate the capability of the program to handle any number of phases. Simulations of steam flooding are performed for highly heterogeneous reservoirs. Finally, a fully compositional simulation of the steam assisted gravity drainage process is realized. To the best of our knowledge, this is the first simulation of the kind for heavy oil mixtures.

Die kontinuierliche Weiterentwicklung und Verbesserung technischer Prozesse erfolgt heute auf der Basis stochastischer und deterministischer Optimierungsstrategien in Kombination mit der numerischen Simulation dieser Abläufe. Da die FE-Simulation von Umformvorgängen in der Regel sehr zeitintensiv ist, bietet sich für die Optimierung solcher Prozesse der Einsatz deterministischer Methoden an, da hier weniger Optimierungsschritte und somit auch weniger FE-Simulationen notwendig sind. Eine wichtige Anforderung an solche Optimierungsverfahren ist globale Konvergenz zu lokalen Minima, da die optimalen Parametersätze nicht immer näherungsweise bekannt sind. Die zwei wichtigsten Strategien zum Ausdehnen des beschränkten Konvergenzradius der natürlichen Optimierungsverfahren (newtonschrittbasierte Verfahren und Gradientenverfahren) sind die Line-Search-Strategie und die Trust-Region-Strategie. Die Grundlagen der Line-Search-Strategie werden aufgearbeitet und die wichtigsten Teilalgorithmen implementiert. Danach wird dieses Verfahren auf eine effiziente Kombination der Teilalgorithmen und Verfahrensparameter hin untersucht. Im Anschluss wird die Leistung eines Optimierungsverfahrens mit Line-Search-Strategie verglichen mit der eines ebenfalls implementierten Optimierungsverfahrens mit skalierter Trust-Region-Strategie. Die Tests werden nach Einfügen der implementierten Verfahren in das Programm SPC-Opt anhand der Lösung eines Quadratmittelproblems aus der Materialparameteridentifikation sowie der Formoptimierung eines Umformwerkzeugs vorgenommen.