This study is concerned with constrained optimization problems where the only inequality constraints are nonnegativity constraints on the variables. In these problems, the ability to identify zero variables (binding c...
详细信息
This study is concerned with constrained optimization problems where the only inequality constraints are nonnegativity constraints on the variables. In these problems, the ability to identify zero variables (binding constraints) early on in an iterative method is of considerable value and can be used to computational advantage. This work first gives a formal presentation of the notion of indicators for identifying zero variables, and then studies various indicators proposed in the literature for use with interior-pointmethods for linearprogramming. Both theory and experimentation are presented that speak strongly against the use of the variables as indicators;perhaps the most frequently used indicator in the literature. This study implies that an indicator proposed by Tapia is particularly effective in the context of primal-dual interior-pointmethods. The local rate of convergence for several indicators is also studied.
interior-pointmethods require strictly feasible points as starting points. In theory, this requirement does not seem to be particularly restrictive, but it can be costly in computation. To overcome this deficiency, m...
详细信息
interior-pointmethods require strictly feasible points as starting points. In theory, this requirement does not seem to be particularly restrictive, but it can be costly in computation. To overcome this deficiency, most existing practical algorithms allow positive but infeasible starting points and seek feasibility and optimality simultaneously. Algorithms of this type shall be called infeasible interior-point algorithms. Despite their superior performance, existing infeasible interior-point algorithms still lack a satisfactory demonstration of theoretical convergence and polynomial complexity This paper studies a popular infeasible interior-point algorithmic framework that was implemented for linearprogramming in the highly successful interior-point code OBI [I. J. Lustig, R. E. Marsten, and D. F. Shanno, linear Algebra Appl., 152 (1991), pp. 191-222]. For generality, the analysis is carried out on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under minimal assumptions, it is demonstrated that with properly controlled steps the algorithm converges at a global Q-linear rate. Moreover, with properly chosen starting points it is established the algorithm can obtain epsilon-feasibility and epsilon-complementarity in at most O(n(2) In(1/epsilon)) iterations.
A new method is proposed for the linesearch procedure in algorithm barrier function and other interiorpointmethods for convex quadratically constrained quadratic programming problems, which includes linear and quadr...
详细信息
A new method is proposed for the linesearch procedure in algorithm barrier function and other interiorpointmethods for convex quadratically constrained quadratic programming problems, which includes linear and quadratic programming as special cases. The method consists in transforming the derivative of the function obtained in this linesearch, so that Newton's method for finding its unique root will be globally convergent. It is equally useful in solving a problem in a matrix theory, namely the computation of the eigenvalues of a matrix, perturbed by the addition of a matrix of rank one. An improved Newton method is also presented together with numerical results.
We consider the linear program min {c'x: Ax less than or equal to b} and the associated exponential penalty function f(r)(x) = c'x + r Sigma exp[(A(i)x - b(i))/r]. For r close to 0, the unconstrained minimizer...
详细信息
We consider the linear program min {c'x: Ax less than or equal to b} and the associated exponential penalty function f(r)(x) = c'x + r Sigma exp[(A(i)x - b(i))/r]. For r close to 0, the unconstrained minimizer x(r) of f(r) admits an asymptotic expansion of the form x(r) = x* + rd* + eta(r) where x* is a particular optimal solution of the linear program and the error term eta(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory lambda(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis when r tends to infinity: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.
We consider the following quasiconvex optimization problem: minimize the largest eigenvalue of a symmetric definite matrix pencil depending on parameters. A new form of optimality conditions is given, emphasizing a co...
详细信息
We consider the following quasiconvex optimization problem: minimize the largest eigenvalue of a symmetric definite matrix pencil depending on parameters. A new form of optimality conditions is given, emphasizing a complementarity condition on primal and dual matrices. Newton's method is then applied to these conditions to give a new quadratically convergent interior-point method which works well in practice. The algorithm is closely related to primal-dual interior-pointmethods for semidefinite programming.
The literature in the field of interiorpointmethods for linearprogramming has been almostexclusively algorithm oriented. Recently Giiler, Roos, Terlaky and Vial presented a complete duality theory for linear progra...
详细信息
We show that recently developed interiorpointmethods for quadratic programming and linear complementarity problems can be put to use in solving discrete-time optimal control problems, with general pointwise constrai...
详细信息
We show that recently developed interiorpointmethods for quadratic programming and linear complementarity problems can be put to use in solving discrete-time optimal control problems, with general pointwise constraints on states and controls. We describe interiorpoint algorithms for a discrete-time linear-quadratic regulator problem with mixed state/control constraints and show how they can be efficiently incorporated into an inexact sequential quadratic programming algorithm for nonlinear problems. The key to the efficiency of the interior-point method is the narrow-banded structure of the coefficient matrix which is factorized at each iteration.
We study the problem of finding a point in the relative interior of the optimal face of a line-ar program. We prove that in the worst case such a point can be obtained in O(n3L) arithmetic operations. This complexity ...
详细信息
We study the problem of finding a point in the relative interior of the optimal face of a line-ar program. We prove that in the worst case such a point can be obtained in O(n3L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linearprogramming problems in the NETLIB test set.
暂无评论