24 January 2014
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.
Quadratic 0-1 programming: geometric methods and duality analysis. / CUHK electronic theses & dissertations collectionJanuary 2008 (has links)
In part I of this dissertation, certain rich geometric properties hidden behind quadratic 0-1 programming are investigated. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0-1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0-1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results. / In part II of this dissertation, we present new results of the duality gap between the binary quadratic optimization problem and its Lagrangian dual. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the problem. We then characterize the zeroness of duality gap by the distance, delta, between the binary set and certain affine space C. Finally, we discuss a computational procedure of the distance delta. These results provide new insights into the duality gap and polynomial solvability of binary quadratic optimization problems. / The unconstraint quadratic binary problem (UBQP), as a classical combinatorial problem, finds wide applications in broad field and human activities including engineering, science, finance, etc. The NP-hardness of the combinatorial problems makes a great challenge to solve the ( UBQP). The main purpose of this research is to develop high performance solution method for solving (UBQP) via the geometric properties of the objective ellipse contour and the optimal solution. This research makes several contributions to advance the state-of-the-art of geometric approach of (UBQP). These contributions include both theoretical and numerical aspects as stated below. / Liu, Chunli. / Adviser: Duan Li. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3764. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 140-153). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong,  System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.
Continuous-time recurrent neural networks for quadratic programming: theory and engineering applications.January 2005 (has links)
Liu Shubao. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 90-98). / Abstracts in English and Chinese. / Abstract --- p.i / 摘要 --- p.iii / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Time-Varying Quadratic Optimization --- p.1 / Chapter 1.2 --- Recurrent Neural Networks --- p.3 / Chapter 1.2.1 --- From Feedforward to Recurrent Networks --- p.3 / Chapter 1.2.2 --- Computational Power and Complexity --- p.6 / Chapter 1.2.3 --- Implementation Issues --- p.7 / Chapter 1.3 --- Thesis Organization --- p.9 / Chapter I --- Theory and Models --- p.11 / Chapter 2 --- Linearly Constrained QP --- p.13 / Chapter 2.1 --- Model Description --- p.14 / Chapter 2.2 --- Convergence Analysis --- p.17 / Chapter 3 --- Quadratically Constrained QP --- p.26 / Chapter 3.1 --- Problem Formulation --- p.26 / Chapter 3.2 --- Model Description --- p.27 / Chapter 3.2.1 --- Model 1 (Dual Model) --- p.28 / Chapter 3.2.2 --- Model 2 (Improved Dual Model) --- p.28 / Chapter II --- Engineering Applications --- p.29 / Chapter 4 --- KWTA Network Circuit Design --- p.31 / Chapter 4.1 --- Introduction --- p.31 / Chapter 4.2 --- Equivalent Reformulation --- p.32 / Chapter 4.3 --- KWTA Network Model --- p.36 / Chapter 4.4 --- Simulation Results --- p.40 / Chapter 4.5 --- Conclusions --- p.40 / Chapter 5 --- Dynamic Control of Manipulators --- p.43 / Chapter 5.1 --- Introduction --- p.43 / Chapter 5.2 --- Problem Formulation --- p.44 / Chapter 5.3 --- Simplified Dual Neural Network --- p.47 / Chapter 5.4 --- Simulation Results --- p.51 / Chapter 5.5 --- Concluding Remarks --- p.55 / Chapter 6 --- Robot Arm Obstacle Avoidance --- p.56 / Chapter 6.1 --- Introduction --- p.56 / Chapter 6.2 --- Obstacle Avoidance Scheme --- p.58 / Chapter 6.2.1 --- Equality Constrained Formulation --- p.58 / Chapter 6.2.2 --- Inequality Constrained Formulation --- p.60 / Chapter 6.3 --- Simplified Dual Neural Network Model --- p.64 / Chapter 6.3.1 --- Existing Approaches --- p.64 / Chapter 6.3.2 --- Model Derivation --- p.65 / Chapter 6.3.3 --- Convergence Analysis --- p.67 / Chapter 6.3.4 --- Model Comparision --- p.69 / Chapter 6.4 --- Simulation Results --- p.70 / Chapter 6.5 --- Concluding Remarks --- p.71 / Chapter 7 --- Multiuser Detection --- p.77 / Chapter 7.1 --- Introduction --- p.77 / Chapter 7.2 --- Problem Formulation --- p.78 / Chapter 7.3 --- Neural Network Architecture --- p.82 / Chapter 7.4 --- Simulation Results --- p.84 / Chapter 8 --- Conclusions and Future Works --- p.88 / Chapter 8.1 --- Concluding Remarks --- p.88 / Chapter 8.2 --- Future Prospects --- p.88 / Bibliography --- p.89
07 June 2006
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.
Tuncbilek, Cihan H.
03 August 2007
This dissertation is concerned with the global optimization of polynomial programming problems, and a detailed treatment of its particular special case, the indefinite quadratic programming problem. Polynomial programming problems are generally nonconvex, involving the optimization of a polynomial objective function over a compact feasible region defined in terms of polynomial constraints. These problems arise in a variety of applications in the context of engineering design and chemical process design situations. Despite the wide applicability of these classes of problems, there is a significant gap between the theory and practice in this field, principally due to the challenge faced in solving these rather difficult problems. The purpose of this dissertation is to introduce new solution strategies that assist in closing this gap. For solving polynomial programming problems, we present a branch and bound algorithm that uses a Reformulation Linearization Technique (RLT) to generate tight linear programming relaxations. This bounding scheme involves an automatic reformulation of the problem via the addition of certain nonlinear implied constraints that are generated by using the products of the simple bounding restrictions and, optionally, products involving the structural constraints. Subsequently, in a linearization phase, each distinct nonlinear term in the resulting problem is replaced by a new variable to obtain a linear program. The underlying purpose of this procedure is to closely approximate the convex envelope of the objective function over the convex hull of the feasible region. Various implementation issues regarding the derivation of such a bounding problem using the RLT, and the dominance of such bounds over existing alternative schemes, are investigated, both the- theoretically and computationally. The principal thrust of the proposed method is to construct a tight linear programming relaxation of the problem via an appropriate RLT procedure, and to use this in concert with a suitable partitioning strategy, in order to derive a practically effective algorithm that is theoretically guaranteed to be globally convergent. To address various implementation issues, empirical experiments are conducted using several test problems from the literature, many motivated by the aforementioned practical applications. Our results on solving several such practical engineering design problems demonstrate the viability of the proposed approach. This approach is also specialized and further enhanced for the particular class of indefinite (and concave) quadratic programming problems. These problems are important in their own right, and arise in many applications such as in modelling economies of scale in a cost structure, in location-allocation problems, several production planning and risk management problems, and in various other mathematical models such as the maximum clique problem and the jointly constrained bilinear programming problem. The proposed algorithm is more than just a specialization of the polynomial programming approach; it involves new, nontrivial extensions that exploit the particular special structure of the problem, along with many additional supporting features that improve the computational efficiency of the procedure. Certain types of nonlinearities are also retained and handled implicitly within the bounding problem to obtain sharper bounds. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality.) It is shown that for many problems, including randomly generated problems having up to 50 variables, the initial relaxation itself produces an optimal or a near optimal solution. This is significant in that the proposed methodology affords an approach whereby such hard nonconvex problems can be practically solved via a single or a few higher dimensional linear programming problems. / Ph. D.
22 July 2011
The Barzilai-Borwein (BB) method for unconstrained optimization has attracted attention for its "chaotic" behaviour and fast convergence on image deconvolution problems. However, images with large areas of darkness, such as those often found in astronomy or microscopy, have been shown to benefit from approaches which impose a nonnegativity constraint on the pixel values. We present a new adaptation of the BB method which enforces a nonnegativity constraint by projecting the solution onto the feasible set, but allows for infeasible iterates between projections. We show that this approach results in faster convergence than the basic Projected Barzilai-Borwein (PBB) method, while achieving better quality images than the unconstrained BB method. We find that the new method also performs comparably to the Gradient Projection-Conjugate Gradient (GPCG) method, and in most test cases achieves a lower restoration error, despite being a much simpler algorithm.
Foster, David Martin
No description available.
01 January 2013
Commercial fresh vegetable production is one of the most rewarding and risky farming activities. The price and yield variations throughout the production year, the special characteristics of fresh vegetable produce (i.e. perishability), and the changing consumer demands are some of the factors contributing to the increased uncertainty faced by vegetable producers. This dissertation combined mathematical programming and econometric techniques to: 1) investigate the optimal production and marketing practices under different price distribution information scenarios, risk aversion levels and marketing outlets and 2) examine growers’ preferences as well the effect of risk aversion levels and growers’ risk perception on the choice of marketing contracts. Specifically, the following three modeling approaches were adopted in order to achieve the dissertation objectives: 1) quadratic programming under a mean-variance framework, 2) discrete choice experiments and 3) a combination of quadratic and integer programming embodied in a meanvariance framework. The findings indicate that optimal production practices and the resulting net returns are substantially influenced not only by the choice of marketing channel but also by growers’ risk aversion levels as well as price knowledge. Furthermore, regarding the choice of marketing contracts, the results highlight the existence of heterogeneity in preferences and illustrate the importance of certification cost, in line with the previous literature. Lastly, the findings indicate that risk aversion and risk preferences do not play a significant role in the choice of contractual agreements by farmers.
Intuitive Mission Handling with Automatic Route Re-planning using Model Predictive Control / Intuitiv uppdragshantering med modellbaserad prediktionsreglering för automatisk ruttomplaneringAndersson, Emma January 2012 (has links)
The system for mission handling in the Gripen fighter aircraft, and in its ground supporting system, consists for example of ways to plan mission routes, create mission points and validate performed missions. The system is complex and for example, the number of different mission points used increases due to changing demands and needs. This master thesis presents suggestions for improvements and simplifications for the mission handling system, to make it more intuitive and more friendly to use. As a base for the suggestions, interviews with pilots from Saab, TUJAS and FMV have been conducted, this is to obtain opinions and ideas from those using the system and have deep knowledge about it. Another possible assistance and improvement is to provide the possibility of on-line automatic re-planning of the mission route in case of obstacles. MPC (Model Predictive Control) has been used to estimate the obstacle’s flight path,and calculate a new route to the next mission point which does not conflict with the estimated enemy’s path. This system has been implemented in Matlab and the concept is demonstrated with different test scenarios where the design parameters (prediction horizon and penalty in the cost function) for the controller are varied, and stationary and moving obstacles are induced. / Systemet för uppdragshantering i stridsflygplanet Gripen, och i dess markstödsystem, består bland annat av uppdragsplanering, skapande av uppdragspunkter och möjligheter att validera utförda uppdrag. Systemet är komplext och exempelvis växer antalet uppdragspunkter med omvärldens ökande krav och behov. Detta examensarbete presenterar förslag till förenklingar och förbättringar i uppdragshanteringssystemet, för att göra det mer intuitivt och användarvänligt. Som grund för förslagen har intervjuer med piloter från Saab, TUJAS och FMV gjorts, för att samla in åsikter och idéer från de som använder systemet och har bred kunskap om det. En förbättring är en möjlighet till online automatisk omplanering av uppdragsrutten vid hinder. MPC (modellbaserad prediktionsreglering) har använts för att estimera den dynamiska fiendens flygväg, och beräkna en ny rutt till nästa uppdragspunkt som inte ligger i konflikt med den estimerade vägen för hindret. Detta system har implementerats i Matlab och konceptet demonstreras med olika testscenarion där prestandaparametrar (prediktionshorisont och straff i kostnadsfunktionen) för regulatorn varieras, och stationära och rörliga hinder induceras.
03 August 2005
Co-generation is an efficient energy system that generates steam and electricity simultaneously. In ordinary operation, fuel cost accounts for more than 60% of the operational cost. As a result, the boiler efficiency and optimization level of co-generation are both high. To achieve further energy conservation, objectives of this thesis are to find the Profit-maximizing dispatch and efficiency enhancing strategy of the co-generation systems under deregulation. In a coexistent environment of both Bilateral and Poolco-based power market, there are bid-based spot dispatch, and purchases and sales agreement-based contract dispatch. For profit-maximizing dispatch, the steam of boilers, fuels and generation output will be obtained by using the SQP(Sequential Quadratic Programming ) method. In order to improve the boiler efficiency, this thesis utilizes artificial neural networks(ANN) and evolutionary programming(EP) methods to search for the optimal operating conditions of boilers. A co-generation system (back-pressure type and extraction type) is used to illustrate the effectiveness of the proposed method.
Page generated in 0.1661 seconds