约束优化与拉格朗日乘子法深入解析

5星 · 超过95%的资源需积分: 45 8 浏览量更新于2024-07-23 2 收藏 11.88MB PDF 举报

"Constrained Optimization and Lagrange Multiplier Methods" 是一本由 Dimitri P. Bertsekas 编著的关于约束优化的教材，作者是麻省理工学院的研究者。该书在1982年由 Academic Press, Inc. 首次出版，后由 Athena Scientific 再版。它详细探讨了利用拉格朗日乘数法解决约束优化问题的方法。在约束优化领域，我们通常面临的问题是在满足特定条件（即约束）的同时寻找函数的最大值或最小值。这本书深入讲解了如何运用数学工具来处理这类问题。拉格朗日乘数法是一种强大的数学技术，它通过引入拉格朗日乘数将原问题转化为无约束优化问题，从而简化求解过程。书中可能涵盖了以下几个关键知识点： 1. **拉格朗日函数**：拉格朗日乘数法的核心是构建拉格朗日函数，它是原始目标函数与所有约束的线性组合，每个约束项前都有一个对应的拉格朗日乘数。通过求解这个新的函数的极值，我们可以找到同时满足约束和目标函数的最优解。 2. **Karush-Kuhn-Tucker (KKT) 条件**：这是约束优化问题的一个必要条件，指出了在局部最优解处，拉格朗日函数的梯度、约束函数的梯度以及拉格朗日乘数之间必须满足的关系。这些条件是求解约束优化问题的重要基础。 3. **线性规划与非线性规划**：书中可能详细讨论了在约束优化问题中，目标函数和约束条件为线性或非线性时的处理方法。线性规划通常有更高效的算法，如单纯形法；而非线性规划则需要更复杂的数值方法。 4. **二次规划**：在约束优化中，二次函数作为目标函数的情况很常见，因为它们具有解析解的特殊性质。书中可能介绍了如何处理这类问题，包括配方法和内点法等。 5. **动态规划**：作为优化领域的经典方法，动态规划在解决多阶段决策问题时特别有用，尤其是在约束条件下。书中的这一部分可能会讲述如何应用动态规划来解决约束优化问题。 6. **连续优化与离散优化**：书中可能区分了连续变量和离散变量在约束优化中的处理方式，离散优化通常更加复杂，可能涉及搜索算法和启发式方法。 7. **数值方法与算法**：在实际问题中，往往需要使用数值方法来逼近最优解，例如梯度下降法、牛顿法、拟牛顿法等。这些方法的实现和收敛性分析也是书中可能涵盖的内容。 8. **实例与应用**：为了使理论更具实践意义，书中很可能包含各种工程、经济、管理等领域中的约束优化实例，帮助读者理解并掌握所学方法。此外，书籍通常会提供详细的文献参考和索引，方便读者进一步研究相关主题。对于希望深入学习约束优化和拉格朗日乘数法的人来说，这本教材是一个宝贵的资源。

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页未读，继续阅读

markbluesky

粉丝: 1

约束优化与拉格朗日乘子法深入解析

MIT Athena Scientific出版丛书：信息技术领域必读书籍

"基于环邻域拓扑的约束优化改进模因算法研究

"杨振华南邮最优化方法课件2021：线性规划与约束问题概述

constrained optimization and lagrange multiplier methods.djvu

Practical Methods of Optimization Vol2 (Constrained Optimization)

MATLAB Constrained Optimization: A Dual Strategy of Algorithms and Practices

【fmincon Optimization Algorithm: Mastering the Principles, Parameters, and Applications in 10 Steps...

ode45 Solving Differential Equations: The Insider's Guide to Decision Making and Optimization, ...

Nonlinear Optimization Algorithms: A MATLAB Practical Guide

Solving Differential Equations with ode45: A Powerful Tool in Optimization Theory, Addressing 5 ...

最新资源