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 
Nonconvex Economic Dispatch by Integrated Artificial IntelligenceCheng, FuSheng 11 June 2001 (has links)
Abstract
This dissertation presents a new algorithm by integrating evolutionary programming (EP), tabu search (TS) and quadratic programming (QP), named the evolutionarytabu quadratic programming (ETQ) method, to solve the nonconvex economic dispatch problem (NED). This problem involves the economic dispatch with valvepoint effects (EDVP), economic dispatch with piecewise quadratic cost function (EDPQ), and economic dispatch with prohibited operating zones (EDPO). EDPV, EDPQ and EDPO are similar problems when ETQ was employed. The problem was solved in two phases, the costcurveselection subproblem, and the typical ED solving subproblem. The first phase was resolved by using a hybrid EP and TS, and the second phase by QP. In the solving process, EP with repairing strategy was used to generate feasible solutions, TS was used to prevent prematurity, and QP was used to enhance the performance. Numerical results show that the proposed method is more effective than other previously developed evolutionary computation algorithms.

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 
[en] AN IMPROVED EXACT METHOD FOR THE UBQP / [pt] UM MÉTODO EXATO MELHORADO PARA O UBQPDANIEL FLEISCHMAN 11 March 2011 (has links)
[pt] A Programação Quadrática Binária Irrestrita (UBQP) é amplamente
estudada. Tratase de uma ferramenta de modelagem poderosa, mas
otimizar de um problema NPdifícil. Neste trabalho uma nova abordagem
é apresentada, que pode ser usada para construir um algoritmo exato.
Além disso, a ideia básica que fundamenta o trabalho pode ser usado em
um espectro ainda mais amplo de problemas. O algoritmo exato derivado
do novo método é altamente paralelizável, o que é uma característica
desejável nos dias de hoje em que cloud computing já é uma realidade. Para
instâncias razoavelmente grandes do UBQP, o novo método pode paralelizar
a centenas, ou até milhares, de núcleos com facilidade, com um aumento
de desempenho quase linear. / [en] Unconstrained Binary Quadratic Programming (UBQP) is widely studied.
It is a powerful modeling tool and its associate problem is NPhard. In
this work a new approach is introduced, which can be used to build an
exact algorithm. Also, the fundamental idea behind it can be used in an
even wider family of problems. This exact algorithm derived from the new
method is highly parallelizable, which is a desired feature nowadays, when
the cloud computing is a reality. For reasonably large instances of UBQP,
the new method can parallelize to hundreds, or even thousands, of cores
easily, with a nearlinear speedup.

Page generated in 0.187 seconds