Spelling suggestions: "subject:"quadratic programming"" "subject:"cuadratic programming""
41 
Applications of Integer Quadratic Programming in Control and CommunicationAxehill, Daniel January 2005 (has links)
<p>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 principles is the discretetime method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, 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 from constrained linear systems to socalled 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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a socalled multiaccess channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two 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 simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as 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 KKTsystems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers.</p> / Report code: LiUTEKLIC2005:71.

42 
Cancer treatment optimizationCha, Kyungduck 01 April 2008 (has links)
This dissertation investigates optimization approaches applied to radiation therapy in cancer treatment. Since cancerous cells are surrounded by critical organs and normal tissues, there is conflicting objectives in the treatment design of providing sufficient radiation dose to tumor region, while avoiding normal healthy cells. In general, the goal of radiation therapy is to conform the spatial distribution of the prescribed dose to the tumor volume while minimizing the dose to the surrounding normal structures. A recent advanced technology, using multileaf collimator integrated into linear accelerator, provides much better opportunities to achieve this goal: the radiotherapy based on nonuniform radiation beams intensities is called IntensityModulated Radiation Therapy.
My dissertation research offers a quadratic mixed integer programming approach to determine optimal beam orientations and beamlets intensity simultaneously. The problems generated from real patient cases are largescale dense instances due to the physics of dose contributions from beamlets to volume elements. The research highlights computational techniques to improve solution times for these intractable instances. Furthermore,
results from this research will provide plans that are clinically acceptable and superior in plan quality, thus directly improve the curity rate and lower the normal tissue complication for cancer patients.

43 
Applications of Integer Quadratic Programming in Control and CommunicationAxehill, Daniel January 2005 (has links)
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 principles is the discretetime method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, 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 from constrained linear systems to socalled 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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a socalled multiaccess channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two 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 simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as 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 KKTsystems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers. / Report code: LiUTEKLIC2005:71.

44 
Optimal power flow via quadratic modelingTao, Ye 29 August 2011 (has links)
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 KuhnTucker 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 firstorder methods and are totally inefficient for largescale 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 wellknown 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 threephase OPF (TOPF) algorithm for unbalanced networks using the quadratized threephase 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.

45 
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic ProgrammingDing, Yichuan 17 May 2007 (has links)
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the SProcedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

46 
kernlab  An S4 package for kernel methods in RKaratzoglou, Alexandros, Smola, Alex, Hornik, Kurt, Zeileis, Achim January 2004 (has links) (PDF)
kernlab is an extensible package for kernelbased machine learning methods in R. It takes advantage of R's new S4 object model and provides a framework for creating and using kernelbased algorithms. The package contains dot product primitives (kernels), implementations of support vector machines and the relevance vector machine, Gaussian processes, a ranking algorithm, kernel PCA, kernel CCA, and a spectral clustering algorithm. Moreover it provides a general purpose quadratic programming solver, and an incomplete Cholesky decomposition method. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

47 
Trade Study of Decomissioning Strategies for the International Space StationHerbort, Eric 06 September 2012 (has links)
This thesis evaluates decommissioning strategies for the International Space Station ISS. A permanent solution is attempted by employing energy efficient invariant manifolds that arise in the circular restricted three body problem CRTBP to transport the ISS from its low Earth orbit LEO to a lunar orbit. Although the invariant manifolds provide efficient transport, getting the the ISS onto the manifolds proves quite expensive, and the trajectories take too long to complete. Therefore a more practical, although temporary, solution consisting of an optimal reboost maneuver with the European Space Agency's automated transfer vehicle ATV is proposed. The optimal reboost trajectory is found using control parameterization and the sequential quadratic programming SQP algorithm. The model used for optimization takes into account the affects of atmospheric drag and gravity perturbations. The optimal reboost maneuver produces a satellite lifetime of approximately ninetyfive years using a two ATV strategy.

48 
Uncertainty modelling in power system state estimationAlOthman, Abdul Rahman K. January 2004 (has links)
As a special case of the static state estimation problem, the loadflow problem is studied in this thesis. It is demonstrated that the nonlinear loadflow formulation may be solved by realcoded genetic algorithms. Due to its global optimisation ability, the proposed method can be useful for offline studies where multiple solutions are suspected. This thesis presents two methods for estimating the uncertainty interval in power system state estimation due to uncertainty in the measurements. The proposed formulations are based on a parametric approach which takes in account the meter inaccuracies. A nonlinear and a linear formulation are proposed to estimate the tightest possible upper and lower bounds on the states. The uncertainty analysis, in power system state estimation, is also extended to other physical quantities such as the network parameters. The uncertainty is then assumed to be present in both measurements and network parameters. To find the tightest possible upper and lower bounds of any state variable, the problem is solved by a Sequential Quadratic Programming (SQP) technique. A new robust estimator based on the concept of uncertainty in the measurements is developed here. This estimator is known as Maximum Constraints Satisfaction (MCS). Robustness and performance of the proposed estimator is analysed via simulation of simple regression examples, D.C. and A.C. power system models.

49 
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic ProgrammingDing, Yichuan 17 May 2007 (has links)
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the SProcedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

50 
Application of Genetic Algorithm to a Forced Landing Manoeuvre on Transfer of Training AnalysisTong, Peter, mail@petertong.com January 2007 (has links)
This study raises some issues for training pilots to fly forced landings and examines the impact that these issues may have on the design of simulators for such training. It focuses on flight trajectories that a pilot of a singleengine general aviation aircraft should fly after engine failure and how pilots can be better simulator trained for this forced landing manoeuvre. A sensitivity study on the effects of errors and an investigation on the effect of tolerances in the aerodynamic parameters as prescribed in the Manual of Criteria for the Qualification of Flight Simulators have on the performance of flight simulators used for pilot training was carried out. It uses a simplified analytical model for the Beech Bonanza model E33A aircraft and a vertical atmospheric turbulence based on the MILF8785C specifications. It was found that the effect of the tolerances is highly sensitive on the nature of the manoeuvre flown and that in some cases, negative transfe r of training may be induced by the tolerances. A forced landing trajectory optimisation was carried out using Genetic Algorithm. The forced landing manoeuvre analyses with preselected touchdown locations and preselected final headings were carried out for an engine failure at 650 ft AGL for bank angles varying from banking left at 45° to banking right at 45°, and with an aircraft's speed varying from 75.6 mph to 208 mph, corresponding to 5% above airplane's stall speed and airplane's maximum speed respectively. The results show that certain preselected touchdown locations are more susceptible to horizontal wind. The results for the forced landing manoeuvre with a preselected location show minimal distance error while the quality of the results for the forced landing manoeuvre with a preselected location and a final heading show that the results depend on the end constraints. For certain preselected touchdown locations and final headings, the airplane may either touchdown very close to the preselected touchdown location but with greater final h eading error from the preselected final heading or touchdown with minimal final heading error from the preselected final heading but further away from the preselected touchdown location. Analyses for an obstacle avoidance forced landing manoeuvre were also carried out where an obstacle was intentionally placed in the flight path as found by the GA program developed for without obstacle. The methodology developed successfully found flight paths that will avoid the obstacle and touchdown near the preselected location. In some cases, there exist more than one ensemble grouping of flight paths. The distance error depends on both the preselected touchdown location and where the obstacle was placed. The distance error tends to increase with the addition of a specific final heading requirement for an obstacle avoidance forced landing manoeuvre. As with the case without specific final heading requirement, there is a trade off between touching down nearer to the preselected location and touching down with a smaller final heading error.

Page generated in 0.14 seconds