This paper presents a new method for solving a linear discrete-time finite horizon optimal control problem (FHOCP) with quadratic cost and linear constraints on the states and inputs. Such a FHOCP needs to be solved o...
详细信息
ISBN:
(纸本)9781424474264
This paper presents a new method for solving a linear discrete-time finite horizon optimal control problem (FHOCP) with quadratic cost and linear constraints on the states and inputs. Such a FHOCP needs to be solved online, at each sampling instant, in predictive control. In order to solve such a FHOCP, it is necessary to solve a quadratic programming (QP) problem. The proposed technique uses an inexact interior-point method (IIPM) to solve the QP problem. This new technique is computationally more efficient than the Riccati Recursion method of Rao, Wright and Rawlings (Journal of Optimization theory and Applications, 1998), when measured in terms of the number of floating point operations. The computational advantage is obtained by the use of an inexact Newton method, and with the use of novel preconditioners in the minimum residual (MINRES) method. The computational performance of this method is demonstrated by numerical results.
We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (th...
详细信息
We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis.
In this paper we present the theory and practical aspects of implementing the path following interiorpointmethods for linear optimization, based on kernel functions. We will investigate the influence of the choice o...
详细信息
ISBN:
(纸本)9781424453146
In this paper we present the theory and practical aspects of implementing the path following interiorpointmethods for linear optimization, based on kernel functions. We will investigate the influence of the choice of the kernel function on the computational behavior of the generic primal-dual algorithm for linear Optimization. We find that the finite kernel function gives the best results for more than 50 % of the tested problems compared to the standard log-barrier method.
The thesis is concerned with the interiorpointmethods for linear complementarity prob- lems (LCP). The LCP is an NP-complete problem, when we have no information about the coe cient matrix of the problem. In the lit...
The thesis is concerned with the interiorpointmethods for linear complementarity prob- lems (LCP). The LCP is an NP-complete problem, when we have no information about the coe cient matrix of the problem. In the literature there are e cient algorithms to solve the LCP, but only when the matrix of the problem belongs to a certain special matrix class. An arbitrary LCP problem can not be solved in polynomial time, not even if the coe cient matrix belongs to the su cient matrix class, since it can not be decided in polynomial time. Our aim was to construct an algorithm, which provides some kind of information about the LCP problem in polynomial time it gives a solution in the best case. We take well-known interiorpointmethods (for LCPs with P ( )-matrices) for the basis of the new algorithm. The modi ed algorithms are polynomial time methods. Our motivation was not only to handle the LCP problems in applications e ciently, but it was also theoretical. Based on the modi ed interiorpointmethods we gave constructive proofs for new EP theorems. The thesis can be divided into two parts. In the rst part we mainly collect well-known results according to the LCPs and interiorpointmethods. At the end of the Introduction we collect some well known problems, which can be reformulated as an LCP to illustrate how important an e cient algorithm for handling LCPs with arbitrary matrices will be in practice. Then we deal with some matrix classes related to LCPs, which are important for our purposes. Finally, we give an overview of the theory of interiorpointmethods. In the second part of the thesis rst the dual of the LCP is considered. We show that the dual LCP can be solved in polynomial time if the matrix is row su cient, and we give an EP type theorem based on this complexity result. We generalize the Mizuno Todd Ye predictor-corrector algorithm for LCPs with P ( )- matrices and show that the algorithm preserves its nice property, that is, if the two used neighbourhoods
The paper presents an implementation of LP decoding algorithm based on the primal path-following interiorpoint method. Numerical examples show some behaviors of an LP decoder based on the exact interiorpoint method....
详细信息
The paper presents an implementation of LP decoding algorithm based on the primal path-following interiorpoint method. Numerical examples show some behaviors of an LP decoder based on the exact interiorpoint method. It is shown that very accurate solution can be obtained after 40-50 iterations of the outer loop of the interiorpoint method. Complexity analysis on the proposed algorithm is given as well.
In this paper three different procedures to solve load distribution problems of gear teeth for static transmission error (TE) calculation of gear pairs are presented. Performance assessment was carried out with the th...
详细信息
In this paper three different procedures to solve load distribution problems of gear teeth for static transmission error (TE) calculation of gear pairs are presented. Performance assessment was carried out with the three procedures in static TE calculation of a helical gear pair under load with global tooth contact analysis. The procedures were compared in terms of computational effort to solve the load distribution problem and the accuracy of the solution. An incremental procedure with gradual and iterative load application was assessed for solving the full load distribution problem and calculating TE. Then the full load distribution problem was replaced by a reduced, but equivalent, problem through a method called pseudo-interference. The reduced problem was solved using the other two proposed procedures, a linearprogramming solution based on an interior-point algorithm and a direct matrix solver based on Cholesky factorisation. This latter procedure showed to be highly efficient in solving load distribution problems of gear teeth. (C) 2007 Elsevier Ltd. All rights reserved.
We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal O *(√T) regret. The setting is a natural generalization of the non-stochastic multi-a...
详细信息
We introduce an efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal O *(√T) regret. The setting is a natural generalization of the non-stochastic multi-armed bandit problem, and the existence of an efficient optimal algorithm has been posed as an open problem in a number of recent papers. We show how the difficulties encountered by previous approaches are overcome by the use of a self-concordant potential function. Our approach presents a novel connection between online learning and interiorpointmethods.
Mehrotra-type predictor-corrector algorithms are the basis of interiorpointmethods software packages. Salahi et al. in their recent work have shown a feasible version of a variation of Mehrotra's second order al...
详细信息
ISBN:
(纸本)9783540877318
Mehrotra-type predictor-corrector algorithms are the basis of interiorpointmethods software packages. Salahi et al. in their recent work have shown a feasible version of a variation of Mehrotra's second order algorithm for linear optimization may be forced to make many small steps that motivated them to introduce certain safeguards, what allowed them to prove polynomial iteration complexity while keeping its practice efficiency. In this paper, we extend their algorithm to monotone linear complementarity problems. Our algorithm is different from their method in the way of updating the barrier parameter and the complexity analysis, and we also show that the Polynomial complexity Of out algorithm is O(n(2) log (x(0))(T)s(0) / E).
This textbook provides a self-contained introduction to linearprogramming using MATLAB software to elucidate the development of algorithms and theory. Early chapters cover linear algebra basics, the simplex method, d...
详细信息
ISBN:
(纸本)9780898716436
This textbook provides a self-contained introduction to linearprogramming using MATLAB software to elucidate the development of algorithms and theory. Early chapters cover linear algebra basics, the simplex method, duality, the solving of large linear problems, sensitivity analysis, and parametric linearprogramming. In later chapters, the authors discuss quadratic programming, linear complementarity, interior-pointmethods, and selected applications of linearprogramming to approximation and classification problems. Exercises are interwoven with the theory presented in each chapter, and two appendices provide additional information on linear algebra, convexity, nonlinear functions, and on available MATLAB commands, respectively. Readers can access MATLAB codes and associated mex files at a Web site maintained by the authors. Only a basic knowledge of linear algebra and calculus is required to understand this textbook, which is geared toward junior and senior-level undergraduate students, first-year graduate students, and researchers unfamiliar with linearprogramming.
暂无评论