优化理论与实践：数值方法详解

4星 · 超过85%的资源需积分: 50 58 浏览量更新于2024-07-19 收藏 4.45MB PDF 举报

"数值优化"是决策科学和工程领域中一个关键工具，它源自微积分变分法和欧拉与拉格朗日的工作。作为数学规划的基础方法，数值优化主要关注有限维问题的解决策略，从基础概念出发，逐渐深入到更复杂的理论和技术。该主题的核心内容包括： 1. 历史渊源：起源于18世纪末的数学分析，尤其是卡尔达诺-费马最小化原理，以及拉格朗日乘数法的引入，这些都是数值优化的早期里程碑。 2. 理论框架：理论方面，它涵盖了梯度下降、牛顿法、拟牛顿法等基本算法，这些方法基于函数的导数信息，通过迭代逼近全局或局部最优解。此外，还有最优化理论，如凸优化、非凸优化、约束优化等，提供了理解和评估优化问题的结构特性。 3. 实践应用：在实际工程问题中，数值优化被广泛应用于诸如信号处理、机器学习、控制系统设计、经济学决策等领域，如参数估计、图像处理、网络路由、生产计划等。 4. 第二版著作："Numerical Optimization: Theoretical and Practical Aspects" 是一本由J.Frédéric Bonnans、J.Charles Gilbert、Claude Lemaréchal和Claudia A. Sagastizábal合著的权威教材，第二版包含52幅图表，深入浅出地介绍了理论和实际操作技巧。书中涵盖了从基础算法到高级优化技术的全面讲解，适合研究人员和工程师使用。 5. 作者介绍：四位作者分别来自法国的Ecole Polytechnique和INRIA，他们的背景涵盖了理论研究和实际应用，确保了内容的严谨性和实用性。Claudia A. Sagastizábal当时是在IMPA（巴西里约热内卢的研究机构）进行访问，表明了这本书在国际学术界的地位。 6. 出版信息：最初由Springer-Verlag出版社于1997年以德语出版的《Numerikale Optimierung》后来被翻译成英文，并在2000年分类为数学主题65K10、90-08、90-01和90CXX，反映出其在数学和工程文献中的重要性。数值优化是一门综合性的学科，涵盖了数学、计算和实际工程问题的交汇点，对理解和解决实际问题具有深远影响。学习和掌握这一领域的知识对于从事工程、科研和数据分析的专业人士来说至关重要。

1 General Introduction

We use the following notation: the working space is R

, where the scalar

product will be denoted indiﬀerently by (x, y)orx, y or x



y (actually, it

will be the usual dot-product: (x, y)=



i=1

); |·|or ·will denote the

associated norm. The gradient (vector of partial derivatives) of a function

f : R

→ R will be denoted by ∇f or f



; the Hessian (matrix of second

derivatives) by ∇

f or f



. We will also use continually the notation g(x)=



(x).

1.1 Generalities on Optimization

1.1.1 The Problem

Given a set X and a function f : X → R (the objective function), we want to

ﬁnd x

∗

∈ X such that, for all x ∈ X, there holds f (x)  f(x

∗

). The variable

x is usually called decision or control variable.

We will consider only the case where X is a subset of R

, deﬁned by

constraints, i.e., given a number m

+ m

of functions c

: R

→ R for

j =1,...,m

+ m

, the problem is

⎧

⎨

⎩

min f(x) x ∈ R

(x)  0 j ∈ I

(x)=0 j ∈ E.

(P )

Here, I and E are two disjoint sets of integers, of cardinalities m

and m

respectively. We thus have m

inequality constraints, indexed in I, and m

equality constraints, indexed in E.

Remark 1.1. We do not consider problems of combinatorial optimization,

where the set X is discrete, or even ﬁnite. They could be covered by our

formalism via constraints of the type x

(1 − x

) = 0 (to express x

∈{0, 1})

but this is very artiﬁcial – and not at all eﬃcient in general. Actually, combi-

natorial optimization problems call for methods totally diﬀerent from those

presented in this book. Their intersection is not totally empty, though: §8.2

will mention the use of continuous optimization to bound the optimal value

in combinatorial problems. Section 1.2.4 will give an illustrative example.

4 1 General Introduction

In another class of problems, the vector-variable x ∈ R

becomes a func-

tion of time x(t),t ∈ [0,T]: these are optimal control problems. They are

close to our formalism, possibly after discretizing [0,T]; in fact, examples are

given in §1.2.2 and 1.2.3.

Perhaps rather paradoxically, the methods in this book extend easily to

optimal control problems, while they ﬁt very badly to combinatorial opti-

mization. 

1.1.2 Classiﬁcation

Among the various possible classiﬁcations, the following is made according

to the diﬃculty of the problem to solve.

1. Unconstrained problems (m

= m

=0,I = E = ∅)

1.1 Quadratic problems: f (x)=

(x, Mx) −(b, x)(M symmetric n ×n)

1.2 Nonlinear problems: f neither linear nor quadratic.

2. Linearly constrained problems (the functions c

are aﬃne)

2.1. Problems with equality constraints only (m

=0,I = ∅)

2.1.1 Linear-quadratic problems: f quadratic

2.1.2 Nonlinear problems: f neither linear nor quadratic

2.2 Problems with inequality constraints

2.2.1 Linear programming: f linear (needs m

 n − m

)

2.2.2 Linear-quadratic problems: f quadratic

2.2.3 Linearly constrained nonlinear problems.

3. Nonlinear programming

3.1 With equality constraints only

3.2 General nonlinear programming.

Observe that

– in optimization, the word “linear” is frequently (mis)used, instead of aﬃne

(see 2; recall that an aﬃne function is the sum of a linear function and a

constant term);

– 2.1 is the minimization in a hyperplane, isomorphic to a subspace of di-

mension n −m

, so that 2.1 is equivalent to 1, at least theoretically;

– 1.1 reduces to solving a linear system (Ax = b – at least if A is positive

deﬁnite); 2.1.1 as well, in view of the preceding remark;

– 2.2 minimizes f in a convex polyhedron, the simplest being a parallelotope,

deﬁned by simple bounds: a

 x

 b

, for i =1,...,n;

– 2.2 is considerably more complicated than 2.1, simply because one does not

know in advance which inequalities will play a role at the optimal point.

Said otherwise, there are 2

ways of putting a problem 2.2 into the form

2.1; the question is: which is the correct one? An inequality constraint is

said to be active at x (not necessarily optimal) when c

(x) = 0. To put 2.2

into the form 2.1, one needs to know which constraints will be active at the

(unknown!) optimum point.

6 1 General Introduction

Other types of energies may also be considered: electrostatic, torsion an-

gles, etc. The total energy is then the sum of all these terms, over all pairs/-

triples/quadruples of atoms. The important thing to understand here, is that

this energy can be computed (as well as its derivatives) for any numerical

values taken by the variables x

. And this is true even if these values do not

correspond to any reasonable conﬁguration; simply, the resulting energy will

then be unreasonably large (if the model is reasonable!); the optimization

process, precisely, will aim at eliminating these values.

This is obviously a problem from category 1.2 in §1.1.2. Note that the

objective function is disagreeable:

– With its many terms, it is long to compute.

– With its strong nonlinearities, it does not enjoy the properties useful for

optimization: it is deﬁnitely not quadratic, and not even convex. Actually,

in most examples there are many equilibrium points X

∗

(local minima);

this is why the only hope is to reﬁne a speciﬁc one: by assumption, some

estimate X

is available, close to the sought “optimal” X

∗

. Otherwise the

optimization algorithm could only ﬁnd some uncontrolled equilibrium, “by

chance”.

Such a problem will call for methods from the ﬁrst part of this book,

more precisely §4.4. Actually, since nowaday’s “interesting” molecules have

atoms and more, this problem is also large-scale; as a result, it will rather

be necessary to use methods from Sections 5.6, 6.3, or also 6.4.

1.2.2 Meteorology

To forecast the weather is to know the state of the atmosphere in the fu-

ture. This is quite possible, at least theoretically (and within limits due to

the chaotic character of phenomena involved). Let p(z,t) be the state of the

atmosphere at point z ∈ R

and time t ∈ [0, 7] (assuming a forecast over one

week, say); p is actually a vector made up of pressure, wind speed, humid-

ity... The evolution of p along time can be modeled: avoiding technicalities,

ﬂuid mechanics tells us that

∂p

∂t

(z,t)=Φ(p(z,t)) , (1.1)

where Φ is a certain diﬀerential operator. For example, (1.1) could be the

Navier-Stokes equation, but approximations are generally introduced.

To forecast the weather once our model Φ is chosen, it “suﬃces” to inte-

grate (1.1). For this, initial conditions are needed (the question of boundary

conditions is neglected here; for example, we shall say that they are peri-

odicity conditions, (1.1) being integrated on the whole earth). Here comes

optimization, in charge of estimating p(·, 0) via an identiﬁcation process,

which we roughly explain.

In fact, the available information also contains all the meteorological ob-

servations collected in the past, say during the preceding day. Let us denote

1.2 Motivation and Examples 7

by Ω = {ω

}

i∈I

these observations. To ﬁx ideas, we could say that each ω

represents the value of p at a certain point (z

) (but actually, only some

coordinates of the vector p(z

) are observed). To take these – noisy – data

into account, a natural and well-known idea is to consider the problem

min

p −Ω, (1.2)

(1.1) being considered as a constraint (called in this context the state equa-

tion).

– Observe here that our optimization problem is not posed with respect to

some x ∈ R

but to p, varying in a functional, inﬁnite-dimensional, space.

See Remark 1.1; we are dealing with an optimal control problem. Notwith-

standing, any numerical implementation implies ﬁrst a discretization, which

reduces the problem to the framework of this book.

– Note also that (1.1) is a priori valid on the whole interval [−1, +7], but

(1.2) concerns [−1, 0] only. Actually, optimization just deals with this latter

interval; it is only for the forecast itself, after optimization is ﬁnished, that

the interval [0, 7] will come into play.

– Since p and Ω do not live in the same space (the number |I| of observations,

possibly very large, is certainly ﬁnite), Ω must ﬁrst be embedded in the

same function space as p. Besides, the norm ·in (1.2) must be carefully

chosen. These aspects, which concern modeling only, have a big inﬂuence

on the behaviour of solution algorithms.

At this point, it is a good idea not to view (1.1), (1.2) as a nonlinearly

constrained optimization problem (category 3.2 in §1.1.2), but rather as an

unconstrained one (category 1.2). In fact, call u(z)=p(z,−1) the state of

the atmosphere at z, at initial time t = −1. A fundamental remark is then:

assuming u to be known, (1.1) gives unambiguously p(z, t)=p

(z,t) for all

z and all t  −1: the unknown p

depends on the variable u only. Hence, the

objective value in (1.2) also depends on u only. Our problem can therefore

be formulated as min

p

− Ω, which means:

– to minimize with respect to u (unconstrained variable)

– the function deﬁned by (1.2),

– where p = p

is obtained from (1.1)

– via the initial condition p(·, −1) = u.

The actual decision variable in this formulation is u indeed: p plays only

the role of a parameter, called state variable, while the terminology control

variable is here reserved to u. The objective function will be denoted by

J(u), rather than f(x). Thus, the number of variables is reduced (drastically:

passing from about 10

for p, to about 10

for u alone) and, more importantly,

any form of constraint is eliminated.

Remark 1.2. The “normal”, direct , problem is to compute p(z,t) from

p(z,0) via (1.1). Here we solve the inverse problem: to compute p(z,0) from

(a partial knowledge of) p(z, t).

剩余491页未读，继续阅读

拜托了，2020年2月

粉丝: 0
资源: 1

优化理论与实践：数值方法详解

Numerical Optimization_2nd E

numerical-optimization:数值优化课程代码

Numerical Optimization (Second Edition)

Numerical Optimization

Numerical optimization

Numerical Optimization 2nd

Numerical Optimization 数值优化

Numerical optimization-bonnas

numerical optimization习题答案

numerical optimization课后答案

最新资源