检索结果-内蒙古大学图书馆

On interior-point Newton algorithms for discretized optimal control problems with state constraints

OPTIMIZATION METHODS & SOFTWARE 1998年第3-4期8卷 249-275页

作者： Vicente, LN Univ Coimbra Dept Matemat P-3000 Coimbra Portugal

In this paper we consider a class of nonlinear programming problems that arise from the discretization of optimal control problems with bounds on both the state and the control variables. For this class of problems, we analyze constraint qualifications and optimality conditions in detail. We derive an affine-scaling and two primal-dual interior-point Newton algorithms by applying, in an interior-point way, Newton's method to equivalent forms of the first-order optimality conditions. Under appropriate assumptions, the interior-point Newton algorithms are shown to be locally well-defined with a q-quadratic rate of local convergence. By using the structure of the problem, the linear algebra of these algorithms can be reduced to the null space of the Jacobian of the equality constraints. The similarities between the three algorithms are pointed out, and their corresponding versions for the general nonlinear programming problem are discussed.

关键词： nonlinear programming Newton's method interior-point algorithms affine scaling primal dual optimal control problems state constraints

来源：评论

学校读者我要写书评

暂无评论

Superlinear convergence of affine-scaling interior-point Newton methods for infinite-dimensional nonlinear problems with pointwise bounds

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2000年第6期38卷 1938-1984页

作者： Ulbrich, M Ulbrich, S Tech Univ Munich Lehrstuhl Angew Math & Math Stat D-80290 Munich Germany

We develop and analyze a superlinearly convergent affine-scaling interior-point Newton method for infinite-dimensional problems with pointwise bounds in L-p-space. The problem formulation is motivated by optimal control problems with L-p-controls and pointwise control constraints. The finite-dimensional convergence theory by Coleman and Li [SIAM J. Optim., 6 (1996), pp. 418-445] makes essential use of the equivalence of norms and the exact identifiability of the active constraints close to an optimizer with strict complementarity. Since these features are not available in our infinite-dimensional framework, algorithmic changes are necessary to ensure fast local convergence. The main building block is a Newton-like iteration for an affine-scaling formulation of the KKT-condition. We demonstrate in an example that a stepsize rule to obtain an interior iterate may require very small stepsizes even arbitrarily close to a nondegenerate solution. Using a pointwise projection instead we prove superlinear convergence under a weak strict complementarity condition and convergence with Q-rate >1 under a slightly stronger condition if a smoothing step is available. We discuss how the algorithm can be embedded in the class of globally convergent trust-region interior-point methods recently developed by M. Heinkenschloss and the authors. Numerical results for the control of a heating process confirm our theoretical findings.

关键词： infinite-dimensional optimization bound constraints affine scaling interior-point algorithms superlinear convergence trust-region methods optimal control nonlinear programming optimality conditions

来源：评论

学校读者我要写书评

暂无评论

Adaptive linear filtering using interior paint optimization techniques

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2000年第6期48卷 1637-1648页

作者： Afkhamie, KH Luo, ZQ Wong, KM McMaster Univ Dept Elect & Comp Engn Commun Res Lab Hamilton ON L8S 4L7 Canada

We propose a novel approach for the linear adaptive filtering problem using techniques from interior point optimization, The main idea is to formulate a com ex feasibility problem at each iteration and obtain as an estimate a filter near the center of the feasible region. It is shown, under some mild conditions, that this algorithm generates a sequence of filters converging to the optimum linear filter at the rate O(1/n), where n is the number of data samples. Furthermore, we show that the algorithm can be made recursive with a per-sample complexity of O(M-2.2), where M is the filter length. The potential of the algorithm for practical applications is demonstrated via numerical simulations where the new algorithm is shown to have superior transient behavior and improved robustness to the source signal statistics when compared to the recursive least-squares (RLS) method.

关键词： adaptive filters interior-point algorithms recursive least-squares

来源：评论

学校读者我要写书评

暂无评论

On the interplay among entropy, variable metrics and potential functions in interior-point algorithms

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1997年第1期8卷 5-19页

作者： Tuncel, L Todd, MJ CORNELL UNIV SCH OPERAT RES & IND ENGNITHACANY 14853

We are motivated by the problem of constructing a primdi-dual barrier function whose Hessian induces the (theoretically and practically) popular symmetric primal and dual scalings for linear programming problems. Although this goal is impossible to attain, we show that the primal-dual entropy function map provide a satisfactory alternative. We study primal-dual interior-point algorithms whose search directions are obtained from a potential function based on this primal-dual entropy barrier. We provide polynomial iteration bounds for these interior-point algorithms. Then we illustrate the connections between the barrier function and a reparametrization of the central path equations. Finally, we consider the possible effects of more general reparametrizations on infeasible-interior-point algorithms.

关键词： linear programming interior-point algorithms primal-dual entropy potential function

来源：评论

学校读者我要写书评

暂无评论

Two interior-point methods for nonlinear P_*(τ)-complementarity problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1999年第3期102卷 659-679页

作者： Zhao, YB Han, JY Chinese Acad Sci Inst Appl Math Beijing Peoples R China

Two interior-point algorithms using a wide neighborhood of the central path are proposed to solve nonlinear P*-complementarity problems. The proof of the polynomial complexity of the first method requires the problem to satisfy a scaled Lipschitz condition. When specialized to monotone complementarity problems, the results of the first method are similar to those in Ref 1. The second method is quite different from the first in that the global convergence proof does not require the scaled Lipschitz assumption. However, at each step of this algorithm, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied.

关键词： interior-point algorithms nonlinear P-*-complementarity problems polynomial complexity scaled Lipschitz condition

来源：评论

学校读者我要写书评

暂无评论

Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption

引用

MATHEMATICAL PROGRAMMING 1999年第3期86卷 615-635页

作者： Heinkenschloss, M Ulbrich, M Ulbrich, S Rice Univ Dept Computat & Appl Math Houston TX 77251 USA Tech Univ Munich Zentrum Math D-80290 Munich Germany

A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally q-superlinear or q-quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the solution are satisfied, hut strict complementarity is not required. The methods are modifications of the affine-scaling interior-point Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189-224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.

关键词： bound constraints affine scaling interior-point algorithms superlinear convergence nonlinear programming degeneracy optimality conditions

来源：评论

学校读者我要写书评

暂无评论

On quadratic convergence of the O(√nL)-iteration homogeneous and self-dual linear programming algorithm

引用

ANNALS OF OPERATIONS RESEARCH 1999年 87卷 393-406页

作者： Wu, F Wu, SQ Ye, YY Acad Sinica Inst Appl Math Beijing 100080 Peoples R China Univ Iowa Dept Management Sci Iowa City IA 52242 USA

In this paper, we show that Ye-Todd-Mizuno's O(root nL)-iteration homogeneous and self-dual linear programming (LP) algorithm possesses quadratic convergence of the duality gap to zero. In the case of infeasibility, this shows that a homogenizing variable quadratically converges to zero (which proves that at least one of the primal and dual LP problems is infeasible) and implies that the iterates of the (original) LP variable quadratically diverge. Thus, we have established a complete asymptotic convergence result for interior-point algorithms without any assumption on the LP problem.

关键词： linear programming interior-point algorithms homogeneity self-dual quadratic convergence

来源：评论

学校读者我要写书评

暂无评论

An investigation of interior-point algorithms for the linear transportation problem

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1996年第5期17卷 1202-1223页

作者： Portugal, L Bastos, F Judice, J Paixao, J Terlaky, T UNIV NOVA LISBOA DEPT MATEMATP-2825 MONTE DE CAPARICAPORTUGAL UNIV COIMBRA DEPT MATEMATP-3000 COIMBRAPORTUGAL UNIV LISBON DEPT INFORMATP-1700 LISBONPORTUGAL DELFT UNIV TECHNOL FAC TECH MATH & INFORMATNL-2600 GA DELFTNETHERLANDS

Recently, Resende and Veiga [SIAM J. Optim., 3 (1993), pp. 516-537] proposed an efficient implementation of the dual affine (DA) interior-point algorithm for the solution of Linear transportation models with integer costs and right-hand-side coefficients, This procedure incorporates a preconditioned conjugate gradient (PCG) method for solving the linear system that is required in each iteration of the DA algorithm. In this paper, we introduce an incomplete QR decomposition (IQRD) preconditioning for the PCG algorithm, Computational experience shows that the IQRD preconditioning is appropriate in this instance and is more efficient than the preconditioning introduced by Resende and Veiga. We also show that the primal dual (PD) and the predictor corrector (PC) interior-point algorithms can also be implemented by using the same type of technique. A comparison among these three algorithms is Included and indicates that the PD and PC algorithms are more appropriate for the solution of transportation problems with well-scaled cost and right-hand-side coefficients and assignment problems with poorly scaled cost coefficients. On the other hand, the DA algorithm seems to be more efficient for assignment problems with well-scaled cost coefficients and transportation problems whose cost coefficients are badly scaled.

关键词： linear transportation models interior-point algorithms preconditioned conjugate gradient methods large-scale problems

来源：评论

学校读者我要写书评

暂无评论

Solving large-scale linear programs by interior-point methods under the matlab environment

引用

OPTIMIZATION METHODS & SOFTWARE 1998年第1期10卷 1-31页

作者： Zhang, Y Rice Univ Dept Computat & Appl Math Houston TX 77005 USA

In this paper, we describe our implementation of a primal-dual infeasible-interior-point algorithm for large-scale linear programming under the MATLAB environment. The resulting software is called LIPSOL - Linear-programming interior-point SOLvers. LIPSOL is designed to take the advantages of MATLAB's sparse-matrix functions and external interface facilities, and of existing Fortran sparse Cholesky codes. Under the MATLAB environment, LIPSOL inherits a high degree of simplicity and versatility in comparison to its counterparts in Fortran or C language. More importantly, our extensive computational results demonstrate that LIPSOL also attains an impressive performance comparable with that of efficient Fortran or C codes in solving large-scale problems. In addition, we discuss in detail a technique for overcoming numerical instability in Cholesky factorization at the end-stage of iterations in interior-point algorithms.

关键词： linear programming interior-point algorithms MATLAB LIPSOL

来源：评论

学校读者我要写书评

暂无评论

A trust region method for nonlinear programming based on primal interior-point techniques

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1998年第1期20卷 282-305页

作者： Plantenga, T Sandia Natl Labs Livermore CA 94551 USA

This paper describes a new trust region method for solving large-scale optimization problems with nonlinear equality and inequality constraints. The new algorithm employs interior-point techniques from linear programming, adapting them for more general nonlinear problems. A software implementation based entirely on sparse matrix methods is described. The software handles infeasible start points, identifies the active set of constraints at a solution, and can use second derivative information to solve problems. Numerical results are reported for large and small problems, and a comparison is made with other large-scale optimization codes.

关键词： constrained optimization nonlinear optimization trust region methods interior-point algorithms barrier methods large-scale optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：