伯特塞卡斯的约束优化与拉格朗日乘子方法详析

需积分: 45 43 浏览量更新于2024-07-23 收藏 11.88MB PDF 举报

《受限优化与拉格朗日乘子方法》是由麻省理工学院的知名学者Dimitri P. Bertsekas所撰写的一本权威著作。这本书是探讨约束优化理论的深度之作，特别是在处理带有约束条件的优化问题时，拉格朗日乘子法的应用被详尽地剖析。作为数学优化领域的经典参考书，它不仅提供了深入的理论分析，还包含了大量的实用案例和解题策略。拉格朗日乘子法是一种解决多变量优化问题的有效工具，特别适用于那些在满足某些限制条件下的最优化问题。该方法的核心思想是引入一个额外的函数，即拉格朗日函数，它将原始目标函数和约束条件结合在一起，通过求解这个新函数的极值来找到原问题的最优解。这种方法有助于简化问题，因为求解拉格朗日函数的局部极值通常比直接处理约束优化问题更为直接。 Bertsekas的这本书详细讲解了如何构建拉格朗日函数，如何求解拉格朗日方程，以及如何利用这些工具来求解线性、非线性和凸优化问题。此外，书中还涵盖了梯度下降法、牛顿法等优化算法在有约束情况下的应用，并讨论了KKT条件（Karush-Kuhn-Tucker条件），这是判断解是否为可行解和全局最优解的关键判据。除了理论部分，书中也提供了丰富的实例和习题，帮助读者理解和掌握理论知识，并将其应用到实际问题中。对于希望深入理解优化理论并提高解决实际工程问题能力的读者来说，这是一本不可多得的教材和参考资料。《受限优化与拉格朗日乘子方法》不仅适合研究生、工程师和科研人员，也是教师进行教学的优质辅助材料。作者Dimitri Bertsekas本人在机械和电气工程领域有着深厚背景，他的学术贡献使得本书成为优化理论研究和实践中的重要里程碑。这本书是所有从事或对数学优化、特别是拉格朗日乘子法感兴趣的专业人士必备的参考书籍，它提供了严谨的理论支持和实用的技巧，对于提升读者在面对复杂优化问题时的分析和解决问题的能力具有显著的价值。

Chapter

Introduction

1.1

General

Remarks

Two classical nonlinear programming problems are the equality con-

strained problem

(ECP)

minimize

(x)

subject to

h(x)

and its inequality constrained version

(IcP)

minimize

(x)

subject to

g(x)

where$

Rm,

-t

are given functions. Computational

methods for solving these problems became the subject of intensive investiga-

tion during the late fifties and early sixties. We discuss three of the approaches

that were pursued.

The first approach was based on the idea of iterative descent within

the confines of the constraint set. Given a feasible point

x,,

a direction

was chosen satisfying the descent condition

(xk)'dk

and the condition

INTRODUCTION

ad,

feasible for all

positive and sufficiently small.

search along the

line {x,

ad,

produced a new feasible point x,,

x,d,

satisfying

(x,,

(x,). This led to various classes of feasible direction

methods with which the names of Frank-Wolfe, Zoutendijk, Rosen, Goldstein,

and Levitin-Poljak are commonly associated. These methods, together with

their more sophisticated versions, enjoyed considerable success and still

continue to be very popular for problems with linear constraints. On the

other hand, feasible direction methods by their very nature were unable to

handle problems with nonlinear

equality constraints, and some of them

were inapplicable or otherwise not well suited for handling nonlinear

inequality constraints as well.

number of modifications were proposed for

treating nonlinear equality constraints, but these involved considerable

complexity and detracted substantially from the appeal of the descent idea.

second approach was based on the possibility of solving the system of

equations and (possibly) inequalities which constitute necessary conditions

for optimality for the optimization problem. For (ECP), these conditions are

(la)

V,L(x, A)

Vf (x)

Vh(x)A

(lb)

V, L(x, A)

h(x)

where L is the (ordinary) Lagrangian function

L(x, A)

(x)

A1h(x).

distinguishing feature of this approach is that the Lagrange multiplier

is treated on an equal basis with the vector x. Iterations are carried out

simultaneously on x and

by contrast with the descent approach where

only x is iterated upon and the Lagrange multiplier plays no direct role.

For this reason algorithms of this type are sometimes called Lagrangian

methods. Several methods of this type were considered in Arrow et al. (1958).

In addition to Newton's method for solving system

(I),

a gradient method

was also proposed under the condition that the local concexity assumption

(2)

V:, L(x*, A*)

holds at a solution (x*,

A*).

It was noted, however, by Arrow and Solow

(1958) that if the local convexity assumption did not hold, then (ECP) could

be replaced by the equivalent problem

(3)

minimize

(x)

h(x)

subject to h(x)

where c is a scalar and

1.1

denotes Euclidean norm. If c is taken sufficiently

large, then the local convexity condition can be shown to hold for problem

(3)

under fairly mild conditions. The idea of focusing attention on the necessary

1.1

GENERAL REMARKS

conditions rather than the original problem also attracted considerable

attention in optimal control where the necessary conditions can often be

formulated as a two-point boundary value problem. However, it quickly

became evident that the approach had some fundamental limitations,

mainly the lack of a good mechanism to enforce convergence when far from a

solution, and the difficulty of some of the methods to distinguish between

local minima and local maxima.

third approach was based on elimination of constraints through the

use of penalty functions. For example the quadratic penalty function method

(Fiacco and McCormick,

1968)

for (ECP) consists of sequential uncon-

strained minimization of the form

minimize

(x)

tc,

h(x)

subject to x

R",

where {c,) is a positive scalar sequence with c,

ck+

for all

and c,

ccj.

The sequential minimization process yields

(5)

lim inf

{

(x)

Sc,

h(x)

12).

cr+m

xeRn

On the other hand, the optimal value of (ECP) can be written as

inf lim (f

(x)

tc,

h(x) 12),

xeRn

cr-m

and hence the success of the penalty method hinges on the equality of the

expressions

(5)

and

(6),

i.e., the validity of interchanging "lim" and "inf."

This interchange is indeed valid under mild assumptions (basically con-

tinuity off and h-see Chapter

2).

Lagrange multipliers play no direct role

in this method but it can be shown under rather mild assumptions that the

sequence

{ckh(x,)), where x, solves problem (4), converges to a Lagrange

multiplier of the problem. Despite their considerable disadvantages [mainly

slow convergence and ill-conditioning when solving problem (4) for large

values of c,], penalty methods were widely accepted in practice. The reasons

can be traced to the simplicity of the approach, its ability to handle nonlinear

constraints, as well as the availability of very powerful unconstrained

minimization methods for solving problem (4).

The main idea of the descent approach also made its appearance in a

dual context whereby an ascent method is used to maximize the dual func-

tional for (ECP) given by

d(A)

inf{

(x)

?,'h(x))

inf L(x,

A).

X X

INTRODUCTION

In the simplest such method one minimizes L(., A,) (perhaps in a local

sense) over x for a sequence of multiplier vectors (A,). This sequence is

generated by

(7)

Ak+

where x, is a minimizing point of L(., A,) and

is a stepsize scalar parameter.

It is possible to show under the appropriate assumptions (see Section 2.6)

that h(xk)

Vd(;ik), so

(7)

is actually a steepest ascent iteration for maxi-

mizing the dual functional d. Such methods have been called primal-dual

methods. Actually the dual functional and the method itself make sense only

under fairly restrictive conditions including either the local convexity

assumption

(2)

or other types of convexity conditions. The method is also

often hampered by slow convergence. Furthermore in many cases it is diffi-

cult to know a priori an appropriate range for the stepsize

For this reason

primal-dual methods of the type just described initially found application

only in the limited class of convex or locally convex problems where mini-

mization of

L(.,

A,) can be carried out very efficiently due to special structure

involving, for example, separable objective and constraint functions (Everett,

1963).

Starting around 1968, a number of researchers have proposed a new

class of methods, called methods of multipliers, in which the penalty idea is

merged with the primal-dual and Lagrangian philosophy. In the original

method of multipliers, proposed by Hestenes (1969) and Powell

(1969), the

quadratic penalty term is added not to the objective function

of (ECP)

but rather to the Lagrangian function L

L'h thus forming the aug-

mented Lagrangian function

(8)

Lc(x,

(x)

;ilh(x)

4cI h(x) 12.

A sequence of minimizations of the form

(9) minimize Lc,(x,

A,)

subject to x

is performed where {c,) is a sequence of positive penalty parameters. The

multiplier sequence {A,) is generated by the iteration

where x, is a solution of problem (9). The initial vector

is selected a priori,

and the sequence {c,} may be either preselected or generated during the

computation according to some scheme.

One may view the method just described within the context of penalty

function methods. If

-x,

and the generated sequence

{A,}

turns out to

1.1

GENERAL

REMARKS

be bounded, then the method is guaranteed to yield in the limit the optimal

value of (ECP), provided sufficient assumptions are satisfied which guarantee

the validity of interchange of "lim" and "inf

in the expression

lim

inf{f(x)

&h(x)

4ckjh(x)I2),

Ck+CO

similarly as for the penalty method considered earlier.

Another point of view (see Chapter

is based on the fact that iteration

(10)

is a steepest ascent iteration for maximizing the dual functional

dc,(A)

inf

{

f (x)

Xh(x)

ick

h(x)

12),

which corresponds to the problem

minimize

(x)

4ck

h(x)

subject to

h(x)

As noted earlier, if

is sufficiently large, this problem has locally convex

structure, so the primal-dual viewpoint is applicable.

It turns out that, by combining features of the penalty and the primal-

dual approach, the method of multipliers actually moderates the dis-

advantages of both. As we shall see in the next chapter, convergence in

the method of multipliers can usually be attained

without the need to increase

ck to injnity

thereby alleviating the ill-conditioning problem that plagues

the penalty method. In addition

the multiplier iteration (10) tends to converge

Lagrange multiplier vector much faster than iteration

(7)

of the primal-

dual method, or the sequence {ckh(x,)) in the penalty method.

Because of these

attractive characteristics, the method of multipliers and its subsequently

developed variations have emerged as a very important class of constrained

minimization methods.

great deal of research has been directed toward

their analysis and understanding. Furthermore their discovery provided

impetus for reexamination of Lagrangian methods proposed and nearly

abandoned many years ago. These efforts aided by fresh ideas based on

penalty functions and duality have resulted in a variety ofinteresting methods

utilizing

Lagrange multiplier iterations and competing with each other for

solution of different classes of problems.

The purpose of this monograph is to provide a rather thorough analysis

of these

Lagrange multiplier methods starting with the quadratic method of

multipliers for (ECP) just described. This method is the subject of Chapter

In Chapter

the method is extended to handle problems with both equality

and inequality constraints. In addition the Lagrange multiplier approach is

utilized to construct algorithms for solution of nondifferentiable and minimax

problems. In Chapter

we consider a variety of Lagrangian methods and

剩余410页未读，继续阅读

stief_xw

粉丝: 0
资源: 1

伯特塞卡斯的约束优化与拉格朗日乘子方法详析

constrained optimization and lagrange multiplier methods.djvu

*constrained_lagrange_in_solid

粒子群算法添加约束条件相关的论文有哪些？

拉格朗日乘数法matlab代码

composite differential evolution for constrained evolutionary optimization.

最新的元启发式优化算法有哪些

maple 解决双摆问题的程序

如何利用matlab、

拉格朗日松弛算法代码matlab

外点罚函数法matlab程序

最新资源