Dissertations / Theses on the topic 'Quadratic programmin'
To see the other types of publications on this topic, follow the link: Quadratic programmin.
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 'Quadratic programmin.'
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
Lau, Karen Karman School of Mathematics UNSW. "Multistage quadratic stochastic programming." Awarded by:University of New South Wales. School of Mathematics, 1999. http://handle.unsw.edu.au/1959.4/32672.
Full textAbstract:
Multistage stochastic programming is an important tool in medium to long term planning where there are uncertainties in the data. In this thesis, we consider a special case of multistage stochastic programming in which each subprogram is a convex quadratic program. The results are also applicable if the quadratic objectives are replaced by convex piecewise quadratic functions. Convex piecewise quadratic functions have important application in financial planning problems as they can be used as very flexible risk measures. The stochastic programming problems can be used as multi-period portfolio planning problems tailored to the need of individual investors. Using techniques from convex analysis and sensitivity analysis, we show that each subproblem of a multistage quadratic stochastic program is a polyhedral piecewise quadratic program with convex Lipschitz objective. The objective of any subproblem is differentiable with Lipschitz gradient if all its descendent problems have unique dual variables, which can be guaranteed if the linear independence constraint qualification is satisfied. Expression for arbitrary elements of the subdifferential and generalized Hessian at a point can be calculated for quadratic pieces that are active at the point. Generalized Newton methods with linesearch are proposed for solving multistage quadratic stochastic programs. The algorithms converge globally. If the piecewise quadratic objective is differentiable and strictly convex at the solution, then convergence is also finite. A generalized Newton algorithm is implemented in Matlab. Numerical experiments have been carried out to demonstrate its effectiveness. The algorithm is tested on random data with 3, 4 and 5 stages with a maximum of 315 scenarios. The algorithm has also been successfully applied to two sets of test data from a capacity expansion problem and a portfolio management problem. Various strategies have been implemented to improve the efficiency of the proposed algorithm. We experimented with trust region methods with different parameters, using an advanced solution from a smaller version of the original problem and sorting the stochastic right hand sides to encourage faster convergence. The numerical results show that the proposed generalized Newton method is a highly accurate and effective method for multistage quadratic stochastic programs. For problems with the same number of stages, solution times increase linearly with the number of scenarios.
2
Ilyes, Amy Louise. "Using linear programming to solve convex quadratic programming problems." Case Western Reserve University School of Graduate Studies / OhioLINK, 1993. http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216.
Full text
3
Grainger, Daniel John. "Contributions to Quadratic 0 -1 Programming." Thesis, Lancaster University, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.518188.
Full text
4
Wang, Xianzhi. "Resolution of Ties in Parametric Quadratic Programming." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1199.
Full textAbstract:
We consider the convex parametric quadratic programming problem when the end of the parametric interval is caused by a multiplicity of possibilities ("ties"). In such cases, there is no clear way for the proper active set to be determined for the parametric analysis to continue. In this thesis, we show that the proper active set may be determined in general by solving a certain non-parametric quadratic programming problem. We simplify the parametric quadratic programming problem with a parameter both in the linear part of the objective function and in the right-hand side of the constraints to a quadratic programming without a parameter. We break the analysis into three parts. We first study the parametric quadratic programming problem with a parameter only in the linear part of the objective function, and then a parameter only in the right-hand side of the constraints. Each of these special cases is transformed into a quadratic programming problem having no parameters. A similar approach is then applied to the parametric quadratic programming problem having a parameter both in the linear part of the objective function and in the right-hand side of the constraints.
5
Byrne, Susan Jane. "Quadratic programming using complementarity and orthogonal factorization." Thesis, Imperial College London, 2011. http://hdl.handle.net/10044/1/8893.
Full text
6
Morales-Perez, Jose Luis. "Computational methods for large-scale quadratic programming." Thesis, Imperial College London, 1993. http://hdl.handle.net/10044/1/7511.
Full textAbstract:
For theoretical and practical reasons, quadratic programming problems have attracted the interest of the mathematical programming community. They naturally arise from applications and as subproblems in other numerical techniques. However most existing techniques, designed for solving small and dense problems, tend to be prohibitively expensive when applied directly to solve large-scale problems. In this work we explore methods suitable for solving large-scale sparse convex quadratic programming problems. An interior-point primal-dual algorithmic framework and its computational implementation are presented in the first part of this work. Primal and dual updates are computed at each step by iteratively solving the linear systems posed by the classical method of barriers using a preconditioned Krylov-subspace method. Several variants are suggested by a Taylor approximation of the central path. A truncated Newton strategy has been implemented in order to achieve a significant reduction in the CPU time. In the second part, sparse implementations for Lemke's algorithm and a row-action algorithm based on diagonal approximations of the Hessian, are suggested. Lemke's algorithm implementation is based on updating the sparse LU factorization of a matrix representing the basis at the current step. The implementation of the row-action algorithm relies on the efficient solution of single-constrained diagonal subproblems. In order to compare the relative merits of our implementations, numerical experimentation is conducted on two sets of problems that use randomly generated Hessian matrices and constraints taken from a subset of the netlib problems. Several aspects are studied: the use of iterative linear algebra for solving the linear systems of equations posed by the interior-point variants, the impact on the computational resources (memory and CPU) when different approaches are used to solve large scale problems, and finally, the effectiveness of a second order correction and the truncated Newton strategy implemented in the interior-point methods.
7
Axehill, Daniel. "Integer quadratic programming for control and communcation /." Linköping : Department of Electrical Engineering, Linköping University, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10642.
Full text
8
Jakee, Khan Md Kamall. "Computational convex analysis using parametric quadratic programming." Thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/45182.
Full textAbstract:
The class of piecewise linear-quadratic (PLQ) functions is a very important
class of functions in convex analysis since the result of most convex
operators applied to a PLQ function is a PLQ function. Although there exists
a wide range of algorithms for univariate PLQ functions, recent work has
focused on extending these algorithms to PLQ functions with more than one
variable. First, we recall a proof in [Convexity, Convergence and Feedback
in Optimal Control, Phd thesis, R. Goebel, 2000] that PLQ functions are
closed under partial conjugate computation. Then we use recent results on
parametric quadratic programming (pQP) to compute the inf-projection of
any multivariate convex PLQ function. We implemented the algorithm for
bivariate PLQ functions, and modi ed it to compute conjugates. We provide
a complete space and time worst-case complexity analysis and show that for
bivariate functions, the algorithm matches the performance of [Computing
the Conjugate of Convex Piecewise Linear-Quadratic Bivariate Functions,
Bryan Gardiner and Yves Lucet, Mathematical Programming Series B, 2011]
while being easier to extend to higher dimensions.
9
Axehill, Daniel. "Integer Quadratic Programming for Control and Communication." Doctoral thesis, Linköpings universitet, Reglerteknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10642.
Full textAbstract:
The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control methods is Model Predictive Control (MPC). In each sampling time, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem, which is known to have a computational complexity which grows exponentially in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel. To estimate the information originally sent, a maximum likelihood problem involving binary variables can be solved. The process of simultaneously estimating the information sent by multiple users is called Multiuser Detection (MUD). In this thesis, the problem to efficiently solve MIQP problems originating from MPC and MUD is addressed. Four different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In numerical experiments, the algorithm is applied to unconstrained MPC problems with a mixture of real valued and binary valued control signals, and the result shows that the performance gain can be significant compared to solving the problem using branch and bound. The preprocessing algorithm has also been applied to the MUD problem, where simulations have shown that the bit error rate can be significantly reduced compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the proposed QP solver and MIQP solver have lower computational complexity compared to corresponding generic solvers. Third, the dual active set QP algorithm is enhanced using ideas from gradient projection methods. The performance of this enhanced algorithm is shown to be comparable with the existing commercial state-of-the-art QP solver \cplex for some random linear MPC problems. Fourth, an algorithm for efficient computation of the search directions in an SDP solver for a proposed alternative SDP relaxation applicable to MPC problems with binary control signals is presented. The SDP relaxation considered has the potential to give a tighter lower bound on the optimal objective function value compared to the QP relaxation that is traditionally used in branch and bound for these problems, and its computational performance is better than the ordinary SDP relaxation for the problem. Furthermore, the tightness of the different relaxations is investigated both theoretically and in numerical experiments.This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Linköping University's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it.
10
Ahlbom, Daniel. "Quadratic Programming Models in Strategic Sourcing Optimization." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-334227.
Full textAbstract:
Strategic sourcing allows for optimizing purchases on a large scale.Depending on the requirements of the client and the offers provided forthem, finding an optimal or even a near-optimal solution can become computationally hard. Mixed integer programming (MIP), where theproblem is modeled as a set of linear expressions with an objectivefunction for which an optimal solution results in a minimum objectivevalue, is particularly suitable for finding competitive results. However, given the research and improvements continually being made for quadratic programming (QP), which allows for objective functions with quadratic expressions as well, comparing runtimes and objective values for finding optimal and approximate solutions is advised: for hard problems, applying the correct methods may decrease runtimes by severalorders of magnitude. In this report, comparisons between MIP and QPmodels used in four different problems with three different solverswere made, measuring both optimization and approximation performance interms of runtimes and objective values. Experiments showed that while QP holds an advantage over MIP in some cases, it is not consistentlyefficient enough to provide a significant improvement in comparison with, for example, using a different solver.
11
Lopez, Rafaël. "Stochastic quadratic knapsack problems and semidefinite programming." Paris 11, 2009. http://www.theses.fr/2009PA112283.
Full textAbstract:
Dans cette thèse, nous présentons une étude détaillée de problèmes de sac-à-dos stochastiques quadratiques, ainsi que des applications de la Programmation Semidéfinie (SDP) pour un problème de télécommunications et pour une étude expérimentale pour des problèmes de Coupe Max et de CDMA. La première partie de cette thèse consiste en un rappel des notions et résultats utilisés par la suite. La seconde partie est consacrée à l’étude du problème du sac- à- dos stochastique, dont nous développons un nouveau modèle, à deux phases (recours) et à contraintes probabilistes. Nous en proposons plusieurs variantes. Nous présentons de multiples relaxations, basées sur la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin, nous proposons une heuristique d’approximation basée sur le résultat de la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin nous proposons une heuristique d’approximation, basée sur le résultat de la relaxation linéaire et sur le résultat de la seconde relaxation SDP , dont nous détaillons les performances. La troisième partie de la thèse est centrée sur l’usage de la SDP sur des problèmes pratiques. La première application étudiée est sur un problème de détection multiutilisateur dans le CDMA. Nous développons un nouvel algorithme combinant SDP et une méta-heuristique VNS pour obtenir un signal de meilleure qualité. Nous détaillons les résultats expérimentaux de notre méthode et d’autres, basées sur SDP. La seconde application est une comparaison expérimentale de diverses relaxations pour le problème de la Coupe Max et dans le CDMA. Nous présentons les performances des relaxations Lagrangienne et SDP comparées à la relaxation linéaire, ainsi que celles de la décomposition spectrale dans le cas du CDMAIn this thesis, we study stochastic quadratic knapsack problems and applications of Semidefinite Programming for a telecommunication problem and for an experimental study of the MaxCut and CDMA problems. The first part of this thesis gives the prelimary notions and results necessary to develop and understand the contents of this thesis. The second part is the study of the stochastic quadratic knapsack problem, for which we develop a new formulation, using recourse (two-stage) and probabilistic contraints. We give multiple variants of this formulation. We propose various relaxations of this problems, based on the linear relaxation and on SDP. We show that SDP gives significantly better bounds than linear relaxation. Finally, we develop an approximation heuristic based on the result of the linear relaxation and of the second SDP relaxation, and give details of their respective performances. The third part of this thesis is dedicated to applications of SDP on pratical problems. The first application we study is a telecommunication problem : the multiuser detection problem in CDMA. We develop a new algorithm combining SDP and a VNS meta-heuristic to obtain a better signal quality. We detail the experimental results of our method and of other SDP based methods. The second application is an experimental comparison of various relaxations for the MaxCut problem and the CDMA problem. We detail the performances of Lagrangian and SDP relaxations compared to linear relaxation, and to the spectral decomposition in the CDMA case
12
Cheng, Chun-Min. "Use of linear quadratic and quadratic programming methods in model-based process control /." Thesis, Connect to this title online; UW restricted, 1986. http://hdl.handle.net/1773/9814.
Full text
13
Sharma, Vivek Narain. "Linear programming and quadratic programming approach for graduation in fuzzy environment." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ57577.pdf.
Full text
14
P, Van Voorhis Timothy. "The quadratically constrained quadratic program." Diss., Georgia Institute of Technology, 1997. http://hdl.handle.net/1853/23379.
Full text
15
Pinheiro, Ricardo Bento Nogueira [UNESP]. "Um método previsor-corretor primal-dual de pontos interiores barreira logarítmica modificada, com estratégias de convergência global e de ajuste cúbico, para problemas de programação não-linear e não-convexa." Universidade Estadual Paulista (UNESP), 2012. http://hdl.handle.net/11449/87189.
Full textAbstract:
Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0
Previous issue date: 2012-08-22Bitstream added on 2014-06-13T19:08:11Z : No. of bitstreams: 1
pinheiro_rbn_me_bauru.pdf: 19855827 bytes, checksum: 0c72e37d2b42539464b7fafb4a4e52a2 (MD5)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Neste trabalho apresentamos o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada e estratégia de ajuste cúbico (MPIBLM-EX) e o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada, com estratégias de ajuste cúbico e de convergência global (MPIBLMCG-EX). Na definição do algoritmo proposto, a função barreira logarítmica modificada auxilia o método em sua inicialização com pontos inviáveis. Porém, a inviabilidade pode ocorrer em pontos tais que o logaritmo não está definido, consequentemente, isso implica na não existência de função barreira logarítmica modificada. Para suprir essa dificuldade um polinômio cúbico ajustado ao logaritmo, que preserva as derivadas de primeira e segunda do mestre definido a partir de um ponto da região ampliada ao método previsor-corretor primal-dual de pontos interiores com barreira logarítmica modificada (MPIBML); no processo previsor são realizadas atualizações do parâmetro de barreira nos resíduos das restrições de complementaridade, considerando aproximações de primeira ordem do sistema de direções de busca, enquanto que no procedimento corretor, incluímos os termos quadráticos não-lineares dos resíduos citados, que foram desprezados no procedimento previsor. Considerando também a estratégia de convergência global para o MPIBLM-EX, a qual utiliza uma variante do método de Levenberg-Marquardt para ajustar a matriz dual normal da função lagrangiana, caso esta não seja definida positiva. A matriz dual normal é redefinida para as restrições primais de igualdade, de desigualdade e para as variáveis canalizadas, incorporando variáveis duais e matrizes diagonais relativas às restrições de complementariade. Desse estudo, o MPIBLM-EX é transformado no MPIBLMCG-EX e mostramos...
This work presents a predictor primal-dual interior point method with modified log-barrier and third order extrapolation strategy (IPMLBM-EX) and also and extension of this method with the inclusion of the global convergence strategy (IPMLBGCM-EX). In the definition of the proposed algorithm, the modified log-barrier function helps the method initialize with infeasible points. However, infeasibility may occur for some point where the logarithm is not defined. The implicates in non-existence of the modified log-barrier function. To cope with such as problem, a cubic polynomial function is adjusted to the logarithmic function. Sucha polynomial function preserves first and second order derivatives in certain point defined in the extended region. This function is applied to the predictor-corretor primal-dual interior point method with modified log-barrier function. In the predictor procedure, the barrier parameter is updated in the complementarity conditions considering first-order approximations of the search direction, while the corrector procedure includes the nonlinear quadratic terms of the mentioned residuals, which were neglected in the predictor procedure. We also consider the global convergence strategy for the method, which uses a variant of the Levenberg-Marquardt method to update the normal dual matrix of the Langrangian function, should it fail to be positively defined. In this case, this matrix is redefined for equality primal constraints, bounded inequality primal constraints and bounded variables, incorporating dual variables and diagonal matrices of the complementarity constraints. From such studies, the IPMLBM-EX method is extended to include the global convergence strategy (IPMLBGCM-EX). We have show that both methods are projected gradient methods. An implementation performed with Matlab 6.1 has shown the... (Complete abstract click electronic access below)
16
Pinheiro, Ricardo Bento Nogueira. "Um método previsor-corretor primal-dual de pontos interiores barreira logarítmica modificada, com estratégias de convergência global e de ajuste cúbico, para problemas de programação não-linear e não-convexa /." Bauru : [s.n.], 2012. http://hdl.handle.net/11449/87189.
Full textAbstract:
Orientador: Antonio Roberto BalboBanca: Edilaine Martins Soler
Banca: Leonardo Nepomuceno
Resumo: Neste trabalho apresentamos o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada e estratégia de ajuste cúbico (MPIBLM-EX) e o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada, com estratégias de ajuste cúbico e de convergência global (MPIBLMCG-EX). Na definição do algoritmo proposto, a função barreira logarítmica modificada auxilia o método em sua inicialização com pontos inviáveis. Porém, a inviabilidade pode ocorrer em pontos tais que o logaritmo não está definido, consequentemente, isso implica na não existência de função barreira logarítmica modificada. Para suprir essa dificuldade um polinômio cúbico ajustado ao logaritmo, que preserva as derivadas de primeira e segunda do mestre definido a partir de um ponto da região ampliada ao método previsor-corretor primal-dual de pontos interiores com barreira logarítmica modificada (MPIBML); no processo previsor são realizadas atualizações do parâmetro de barreira nos resíduos das restrições de complementaridade, considerando aproximações de primeira ordem do sistema de direções de busca, enquanto que no procedimento corretor, incluímos os termos quadráticos não-lineares dos resíduos citados, que foram desprezados no procedimento previsor. Considerando também a estratégia de convergência global para o MPIBLM-EX, a qual utiliza uma variante do método de Levenberg-Marquardt para ajustar a matriz dual normal da função lagrangiana, caso esta não seja definida positiva. A matriz dual normal é redefinida para as restrições primais de igualdade, de desigualdade e para as variáveis canalizadas, incorporando variáveis duais e matrizes diagonais relativas às restrições de complementariade. Desse estudo, o MPIBLM-EX é transformado no MPIBLMCG-EX e mostramos... (Resumo completo, clicar acesso eletrônico abaixo)
Abstract: This work presents a predictor primal-dual interior point method with modified log-barrier and third order extrapolation strategy (IPMLBM-EX) and also and extension of this method with the inclusion of the global convergence strategy (IPMLBGCM-EX). In the definition of the proposed algorithm, the modified log-barrier function helps the method initialize with infeasible points. However, infeasibility may occur for some point where the logarithm is not defined. The implicates in non-existence of the modified log-barrier function. To cope with such as problem, a cubic polynomial function is adjusted to the logarithmic function. Sucha polynomial function preserves first and second order derivatives in certain point defined in the extended region. This function is applied to the predictor-corretor primal-dual interior point method with modified log-barrier function. In the predictor procedure, the barrier parameter is updated in the complementarity conditions considering first-order approximations of the search direction, while the corrector procedure includes the nonlinear quadratic terms of the mentioned residuals, which were neglected in the predictor procedure. We also consider the global convergence strategy for the method, which uses a variant of the Levenberg-Marquardt method to update the normal dual matrix of the Langrangian function, should it fail to be positively defined. In this case, this matrix is redefined for equality primal constraints, bounded inequality primal constraints and bounded variables, incorporating dual variables and diagonal matrices of the complementarity constraints. From such studies, the IPMLBM-EX method is extended to include the global convergence strategy (IPMLBGCM-EX). We have show that both methods are projected gradient methods. An implementation performed with Matlab 6.1 has shown the... (Complete abstract click electronic access below)
Mestre
17
Tao, Ye. "Optimal power flow via quadratic modeling." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/45766.
Full textAbstract:
Optimal power flow (OPF) is the choice tool for determining the optimal operating status of the power system by managing controllable devices. The importance of the OPF approach has increased due to increasing energy prices and availability of more control devices. Existing OPF approaches exhibit shortcomings. Current OPF algorithms can be classified into (a) nonlinear programming, (b) intelligent search methods, and (c) sequential algorithms. Nonlinear programming algorithms focus on the solution of the Kuhn-Tucker conditions; they require a starting feasible solution and the model includes all constraints; these characteristics limit the robustness and efficiency of these methods. Intelligent search methods are first-order methods and are totally inefficient for large-scale systems. Traditional sequential algorithms require a starting feasible solution, a requirement that limits their robustness. Present implementations of sequential algorithms use traditional modeling that result in inefficient algorithms.
The research described in this thesis has overcome the shortcomings by developing a robust and highly efficient algorithm. Robustness is defined as the ability to provide a solution for any system; the proposed approach achieves robustness by operating on suboptimal points and moving toward feasible, it stops at a suboptimal solution if an optimum does not exist. Efficiency is achieved by (a) converting the nonlinear OPF problem to a quadratic problem (b) and limiting the size of the model; the quadratic model enables fast convergence and the algorithm that identifies the active constraints, limits the size of the model by only including the active constraints.
A concise description of the method is as follows: The proposed method starts from an arbitrary state which may be infeasible; model equations and system constraints are satisfied by introducing artificial mismatch variables at each bus. Mathematically this is an optimal but infeasible point. At each iteration, the artificial mismatches are reduced while the solution point maintains optimality. When mismatches reach zero, the solution becomes feasible and the optimum has been found; otherwise, the mismatch residuals are converted to load shedding and the algorithm provides a suboptimal but feasible solution. Therefore, the algorithm operates on infeasible but optimal points and moves towards feasibility.
The proposed algorithm maximizes efficiency with two innovations: (a) quadratization that converts the nonlinear model to quadratic with excellent convergence properties and (b) minimization of model size by identifying active constraints, which are the only constraints included in the model. Finally sparsity technique is utilized that provide the best computational efficiency for large systems.
This dissertation work demonstrates the proposed OPF algorithm using various systems up to three hundred buses and compares it with several well-known OPF software packages. The results show that the proposed algorithm converges fast and its runtime is competitive.
Furthermore, the proposed method is extended to a three-phase OPF (TOPF) algorithm for unbalanced networks using the quadratized three-phase power system model. An example application of the TOPF is presented. Specifically, TOPF is utilized to address the problem of fault induced delayed voltage recovery (FIDVR) phenomena, which lead to unwanted relay operations, stalling of motors and load disruptions. This thesis presents a methodology that will optimally enhance the distribution system to mitigate/eliminate the onset of FIDVR. The time domain simulation method has been integrated with a TOPF model and a dynamic programming optimization algorithm to provide the optimal reinforcing strategy for the circuits.
18
Szularz, Marek. "Quadratic programming with constant norm with parallel applications." Thesis, Kingston University, 1991. http://eprints.kingston.ac.uk/20556/.
Full textAbstract:
This thesis is concerned with the problem of minimizing a quadratic function defined on an ellipsoid, and subject to the set of linear inequality constraints. An original method is proposed, a method which generates the descent flow on the spiral, the curve on the surface of the constraining ellipsoid, characterized locally by the steepest descent of the objective function. The spiral is constructed discretely in a number of points which are the solutions of the sequence of certain artificially constrained subproblems. The properties of the spiral are studied extensively to show that the associated descent flow can be divided into three categories of the regular, separated and multiple descent flow. Particular attention is devoted to the case of the separated descent flow, which involves the discontinuity of the spiral and may pose certain difficulties in the search for the solution. The important and the original part of the thesis is also the issue of all local minima of the equality constrained version of the problem. The identification of all such minima is vital to the main problem and the corresponding method. The method which may find many practical applications, has been inspired by the opportunities given by a massively parallel computer, namely the Distributed Array Processor, although the method can find the applications in other parallel environments. The algorithm has been implemented in DAP Fortran-Plus, and a series of numerical examples is presented, some of them of practical importance in structural engineering.
19
Bettiol, Enrico. "Column generation methods for quadratic mixed binary programming." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131073.
Full textAbstract:
La programmation non linéaire mixte peut modéliser un grand nombre de problèmes réels. Cependant, ces problèmes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des méthodes de décomposition afin de les résoudre efficacement. Parmi ces techniques on peut citer la génération de colonnes et notamment la décomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du problème original, qui permet de générer une séquence de sous-problèmes plus simples, appelés maître etpricing, pour obtenir la valeur optimale. Développée d’abord pour les problèmes linéaires, la décomposition de Dantzig-Wolfe peut être généralisée à des problèmes convexes: dans ce contexte, elle est notamment connue sous le nom de décomposition simpliciale. Cette thèse présente des algorithmes de décomposition pour des problèmes quadratiques. La première partie de ce manuscrit est dédiée aux problèmes quadratiques convexes, continus et mixtes binaires. Dans la deuxième partie, des algorithmes pour résoudre des problèmes binaires avec contraintes quadratiques sont présentés. La première partie est consacrée à la résolution de problèmes convexes, quadratiques et continus. Un algorithme basé sur la décomposition simpliciale est proposé: des nouveaux éléments sont ajoutés à la fois au problème maître et au pricing; nous avons testé notre algorithme sur une grande quantité d’instances avec une structure déterminée, et nos résultats montrent que l’algorithme que nous proposons est très efficace par rapport à Cplex, un solveur générique pour ces problèmes. Ce premier travail a été soumis à un journal pour publication. Ensuite, nous étendons cet algorithme aux problèmes convexes mixtes binaires. Nous incorporons la méthode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des propriétés de notre formulation. Dans ce contexte aussi, des résultats numériques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport à Cplex. Ce travail est en préparation pour soumission à un journal. La deuxième partie de cette thèse est dédiée à l’étude d’algorithmes pour des problèmes quadratiques avec contraintes quadratiques. On se concentre sur les problèmes binaires, dont la relaxation continue peut être non convexe. Nous considérons en premier lieu la formulation étendue avec une matrice qui représente les produits des variables. Nous proposons ensuite un algorithme basé sur la décomposition de Dantzig-Wolfe pour obtenir une relaxation dans le Boolean Quadric Polytope (BQP). Ce polytope est connu aussi comme Correlation polytope et il est strictement contenu dans le cône des matrices complètement positives et des matrices semi définies positives. Notre algorithme permet de résoudre cette relaxation, les bornes obtenues sont plus fortes que les bornes SDP et, dans certains cas, les temps de calcul sont comparables ou meilleurs que ceux de BiqCrunch, unsolveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. Une relaxation basée sur les blocs est proposée et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’équivalence entre les deux relaxations est un problème de complétion BQP. La relaxation décomposée par blocs est BQP complétable dans certains cas, mais n’est pas possible dans d’autres cas [....]Non linear programming problems. There are several solution methods in literature for these problems, which are, however, not always efficient in general, in particular for large scale problems. Decomposition strategies such as Column Generation have been developed in order to substitute the original problem with a sequence of more tractable ones. One of the most known of these techniques is Dantzig-Wolfe Decomposition: it has been developed for linear problems and it consists in solving a sequence of subproblems, called respectively master and pricing programs, which leads to the optimum. This method can be extended to convex non linear problems and a classic example of this, which can be seen also as a generalization of the Frank-Wolfe algorithm, is Simplicial Decomposition(SD).In this thesis we discuss decomposition algorithms for solving quadratic optimization problems. In particular, we start with quadratic convex problems, both continuous and mixed binary. Then we tackle the more general class of binary quadratically constrained, quadratic problems. In the first part, we concentrate on SD based-methods for continuous, convex quadratic programming. We introduce new features in the algorithms, for both the master and the pricing problems of the decomposition, and provide results for a wide set of instances, showing that our algorithm is really efficient if compared to the state-of-the-art solver Cplex. This first work is accepted for publication in the journal Computational Optimization and Applications.We then extend the SD-based algorithm to mixed binary convex quadratic problems;we embed the continuous algorithm in a branch and bound scheme that makes us able to exploit some properties of our framework. In this context again we obtain results which show that in some sets of instances this algorithm is still more efficient than Cplex,even with a very simple branch and bound algorithm. This work is in preparation for submission to a journal. In the second part of the thesis, we deal with a more general class of problems, that is quadratically constrained, quadratic problems, where the constraints can be quadratic and both the objective function and the constraints can be non convex. For this class of problems we extend the formulation to the matrix space of the products of variables; we study an algorithm based on Dantzig-Wolfe Decomposition that exploits a relaxation on the Boolean Quadric Polytope (BQP), which is strictly contained in the Completely Positive cone and hence in the cone of positive semi definite (PSD) matrices. This is a constructive algorithm to solve the BQP relaxation of a binary problem an dwe obtain promising results for the root node bound for some quadratic problems. We compare our results with those obtained by the Semi definite relaxation of the ad-hocsolver BiqCrunch. We also show that, for linearly constrained quadratic problems, our relaxation can provide the integer optimum, under certain assumptions. We further study block decomposed matrices and provide results on the so-called BQP-completion problem ; these results are connected to those of PSD and CPP matrices. We show that, given a BQP matrix with some unspecified elements, it can be completed to a full BQP matrix under some assumptions on the positions of the specified elements. This result is related to optimization problems. We propose a BQP-relaxation based on the block structure of the problem. We prove that it provides a lower bound for the previously introduced relaxation, and that in some cases the two formulations are equivalent. We also conjecture that the equivalence result holds if and only if its so-called specification graph is chordal. We provide computational results which show the improvement in the performance of the block-based relaxation, with respect to the unstructured relaxation, and which support our conjecture. This work is in preparation for submission to a journal
20
Boljunčić, Jadranka. "Quadratic programming : quantitative analysis and polynomial running time algorithms." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/27532.
Full textAbstract:
Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial
algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx-½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D.
Another part of the thesis is concerned with proximity and sensitivity of integer and mixed-integer quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such thatz̅ - x̅
∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute sub-determinant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with
z - z̅
∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors b and b', respectively, depends linearly on
b — b'
₁. The extension to the mixed-integer nonseparable quadratic case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixed-integer case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982).
Business, Sauder School of
Graduate
21
Vankova, Martina. "Algorithms for the solution of the quadratic programming problem." Thesis, University of Port Elizabeth, 2004. http://hdl.handle.net/10948/348.
Full textAbstract:
The purpose of this dissertation was to provide a review of the theory of Optimization, in particular quadratic programming, and the algorithms suitable for solving both convex and non-convex quadratic programming problems. Optimization problems arise in a wide variety of fields and many can be effectively modeled with linear equations. However, there are problems for which linear models are not sufficient thus creating a need for non-linear systems. This dissertation includes a literature study of the formal theory necessary for understanding optimization and an investigation of the algorithms available for solving a special class of the non-linear programming problem, namely the quadratic programming problem. It was not the intention of this dissertation to discuss all possible algorithms for solving the quadratic programming problem, therefore certain algorithms for convex and non-convex quadratic programming problems were selected for a detailed discussion in the dissertation. Some of the algorithms were selected arbitrarily, because limited information was available comparing the efficiency of the various algorithms. Algorithms available for solving general non-linear programming problems were also included and briefly discussed as they can be used to solve quadratic programming problems. A number of algorithms were then selected for evaluation, depending on the frequency of use in practice and the availability of software implementing these algorithms. The evaluation included a theoretical and quantitative comparison of the algorithms. The quantitative results were analyzed and discussed and it was shown that the results supported the theoretical comparison. It was also shown that it is difficult to conclude that one algorithm is better than another as the efficiency of an algorithm greatly depends on the size of the problem, the complexity of an algorithm and many other implementation issues. Optimization problems arise continuously in a wide range of fields and thus create the need for effective methods of solving them. This dissertation provides the fundamental theory necessary for the understanding of optimization problems, with particular reference to quadratic programming problems and the algorithms that solve such problems. Keywords: Quadratic Programming, Quadratic Programming Algorithms, Optimization, Non-linear Programming, Convex, Non-convex.
22
Ben, Daya Mohamed. "Barrier function algorithms for linear and convex quadratic programming." Diss., Georgia Institute of Technology, 1988. http://hdl.handle.net/1853/25502.
Full text
23
Helme, Marcia P., and Thomas L. Magnanti. "Designing Satellite Communication Networks by Zero-One Quadratic Programming." Massachusetts Institute of Technology, Operations Research Center, 1987. http://hdl.handle.net/1721.1/5376.
Full textAbstract:
In satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with each other via a local switch at the homing station; demand nodes in different clusters communicate with each other via satellite earth stations at the homing stations. Designing such a communication network requires choices on the locations of the earth stations and on the assignments of demand nodes to the local clusters at the earth stations. We formulate this problem as a zero-one quadratic facility location problem and transform it into an equivalent zero-one integer linear program. Computational experience on real data shows that a branch and bound procedure is effective in solving problems with up to forty demand nodes (major cities) and that the solutions that this algorithm finds improve considerably upon management generated solutions. We also show that a greedy add heuristic, as implemented on an IBM PC, consistently generates optimal or near-optimal solutions.
24
Axehill, Daniel. "Applications of Integer Quadratic Programming in Control and Communication." Licentiate thesis, Linköping : Dept. of Electrical Engineering, Linköping University, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-5263.
Full text
25
Tuncbilek, Cihan H. "Polynomial and indefinite quadratic programming problems: algorithms and applications." Diss., Virginia Tech, 1994. http://hdl.handle.net/10919/39040.
Full text
26
Pajic, Slobodan. "Sequential quadratic programming-based contingency constrained optimal power flow." Link to electronic thesis, 2003. http://www.wpi.edu/Pubs/ETD/Available/etd-0430103-152758.
Full text
27
Santos, Francisco Lucio dos Reis Borges Brito dos. "Optimal irrigation system selection: A multiperiod quadratic programming approach." Diss., The University of Arizona, 1990. http://hdl.handle.net/10150/184980.
Full textAbstract:
This study reports on the optimal temporal selection of irrigation technologies (graded and level furrows, level basin and drip) that maximize net revenues of a farm unit with different soil types. Unique to this study was the inclusion of irrigation water management strategies that allowed unbiased comparison of the different technologies; for each surface and pressurized system of the study simulation models were used to control the governing parameters that determine the distribution and effectiveness of the applied water, infiltrate equal seasonal water depth in the root zone and adequately irrigate a similar fraction of total cropland area. The ultimate effects on crop yield were assessed by linking the areal water distribution depths with specific crop-water production functions. A generalized mean variance model was constructed to simulate the selected production activities of the farm; to integrate the water delivery irrigation systems, crop mix and soil endowments, and to include the alternative irrigation water application strategies. Adjustments to stochastic water supplies and revenues were also included into the model as well as regulatory constraints associated with the quantity of water allocated over the growing season and risk preference levels. Given the model assumptions, the results indicate that: (1) the generalized mean variance model was successful in establishing an intertemporal path for irrigation systems adoption; (2) high uniformity level basins were the technology of choice in all soils, substituting the low uniformity graded furrows; (3) with yield increases realized, drip systems are likely to be first adopted in soils of high intake rates; (4) increasing levels of risk aversion changed the area-technology mix and added to reductions in the areas under production; area reductions under level basin took place in high intake soils, suggesting that adoption of level basin in low intake rate soils provide higher level of farm security and are more likely to be given priority in the farm enterprise planning by growers defined by the model as risk averse; (5) the farm structure is considerably dependent upon cotton for the production of net revenue; wheat contributions to net revenue were relatively small due to the economic inability of the crop to command scarce resources and generate profits.
28
Edwards, Teresa Dawn. "The box method for minimizing strictly convex functions over convex sets." Diss., Georgia Institute of Technology, 1990. http://hdl.handle.net/1853/30690.
Full text
29
Yue, Hongwei. "First-order affine scaling continuous method for convex quadratic programming." HKBU Institutional Repository, 2014. https://repository.hkbu.edu.hk/etd_oa/39.
Full textAbstract:
We develop several continuous method models for convex quadratic programming (CQP) problems with di.erent types of constraints. The essence of the continuous method is to construct one ordinary di.erential equation (ODE) system such that its limiting equilibrium point corresponds to an optimal solution of the underlying optimization problem. All our continuous method models share the main feature of the interior point methods, i.e., starting from any interior point, all the solution trajectories remain in the interior of the feasible regions. First, we present an a.ne scaling continuous method model for nonnegativity constrained CQP. Under the boundedness assumption of the optimal set, a thorough study on the properties of the ordinary di.erential equation is provided, strong convergence of the continuous trajectory of the ODE system is proved. Following the features of this ODE system, a new ODE system for solving box constrained CQP is also presented. Without projection, the whole trajectory will stay inside the box region, and it will converge to an optimal solution. Preliminary simulation results illustrate that our continuous method models are very encouraging in obtaining the optimal solutions of the underlying optimization problems. For CQP in the standard form, the convergence of the iterative .rst-order a.ne scaling algorithm is still open. Under boundedness assumption of the optimal set and nondegeneracy assumption of the constrained region, we discuss the properties of the ODE system induced by the .rst-order a.ne scaling direction. The strong convergence of the continuous trajectory of the ODE system is also proved. Finally, a simple iterative scheme induced from our ODE is presented for finding an optimal solution of nonnegativity constrained CQP. The numerical results illustrate the good performance of our continuous method model with this iterative scheme. Keywords: ODE; Continuous method; Quadratic programming; Interior point method; A.ne scaling.
30
Chen, Chung Long. "A class of successive quadratic programming methods for flowsheet optimisation." Thesis, Imperial College London, 1988. http://hdl.handle.net/10044/1/8462.
Full text
31
Brooks, S. A. "A penalty/modified barrier method for large-scale quadratic programming." Thesis, University of Cambridge, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.596942.
Full textAbstract:
The tools for solving large-scale sparse Quadratic Programming (QP) problems have many applications. They can be used to solve naturally occurring problems, which arise in engineering, economics, etc, or they can be used as part of a Sequential Quadratic Programming (SQP) structure for solving non-linear programming problems. The performance of SQP methods depends greatly on the QP solver, and for this reason the development and implementation of an efficient QP method is of paramount importance. In this work we consider the application of the Penalty/Modified Barrier Function (PE/MBF) method in the solution of large-scale Quadratic Programming problems. We consider using "hot starts" to initialise the parameters for one problem using information based on a related solved problem. The limitations of the Classical Barrier Function (CBF) method are discussed and then it is shown how the CBF can be used to initialise the Lagrange multipliers associated with a Modified Barrier Function. Numerical results showed that this is effective in reducing the number of iterations to convergence. The Newton strategy developed in this work exploits both the sparsity of the problem under consideration and the symmetry of the Hessian matrix. We consider the convergence rates of the Lagrange multipliers. In particular, we show that, in practice the Lagrange multipliers corresponding to inactive constraints converge faster than those corresponding to active constraints. We give a procedure for predicting the active constraints. Numerical results confirm its effectiveness.
32
Zoppke-Donaldson, Christine. "A tolerance-tube approach to sequential quadratic programming with applications." Thesis, University of Dundee, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.531437.
Full textAbstract:
Many optimization problems can be modelled as nonlinear programming problems (NLP). Optimization problems arise from a large number of different applications, such as chemical and electrical engineering and economics. For example, in chemical engineering the aim is to maximize the efficiency of a chemical plant under certain operating restrictions. The model of the efficiency forms the objective function and the operating restrictions form the constraints. In electrical engineering, fuel costs or system losses are minimized in electrical networks. The fuel cost can be expressed as a function of the generated power. This function is used as the objective function. The constraints are given by the consumer demand for power, which has to be met and by certain system restrictions. In order to provide an accurate enough model for the plant or network, it is often necessary to use nonlinear functions for both objective function and constraint functions. Higher accuracy of the model also leads to a larger number of variables and constraints. Some models even require non-smooth constraint functions. If this is the case, N LP methods cannot solve the problem, because first and second derivatives do not exist for all points of the constraint functions.
33
Naik, Vihangkumar Vinaykumar. "Mixed-integer quadratic programming algorithms for embedded control and estimation." Thesis, IMT Alti Studi Lucca, 2018. http://e-theses.imtlucca.it/259/1/Naik_phdthesis.pdf.
Full textAbstract:
The class of optimization problems involving both continuous
and discrete variables is known as mixed-integer programming
(MIP), which emerges in many fields of applications.
Due to their inherent combinatorial nature, solving
such a class of problems in real-time poses a major challenge,
especially in embedded applications where computational
and memory resources are limited. This thesis mainly focuses
on novel solution methods tailored to small-scale Mixed-
Integer Quadratic Programming (MIQP) problems, such as
those that typically arise in embedded hybrid Model Predictive
Control (MPC) and estimation problems. With an emphasis
on algorithm simplicity, efficient solution techniques
to solve MIQP problems are developed in the thesis based
on first-order methods, specialized to find both exact and approximate
solutions. In addition, a numerically robust algorithm
is proposed in order to tackle MIQP problem with
positive semidefinite Hessian matrices, often encountered in
hybrid MPC formulations. The proposed techniques, being
library-free and relatively simple to code, are specifically
tailored to real-time embedded applications. Such techniques
are also employed in a novel algorithm for the MIPbased
PieceWise Affine (PWA) regression, as well as in new
approaches for energy disaggregation using binary quadratic
programming that are particularly suitable for smart energy
meters.
34
Vandenbussche, Dieter. "Polyhedral approaches to solving nonconvex quadratic programs." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/23385.
Full text
35
Adams, Warren Philip. "The mixed-integer bilinear programming problem with extensions to zero-one quadratic programs." Diss., Virginia Polytechnic Institute and State University, 1985. http://hdl.handle.net/10919/74711.
Full textAbstract:
This research effort is concerned with a class of mathematical programming problems referred to as Mixed-Integer Bilinear Programming Problems. This class of problems, which arises in production, location-allocation, and distribution-application contexts, may be considered as a discrete version of the well-known Bilinear Programming Problem in that one set of decision variables is restricted to be binary valued. The structure of this problem is studied, and special cases wherein it is readily solvable are identified. For the more general case, a new linearization technique is introduced and demonstrated to lead to a tighter linear programming relaxation than obtained through available linearization methods. Based on this linearization, a composite Lagrangian relaxation-implicit enumeration-cutting plane algorithm is developed. Extensive computational experience is provided to test the efficiency of various algorithmic strategies and the effects of problem data on the computational effort of the proposed algorithm.
The solution strategy developed for the Mixed-Integer Bilinear Programming Problem may be applied, with suitable modifications,. to other classes of mathematical programming problems: in particular, to the Zero-One Quadratic Programming Problem. In what may be considered as an extension to the work performed on the Mixed-Integer Bilinear Programming Problem, a solution strategy based on an equivalent linear reformulation is developed for the Zero-One Quadratic Programming Problem. The strategy is essentially an implicit enumeration algorithm which employs Lagrangian relaxation, Benders' cutting planes, and local explorations. Computational experience for this problem class is provided to justify the worth of the proposed linear reformulation and algorithm.Ph. D.
36
Celik, Gul. "Parameter Estimation In Generalized Partial Linear Models With Conic Quadratic Programming." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612531/index.pdf.
Full textAbstract:
In statistics, regression analysis is a technique, used to understand and model the
relationship between a dependent variable and one or more independent variables.
Multiple Adaptive Regression Spline (MARS) is a form of regression analysis. It is a
non-parametric regression technique and can be seen as an extension of linear models
that automatically models non-linearities and interactions. MARS is very important
in both classification and regression, with an increasing number of applications in
many areas of science, economy and technology.
In our study, we analyzed Generalized Partial Linear Models (GPLMs), which are
particular semiparametric models. GPLMs separate input variables into two parts
and additively integrates classical linear models with nonlinear model part. In order
to smooth this nonparametric part, we use Conic Multiple Adaptive Regression Spline
(CMARS), which is a modified form of MARS. MARS is very benefical for high
dimensional problems and does not require any particular class of relationship between
the regressor variables and outcome variable of interest. This technique offers a great advantage for fitting nonlinear multivariate functions. Also, the contribution of the
basis functions can be estimated by MARS, so that both the additive and interaction
effects of the regressors are allowed to determine the dependent variable. There are
two steps in the MARS algorithm: the forward and backward stepwise algorithms. In
the first step, the model is constructed by adding basis functions until a maximum
level of complexity is reached. Conversely, in the second step, the backward stepwise
algorithm reduces the complexity by throwing the least significant basis functions from
the model.
In this thesis, we suggest not using backward stepwise algorithm, instead, we employ
a Penalized Residual Sum of Squares (PRSS). We construct PRSS for MARS as a
Tikhonov Regularization Problem. We treat this problem using continuous optimization
techniques which we consider to become an important complementary technology
and alternative to the concept of the backward stepwise algorithm. Especially, we apply
the elegant framework of Conic Quadratic Programming (CQP) an area of convex
optimization that is very well-structured, hereby, resembling linear programming and,
therefore, permitting the use of interior point methods.
At the end of this study, we compare CQP with Tikhonov Regularization problem
for two different data sets, which are with and without interaction effects. Moreover,
by using two another data sets, we make a comparison between CMARS and two
other classification methods which are Infinite Kernel Learning (IKL) and Tikhonov
Regularization whose results are obtained from the thesis, which is on progress.
37
Sirovljevic, Jelena. "Incomplete factorization preconditioners for least squares and linear and quadratic programming." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32071.
Full textAbstract:
Many algorithms for optimization are based on solving a sequence of symmetric indefinite linear systems. These systems are often large and sparse, and the main approaches to solving them are based on direct factorization or iterative Krylovbased methods. In this thesis, we explore how incomplete sparse factorizations can be used as preconditioners for the special case of quasi-definite linear systems that arise in regularized linear and quadratic programming, and the case of least-squares reformulations of these systems. We describe two types of incomplete factorizations for use as preconditioners. The first is based on an incomplete Cholesky-like factorization. The second is based on an incomplete Householder QR factorization. Our approximate factorizations allow the user to prescribe the amount of fill-in, and therefore have predictable storage requirements. We use these incomplete factorizations as preconditioners for SYMMLQ and LSQR, respectively, and present numerical results for matrices that arise within an interior-point context.Science, Faculty of
Computer Science, Department of
Graduate
38
Ellison, E. F. D. "Solution methods and applications of convex quadratic programming and its extensions." Thesis, Brunel University, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.436501.
Full text
39
Kisala, Thomas P. "Successive Quadratic Programming in sequential modular process flowsheet simulation and optimization." Thesis, Massachusetts Institute of Technology, 1985. http://hdl.handle.net/1721.1/99554.
Full textAbstract:
Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Chemical Engineering, 1985.MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE.
Bibliography: leaves 244-248.
by Thomas Patrick Kisala.
Sc.D.
40
Hu, Sha S. M. Massachusetts Institute of Technology. "Semidefinite relaxation based branch-and-bound method for nonconvex quadratic programming." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/39217.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006.Includes bibliographical references (leaves 73-75).
In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly.
(cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems.
by Sha Hu.
S.M.
41
Hernandez, Marli de Freitas Gomes. "Algorithms for large sparse constrained optimisation." Thesis, University of Hertfordshire, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.259626.
Full text
42
Ozmen, Ayse. "Robust Conic Quadratic Programming Applied To Quality Improvement -a Robustification Of Cmars." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612513/index.pdf.
Full textAbstract:
In this thesis, we study and use Conic Quadratic Programming (CQP) for purposes of operational research, especially, for quality improvement in manufacturing. In previous works, the importance and benefit of CQP in this area became already demonstrated. There, the complexity of the regression method Multivariate Adaptive Regression Spline (MARS), which especially means sensitivity with respect to noise in the data, became penalized in the form of so-called Tikhonov regularization, which became expressed and studied as a CQP problem. This was leading to the new method CMARSit is more model-based and employs continuous, actually, well-structured convex optimization which enables the use of Interior Point Methods and their codes such as MOSEK. In this study, we are generalizing the regression problem by including uncertainty in the model, especially, in the input data, too. CMARS, recently developed as an alternative method to MARS, is powerful in overcoming complex and heterogeneous data. However, for MARS and CMARS method, data are assumed to contain fixed variables. In fact, data include noise in both output and input variables. Consequently, optimization problem&rsquo
s solutions can show a remarkable sensitivity to perturbations in the parameters of the problem. In this study, we include the existence of uncertainty in the future scenarios into CMARS and robustify it with robust optimization which is dealt with data uncertainty. That kind of optimization was introduced by Aharon Ben-Tal and Arkadi Nemirovski, and used by Laurent El Ghaoui in the area of data mining. It incorporates various kinds of noise and perturbations into the programming problem. This robustification of CQP with robust optimization is compared with previous contributions that based on Tikhonov regularization, and with the traditional MARS method.
43
Salah, Maher Jawad Younis. "Optimum plastic design of structures by generalized inverse theory and quadratic programming." Thesis, Queen Mary, University of London, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.337445.
Full text
44
Jung, Jin Hyuk. "Adaptive constraint reduction for convex quadratic programming and training support vector machines." College Park, Md. : University of Maryland, 2008. http://hdl.handle.net/1903/8020.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2008.Thesis research directed by: Dept. of Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
45
Paparistodemo, Marios. "Multinomial lattices and a quadratic programming approach for optimal replication in incomplete markets." Thesis, Imperial College London, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.271650.
Full text
46
Kang, Kyehong. "A structured reduced sequential quadratic programming and its application to a shape design problem." Diss., Virginia Tech, 1994. http://hdl.handle.net/10919/38565.
Full textAbstract:
The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called All at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the block structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, Sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with Variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians only of which the dimension is the number of design variables, the storage requirement for Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.
The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed the similar algorithm with the Orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the Black box method - unconstrained optimization formulation.Ph. D.
47
Rajgopal, P. "A flexible construction and improvement heuristic for the quadratic assignment problem." Thesis, Virginia Polytechnic Institute and State University, 1985. http://hdl.handle.net/10919/101253.
Full textAbstract:
This thesis is concerned with the development of heuristic algorithms for the popular Quadratic Assignment Problem (QAP) which finds a wide variety of applications in various fields. This discrete optimization problem, which seeks the placement of m facilities on m locations in order to minimize a quadratic interactive cost, is well known to be NP-hard and turns out to be computationally intractable for even moderately sized problems. Hence, problems involving more than 12-15 facilities usually need to be analysed by approximate solution procedures.
The more successful heuristic procedures which exist for problem QAP are computationally intensive, some of these resulting from a premature termination of exact solution procedures. The motivation here is to develop a polynomial time heuristic which is effective with respect to the quality of solutions obtained, while at the same time not being computationally very expensive.
The method proposed herein is flexible in that one can operate it to suitably trade solution quality against effort as desired, and is portable in that the modules used as building blocks can be employed in conjunction with other heuristics as well. Computational experience on test problems found in the literature is provided to evaluate the worth of this method.M.S.
48
Okan, Osman Burak. "Merging quadratic programming with kernel smoothing for automated cluster expansions of complex lattice Hamiltonians." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/44383.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Materials Science and Engineering, 2008.Includes bibliographical references (p. 46-48).
We present a general outline for automating cluster expansions of configurational energetics in systems with crystallographic order and well defined space group symmetry. The method presented herein combines constrained optimization techniques of positive-definitive quadratic forms with the mathematical tool of Tikhonov regularization (kernel smoothing) for automated expansions of an arbitrary general physical property without compromising the underlying physics. Throughout the thesis we treat formation energy as the fundamental physical observable to expand on since the predominant application of cluster expansions is the extraction of robust approximations for configurational energetics in alloys and oxides. We therefore present the implementational aspects of the novel algorithmic route on a challenging material system NaxCoO2 and reconstruct the corresponding GGA ground state line with arbitrary precision in the formation energy-configuration space. The mathematical arguments and proofs, although discussed for cases with arbitrary spin assignments and multiple candidate species for single site occupancy, are eventually formulated and illustrated for binary systems. Various numerical challanges and the way they are resolved in the framework of kernel smoothing are addressed in detail as well. However, the applicability of the procedure described herein is more universal and can be tailored to probe different observables without resorting to modifications in the algorithmic implementation or the fundemantal mathematical construction. The effectiveness in recovering correct physics shall than be solely tied to the presence of superposable nature (of the physical property of interest) of local atomic configurations or lackthereof.
by Osman Burak Okan.
S.M.
49
Cha, Kyungduck. "Cancer treatment optimization." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/22604.
Full textAbstract:
Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2008.Committee Chair: Lee, Eva K.; Committee Member: Barnes, Earl; Committee Member: Hertel, Nolan E.; Committee Member: Johnson, Ellis; Committee Member: Monteiro, Renato D.C.
50
Theußl, Stefan, Florian Schwendinger, and Kurt Hornik. "ROI: An extensible R Optimization Infrastructure." WU Vienna University of Economics and Business, 2019. http://epub.wu.ac.at/5858/1/ROI_StatReport.pdf.
Full textAbstract:
Optimization plays an important role in many methods routinely used in statistics, machine learning and data science. Often, implementations of these methods rely on highly specialized optimization algorithms, designed to be only applicable within a specific application. However, in many instances recent advances, in particular in the field of convex optimization, make it possible to conveniently and straightforwardly use modern solvers instead with the advantage of enabling broader usage scenarios and thus promoting reusability.
This paper introduces the R Optimization Infrastructure which provides an extensible infrastructure to model linear, quadratic, conic and general nonlinear optimization problems in a consistent way.
Furthermore, the infrastructure administers many different solvers, reformulations, problem collections and functions to read and write optimization problems in various formats.Series: Research Report Series / Department of Statistics and Mathematics