We introduce a very simple but efficient idea for branch & bound (B&B) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new B&B approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used B&B techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical B&B techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations

[pt] Aborda-se o conhecido problema H2/Hinf - otimização de um funcional de custo definido em termos de uma norma quadrática com restrição definida em termos de uma norma infinito para o qual se estuda um método para a obtenção de soluções aproximadas, baseado na solução de seqüências de problema H2/H2 problemas de otimização com funcionais de custo quadráticos e restrições definidas em termos de normas quadráticas. Apresentam-se exemplos numéricos que permitem avaliar o desempenho do método. Estuda-se, também, o problema do rastreamento assintótico de sinais persistentes com restrições de desacoplamento total ou parcial - para sistemas lineares de controle em dimensão finiita. Para aqueles controladores que alcançam as propriedades do desacoplamento e do rastreamento, obtém- se a solução de um problema de otimização H2 - funcional de custo quadrático. Apresentam-se exemplos numéricos enfatizando o aumento do custo ótimo quando se impõe o desacoplamento total e como se pode obter um compromisso entre o valor do custo ótimo e o nível de desacoplamento do sistema através da solução de um problema H2/H2. / [en] A new method to obtain approximate solutions to H2/HINF problems is presented. This method is based on the solution of sequences of H2/H2 problems. Numerical examples are given to show the performance of the method. This work also considers the problem of asymptotic tracking of persistent signals and decoupling - include approximate decoupling to control linear systems. Undo these constraints, a H2 - optimization problem is resolved.

Quadratic optimization problems arise in various real world application domains including engineering design, microeconomics, genetic algorithms, integrated circuit chip design, probabilistic graphical models and computer vision. In particular, there are many problems in computer vision that require binary quadratic optimization such as motion segmentation, correspondences, figure-ground segmentation, clustering, grouping, subgraph matching, and digital matting. The objective of an optimization algorithm can be related to the state of a physical system, where the goal is to bring the initial arbitrary state of the system to a state with minimum possible energy. By recognizing that the Hamiltonian of nanomagnets can be expressed in a quadratic form, we exploit the energy minimization aspect of these nanomagnets to solve the quadratic optimization problem in a direct manner. Most hard problems especially in computer vision can be naturally cast as energy minimization problems and solving these using traditional techniques like simulated annealing, graph cuts evidently associate with exorbitant computational efforts. In this dissertation, transcoding the conceptual crossover between the magnetic Hamiltonian and the optimization problem, we envision a nanomagnetic coprocessor with a grid of nanomagnets embracing an optimization heuristic enabling to solve energy minimization in a single clock cycle. We will essentially be solving an optimization problem with each input-and-readout cycle as compared to orders of magnitude more clock cycles that would be needed in a Boolean logic circuit. The dissertation presents results for quadratic minimization problem in the context of perceptual organization of edges in computer vision and compare quality of results using traditional optimization methods and that expected from magnetic computing. The dissertation also presents image processing algorithms for analysis of results produced by actual fabrication of the magnetic systems.

[pt] Nesta tese, é apresentado e analisado em termos da propriedade de convergência global um novo algoritmo para problemas de otimização quadrática sujeitos ou a restrições de desigualdades matriciais bilineares (BMIs) ou a restrições de desigualdades matriciais lineares (LMIs) dependentes da freqüência, estes problemas são muito relevantes para a teoria de controle porque uma ampla classe de controladores (por exemplo, controladores H2/Hinf de ordem fixa, síntese de controladores descentralizados, análise do desempenho robusto H2 ou Hinf, etc.) pode ser computada a partir da solução de problemas de otimização desta natureza. Infelizmente, estes problemas são reconhecidamente de difícil solução, pois envolvem, entre outras coisas, não convexidade (restrição BMI), não diferenciabilidade da restrição, etc. em função dessa complexibilidade, algumas alternativas para a obtenção de soluções aproximadas têm sido adotada na literatura especializada recente (Safonov, 1994; Paganini, 1996). O algoritmo proposto neste trabalho de tese é uma alternativa para as abordagens atuais com vantagens no sentido de permitir a obtenção de melhores aproximações assim como a possibilidade de explorar a estrutura particular de cada problema de interesse e, com isso, viabilizar do ponto de vista computacional o projeto de controladores envolvendo plantas de ordem mais elevada. Este algoritmo pode ser visto como a generalização de um algoritmo anterior com boas propriedades proposto por Corrêa & Sales (1998) para problemas quadráticos sujeitos a restrições envolvendo LMIs canônicas. De forma bastante genética, a solução do problema original (um problema envolvendo um número infinito de restrições é substituído por uma única) onde, em cada passo do algoritmo, a restrição é interativamente modificada. Demonstrar-se-á que para problemas quadráticos envolvendo restrições BMIs (problemas não convexos) a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Por outro lado, no caso dos problemas quadráticos envolvendo restrições LMIs dependentes da freqüência, a seqüência gerada de custos auxiliares é monótona crescente e, adicionalmente, se a seqüência de matrizes de ponderação for limitada superiormente (uma condição suficiente), demonstrar-se-á que a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Finalmente, são apresentadas algumas aplicações a problemas de controle acompanhadas de alguns exemplos numéricos ilustrativos. / [en] In this thesis, it is proposed and analysed in terms of the global-convergence property a new algorithm for solving quadratic optimisation problems under either a BMI (bilinear matrix inequality) or a frequency-dependent LMI (linear matrix inequality) constraints. These problems are of special interest in the control literature a some very important control problems such as the H2/H(infinite) fixed-order controller, multiobjectives, H2 and H (infinite) robust performance analysis among others problems can be posed as problems of this kind for which does not still exist yet a reliable global convergent algorithm. Nowadays, approximate solutions to those problems are based upon grid and interpolation techniques as suggested by Paganini (1996) in the case of frequency- wise LMI constraints or branch and bound algorithms or branch and bound algorithms mainly and alternating LMIs as far as BMIs constraints are involved (Safonov, 1994). All of those approaches suffer, of course, from obvious numerical difficulties. In fact, those approaches were introduced as preliminary attempts in solving the problems just mentioned. The algorithm to presented here, which can be seen as a generalisation of an earlier algorithm proposed by Corrêa e Sales (1998) for solving standard feasibility LMIs problems, is a step forward in an attempt of handling difficulties not faced properly by those methodologies. In a broaden sense, the proposed algorithm solves the original problem (a problem subject to an infinite number of constraints is replaced by a single one properly chosen. It is worth noting that this basic idea was introduced by Lawson (1961) in a rather different context, namely, the problem of computing Tchebycheff approximations by means of sequences of weighted quadratic problems. It is pointed out here that in the case of quadratic problems under a BMI constraint (a nonconvex problem); it is proved that the sequence of auxiliary solutions generated by the algorithm converges to the global optimal solution of the original one. On the other hand, as for quadratic problems under a frequency-dependent LMI constraint (an infinite-dimensional problem) it is proved that the auxiliary cost-sequence values increases asymptotically and, If the weight updating sequence is bounded from above (a sufficient condition), the sequence of auxiliary solutions will converge to the optimal solution of the original problem as well. Finally, some applications to control problem are presented accompanied by some numerical examples.

In this paper we study through iterative methods the minimization problem min_{x∈C} £K(x) (P) where the set C of constraints is the set of fixed points of a nonexpansive mapping T in a real Hilbert space H, and the objective function £K:H¡÷R is supposed to be continuously Gateaux dierentiable. The gradient projection method for solving problem (P) involves with the projection P_{C}. When C = Fix(T), we provide a so-called hybrid iterative method for solving (P) and the method involves with the mapping T only. Two special cases are included: (1) £K(x)=(1/2)||x-u||^2 and (2) £K(x)=<Ax,x> - <x,b>. The first case corresponds to finding a fixed point of T which is closest to u from the fixed point set Fix(T). Both cases have received a lot of investigations recently.

[pt] Este trabalho apresenta um modelo de Regressão Linear Nebulosa por Partes(RLNP). Trata-se de uma estrutura que envolve modelos de regressão linear por partes ponderadas por pertinências advindas da lógica nebulosa. Este modelo é comparado com o modelo de regressão linear. Os resultados mostram que o RLNP consegue identificar a estrutura não-linear dos dados simulados e que na maioria dos casos ele possui bom poder de ajuste. / [en] In this dissertation a Fuzzy Piece-Wise Linear Regressive model FPLieR is developed. The model´s structure combines linear regressive models with fuzzy logic´s grade of membership in a piece-wise fashion. A comparision is made between this model and the linear regression one. The results show that FPLieR is able to find the linear substructure of simulated data and that in most cases it presents a good fit.

Cette thèse concerne l'élaboration de stratégies de commande prédictive pour certaines classes de systèmes dynamiques continus, discrets et hybrides modélisés par des extensions de réseaux de Petri ad hoc. Pour les systèmes continus et en vue de limiter la complexité de calcul inhérente à la forme standard de la commande prédictive, plusieurs améliorations sont proposées. Celles-ci permettent de surmonter le problème de "hill climbing" caractéristique des trajectoires obtenues avec certains réseaux de Petri. Elles assurent également la possibilité d'implémenter la commande en temps réel en adaptant l'horizon de prédiction pour réduire la complexité algorithmique. Enfin, elles permettent de limiter la sollicitation des actionneurs tout en garantissant la stabilité asymptotique du système commandé. Pour les systèmes discrets temporisés et pour éviter l'exploration exhaustive du graphe d'atteignabilité, une méthode de commande est proposée, basée sur la commande prédictive appliquée à une approximation continue du système discret. Enfin pour les systèmes hybrides, une commande prédictive hybride est développée, inspirée de la commande prédictive continue. Les performances de ces différentes stratégies de commande sont évaluées et comparées avec différentes simulations numériques / This thesis concerns the development of predictive control strategies for some classes of continuous, discrete and hybrid dynamic systems modeled by specific extensions of Petri nets. For continuous systems and in order to limit the computational complexity inherent to the standard form of the predictive control, several improvements are proposed. These improvements allow overcoming the problem of hill climbing that characterizes trajectories obtained with some Petri nets. They also ensure the possibility to implement real-time control by adapting the prediction horizon in order to reduce the algorithmic complexity. Finally, they limit actuators solicitation while ensuring the asymptotic stability of the controlled system. For timed discrete systems and in order to avoid the exhaustive exploration of the reachability graph, a control method is proposed, based on the predictive control applied to a continuous approximation of the discrete system. Finally for hybrid systems, hybrid predictive control is developed, inspired by the continuous predictive control. The performance of these different control strategies are evaluated and compared to different numerical simulations.

Modern machine learning methods are dependent on active optimization research to improve the set of methods available for the efficient and effective extraction of information from large datasets. This, in turn, requires an intense and rigorous study of optimization methods and their possible applications to crucial machine learning applications in order to advance the potential benefits of the field. This thesis provides a study of several modern optimization techniques and supplies a mathematical inquiry into the effectiveness of homotopy methods to attack a fundamental machine learning problem, effective clustering under constraints. The first part of this thesis provides an empirical survey of several popular optimization algorithms, along with one approach that is cutting-edge. These algorithms are tested against deeply challenging real-world problems with vast numbers of local minima, and compares and contrasts the benefits of each when confronted with problems of different natures. The second part of this thesis proposes a new homotopy map for use with constrained clustering problems. This thesis explores the connections between the map and the problem, providing several theorems to justify the use of the map and making use of modern homotopy tracking software to compare an optimization that employs the map with several modern approaches to solving the same problem. / Ph. D.

[pt] A geração de malhas geomecânicas de reservatórios ainda é uma tarefa tediosa que consome muito tempo. Para acelerar este processo, soluções que reconstroem analiticamente a geometria do reservatório têm sido propostas, mas essas soluções não são as mais adequadas para modelagem de objetos naturais. Este trabalho propõe uma modelagem discreta para a geometria do reservatório, onde os vértices da malha são posicionados por meio da solução de um problema de otimização quadrático e convexo. O problema de otimização é modelado de forma a garantir que as malhas geomecânicas de saída sejam suaves e que ao mesmo tempo respeitem as restrições do reservatório e dos horizontes presentes. Além disso, a metodologia proposta permite uma implementação eficiente, paralelizável e de baixo consumo de memória. Casos de teste com milhões de variáveis são apresentados para validar essa abordagem. Finalmente, a metodologia proposta neste trabalho para malhas de geomecânica pode ser naturalmente estendida para a modelagem estrutural de sub-superfícies na interpretação sísmica e de restauração geológica. / [en] Geomechanical mesh generation of complex reservoirs remains a tedious task prone to errors. Recently proposed solutions based on analytical reconstruction of the sub-surfaces are not capable to represent all the geometric details of natural objects. This work proposes a discrete model where the mesh vertices are positioned based on a convex quadratic optimization process. The optimization problem seeks to guarantee smooth meshes that conform with prescribed constraints. The resulting mesh therefore respects, as far as possible, the finite volume mesh of the reservoir pay zone and the existing horizons. Finally, the proposed methodology for Geomechanical meshes can be easily extend to model sub-surfaces present in the structural interpretation and geological restauration.

This thesis discusses the operational coordination of electrical appliances and devices in a smart home. At present, the diminishing volume of fossil fuels and the increasing pressure to use renewable sources of energy necessitate the integration of such volatile sources into electrical grids. This process, however, results in higher energy costs, and the consumers are thus more willing to change their behaviour to either reduce the expenses or maintain them at a reasonable level. One of the relatively few customer-oriented options to optimise energy costs consists in the demand – response principle, which utilises external information to minimise energy consumption during high price periods. Assuming the constantly changing conditions in electrical grids, and thus also the varying demands, it is vital to provide for automatic optimisation excluding the need of user intervention. The thesis presents a method which, after being implemented into the control member, will facilitate the optimal use of appliances and devices within a smart home. As the behaviour considered optimal from the perspective of demand - response is often inconsistent with the consumer‘s requirements for comfortable use of the appliances, the proposed technique offers a compromise through enabling the consumer to select the appropriate strategy. Five universal optimisation models are designed within the thesis; these models facilitate description of common home appliances and local electricity sources. The core of the method lies in formulating and optimising a mixed integer quadratic problem (MIQP). The optimisation task yields an operational schedule for the individual appliances, and this scheme considers the energy costs, the working cycle of the appliance, the user’s demands, the system restrictions and/or other input data. Furthermore, the author extends the above-discussed general technique, enabling it to adopt robust behaviour. The method then secures the preset strategy even during a marked change of the input conditions, and its robustness is a viable precondition for the overall applicability of the technique in the real control member.