interiorpointmethod资源-CSDN文库

5星 · 超过95%的资源需积分: 10 56 浏览量 2011-03-27 11:00:44 上传评论 1 收藏 244KB PDF 举报

The design and implementation of a new algorithm for solving large nonlinear programming problems is described. It follows a barrier approach that employs sequential quadratic programming and trust regions to solve the subproblems occurring in the iteration. Both primal and primal-dual versions of the algorithm are developed, and their performance is illustrated in a set of numerical tests. ### 内点法在大规模非线性规划中的应用 #### 概述本文介绍了一种新的算法设计与实现，该算法旨在解决大规模非线性规划问题。算法采用障碍方法（Barrier Method），结合了序列二次规划（Sequential Quadratic Programming, SQP）与信赖域方法（Trust Region Method）来求解迭代过程中的子问题。此外，文中还开发了原问题和原对偶版本的算法，并通过一系列数值测试展示了它们的表现。 #### 关键技术与方法 **1. 障碍方法（Barrier Method）** 障碍方法是一种解决约束优化问题的有效途径，尤其适用于处理不等式约束。该方法的核心思想是将约束条件转化为目标函数的一部分，通过引入一个称为“障碍函数”的附加项来惩罚违反约束的行为。随着迭代进行，障碍参数逐渐减小，最终逼近原始问题的最优解。 **2. 序列二次规划（SQP）** 序列二次规划是一种广泛应用于解决非线性优化问题的技术。它通过构建一个局部的二次近似模型来逐步逼近全局最优解。在每一步迭代中，SQP算法都会基于当前点的一阶和二阶导数信息构建一个二次规划问题，并求解该子问题以确定搜索方向。这种方法的优点在于能够高效地处理非线性和约束问题，同时保持较好的收敛性能。 **3. 信赖域方法（Trust Region Method）** 信赖域方法是一种全局优化策略，用于控制每次迭代中的步长，以确保算法的稳定性。它通过定义一个“信赖域”来限制每一步迭代的最大步长，从而避免因步长过大而导致的数值不稳定。与传统的线搜索方法相比，信赖域方法在处理大规模非线性问题时更加稳定可靠。 **4. 原问题与原对偶算法** 文中提到开发了原问题和原对偶版本的算法。原问题是指直接针对原始优化问题进行求解的方法；而原对偶算法则是通过求解原问题的对偶问题来间接找到原问题的解。原对偶算法可以提供更强的理论保证，并且在某些情况下能够更有效地利用问题结构，提高计算效率。 #### 实验结果与分析文中通过一系列数值测试来评估所提出的算法性能。这些测试不仅验证了算法的有效性，还展示了其在处理大规模非线性规划问题时的优越性。具体来说，实验结果表明，无论是原问题版本还是原对偶版本的算法，在处理大规模、复杂度高的非线性规划问题时均表现出了良好的收敛性和稳定性。 #### 结论本文提出的一种结合障碍方法、SQP和信赖域技术的内点算法为解决大规模非线性规划问题提供了一个强有力的工具。该算法不仅能有效处理非凸问题，还能在变量数量较大的情况下表现出色。通过开发原问题和原对偶版本的算法，并结合数值测试的结果，证明了这一方法在实际应用中的可行性和优势。对于那些需要高效解决复杂非线性规划问题的应用领域而言，该算法无疑是一个重要的进展。

资源推荐

资源详情

资源评论

An Interior Point Algorithm for Large Scale Nonlinear

Programming

∗

Richard H. Byrd

†

Mary E. Hribar

‡

Jorge Nocedal

December 15, 1998

Abstract

The design and implementation of a new algorithm for solving large nonlinear pro-

gramming problems is described. It follows a barrier approach that employs sequential

quadratic programming and trust regions to solve the subproblems occurring in the

iteration. Both primal and primal-dual versions of the algorithm are developed, and

their performance is illustrated in a set of numerical tests.

Key words: constrained optimization, interior point method, large-scale optimization, non-

linear programming, primal method, primal-dual method, sequential quadratic program-

ming, barrier method, trust region method.

∗

Original manuscript: July 27, 1997.

†

Computer Science Department, University of Colorado, Boulder CO 80309. This author was supported

by ARO grant DAAH04-94-0228, and AFOSR grant F49620-94-1-0101.

‡

CAAM Department, Rice University, Houston TX 77005. This author was supported by Department of

Energy grant DE-FG02-87ER25047-A004.

ECE Department, Northwestern University, Evanston Il 60208. This author was supported by National

Science Foundation grant CCR-9625613 and by Department of Energy grant DE-FG02-87ER25047-A004.

1. Introduction

In this paper we discuss the design, implementation and performance of an interior point

method for solving the nonlinearly constrained optimization problem

min f(x)

subject to h(x) = 0

g(x) ≤ 0, (1.1)

where f : R

→ R, h : R

→ R

, and g : R

→ R

are smo oth f unctions. We are

particularly interested in the case when (1.1) is not a convex program and when the number

of variables n is large. We assume in this paper that ﬁrst and second derivatives of the

objective f unction and constraints are available, bu t our strategy can be extended so as to

make use of quasi-Newton appr oximations.

Interior point methods p rovide an alternative to active set methods for the treatment

of inequality constraints. Our algorithm, which is based on the framework proposed by

Byrd, Gilbert and Nocedal [7], incorporates within the interior p oint method two powerful

tools for solving nonlinear problems: sequential qu adratic programming and trust region

techniques. Sequential quadratic programming (SQP) ideas are used to eﬃciently handle

nonlinearities in the constraints. Trust region strategies allow the algorithm to treat convex

and non-convex problems uniformly, permit the direct use of second derivative information

and provide a safeguard in the presence of nearly d ependent constraint gradients.

Of crucial importance in the new algorithm is the formulation and solution of the equality

constrained barrier subproblems that determine the steps of the algorithm. The formulation

of the subproblems gives the iteration primal or primal-dual characteristics, and ensures that

the slack variables remain safely positive. The technique used to solve the subproblems has

a great impact on the eﬃciency and robustness of the algorithm; we use an adaptation of

the trust region method of Byrd and Omojokun [6, 34] which has proved to be eﬀective for

solving large equality constrained problems [31].

Our numerical results suggest that the new algorithm holds much promise: it appears

to be robust and eﬃcient (in terms of function evaluations), and can make eﬀective use of

second derivative information. The test results also indicate that the primal-dual version of

the algorithm is superior to the primal version. The new algorithm has a solid theoretical

foundation, since it follows the principles of the globally convergent primal method devel-

oped in [7]. In particular, the approximate solution strategies for the subproblems solved

by our algorithm are chosen to satisfy the explicit conditions f or global convergence stated

in that paper.

There has been much research in using interior point methods for nonlinear program-

ming; most of it concerns line search methods. The special case when the problem is a

convex program can be handled by line search methods that are direct extensions of interior

point methods for linear programming (see e.g. [1]). In the convex case, the step generated

by the solution of the primal-dual equations can be shown to be a d escent direction for

several merit functions, and this allows one to establish global convergence results. Other

research [19, 44] has focused on the local behavior of interior point line search methods

for nonlinear programming. Conditions have been given that guarantee superlinear and

quadratic rates of convergence. These algorithms can also be viewed as a direct extension

of linear programming methods, in that they do not make provisions for the case when the

problems is non-convex.

Several line search algorithms designed for non-convex problems have r ecently been

proposed [43, 22, 15, 23, 2, 35]. An important feature of many of these methods is a

strategy for modifying the KKT system used in the computation of the search direction.

This modiﬁcation, which is usually based on a matrix factorization algorithm, ensures that

the search direction is a descent direction for the merit function. This is an approaches

are interesting, but there is not yet enough experience to fully evaluate their eﬃcacy in

general-purpose codes.

The use of trust region strategies in interior point methods for linear and nonlinear

problems is not new [5, 33]. C oleman and Li [13, 14] proposed a primal method for bound

constrained nonlinear optimization; see also [18]. Plantenga [36] developed an algorithm for

general nonlinear pr ogramming that has some features in common with our algorithm; the

main diﬀerences lie in his treatment of the trust region, in the purely primal nature of his

step, and in the fact that his algorithm reverts to an active set method near the solution.

The algorithm proposed in this paper makes use of sequential quadratic programming

techniques [3, 21, 24, 25], and in this sense is related to the line search algorithm of Ya-

mashita [43]. But the way in which our algorithm combines trust region strategies, interior

point approaches and sequential quadratic programming techniques leads to an iteration

that is diﬀerent from those proposed in the literature.

2. The New Algorithm

The algorithm is a barrier method in which the subproblems are solved approximately

by an SQP iteration with tru st regions. Each barrier subproblem is of the form

min

x,s

f(x) − µ

i=1

ln s

subject to h(x) = 0 (2.1)

g(x) + s = 0,

where µ > 0 is the barrier parameter and where the slack variable s is assumed to be

positive. By letting µ converge to zero, the sequence of solutions to (2.1) should normally

converge to a stationary point of the original nonlinear program (1.1). As in some interior

point methods for linear programming [42], our algorithm does not require feasibility of the

iterates with respect to the inequality constraints in (1.1), but only forces the slack variables

in (2.1) to r emain positive.

To characterize the solution of the barrier problem (2.1) we introd uce its Lagrangian,

L(x, s, λ

, λ

) = f (x) − µ

i=1

ln s

+ λ

h(x) + λ

(g(x) + s), (2.2)

where λ

and λ

are the Lagrange multipliers. Rather than solving each barrier sub-

problem (2.1) accurately, we will be content with an approximate solution (ˆx, ˆs) satisfying

E(ˆx, ˆs; µ) ≤ ǫ

, where E measures the optimality conditions of the barrier problem and is

deﬁned by

E(x, s; µ) = max (k∇f(x) + A

(x)λ

+ A

(x)λ

∞

, kSλ

− µek

∞

, kh(x)k

∞

kg(x) + sk

∞

) . (2.3)

Here e = [1, ..., 1]

, S = diag(s

, ..., s

), with superscripts indicating components of a

vector, and

(x) = [∇h

(x), . . . , ∇h

(x)], A

(x) = [∇g

(x), . . . , ∇g

(x)]

are the matrices of constraint gradients. Throughout the paper we will assume that A

has full column rank. In the deﬁnition of the optimality measure E, the vectors λ

, λ

are

least squares multiplier estimates (to be discussed later), and thus are functions of x, s and

µ. We will show later (see (3.7)-(3.10)) that the terms in (2.3) corresp ond to each of the

equations of the so-called p erturbed KKT system upon which our primal-dual algorithm

is based. The tolerance ǫ

, which determines the accuracy in the solution of the b arrier

problems, is decreased from one barrier problem to the next, and must converge to zero. In

this paper we will use the simple strategy of reducing both ǫ

and µ by a constant factor

θ ∈ (0, 1). We test for optimality for the nonlinear program (1.1) by means of E(x, s; 0).

Algorithm I: Barrier Algorithm for S olving the Nonlinear Problem (1.1)

Choose an initial value for the barrier parameter µ > 0, and select the parame-

ters ǫ

> 0, θ ∈ (0, 1), and the ﬁnal stop tolerance ǫ

TOL

. Choose the starting

point x and s > 0, and evaluate the objective function, constraints, and their

derivatives at x.

Repeat until E(x, s; 0) ≤ ǫ

TOL

1. Apply an SQP method with trust regions, starting from (x, s),

to ﬁnd an approximate solution (x

, s

) of the barrier

problem (2.1) satisfying E(x

, s

; µ) ≤ ǫ

2. Set µ ← θµ, ǫ

← θǫ

, x ← x

, s ← s

end

To obtain a rapidly convergent algorithm, it is n ecessary to carefully control the rate

at wh ich the barrier parameter µ and the convergence tolerance ǫ

are decreased [19, 44].

This question has been studied, in the context of our algorithm, in [8].

Most of the work of Algorithm I lies clearly in step 1, in the approximate solution of

an equality constrained problem with an implicit lower bound on the slack variables. The

challenge is to perform this step eﬃciently, even when µ is small, while forcing the slack

variables to remain p ositive. To do this we apply an adaptation of the equality constrained

SQP iteration with trust regions proposed by Byrd [6] and Omojokun [34] and developed

by Lalee, Nocedal and Plantenga [31] for large-scale equality constrained optimization. We

follow an SQP approach because, in our view, it is eﬀective for solving equality constrained

problems, even w hen the problem is ill-conditioned and the constraints are highly nonlinear

(see also [3, 25, 21, 24]), and choose to use trust region strategies to globalize the SQP

iteration because they facilitate the use of second d erivative information when the problem

is non-convex.

However, our numerical experience shows that a straightforward application of this SQP

method to the barrier problem leads to ineﬃcient steps that tend to violate the positivity

of the slack variables, and that are thus frequently cut short by the trust region constraint.

The novelty of our approach lies in the formulation of the quadratic model in the SQP

iteration and in the deﬁnition of the (scaled) trust region. These are designed so as to

produce steps that have some of the properties of primal-dual iterations and that avoid

approaching the bound ary of the feasible region too soon.

In order to describe our approach more p recisely, it is instructive to brieﬂy review the

basic principles of Sequential Quadratic Programming for equality constrained optimization

with trust regions [3, 9, 10, 31, 40]. Every iteration of such an SQP method begins by

constructing a quadratic mo del of the Lagrangian function. A step d of the algorithm is

computed by minimizing the quadratic model, subject to satisfying a linear approximation

to the constraints, and subject to a trust region bound on this step. If the step d gives a

suﬃcient reduction in the chosen merit function, then it is accepted; otherwise the step is

rejected, the trust region is reduced and a new step is computed.

Let us apply these ideas to the barrier problem (2.1), in order to compute a step d =

, d

) from the current iterate (x

, s

). To economize space we will often write vectors

with x and s-components as

= (d

, d

After computing Lagrange multiplier estimates (λ

, λ

), we formulate the subproblem

min

∇f(x

)

∇

L(x

, s

, λ

− µe

−1

(2.4)

subject to A

)

+ h(x

) = r

(2.5)

)

+ d

+ g(x

) + s

= r

(2.6)

, d

) ∈ T

. (2.7)

Here Σ

is an m × m positive deﬁnite diagonal matrix that represents either the Hessian

of the Lagrangian (2.2) with respect to s or an approximation to it. As we will see in the

next section, the choice of Σ

is of crucial importance because it determines whether the

iteration has pr imal or primal-dual characteristics. Ideally, we would like our step to satisfy

(2.5)-(2.6) with r = (r

, r

) = 0, i.e. to satisfy the linearized constraints. However, this

may may be inconsistent with (2.7), so we choose the residual vector r to be the smallest

vector such that (2.5)-(2.7) are consistent (with some margin). This computation is done by

solving the preliminary subproblem in which we compute the normal step, described in §3.2.

The closed and bounded set T

deﬁnes the region around x

where the quadratic mo del

剩余28页未读，继续阅读

评论收藏

内容反馈

wujian6029

2012-11-08

英文的，还是稍微有点麻烦！
p007300

2012-11-11

关于内点法的一个新算法, 用于解决大型非线性规划问题
michelyang1990

2012-11-22

挺好的，要是有外点发更好了

godspeed13

粉丝: 0
资源: 2

interior point method

Ipopt (Interior Point OPTimizer, pronounced eye-pea-Opt) is

ArchVizPRO Interior Vol.4.txt

ArchVizPRO Interior Vol4.txt

Unity3D ArchVizPRO Interior Vol.01 - Vol.06 合集

ArchVizPRO Interior Vol.1.txt

ArchVizPRO Interior Vol.6.txt

Optimization.rar_interior point_乘子法_乘子法程序_内点_外点法

A superlinearly convergent wide-neighborhood predictor-corrector interior- point algorithm for linear programming

a primal-dual interior-point method for conic quadratic optimization.pdf

Primal-dual interior point method ppt

A new polynomial-time interior-point algorithms for the Cartesian $P_*(kappa)$-SCLCP

On the Complexity of a Combined Homotopy Interior Point Method for Convex Programming

golden_Interior-Point-Method.rar_interior point_interior-point_内

A Homotopy Interior Point Method for Nonlinear Complementarity Problems (1995年)

interior_newton.zip_interior point_interior-point_newton

控制分配工具箱，QCAT工具箱，matlab程序

neidian.rar_interior point_powell_内惩罚函数法_机械优化设计_罚函数法

toy_interior_point_solver：用Lua编写的Toy Interior Point求解器

Composite Mid-point method for numeric integration：数值积分的一些数值计算和分析练习。-matlab开发

Design of a grating by a joint optimization method for a phase-shifting point diffraction interferometer

Interior point methods for linear optimization

线性规划讲义.zip

最优化理论与算法最优化理论与算法.pdf

Interiorpointmethod.rar_内点对偶法_内点法潮流_原对偶内点法求解电力系统最优潮流_对偶内点法_电力系统

Exploiting the point spread function for optical imaging through a scattering medium based on deconvolution method

Material point method and smoothed particle hydrodynamics

最新资源