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.
Ben Daya, Mohamed
No description available.
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.
Thesis (Ph. D.)--University of Washington, 1986. / Vita. Bibliography: leaves -168.
2010 May 1900
Clock mesh is widely used in microprocessor designs for achieving low clock skew and high process variation tolerance. Clock mesh optimization is a very diffcult problem to solve because it has a highly connected structure and requires accurate delay models which are computationally expensive. Existing methods on clock network optimization are either restricted to clock trees, which are easy to be separated into smaller problems, or naive heuristics based on crude delay models. A clock mesh sizing algorithm, which is aimed to minimize total mesh wire area with consideration of clock skew constraints, has been proposed in this research work. This algorithm is a systematic solution search through rigorous Sequential Quadratic Programming (SQP). The SQP is guided by an efficient adjoint sensitivity analysis which has near-SPICE(Simulation Program for Integrated Circuits Emphasis)-level accuracy and faster-than-SPICE speed. Experimental results on various benchmark circuits indicate that this algorithm leads to substantial wire area reduction while maintaining low clock skew in the clock mesh. The reduction in mesh area achieved is about 33%.
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.
Page generated in 0.258 seconds