This thesis is mainly concerned with the efficient solution of a linear discrete-time
finite horizon optimal control problem (FHOCP) with quadratic cost and linear constraints
on the states and inputs. In predictive control, such a FHOCP needs to be
solved online at each sampling instant. In order to solve such a FHOCP, it is necessary
to solve a quadratic programming (QP) problem. Interior point methods (IPMs) have
proven to be an efficient way of solving quadratic programming problems. A linear system
of equations needs to be solved in each iteration of an IPM. The ill-conditioning
of this linear system in the later iterations of the IPM prevents the use of an iterative
method in solving the linear system due to a very slow rate of convergence; in some cases
the solution never reaches the desired accuracy. A new well-conditioned IPM, which increases
the rate of convergence of the iterative method is proposed. The computational
advantage is obtained by the use of an inexact Newton method along with the use of
novel preconditioners.
A new warm-start strategy is also presented to solve a QP with an interior-point
method whose data is slightly perturbed from the previous QP. The effectiveness of
this warm-start strategy is demonstrated on a number of available online benchmark
problems. Numerical results indicate that the proposed technique depends upon the
size of perturbation and it leads to a reduction of 30-74% in floating point operations
compared to a cold-start interior point method.
Following the main theme of this thesis, which is to improve the computational efficiency
of an algorithm, an efficient algorithm for solving the coupled Sylvester equation
that arises in converting a system of linear differential-algebraic equations (DAEs) to
ordinary differential equations is also presented. A significant computational advantage
is obtained by exploiting the structure of the involved matrices. The proposed algorithm
removes the need to solve a standard Sylvester equation or to invert a matrix. The
improved performance of this new method over existing techniques is demonstrated by
comparing the number of floating-point operations and via numerical examples.