To see the other types of publications on this topic, follow the link: Linear problems.
Dissertations / Theses on the topic 'Linear problems'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Linear problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Kumar, Manish. "Converting some global optimization problems to mixed integer linear problems using piecewise linear approximations." Diss., Rolla, Mo. : University of Missouri-Rolla, 2007. http://scholarsmine.umr.edu/thesis/pdf/Kumar_09007dcc803c8e68.pdf.
Full textAbstract:
Thesis (M.S.)--University of Missouri--Rolla, 2007.Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed December 7, 2007) Includes bibliographical references (p. 28).
2
Minne, Andreas. "Non-linear Free Boundary Problems." Doctoral thesis, KTH, Matematik (Avd.), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-178110.
Full textAbstract:
This thesis consists of an introduction and four research papers related to free boundary problems and systems of fully non-linear elliptic equations. Paper A and Paper B prove optimal regularity of solutions to general elliptic and parabolic free boundary problems, where the operators are fully non-linear and convex. Furthermore, it is proven that the free boundary is continuously differentiable around so called "thick" points, and that the free boundary touches the fixed boundary tangentially in two dimensions. Paper C analyzes singular points of solutions to perturbations of the unstable obstacle problem, in three dimensions. Blow-up limits are characterized and shown to be unique. The free boundary is proven to lie close to the zero-level set of the corresponding blow-up limit. Finally, the structure of the singular set is analyzed. Paper D discusses an idea on how existence and uniqueness theorems concerning quasi-monotone fully non-linear elliptic systems can be extended to systems that are not quasi-monotone.QC 20151210
3
Wokiyi, Dennis. "Non-linear inverse geothermal problems." Licentiate thesis, Linköpings universitet, Matematik och tillämpad matematik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-143031.
Full textAbstract:
The inverse geothermal problem consist of estimating the temperature distribution below the earth’s surface using temperature and heat-flux measurements on the earth’s surface. The problem is important since temperature governs a variety of the geological processes including formation of magmas, minerals, fosil fuels and also deformation of rocks. Mathematical this problem is formulated as a Cauchy problem for an non-linear elliptic equation and since the thermal properties of the rocks depend strongly on the temperature, the problem is non-linear. This problem is ill-posed in the sense that it does not satisfy atleast one of Hadamard’s definition of well-posedness. We formulated the problem as an ill-posed non-linear operator equation which is defined in terms of solving a well-posed boundary problem. We demonstrate existence of a unique solution to this well-posed problem and give stability estimates in appropriate function spaces. We show that the operator equation is well-defined in appropriate function spaces. Since the problem is ill-posed, regularization is needed to stabilize computations. We demostrate that Tikhonov regularization can be implemented efficiently for solving the operator equation. The algorithm is based on having a code for solving a well- posed problem related to the operator equation. In this study we demostrate that the algorithm works efficiently for 2D calculations but can also be modified to work for 3D calculations.
4
Ang, W. T. "Some crack problems in linear elasticity /." Title page, table of contents and summary only, 1987. http://web4.library.adelaide.edu.au/theses/09PH/09pha581.pdf.
Full text
5
Higham, N. J. "Nearness problems in numerical linear algebra." Thesis, University of Manchester, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.374580.
Full text
6
Austin, D. M. "On two problems in linear elasticity." Thesis, University of Manchester, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.378026.
Full text
7
Yodpinyanee, Anak. "Sub-linear algorithms for graph problems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120411.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models.
by Anak Yodpinyanee.
Ph. D.
8
Chonev, Ventsislav. "Reachability problems for linear dynamical systems." Thesis, University of Oxford, 2015. https://ora.ox.ac.uk/objects/uuid:e73d1a5b-edce-4e1d-a593-fd8df7e2a817.
Full textAbstract:
The object of principal interest in this thesis is linear dynamical systems: deterministic systems which evolve under a linear operator. They are specified by an initial state set I, contained in ℝm, and a real m-by-m evolution matrix A. We distinguish two varieties of linear dynamical systems: discrete-time and continuous-time. In the discrete-time setting, the state x(n) of the system at time n for natural n is governed by the difference equation x(n)=Ax(n-1). Similarly, in the continuous case, the state x(t) at real, non-negative times t is determined by a system of first-order linear differential equations: x'(t) = Ax(t). In both cases, x(0) lies in I. Throughout this thesis, we will be interested in the Reachability Problem for linear dynamical systems, which may be formulated in a general way as follows: given a target set T contained in ℝm and a (discrete- or continuous-time) linear dynamical system specified by the evolution matrix A and the set of initial states I, determine whether for all x(0) in I, starting from x(0), the system will eventually be in a state which lies in T. In order to make the decision problem well-defined, one must first fix an admissible class of initial sets and, similarly, a class of target sets of interest. For the purposes of expressing the problem instance, it is also necessary to restrict the domain of the input data to a subset of the reals which may be represented effectively, such as the rational numbers or the algebraic numbers. As we vary the choice of domain, the types of initial and target sets under consideration and the discreteness of time, a rich landscape of decision problems emerges. The goal of the present thesis is to explore pointwise reachability problems, that is, reachability from a single initial state. Under the assumption that I consists of a single point in ℝm provided as part of the input data, we will study reachability to polyhedral targets, in the context of both discrete- and continuous-time linear dynamical systems. We prove both upper complexity bounds and hardness results, employing in the process a wide-ranging arsenal of techniques and mathematical tools. We rely on powerful number-theoretic results, such as Baker's Theorem on inhomogeneous linear forms of logarithms of algebraic numbers, Schanuel's Conjecture on the transcendence degree of certain field extensions of the rationals, and Kronecker's Theorem on simultaneous inhomogeneous Diophantine approximation. We draw interesting connections with the study of linear recurrence sequences and exponential polynomials, and relate pointwise reachability to open problems concerning the approximability by rationals of algebraic numbers and logarithms of algebraic numbers. Albeit a simple model, linear dynamical systems are of profound interest, both from a theoretical and a practical standpoint. Reachability problems for linear dynamical systems have recently elicited considerable attention, due to their frequent occurrence in practice and their deep and wide-ranging connections with other fascinating areas of study, such as problems on Markov chains (Akshay et al., 2015), quantum automata (Derksen et al., 2005), Lindenmayer systems (Salomaa and Soittola, 1978), linear loops (Braverman, 2006), linear recurrence sequences (Everest et al., 2003) and exponential polynomials (Bell et al., 2010).
9
Julius, Hayden. "Nonstandard solutions of linear preserver problems." Kent State University / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=kent1626101272174819.
Full text
10
羅恩妮 and Yan-nei Law. "Some additive preserver problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2000. http://hub.hku.hk/bib/B31222912.
Full text
11
Law, Yan-nei. "Some additive preserver problems /." Hong Kong : University of Hong Kong, 2000. http://sunzi.lib.hku.hk/hkuto/record.jsp?B22054820.
Full text
12
Edlund, Ove. "Solution of linear programming and non-linear regression problems using linear M-estimation methods /." Luleå, 1999. http://epubl.luth.se/1402-1544/1999/17/index.html.
Full text
13
Stoth, Barbara E. E. Jiang Song. "On periodic solutions of linear thermostat problems." Bonn : [s.n.], 1989. http://catalog.hathitrust.org/api/volumes/oclc/19990668.html.
Full text
14
Jamieson, Alan C. "Linear-time algorithms for edge-based problems." Connect to this title online, 2007. http://etd.lib.clemson.edu/documents/1193079463/.
Full text
15
馮漢國 and Hon-kwok Fung. "Some linear preserver problems in system theory." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1995. http://hub.hku.hk/bib/B3121227X.
Full text
16
Noble, Raymond Keith. "Some problems associated with linear differential operators." Thesis, Cardiff University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.238160.
Full text
17
McKay, Barry. "Wrinkling problems for non-linear elastic membranes." Thesis, University of Glasgow, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.307187.
Full text
18
Baek, Kwang-Hyun. "Non-linear optimisation problems in active control." Thesis, University of Southampton, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.243131.
Full text
19
Fung, Hon-kwok. "Some linear preserver problems in system theory /." [Hong Kong] : University of Hong Kong, 1995. http://sunzi.lib.hku.hk/hkuto/record.jsp?B16121673.
Full text
20
GANDOLPHO, ANDRE ALVES. "METHODOLOGY FOR SOLVING FUZZY LINEAR PROGRAMMING PROBLEMS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2005. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=8070@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOREsta tese propõe uma metodologia para obter uma solução para problemas de programação linear fuzzy. A metodologia aqui descrita apresenta um conjunto de soluções em que tanto os valores das variáveis quanto o valor ótimo para a função de custo, ou função objetivo, possuem uma faixa de valores possíveis. Assim, é possível fornecer um conjunto de soluções factíveis que atendam a diferentes cenários, além de fornecer ao tomador de decisões uma ferramenta de análise mais útil, permitindo que sejam analisadas outras soluções possíveis antes de se escolher uma solução em particular. O problema é resolvido de forma iterativa, tornando mais simples e de fácil aplicação a metodologia desenvolvida.
This work proposes an approach to obtain a solution to linear fuzzy programming problems. The approach described here presents a solution set in where both the variables values and the cost function optimun value to have an associated membership function. Thus, it is possible to provided not only a feasible solution set applicable to different scenarios but also to supply the decision maker with a more powerful tool for the analysis of other possible solutions. The problem is solved in an interactive way, so that the developed is approach easily applicable and simple to handle
21
Spence, Euan Alastair. "Boundary value problems for linear elliptic PDEs." Thesis, University of Cambridge, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.609476.
Full text
22
Chen, Shang. "Reachability problems for systems with linear dynamics." Thesis, Loughborough University, 2016. https://dspace.lboro.ac.uk/2134/22331.
Full textAbstract:
This thesis deals with reachability and freeness problems for systems with linear dynamics, including hybrid systems and matrix semigroups. Hybrid systems are a type of dynamical system that exhibit both continuous and discrete dynamic behaviour. Thus they are particularly useful in modelling practical real world systems which can both flow (continuous behaviour) and jump (discrete behaviour). Decision questions for matrix semigroups have attracted a great deal of attention in both the Mathematics and Theoretical Computer Science communities. They can also be used to model applications with only discrete components. For a computational model, the reachability problem asks whether we can reach a target point starting from an initial point, which is a natural question both in theoretical study and for real-world applications. By studying this problem and its variations, we shall prove in a formal mathematical sense that many problems are intractable or even unsolvable. Thus we know when such a problem appears in other areas like Biology, Physics or Chemistry, either the problem itself needs to be simplified, or it should by studied by approximation. In this thesis we concentrate on a specific hybrid system model, called an HPCD, and its variations. The objective of studying this model is twofold: to obtain the most expressive system for which reachability is algorithmically solvable and to explore the simplest system for which it is impossible to solve. For the solvable sub-cases, we shall also study whether reachability is in some sense easy or hard by determining which complexity classes the problem belongs to, such as P, NP(-hard) and PSPACE(-hard). Some undecidable results for matrix semigroups are also shown, which both strengthen our knowledge of the structure of matrix semigroups, and lead to some undecidability results for other models.
23
Schenck, David Robert. "Some Formation Problems for Linear Elastic Materials." Diss., Virginia Tech, 1999. http://hdl.handle.net/10919/28608.
Full textAbstract:
Some equations of linear elasticity are developed, including those
specific to certain actuator structures considered in formation
theory. The invariance of the strain-energy under the transformation
from rectangular to spherical coordinates is then established for use
in two specific formation problems. The first problem, involving an
elastic structure with a cylindrical equilibrium configuration, is
formulated in two dimensions using polar coordinates. It is shown
that $L^2$ controls suffice to obtain boundary displacements in
$H^{1/2}$. The second problem has a spherical equilibrium
configuration and utilizes the elastic equations in spherical
coordinates. Results similar to those obtained in the two dimensional
case are indicated for the three dimensional problem.Ph. D.
24
Garcia, Francisco Javier. "THREE NON-LINEAR PROBLEMS ON NORMED SPACES." Kent State University / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=kent1171042141.
Full text
25
Kannan, Ramaseshan. "Numerical linear algebra problems in structural analysis." Thesis, University of Manchester, 2014. https://www.research.manchester.ac.uk/portal/en/theses/numerical-linear-algebra-problems-in-structural-analysis(7df0f708-fc12-4807-a1f5-215960d9c4d4).html.
Full textAbstract:
A range of numerical linear algebra problems that arise in finite element-based structural analysis are considered. These problems were encountered when implementing the finite element method in the software package Oasys GSA. We present novel solutions to these problems in the form of a new method for error detection, algorithms with superior numerical effeciency and algorithms with scalable performance on parallel computers. The solutions and their corresponding software implementations have been integrated into GSA's program code and we present results that demonstrate the use of these implementations by engineers to solve real-world structural analysis problems.
26
Tsang, Siu Chung. "Preconditioners for linear parabolic optimal control problems." HKBU Institutional Repository, 2017. https://repository.hkbu.edu.hk/etd_oa/464.
Full textAbstract:
In this thesis, we consider the computational methods for linear parabolic optimal control problems. We wish to minimize the cost functional while fulfilling the parabolic partial differential equations (PDE) constraint. This type of problems arises in many fields of science and engineering. Since solving such parabolic PDE optimal control problems often lead to a demanding computational cost and time, an effective algorithm is desired. In this research, we focus on the distributed control problems. Three types of cost functional are considered: Target States problems, Tracking problems, and All-time problems. Our major contribution in this research is that we developed a preconditioner for each kind of problems, so our iterative method is accelerated. In chapter 1, we gave a brief introduction to our problems with a literature review. In chapter 2, we demonstrated how to derive the first-order optimality conditions from the parabolic optimal control problems. Afterwards, we showed how to use the shooting method along with the flexible generalized minimal residual to find the solution. In chapter 3, we offered three preconditioners to enhance our shooting method for the problems with symmetric differential operator. Next, in chapter 4, we proposed another three preconditioners to speed up our scheme for the problems with non-symmetric differential operator. Lastly, we have the conclusion and the future development in chapter 5.
27
Toutip, Wattana. "The dual reciprocity boundary element method for linear and non-linear problems." Thesis, University of Hertfordshire, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.369302.
Full textAbstract:
A problem encountered in the boundary element method is the difficulty caused by corners and/or discontinuous boundary conditions. An existing code using standard linear continuous elements is modified to overcome such problems using the multiple node method with an auxiliary boundary collocation approach. Another code is implemented applying the gradient approach as an alternative to handle such problems. Laplace problems posed on variety of domain shapes have been introduced to test the programs. For Poisson problems the programs have been developed using a transformation to a Laplace problem. This method cannot be applied to solve Poissontype equations. The dual reciprocity boundary element method (DRM) which is a generalised way to avoid domain integrals is introduced to solve such equations. The gradient approach to handle corner problems is co-opted in the program using DRM. The program is modified to solve non-linear problems using an iterative method. Newton's method is applied in the program to enhance the accuracy of the results and reduce the number of iterations. The program is further developed to solve coupled Poisson-type equations and such a formulation is considered for the biharmonic problems. A coupled pair of non-linear equations describing the ohmic heating problem is also investigated. Where appropriate results are compared with those from reference solutions or exact solutions. v
28
Sze, Nung-sing. "A study of preserver problems." Click to view the E-thesis via HKUTO, 2005. http://sunzi.lib.hku.hk/hkuto/record/B31607998.
Full text
29
Sze, Nung-sing, and 施能聖. "A study of preserver problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2005. http://hub.hku.hk/bib/B31607998.
Full text
30
Mehadhebi, Karim. "Linear expected time algorithms for nearest neighbor problems." Thesis, McGill University, 1994. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=22774.
Full textAbstract:
This thesis presents and analyses a bucketing algorithm that finds a proximity graph in linear expected time when the points are independent identically distributed with a Lipschitz density f, provided f satisfies a weak assumption. From this proximity graph one can either find the minimum spanning tree in $O(n$ log* $n)$ time or solve the all nearest neighbors problem in $O(n)$ time.
31
Chinviriyasit, Settapat. "Numerical methods for treating quasistatic linear viscoelastic problems." Thesis, Brunel University, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.367443.
Full text
32
Branford, Simon. "Hybrid Monte Carlo methods for linear algebraic problems." Thesis, University of Reading, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.499367.
Full textAbstract:
Forsythe and Leibler presented the first research, in 1950, showing how a matrix could be inverted using Monte Carlo (MC) methods. West and Sobol extended this research by presenting MC algorithms to give statistical estimates for the elements of the inverse matrix, or for the components of the solution vector of a system of linear algebraic equations (SLAE). This algorithm uses a Markov chain MC method to generate a rough approximation to the inverse matrix and then rapidly improves the accuracy of the rough inverse using an iterative refinement scheme. Further results are presented comparing the performance of the sparse hybrid MC algorithm with other methods for producing inverse matrices.
33
Sorour, Ahmed El-Sayed. "Some problems in non-linear open loop systems." Thesis, University of Kent, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.279420.
Full text
34
Shikongo, Albert. "Numerical Treatment of Non-Linear singular pertubation problems." Thesis, Online access, 2007. http://etd.uwc.ac.za/usrfiles/modules/etd/docs/etd_gen8Srv25Nme4_3831_1257936459.pdf.
Full text
35
Akinola, Richard O. "Numerical solution of linear and nonlinear eigenvalue problems." Thesis, University of Bath, 2010. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.520903.
Full textAbstract:
Given a real parameter-dependent matrix, we obtain an algorithm for computing the value of the parameter and corresponding eigenvalue for which two eigenvalues of the matrix coalesce to form a 2-dimensional Jordan block. Our algorithms are based on extended versions of the implicit determinant method of Spence and Poulton [55]. We consider when the eigenvalue is both real and complex, which results in solving systems of nonlinear equations by Newton’s or the Gauss-Newton method. Our algorithms rely on good initial guesses, but if these are available, we obtain quadratic convergence. Next, we describe two quadratically convergent algorithms for computing a nearby defective matrix which are cheaper than already known ones. The first approach extends the implicit determinant method in [55] to find parameter values for which a certain Hermitian matrix is singular subject to a constraint. This results in using Newton’s method to solve a real system of three nonlinear equations. The second approach involves simply writing down all the nonlinear equations and solving a real over-determined system using the Gauss-Newton method. We only consider the case where the nearest defective matrix is real. Finally, we consider the computation of an algebraically simple complex eigenpair of a nonsymmetric matrix where the eigenvector is normalised using the natural 2-norm, which produces only a single real normalising equation. We obtain an under-determined system of nonlinear equations which is solved by the Gauss-Newton method. We show how to obtain an equivalent square linear system of equations for the computation of the desired eigenpairs. This square system is exactly what would have been obtained if we had ignored the non uniqueness and nondifferentiability of the normalisation.
36
Furini, Fabio <1982>. "Decomposition and reformulation of integer linear programming problems." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2011. http://amsdottorato.unibo.it/3593/.
Full textAbstract:
This thesis deals with an investigation of Decomposition and Reformulation to solve Integer
Linear Programming Problems. This method is often a very successful approach computationally,
producing high-quality solutions for well-structured combinatorial optimization problems
like vehicle routing, cutting stock, p-median and generalized assignment . However, until now
the method has always been tailored to the specific problem under investigation. The principal
innovation of this thesis is to develop a new framework able to apply this concept to
a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation
of the input problem applicable as a resolving black box algorithm and works as
a complement and alternative to the normal resolving techniques. The idea of Decomposing
and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is,
given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the
partially convexified polyhedron(s) obtained. For a given MIP several decompositions can
be defined depending from what sets of constraints we want to convexify. In this thesis we
mainly reformulate MIPs using two sets of variables: the original variables and the extended
variables (representing the exponential extreme points). The master constraints consist of
the original constraints not included in any slaves plus the convexity constraint(s) and the
linking constraints(ensuring that each original variable can be viewed as linear combination
of extreme points of the slaves). The solution procedure consists of iteratively solving the
reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and
in which case adding it to the master and solving it again (columns generation), or otherwise
stopping the procedure. The advantage of using DWD is that the reformulated relaxation
gives bounds stronger than the original LP relaxation, in addition it can be incorporated in
a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality.
If the computational time for the pricing problem is reasonable this leads in practice to a
stronger speed up in the solution time, specially when the convex hull of the slaves is easy
to compute, usually because of its special structure.
37
Aldahmani, Saeed. "High-dimensional linear regression problems via graphical models." Thesis, University of Essex, 2017. http://repository.essex.ac.uk/19207/.
Full textAbstract:
This thesis introduces a new method for solving the linear regression problem where the number of observations n is smaller than the number of variables (predictors) v. In contrast to existing methods such as ridge regression, Lasso and Lars, the proposed method uses the idea of graphical models and provides unbiased parameter estimates under certain conditions. In addition, the new method provides a detailed graphical conditional correlation structure for the predictors, whereby the real causal relationship between predictors can be identified. Furthermore, the proposed method is extended to form a hybridisation with the idea of ridge regression to improve efficiency in terms of computation and model selection. In the extended method, less important variables are regularised by a ridge type penalty, and a search for models in the space is made for important covariates. This significantly reduces computational cost while giving unbiased estimates for the important variables as well as increasing the efficiency of model selection. Moreover, the extended method is used in dealing with the issue of portfolio selection within the Markowitz mean-variance framework, with n < v. Various simulations and real data analyses were conducted for comparison between the two novel methods and the aforementioned existing methods. Our experiments indicate that the new methods outperform all the other methods when n
38
Schülke, Christophe. "Statistical physics of linear and bilinear inference problems." Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC058.
Full textAbstract:
Le développement récent de l'acquisition comprimée a permis de spectaculaires avancées dans la compréhension des problèmes d'estimation linéaire parcimonieuse. Ce développement a suscité un intérêt renouvelé pour les problèmes d'inférence linéaire et bilinéaire généralisée. Ces problèmes combinent une étape linéaire avec une étape non lineaire et probabiliste, à l'issue de laquelle des mesures sont effectuées. Ce type de situations se présente notamment en imagerie médicale et en astronomie. Cette thèse s'intéresse à des algorithmes pour la résolution de ces problèmes et à leur analyse théorique. Pour cela, nous utilisons des algorithmes de passage de message, qui permettent d'échantillonner des distributions de haute dimension. Ces algorithmes connaissent des changements de phase, qui se laissent analyser à l'aide de la méthode des répliques, initialement développée dans le cadre de la physique statistique des milieux désordonnés. L'analyse des phases révèle qu'elles correspondent à des domaines dans lesquels l'inférence est facile, difficile ou impossible. Les principales contributions de cette thèse sont de trois types. D'abord, l'application d'algorithmes connus à des problèmes concrets : détection de communautés, codes correcteurs d'erreurs ainsi qu'un système d'imagerie innovant. Ensuite, un nouvel algorithme traitant le problème de calibration aveugle de capteurs, potentiellement applicable à de nombreux systèmes de mesure. Enfin, une analyse théorique du problème de reconstruction de matrices à petit rang à partir de projections linéaires, ainsi qu'une analyse d'une instabilité présente dans les algorithmes d'inférence bilinéaireThe recent development of compressed sensing has led to spectacular advances in the under standing of sparse linear estimation problems as well as in algorithms to solve them. It has also triggered anew wave of developments in the related fields of generalized linear and bilinear inference problems. These problems have in common that they combine a linear mixing step and a nonlinear, probabilistic sensing step, producing indirect measurements of a signal of interest. Such a setting arises in problems such as medical or astronomical Imaging. The aim of this thesis is to propose efficient algorithms for this class of problems and to perform their theoretical analysis. To this end, it uses belief propagation, thanks to which high-dimensional distributions can be sampled efficiently, thus making a bayesian approach to inference tractable. The resulting algorithms undergo phase transitions that can be analyzed using the replica method, initially developed in statistical physics of disordered systems. The analysis reveals phases in which inference is easy, hard or impossible, corresponding to different energy landscapes of the problem. The main contributions of this thesis can be divided into three categories. First, the application of known algorithms to concrete problems : community detection, superposition codes and an innovative imaging system. Second, a new, efficient message-passing algorithm for blind sensor calibration, that could be used in signal processing for a large class of measurement systems. Third, a theoretical analysis of achievable performances in matrix compressed sensing and of instabilities in bayesian bilinear inference algorithms
39
Ozdaryal, Burak. "Exterior Penalty Approaches for Solving Linear Programming Problems." Thesis, Virginia Tech, 1999. http://hdl.handle.net/10919/33862.
Full textAbstract:
In this research effort, we study three exterior penalty function approaches for solving linear programming problems. These methods are an active set l2 penalty approach (ASL2), an inequality-equality based l2 penalty approach (IEL2), and an augmented Lagrangian approach (ALAG). Particular effective variants are presented for each method, along with comments and experience on alternative algorithmic strategies that were empirically investigated. Our motivation is to examine the relative performance of these different approaches based on the basic l2 penalty function in order to provide insights into the viability of these methods for solving linear programs. To test the performance of these algorithms, a set of randomly generated problems as well as a set of NETLIB test problems from the public domain are used. By way of providing a benchmark for comparisons, we also solve the test problems using CPLEX 6.0, an advanced simplex implementation. While a particular variant (ALAG2) of ALAG performed the best for randomly generated test problems, ASL2 performed the best for the NETLIB test problems. Moreover, for test problems having only equality constraints, IEL2, and ASL2 (which is a finer-tuned version of IEL2 in this case) were comparable and yielded a second-best performance in comparison with ALAG2. Furthermore, a set of problems with relatively higher density parameter values, as well as a set of low-density problems were used to determine the effect of density on the relative performances of these methods. This experiment revealed that for linear programs with a high density parameter, ASL2 is the best alternative among the tested algorithms; whereas, for low-density problems ALAG2 is the fastest method. Moreover, although our implementation was rudimentary in comparison with CPLEX, all of the tested methods attained a final solution faster than CPLEX for the set of large-scale low-density problems, sometimes as fast as requiring only 16-23% of the effort consumed by CPLEX. Average rank tests based on the computational results obtained are performed using two different statistics, that assess the speed of convergence and the quality or accuracy of the solution, in order to determine the relative effectiveness of the algorithms and to validate our conclusions. Overall, the results provide insights into selecting algorithmic strategies based on problem structure and indicate that while this class of methods is viable for computing near optimal solutions, more research is needed to design robust and competitive exterior point methods for solving linear programming problems. However, the use of the proposed variant of the augmented Lagrangian method to solve large-scale low-density linear programs is promising and should be explored more extensively.Master of Science
40
Indratno, Sapto Wahyu. "Numerical methods for solving linear ill-posed problems." Diss., Kansas State University, 2011. http://hdl.handle.net/2097/8109.
Full textAbstract:
Doctor of PhilosophyDepartment of Mathematics
Alexander G. Ramm
A new method, the Dynamical Systems Method (DSM), justified recently, is applied to solving ill-conditioned linear algebraic system (ICLAS). The DSM gives a new approach to solving a wide class of ill-posed problems. In Chapter 1 a new iterative scheme for solving ICLAS is proposed. This iterative scheme is based on the DSM solution. An a posteriori stopping rules for the proposed method is justified. We also gives an a posteriori stopping rule for a modified iterative scheme developed in A.G.Ramm, JMAA,330 (2007),1338-1346, and proves convergence of the solution obtained by the iterative scheme. In Chapter 2 we give a convergence analysis of the following iterative scheme: u[subscript]n[superscript]delta=q u[subscript](n-1)[superscript]delta+(1-q)T[subscript](a[subscript]n)[superscript](-1) K[superscript]*f[subscript]delta, u[subscript]0[superscript]delta=0, where T:=K[superscript]* K, T[subscript]a :=T+aI, q in the interval (0,1),\quad a[subscript]n := alpha[subscript]0 q[superscript]n, alpha_0>0, with finite-dimensional approximations of T and K[superscript]* for solving stably Fredholm integral equations of the first kind with noisy data. In Chapter 3 a new method for inverting the Laplace transform from the real axis is formulated. This method is based on a quadrature formula. We assume that the unknown function f(t) is continuous with (known) compact support. An adaptive iterative method and an adaptive stopping rule, which yield the convergence of the approximate solution to f(t), are proposed in this chapter.
41
Araujo, Luiz Jonatã Pires de. "A hybrid methodology to solve the container loading problem with weight distribution and cutting problems." Universidade de Fortaleza, 2011. http://dspace.unifor.br/handle/tede/88221.
Full textAbstract:
Made available in DSpace on 2019-03-29T23:27:59Z (GMT). No. of bitstreams: 0
Previous issue date: 2011-09-27Transport of goods has represented an important role in economic development throughout the history and ship containerization brought great advantages. Its invention in mid-1950s brought down the cost of transport and reduced time for loading and unloading cargo. Consequently, it increased efficiency of port working and reduced handling cargo to hours instead of weeks, as before. However, the good use of containerization involves new and specialized logistic process, a number of technologies and automated systems to handle a great number of containers and even greater volume of cargo. To answer these requirements, computation appears as important tool. The described scenary has been treated in academic literature as the Container Loading Problem (CLP), with some variants. It is necessary consider practical requirements, for example the stability of cargo or weight distribution. The last one is of vital importance since the position of the centre of gravity of cargo affects the stability during its transport. When desconsidered, it could result in damage to cargo or vehicle. During our research, we were specially interested in this requirement. But, in order compare the found solutions with other ones, we proposed a methodology to measures the weight distribution. So, to the described problem, specifically the Knapsack Loading Problem (3D-KLP), this work presents a methodology that not only maximizes the packed cargo volume but also optimizes the weight distribution, its great contribution. Mainly if we consider that the cargo to be packed is composed by items with different densities, which turns the problem more difficult. The present methodology is composed by two phases with distinct goals. The first phase is concerned with maximize the weight distribution combining a search algorithm, the backtracking, with heuristics that solve integer linear programming models. The second phase executes a Genetic Algorithm to maximize the weight distribution of previously packed cargo. We also present a justification for why genetic algorithm was used in our methodology. An additional application was made to solve cutting problems. This class of problems occurs in various industrial process, when it is necessary to cut different types of material as glass, wood or parper, with a minimum of waste. We use a well-known benchmark test to compare our results with other approaches. This work also presents a case study of our implementation using some real data in a factory of stoves and refrigerators in Brazil. It shown promising results in reduced time. Keywords: Container Loading Problem, Knapsack Loading Problem, Weight Distribution, Integer Programming, Backtracking, Genetic Algorithms.
O transporte de carga tem representado um papel fundamental no desenvolvimento econômico no decorrer da história e a conteinerização trouxe grandes vantagens. Seu advento reduziu os custos de transporte bem como o tempo de carga. Portanto, aumentou a eficiência do trabalho em portos e reduziu o tempo necessário para operações com carga para horas, ao invés de semanas como anteriormente. Contudo, o bom uso dos contêineres involve novos e especializados processos logísticos, uma grande quantidade de tecnologias além de sistemas automatizados para manipular uma elevada quantidade de contêineres e ainda maior volume de carga. Para atender a estes requisitos, computação aparece como uma importante ferramenta. O cenário descrito tem sido tratado na literatura acadêmica como o Problema de Carregamento de Contêiner (CLP, do inglês Container Loading Problem), com algumas variantes. é também necessário considerar requisitos práticos como, por exemplo, a estabilidade da carga ou distribuição do peso. Este último de vital importância uma vez que o centro de gravidade da carga afeta a estabilidade durante seu transporte. Se descosiderado, pode-se danificar tanto a carga como o veículo. Durante nossa pesquisa, nós estivemos especialmente interessados neste requisito. E a fim de comparar a qualidade dos resultados obtidos, propusemos uma maneira de mensurar a distribuição do peso. Portanto, dado o problema descrito, especificamente o 3D Knapsack Loading Problem, este trabalho apresenta um algoritmo que não apenas maximiza o volume total carregado mas também otimiza a distribuição do peso da carga, sua grande contribuição. Principalmente se considerarmos que a carga é composta de itens com diferentes valores de densidade, o que torna o problema ainda mais difícil. A metodologia consiste em duas fases com objetivos diferentes. A primeira fase ocupa-se em maximizar o volume carregado por combinar um algoritmo de busca, o backtracking, com heurísticas que resolvem modelos de programação linear inteira. A segunda fase executa um algoritmo genético para maximizar a distribuição do peso da carga previamente colocada. Apresentamos também uma justificativa do porque algoritmo genéticos foram usados em nossa metodologia. Uma aplicação adicional foi feita para resolver problemas de corte. Esta classe de problemas ocorre em vários processos industriais, quando é necessário cortar diferentes tipos de materiais, como vidro, madeira ou papel, com um mínimo de desperdício. A fim de comparação, usamos bibliotecas de teste bem conhecidas na literatura e um estudo de caso usando informações reais de uma fábrica de fogões e geladeiras no Brasil. São apresentados resultados promissores alcançados em tempo reduzido. Palavras-chave: Problema de Carregamento de Contêiner, Knapsack Loading Problem, Distribuição do Peso, Programação Linear Inteira, Backtracking, Algoritmos Genéticos.
42
Hofmann, Bernd, and Masahiro Yamamoto. "Realization of source conditions for linear ill-posed problems by conditional stability." Universitätsbibliothek Chemnitz, 2008. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200800558.
Full textAbstract:
We prove some sufficient conditions for obtaining convergence rates in regularization
of linear ill-posed problems in a Hilbert space setting and show that these
conditions are directly related with the conditional stability in several concrete inverse
problems for partial differential equations.
43
Meyer, Arnd, and Cornelia Pester. "The Laplace and the linear elasticity problems near polyhedral corners and associated eigenvalue problems." Universitätsbibliothek Chemnitz, 2006. http://nbn-resolving.de/urn:nbn:de:swb:ch1-200601506.
Full textAbstract:
The solutions to certain elliptic boundary value problems have singularities with a typical structure near polyhedral corners. This structure can be exploited to devise an eigenvalue problem whose solution can be used to quantify the singularities of the given boundary value problem. It is necessary to parametrize a ball centered at the corner. There are different possibilities for a suitable parametrization; from the numerical point of view, spherical coordinates are not necessarily the best choice. This is why we do not specify a parametrization in this paper but present all results in a rather general form. We derive the eigenvalue problems that are associated with the Laplace and the linear elasticity problems and show interesting spectral properties. Finally, we discuss the necessity of widely accepted symmetry properties of the elasticity tensor. We show in an example that some of these properties are not only dispensable, but even invalid, although claimed in many standard books on linear elasticity.
44
Ketabi, Saeedeh. "Network routing and design problems with piecewise linear costs." Title page, contents and summary only, 1997. http://web4.library.adelaide.edu.au/theses/09PH/09phk428.pdf.
Full text
45
Weihrauch, Christian. "Analysis of Monte Carlo algorithms for linear algebra problems." Thesis, University of Reading, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.515747.
Full text
46
Yagoob, Muhammad Moeen. "Computationally efficient algorithms for non-linear target tracking problems." Thesis, Imperial College London, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.499109.
Full text
47
Tsakonas, Efthymios. "Convex Optimization for Assignment and Generalized Linear Regression Problems." Doctoral thesis, KTH, Signalbehandling, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-150338.
Full textAbstract:
This thesis considers optimization techniques with applications in assignment and generalized linear regression problems. The first part of the thesis investigates the worst-case robust counterparts of combinatorial optimization problems with least squares (LS) cost functions, where the uncertainty lies on the linear transformation of the design variables. We consider the case of ellipsoidal uncertainty, and prove that the worst case robust LS optimization problem, although NP-hard, is still amenable to convexrelaxation based on semidefinite optimization. We motivate our proposed relaxation using Lagrangian duality, and illustrate that the tightness of the Lagrange bidual relaxation is strongly dependent on the description of the feasible region of the worst-case robust LS problem. The results arising from this analysis are applicable to a broad range of assignment problems. The second part of the thesis considers combinatorial optimization problems arising specifically in the context of conference program formation. We start by arguing that both papers and reviewers can be represented as feature vectors in a suitable keyword space. This enables rigorous mathematical formulation of the conference formation process. The first problem, paper-to-session assignment, is formulated as a capacitatedk-means clustering problem. We formally prove that it is NP-hard and propose a variety of approximate solutions, ranging from alternating optimization to semidefinite relaxation. Suitable convex relaxation methods are proposed for the paper-to-reviewer assignment problem as well. Our methods are tested using real conference data for both problems, and show very promising results. In a related but distinct research direction, the third part of the thesis focuses on preference measurement applications: Review profiling, i.e., determining the reviewer’s expertise (and thus identifying the associated feature vector for the reviewer) on the basis of their past and present review preferences, or ‘bids’, is an excellent example of preference measurement. We argue that the need for robust preference measurement is apparent in modern applications. Using conjoint analysis (CA) as a basis, we propose a new statistical model for choice-based preference measurement, a part of preference analysis where data are only expressed in the form of binary choices. The model uses deterministic auxiliary variables to account for outliers and to detect the salient features that influence decisions. Contributions include conditions for statistical identifiability, derivation of the pertinent Cramér-Rao Lower Bound (CRLB), and ML consistency conditions for the proposed nonlinear model. The proposed ML approach lends itself naturally to ℓ1-type convex relaxations which are well-suited for distributed implementation, based on the alternating direction method of multipliers (ADMM). A particular decomposition is advocated which bypasses the apparent need for outlier variable communication, thus maintaining scalability. In the last part of the thesis we argue that this modeling has greater intellectual merits than preference measurement, and explain how related ideas can be put in the context of generalized linear regression models, drawing links between ℓ1-methods, stochastic convex optimization, and the field of robust statistics.QC 20140902
48
Rahmouni, M. K. "The conversion of linear programmes to network flow problems." Thesis, University of Southampton, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.380042.
Full text
49
LOPES, JOSE MARCOS. "INTERATIVE METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS AND LEAST NORM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 1992. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=8250@1.
Full textAbstract:
UNIVERSIDADE ESTADUAL PAULISTA JÚLIO DE MESQUITA FILHOApresentamos nesta dissertação novos métodos interativos para resolver o Problema de Complementaridade Linear (PCL) e Problemas de Norma Mínima. Após uma revisão geral sobre métodos interativos para o PCL, apresentaremos no Capítulo 2, uma forma de aceleração aplicada a métodos clássicos para o PCL simétrico, através de uma decomposição (Splitting) conveniente da matriz associada ao problema. A aceleração para os novos métodos consiste em calcular uma direção de avanço usando o método básico mais uma minimização unidimensional que respeite as condições de não negatividade, provas de convergência forte são apresentadas. No Capítulo 3 comparamos algoritmos do tipo seqüencial e paralelo para solução de um Problema de Programação Linear e Problemas de Norma Mínima em l 1: para o segundo problema os métodos iterativos são aplicados no dual do problema original penalizado com um termo quadrático. Introduzimos um novo método paralelo para o Problema de Norma mínima em l 1 e provamos sua convergência. Propomos no capítulo 4, novos métodos iterativos paralelos para Problemas de Norma Mínima, convenientes para problemas de grande porte, provas de convergência são fornecidas. Finalmente, no capítulo 5 baseados sobre uma combinação da iteração de ponto proximal e métodos iterativos clássicos, propomos novos métodos iterativos para a solução de um PCL monótono não simétrico. Ilustramos todos os algoritmos apresentados, em diferentes versões, com um extensa experimentação numérica.
We present in this dissertation new iterative methods for solving Linear Complementarity (LCP) and Least Norm (LNP) Problems. After a general overview on iterative methods for the LCP, in chapter 2 we present an acceleration techinique applied to classic methods for symmetric LCP generated by considering appropriate splittings of the associated matrix. The acceleration gives rise to new methods consisting of computing a search direction using the basic method plus a one dimensional minimization taking into account the nonnegative constraints. Strong convergence proofs are given. In chapter 3 we compare sequential and parallel algorithms for solving Linear Programming and least 1-Norm Problems obtained by applying iterative methods to a dual of the original problem penalized with a quadratic term. We introduce a new parallel method for the Least 1-Norm Problem, proving its convergence. In chapter 4, we present new parallel iterative methods for solving large LNP, giving convergence proofs. Finally, in chapter 5 we propose new iterative methods for solving monotone nonsymmetric LCp based on a combination of proximal point iterations and classic iterative methods. All the algorithms, in their different versions are illustrated and compared through many numerical experiments.
50
Lewin, Andrew W. (Andrew Wayne). "An automated tool for formulating linear covariance analysis problems." Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/43264.
Full text