This thesis gives an overall survey of preprocessing and postprocessing techniques in linear optimization (LO) and its implementations in the software package McMaster Interior Point Method (McIPM). We first review the basic concepts and theorems in LO. Then we present all the techniques used in preprocessing and the corresponding operations in postprocessing. Further, we discuss the implementation issues in our software development. Finally we test a series of problems from the Netlib test set and compare our results with state of the art software, such as LIPSOL and CPLEX. / Thesis / Master of Science (MS)

This dissertation provides several techniques for solving a class of nonconvex optimization problems that arise in the thermal analysis of electronic chip packages. The topic is of interest because in systems containing delicate electronic components both performance and reliability are impacted by thermal behavior. A modeling paradigm, called Compact Thermal Modeling (CTM), has been demonstrated to show promise for accurately estimating steady state thermal behavior without resorting to computationally intensive finite element models or expensive direct experimentation. The CTM is a network model that gives rise to a nonconvex optimization problem. A solution to this nonconvex optimization problem provides a reasonably accurate characterization of the steady state temperature profile the chip will attain under arbitrary boundary conditions, which allows the system designer to model the application of a wide range of thermal design strategies with useful accuracy at reasonable computational cost. This thesis explores several approaches to solving the optimization problem. We present a heuristic technique that is an adaptation of the classical coordinate search method that has been adapted to run efficiently by exploiting the algebraic structure of the problem. Further, the heuristic is able to avoid stalling in poor local optima by using a partitioning scheme that follows from an examination of special structure in the problem's feasible region. We next present several exact approaches using a globally optimal method based on the Reformulation Linearization Technique (RLT). This approach generates and then solves convex relaxations of the original problem, tightening the approximations within a branch and bound framework. We then explore several approaches to improving the performance of the RLT technique by introducing variable substitutions and valid inequalities, which tighten the convex relaxations. Computational results, conclusions, and recommendations for further research are also provided.

Digital medical atlases can contain anatomical information which is valuable for medical doctors in diagnosing and treating illnesses. The increased availability of such atlases has created an interest for computer algorithms which are capable of integrating such atlas information into patient specific dataprocessing. The field of medical image registration aim at calculating how to match one medical image to another. Here the atlas information could give important hints of which kinds of motion are plausible in different locations of the anatomy. Being able to incorporate such atlas specific information could potentially improve the matching of images and plausibility of image registration - ultimately providing a more correct information on which to base health care diagnosis and treatment decisions. In this licentiate thesis a generic signal processing framework is derived : Global Linear Optimization (GLO). The power of the GLO framework is first demonstrated quantitatively in a very high performing image denoiser. Important proofs of concepts are then made deriving and implementing three important capabilities regarding adaptive filtering of vector fields in medica limage registration: Global regularization with local anisotropic certainty metric. Allowing sliding motion along organ and tissue boundaries. Enforcing an incompressible motion in specific areas or volumes. In the three publications included in this thesis, the GLO framework is shown to be able to incorporate one each of these capabilities. In the third and final paper a demonstration is made how to integrate more and more of the capabilities above into the same GLO to perform adaptive processing on relevant clinical data. It is shown how each added capability improves the result of the image registration. In the end of the thesis there is a discussion which highlights the advantage of the contributions made as compared to previous methods in the scientific literature. / Dynamic Context Atlases for Image Denoising and Patient Safety

The modern theory of condition measures for convex optimization problems was initially developed for convex problems in conic format, and several aspects of the theory have now been extended to handle non-conic formats as well. In this theory, the (Renegar-) condition measure C(d) for a problem instance with data d=(A,b,c) has been shown to be connected to bounds on a wide variety of behavioral and computational characteristics of the problem instance, from sizes of optimal solutions to the complexity of algorithms. Herein we test the practical relevance of the condition measure theory, as applied to linear optimization problems that one might typically encounter in practice. Using the NETLIB suite of linear optimization problems as a test bed, we found that 71% of the NETLIB suite problem instances have infinite condition measure. In order to examine condition measures of the problems that are the actual input to a modern IPM solver, we also computed condition measures for the NETLIB suite problems after pre-preprocessing by CPLEX 7.1. Here we found that 19% of the post-processed problem instances in the NETLIB suite have infinite condition measure, and that log C(d) of the post-processed problems is fairly nicely distributed. Furthermore, there is a positive linear relationship between IPM iterations and log C(d) of the post-processed problem instances (significant at the 95% confidence level), and 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the post-processed problem instances. / Singapore-MIT Alliance (SMA)

A Residential Energy Management System (REMS) in smart grid provides capability to manage a daily load curve in order to reduce power consumption and energy cost. Consequently, (REMS) offers significant benefits for both the electricity suppliers and consumers in terms of control and schedule time of use of major appliances. In recent years, however, the rate of energy demand has increased rapidly throughout the world while the price of energy has been fluctuating. Numerous methods for (REMS) are used; this thesis analyzes many candidate scenarios during peak load periods comparing to the tariff to reduce the usage and its associated costs. It presents simulated results of proposed (REMS) to provide an automated least cost demand response. The main approach will be to ensure the satisfaction of the requirements with constraints on efficient use of energy. Multiphasic system behaviors of smart appliances in (REMS) with a realistic manner are proposed. / This thesis examines many mathematical models of home appliances in order to calculate the physical quantities that reflect the parameters’ impact and the system behavior. Main contribution determines the optimal solution of (TOU) problem to reduce energy cost and determine the best operation time by using (Linear optimization technique).

[pt] Este trabalho está dividido em duas partes. A primeira parte trata das relações entre o problema de otimização d.c. (diferença de duas funções convexas) e o problema de otimização d.c. regularizado por inf-convolução, com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. Neste sentido se generaliza a relação de TOLAND (1979): inf { g(x) - h(x) } = inf { h(asterístico (y) - g (asterístico(y) }, H H E a relação de GABAY (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Onde g, h , são funções convexas próprias e semicontínuas inferiormente, g(asterístico), h(asterístico), são conjugadas de g e h, respectivamente, H é um espaço de Hilbert real, e g (lambda), h lambda , são as funções regularizadas respectivas de g e h, por inf-convolução com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. A segunda parte deste trabalho apresenta um algoritmo novo para tratar com o problema de otimização d.c.. Trata-se de um método de descida do tipo proximal, onde se leva em consideração separadamente as propriedades de convexidade das duas funções convexas. / [en] The work is divided in two parts. The first part is concerned with the relationship between the d.c. optimization problem. In this sence we geralize the TOLAND´s relation (1979): inf { g(x) - h(x) } = inf { h(asteristic)(y) - g (asteristic)(y) }, H H And the GABAY´s relation (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Where g, h, are l.s.c. convex functions, g(asteristic) and h(asteristic) are their conjugates, H is a real Hilbert space, and g lambda, h lambda, are the inf-convolution of g and h respectively, with the núcleos 8( . ) = (2 lambda)- 1 l l . l l 2 , lambda > 0. In the second part we present a new algorithm for dealing with d.c. functions. It is a descent method of proximal kind which takes in consideration the convex properties of the two convex functions separately

The purpose of this thesis is to provide a new scheduling model of a large constellation of imaging satellites that does not use a heuristic solving method. The objective is to create a mixed-integer linear model that would be competitive in speed and in its closeness to reality against a current model using simulated annealing, while trying to improve both models. Each satellite has the choice between a number of possible events, each event having a utility and a cost, and the chosen schedule must take into account numerous time-related constraints. The main difficulties appeared in modeling realistically a battery level and in handling infeasible configurations due to inaccurate parameters. The obtained linear model has enabled a better understanding of the performance of the simulated annealing solver, and could also be adapted to different real-world scheduling problems.

O objetivo principal desta tese foi a implantação de uma nova estratégia para a integração da otimização em tempo real (RTO), com o controle preditivo multivariável em uma unidade de processo industrial. A solução proposta pode ser considerada como uma estratégia de uma camada, na qual os problemas de controle e otimização econômica são resolvidos simultaneamente, na mesma camada da estrutura de controle. Supondo que o objetivo econômico a ser maximizado (minimizado) seja uma função côncava (convexa) das entradas e saídas de processo, o controlador MPC com otimização econômica (OMPC) foi obtido através da inclusão do gradiente reduzido do objetivo econômico, na função objetivo do controlador preditivo. Esta abordagem foi testada inicialmente através da simulação do conjunto reator regenerador de uma Unidade de Craqueamento Catalítico Fluido (UFCC). O controlador otimizador foi implementado com sucesso em uma coluna de destilação de tolueno, na Unidade de Recuperação de Aromáticos da refinaria de Cubatão da Petrobras. Este controlador está em funcionamento contínuo por cerca de um ano, sem qualquer problema relatado. Para a determinação das condições ótimas, um modelo rigoroso de coluna de destilação multicomponentes no estado estacionário é incluído no controlador preditivo para permitir o cálculo online do objetivo econômico. A trajetória prevista para o sistema de destilação até o ponto ótimo é calculada utilizando-se um modelo linear dinâmico, o qual foi obtido através de testes em degrau na planta real. O ponto ótimo obtido através da estratégia proposta leva em consideração as restrições nas entradas manipuladas e a faixa de controle para as saídas. O problema de otimização resultante para cálculo das ações de controle é uma QP, que pode ser facilmente resolvida com os solvers disponíveis. O MPC com otimização econômica foi implementado como um módulo do pacote SICON (Sistema de Controle da Petrobras). / This thesis was mainly aimed at the implementation of a new strategy for the integration of real time optimization (RTO) with multivariable predictive control in an industrial process system. The proposed strategy can be considered as a one-layer strategy where the control and economic optimization problems are solved simultaneously in the same layer of the control structure. Assuming that the economic objective to be maximized (minimized) is a concave (convex) function of the process inputs and outputs, the optimizing model predictive control (OMPC) was obtained through the inclusion of the reduced gradient of the economic objective in the control objective of the predictive controller. The approach was initially tested through the simulation of the reactorregenerator of a Fluid Catalytic Cracking Unit (FCCU). The optimizing controller has been successfully implemented in a toluene distillation column at the Aromatic Recovery Unit of the Cubatão refinery of Petrobras. This controller has been in continuous operation for about one year without any reported problem. For determining the optimum operating conditions, a steady-state rigorous multicomponent distillation model is included in the predictive controller to allow the on-line computation of the economic objective. The predicted trajectory of the distillation system towards the optimum point is computed with a linear dynamic model that was obtained through step tests in the real plant. The optimum point that is achieved with the proposed strategy takes into account the constraints in the manipulated inputs and the zone control of the outputs. The resulting optimization problem that produces the control actions is a QP that can be easily solved with available solvers. The optimizing MPC was implemented as a module of the SICON (Petrobras Control System) package.

O objetivo principal desta tese foi a implantação de uma nova estratégia para a integração da otimização em tempo real (RTO), com o controle preditivo multivariável em uma unidade de processo industrial. A solução proposta pode ser considerada como uma estratégia de uma camada, na qual os problemas de controle e otimização econômica são resolvidos simultaneamente, na mesma camada da estrutura de controle. Supondo que o objetivo econômico a ser maximizado (minimizado) seja uma função côncava (convexa) das entradas e saídas de processo, o controlador MPC com otimização econômica (OMPC) foi obtido através da inclusão do gradiente reduzido do objetivo econômico, na função objetivo do controlador preditivo. Esta abordagem foi testada inicialmente através da simulação do conjunto reator regenerador de uma Unidade de Craqueamento Catalítico Fluido (UFCC). O controlador otimizador foi implementado com sucesso em uma coluna de destilação de tolueno, na Unidade de Recuperação de Aromáticos da refinaria de Cubatão da Petrobras. Este controlador está em funcionamento contínuo por cerca de um ano, sem qualquer problema relatado. Para a determinação das condições ótimas, um modelo rigoroso de coluna de destilação multicomponentes no estado estacionário é incluído no controlador preditivo para permitir o cálculo online do objetivo econômico. A trajetória prevista para o sistema de destilação até o ponto ótimo é calculada utilizando-se um modelo linear dinâmico, o qual foi obtido através de testes em degrau na planta real. O ponto ótimo obtido através da estratégia proposta leva em consideração as restrições nas entradas manipuladas e a faixa de controle para as saídas. O problema de otimização resultante para cálculo das ações de controle é uma QP, que pode ser facilmente resolvida com os solvers disponíveis. O MPC com otimização econômica foi implementado como um módulo do pacote SICON (Sistema de Controle da Petrobras). / This thesis was mainly aimed at the implementation of a new strategy for the integration of real time optimization (RTO) with multivariable predictive control in an industrial process system. The proposed strategy can be considered as a one-layer strategy where the control and economic optimization problems are solved simultaneously in the same layer of the control structure. Assuming that the economic objective to be maximized (minimized) is a concave (convex) function of the process inputs and outputs, the optimizing model predictive control (OMPC) was obtained through the inclusion of the reduced gradient of the economic objective in the control objective of the predictive controller. The approach was initially tested through the simulation of the reactorregenerator of a Fluid Catalytic Cracking Unit (FCCU). The optimizing controller has been successfully implemented in a toluene distillation column at the Aromatic Recovery Unit of the Cubatão refinery of Petrobras. This controller has been in continuous operation for about one year without any reported problem. For determining the optimum operating conditions, a steady-state rigorous multicomponent distillation model is included in the predictive controller to allow the on-line computation of the economic objective. The predicted trajectory of the distillation system towards the optimum point is computed with a linear dynamic model that was obtained through step tests in the real plant. The optimum point that is achieved with the proposed strategy takes into account the constraints in the manipulated inputs and the zone control of the outputs. The resulting optimization problem that produces the control actions is a QP that can be easily solved with available solvers. The optimizing MPC was implemented as a module of the SICON (Petrobras Control System) package.

As unidades industriais de produção de poliolefinas operam de maneira contínua, mas precisam produzir diferentes tipos de grades poliméricos (polímeros com diferentes especificações, para diferentes aplicações). As condições de operação do reator são mantidas por um certo período de tempo para produzir um determinado grade, e periodicamente as condições são alteradas para produzir lotes de outros grades. Estas transições permitem produzir diferentes grades usando o mesmo reator, mas exige mudanças nas condições operacionais e, como consequência, o polímero produzido durante uma transição fica fora da especificação. Assim, é desejável que as transições sejam realizadas no menor tempo possível, de maneira a produzir a menor quantidade de polímero fora da especificação. Estratégias mais eficientes de operar a transição podem ser obtidas através da solução de um problema de otimização dinâmica. Neste trabalho uma função objetivo integral quadrática foi minimizada, utilizando técnicas sequenciais dinâmicas para resolução da otimização. Os resultados foram primeiramente simulados e depois otimizados para a homopolimerização e copolimerização. No caso da homopolimerização, as otimizações mostraram que para aumentar o MI é preciso aumentar a concentração de hidrogênio na alimentação. Já na copolimerização, para aumentar o MI foi preciso diminuir a concentração de hidrogênio na alimentação e aumentar a vazão de comonômero; e para diminuir a densidade foi preciso aumentar a vazão de comonômero. Observou-se que as propriedades instantâneas têm dinâmica mais rápida e agressiva que as cumulativas. Os resultados mostraram que quando a parametrização não era adequada a solução se afastava do ótimo. Foi possível notar que atuar durante 2 tempos de residência já traz uma redução significativa do tempo para o término da transição e da massa de produto fora da especificação. O perfil das propriedades da transição no sentido grade 1 - grade 2 se mostrou diferente do grade 2 - grade 1, concluindo que o perfil de uma transição depende fortemente da direção da mudança nas propriedades. / Polyolefin plants operate under continuous production, but they need to supply many types of polymer grades (polymer with different specification, used in different applications). The operating conditions are maintained constant during the production of a certain grade and need to change periodically to produce another grade. Grade transitions allow the production of different polymer grades in a single reactor, but as they require changes in the operating conditions, there is a large production of off-specification polymer. Therefore, a desired transition drives the polymer properties to the new grade in a short period of time, producing a small amount of off-specification polymer. Efficient strategies to operate the transition can be obtained by solving a problem of dynamic optimization. In this work, a quadratic integral objective function was minimized by using dynamic sequential techniques for solving optimization. The results were first simulated and then optimized for the homopolymerization and copolymerization. In the case of homopolymerization, optimizations showed that to increase the MI is necessary to increase the hydrogen concentration in the feed. In the copolymerization, to increase the MI was necessary to reduce the concentration of hydrogen in the feed and increase the comonomer flow rate; and to decrease the density was necessary to increase the comonomer flow rate. It was observed that the instantaneous properties have faster and aggressive dynamics compared to the cumulative properties. The results showed that when the parameterization was not adequate the solution moves away from the optimum. It was observed that to act for 2 residence times makes a significant reduction in the transition time completion and in the mass of product out of specification. The trajectories of the transition properties towards grade 1 - grade 2 showed different behavior compared to grade 2 - grade 1 transition, concluding that the profile of a transition depends strongly on the direction of change in the properties.