Spelling suggestions: "subject:"con programming"" "subject:"code programming""
1 |
Global Optimization with PolynomialsHan, Deren 01 1900 (has links)
The class of POP (Polynomial Optimization Problems) covers a wide rang of optimization problems such as 0 - 1 integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. In this paper, we review some methods on solving the unconstraint case: minimize a real-valued polynomial p(x) : Rn â R, as well the constraint case: minimize p(x) on a semialgebraic set K, i.e., a set defined by polynomial equalities and inequalities. We also summarize some questions that we are currently considering. / Singapore-MIT Alliance (SMA)
|
2 |
Solving symmetric indefinite systems in an interior-point method for second order cone programmingToh, Kim Chuan, Cai, Zhi, Freund, Robert M. 01 1900 (has links)
Many optimization problems can be formulated as second order cone programming (SOCP) problems. Theoretical results show that applying interior-point method (IPM) to SOCP has global polynomial convergence. However, various stability issues arise in the implementation of IPM. The standard normal equation based implementation of IPM encounters stability problems in the computation of search direction. In this paper, an augmented system approach is proposed to overcome the stability problems. Numerical experiments show that the new approach can improve the stability. / Singapore-MIT Alliance (SMA)
|
3 |
Approximate LMMSE detector for uplink in multi-receiver MIMO systemLo, Kun-Feng 15 August 2011 (has links)
In this thesis, we consider receiver design problems in a multi-cell MIMO system using the coordinated multi-point transmission/reception technique. The linear minimum
mean square error (LMMSE) receiver, which involves the inverse operation, is adopted. By the Cayley-Hamilton theorem, the matrix inverse can be represented by weighted sum of power of matrices. Given an order of the matrix power, we calculate the best weight in sense of the minimum mean square error. Both the uplink and the downlink scenarios are considered. Also, given a target signal to interference and noise ratio (SINR), we consider the best weight design problem in the downlink scenario. This problem can be formulated as the second-order cone programming (SOCP) and semidefinite relaxation (SDR) programming. By computer simulations, we show that the SDR and SOCP are equivalent.
|
4 |
Dimension reduction methods for nonlinear association analysis with applications to omics dataWu, Peitao 06 November 2021 (has links)
With advances in high-throughput techniques, the availability of large-scale omics data has revolutionized the fields of medicine and biology, and has offered a better understanding of the underlying biological mechanisms. However, the high-dimensionality and the unknown association structure between different data types make statistical integration analyses challenging. In this dissertation, we develop three dimensionality reduction methods to detect nonlinear association structure using omics data. First, we propose a method for variable selection in a nonparametric additive quantile regression framework. We enforce a network regularization to incorporate information encoded by known networks. To account for nonlinear associations, we approximate the additive functional effect of each predictor with the expansion of a B-spline basis. We implement the group Lasso penalty to achieve sparsity. We define the network-constrained penalty by regulating the difference between the effect functions of any two linked genes (predictors) in the network. Simulation studies show that our proposed method performs well in identifying truly associated genes with fewer falsely associated genes than alternative approaches. Second, we develop a canonical correlation analysis (CCA)-based method, canonical distance correlation analysis (CDCA), and leverage the distance correlation to capture the overall association between two sets of variables. The CDCA allows untangling linear and nonlinear dependence structures. Third, we develop the sparse CDCA (sCDCA) method to achieve sparsity and improve result interpretability by adding penalties on the loadings from the CDCA. The sCDCA method can be applied to data with large dimensionality and small sample size. We develop iterative majorization-minimization-based coordinate descent algorithms to compute the loadings in the CDCA and sCDCA methods. Simulation studies show that the proposed CDCA and sCDCA approaches have better performance than classical CCA and sparse CCA (sCCA) in nonlinear settings and have similar performance in linear association settings. We apply the proposed methods to the Framingham Heart Study (FHS) to identify body mass index associated genes, the association structure between metabolic disorders and metabolite profiles, and a subset of metabolites and their associated type 2 diabetes (T2D)-related genes. / 2023-11-05T00:00:00Z
|
5 |
Convex relaxations in nonconvex and applied optimizationChen, Jieqiu 01 July 2010 (has links)
Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP).
We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically.
We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting.
New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement.
The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.
|
6 |
Evaluation structurale des murs de soutènement en maçonnerie / Stability assessment of masonry retaining wallsTerrade, Benjamin 15 December 2017 (has links)
Partout où la pierre est facilement disponible, on trouve des constructions en maçonnerie de pierre. Suivant les coutumes et les usages, les blocs de pierres sont assemblés bruts, simplement ébauchés ou parfaitement taillés, avec ou sans l'ajout d'un liant. Supplantée par le béton dans les constructions neuves depuis le milieu du XX} siècle, les ouvrages en maçonnerie demeurent majoritaires dans le patrimoine bâti français, un patrimoine qu'il convient d'entretenir rationnellement. L'objectif de ce travail de thèse est de poursuivre l'élaboration d'un cadre scientifique rigoureux et opérationnel afin de donner aux décideurs et aux gestionnaires les outils nécessaires pour mener à bien leur mission. Nous proposons ici deux outils d'évaluation de la stabilité d'ouvrages de soutènement en maçonnerie basés sur l'utilisation conjointe du calcul à la rupture avec des méthodes d'homogénéisation. Dans un premier temps, nous mettons d'abord au point un outil analytique permettant de dimensionner des ouvrages neufs ou d'évaluer la stabilité d'ouvrages peu déformés. Cet outil permet également de dimensionner des solutions de renforcement par clouage lorsque cela est jugé nécessaire. Dans un deuxième temps, nous implémentons cet outil dans un code numérique afin de lui donner la souplesse nécessaire à l'étude d'ouvrages non-conventionnels, de grandes taille ou fortement pathologique. Enfin, nous mettons en oeuvre plusieurs campagnes expérimentales qui nous fournissent les données nécessaires à la validation de ces modèles de calcul / Wherever stone is readily available, we encounter stone masonry buildings. Depending on customs or dedicated use, the blocks are used raw, lightly faced or perfectly cut, with or without the use of mortar. Althougth concrete has replaced masonry in new construction for some decades, the better part of the French built heritage is made of masonry, an heritage we are responsible for. This works aims at contributing to create a reliable scientific frame for that purpose. This thesis uses the yield design theory alongside with homogenisation techniques to study the stability of stone masonry earth retaining walls. First, we provide an analytical tool suitable for designing new structures or assessing the stability of existing ones that are still in good shape. Should it be needed, this tools allows for the design of a strengthening solution based on soil-nailing. Then, we implement it in a finite element code to give it the versatility required to study unconventionnal structures or structures badly damaged. We then present several experimental campaigns aiming at validating the proposed tools
|
7 |
Camera Motion Estimation for Multi-Camera SystemsKim, Jae-Hak, Jae-Hak.Kim@anu.edu.au January 2008 (has links)
The estimation of motion of multi-camera systems is one of the most important tasks in computer vision research. Recently, some issues have been raised about general camera models and multi-camera systems. Using many cameras as a single camera is studied [60], and the epipolar geometry constraints of general camera models is theoretically derived. Methods for calibration, including a self-calibration method for general camera models, are studied [78, 62]. Multi-camera systems are an example of practically implementable general camera models and they are widely used in many applications nowadays because of both the low cost of digital charge-coupled device (CCD) cameras and the high resolution of multiple images from the wide field of views. To our knowledge, no research has been conducted on the relative motion of multi-camera systems with non-overlapping views to obtain a geometrically optimal solution. ¶
In this thesis, we solve the camera motion problem for multi-camera systems by using linear methods and convex optimization techniques, and we make five substantial and original contributions to the field of computer vision. First, we focus on the problem of translational motion of omnidirectional cameras, which are multi-camera systems, and present a constrained minimization method to obtain robust estimation results. Given known rotation, we show that bilinear and trilinear relations can be used to build a system of linear equations, and singular value decomposition (SVD) is used to solve the equations. Second, we present a linear method that estimates the relative motion of generalized cameras, in particular, in the case of non-overlapping views. We also present four types of generalized cameras, which can be solvable using our proposed, modified SVD method. This is the first study finding linear relations for certain types of generalized cameras and performing experiments using our proposed linear method. Third, we present a linear 6-point method (5 points from the same camera and 1 point from another camera) that estimates the relative motion of multi-camera systems, where cameras have no overlapping views. In addition, we discuss the theoretical and geometric analyses of multi-camera systems as well as certain critical configurations where the scale of translation cannot be determined. Fourth, we develop a global solution under an L∞ norm error for the relative motion problem of multi-camera systems using second-order cone programming. Finally, we present a fast searching method to obtain a global solution under an L∞ norm error for the relative motion problem of multi-camera systems, with non-overlapping views, using a branch-and-bound algorithm and linear programming (LP). By testing the feasibility of LP at the earlier stage, we reduced the time of computation of solving LP.¶
We tested our proposed methods by performing experiments with synthetic and real data. The Ladybug2 camera, for example, was used in the experiment on estimation of the translation of omnidirectional cameras and in the estimation of the relative motion of non-overlapping multi-camera systems. These experiments showed that a global solution using L∞ to estimate the relative motion of multi-camera systems could be achieved.
|
8 |
Um algoritmo branch-and-bound para o problema do caixeiro viajante suficientemente próximoCoutinho, Walton Pereira 13 February 2014 (has links)
Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 7900350 bytes, checksum: fbca2db827307d8c3ed2a1c15067d0da (MD5)
Previous issue date: 2014-02-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research deals with the Close-Enough Traveling Salesman Problem, a variant of the
Traveling Salesman Problem wich has several applicatios in logistics. In the Close-Enough
Traveling Salesman Problem, rather than visiting the vertex (customer) itself, the salesman
must visit a specific region containing such vertex. To solve this problem, we propose
a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order
Cone Programming. The proposed algorithm was tested in 824 instances suggested in
the literature. Optimal solutions are obtained for open problems with up to a thousand
vertices. We consider both instances in the two- and three-dimensional space. / Esta pesquisa trata do Problema do Caixeiro Viajante Suficientemente Próximo, uma variante
do Problema do Caixeiro Viajante que possui diversas aplicações em logística. No
Problema do Caixeiro Viajante Suficientemente Próximo, ao invés de visitar o próprio
vértice (cliente), o caixeiro deve visitar uma região especifica contendo este vértice. Para
resolver este problema, é proposto um algoritmo exato, simples e efetivo, baseado em
branch-and-bound e Programação Cônica de Segunda Ordem. O algoritmo proposto foi
testado em 824 instâncias sugeridas na literatura. Soluções ótimas foram obtidas para
instâncias com até mil vértices. Foram consideradas instâncias nos espaços bi e tridimensional.
|
9 |
Détermination numérique des propriétés de résistance de roches argileuses / Numerical determination of the resistance properties of claystonesPham, Anh Tu 21 December 2017 (has links)
Les capacités de résistance de l'argilite Callovo-Oxfordian (COx), qui est une roche hôte potentielle pour le dépôt souterrain profond de déchets radioactifs de haute activité en France, sont étudiées. À une échelle microscopique, des micros pores peuvent être observés dans la matrice. Une première étape d'homogénéisation a été réalisée afin d'évaluer le critère de résistance de la matrice. L'analyse microstructurale de ce matériau à quelques centaines d'échelle, référencée échelle échelle mésoscopique, montre une matrice argileuse et une distribution aléatoire d'inclusions minérales (quartz et calcite).Dans le but de déterminer le domaine de résistance à l'argilite COx, un premier outil numérique a été développé dans le contexte du comportement élastoplastique de la matrice. Plusieurs modèles morphologiques du volume élémentaire représentatif ont été considérés, et soumis à un chargement incrémental dans des conditions périodiques jusqu'à la charge limite. A la suite de ce calcul élastoplastique, un point de la frontière du domaine de résistance est obtenu. Ce dernier est alors obtenu par des calculs élastoplastiques successifs.Une alternative aux simulations élastoplastique directes, des approches cinématiques et statiques du calcul à la rupture sont réalisées. Une méthode du type éléments finis basée sur la construction d'un champ de contrainte (dans l'approche statique) et d'un champ de vitesse (dans l'approche cinématique) est développé dans un outil numérique permettant de calculer une limite inférieure et une limite supérieure de domaine de résistance / The strength capacities of Callovo-Oxfordian (COx) argillite which is a potential host rock for the deep underground repository of high-level radioactive waste in France are investigated. At a micro-scale, micro-pores can be observed in the matrix. A first strength homogenization step has been performed in order to evaluate the matrix strength criteria. The microstructure analysis of this material at some hundreds of micromet scale, referred at meso-scale, shows a clay matrix and a random distribution of mineral inclusions (quartz and calcite).Aiming to the determination of COx argillite strength domain, an FEM numerical tool has been developed in the context of the elastoplastic behavior of the matrix. Several morphological patterns of the representative elementary volume have been considered and subjected to an incremental loading in periodic conditions until collapse occurs. As a result of such elastoplastic calculation, one point of the boundary of the strength domain is obtained. The latter then could be reached by successive elastoplastic calculations.As an alternative to direct elastoplastic simulations, kinematic and static approaches of limit analysis are performed. The stress-based (static approach) and the velocity-based (kinematic approach) finite element method are used to develop a numerical tool able to derive a lower bound and upper bound of strength domain, respectively
|
10 |
Localization algorithms for passive sensor networksIsmailova, Darya 23 January 2017 (has links)
Locating a radiating source based on range or range measurements obtained from a network of passive sensors has been a subject of research over the past two decades due to the problem’s importance in applications in wireless communications, surveillance, navigation, geosciences, and several other fields. In this thesis, we develop new solution methods for the problem of localizing a single radiating source based on range and range-difference measurements. Iterative re-weighting algorithms are developed for both range-based and range-difference-based least squares localization. Then we propose a penalty convex-concave procedure for finding an approximate solution to nonlinear least squares problems that are related to the range measurements. Finally, the sequential convex relaxation procedures are proposed to obtain the nonlinear least squares estimate of source coordinates. Localization in wireless sensor network, where the RF signals are used to derive the ranging measurements, is the primary application area of this work. However, the solution methods proposed are general and could be applied to range and range-difference measurements derived from other types of signals. / Graduate / 0544 / ismailds@uvic.ca
|
Page generated in 0.1008 seconds