线性与非线性编程：优化方法探索

5星 · 超过95%的资源需积分: 12 41 浏览量更新于2024-07-24 收藏 4.94MB PDF 举报

"《Linear and Nonlinear Programming》是由David G. Luenberger和Yinyu Ye合著的一本书，属于国际运筹学与管理科学系列。这本书深入探讨了线性与非线性优化领域的理论与应用。" 在优化领域，线性编程（Linear Programming, LP）和非线性编程（Nonlinear Programming, NLP）是两种核心方法。线性编程主要处理目标函数和约束条件都是线性的问题，其解决方案可以通过图解法、单纯形法或者内点法等有效算法求得。线性规划广泛应用于生产计划、资源配置、运输问题等领域，其中单纯形法是解决线性规划问题的经典方法，由George Dantzig于1947年提出，它保证了找到全局最优解。非线性编程则涉及到更复杂的优化问题，目标函数或约束条件至少有一个是非线性的。这导致了可能的局部最优解，使得寻找全局最优解更具挑战性。解决非线性规划问题的方法包括梯度法、牛顿法、拟牛顿法、遗传算法、模拟退火法等。非线性优化在工程设计、经济规划、机器学习等诸多领域有广泛应用。《Linear and Nonlinear Programming》这本书可能涵盖了以下主题： 1. 线性规划的基本概念和理论：包括定义、标准形式、可行域、最优解的性质等。 2. 单纯形法和内点法的详细解释及其在实际问题中的应用。 3. 非线性规划的数学基础：如连续可微性、凸性、约束条件的处理等。 4. 非线性优化算法：梯度下降法、牛顿法、拟牛顿法等的描述和实现细节。 5. 全局优化策略：如何处理多极点和局部最优解，如全局收敛性分析。 6. 应用案例：在运营管理、工程设计、财务规划等方面的实际问题分析。 7. 数值稳定性与计算效率：讨论算法在大规模问题中的表现和优化。 8. 随机优化和随机过程：在不确定环境下如何进行优化决策，可能包括随机变量、随机过程和概率论的相关知识。通过阅读这本书，读者可以系统地学习线性和非线性优化的基本理论，掌握解决实际问题的工具和方法，同时对优化理论的发展和前沿有深入理解。对于运筹学家、管理科学家以及需要用到优化技术的工程师来说，这本书是一个宝贵的参考资料。

2 Chapter 1 Introduction

This book is centered around a certain optimization structure—that character-

istic of linear and nonlinear programming. Examples of situations leading to this

structure are sprinkled throughout the book, and these examples should help to

indicate how practical problems can be often fruitfully structured in this form. The

book mainly, however, is concerned with the development, analysis, and comparison

of algorithms for solving general subclasses of optimization problems. This is

valuable not only for the algorithms themselves, which enable one to solve given

problems, but also because identification of the collection of structures they most

effectively solve can enhance one’s ability to formulate problems.

1.2 TYPES OF PROBLEMS

The content of this book is divided into three major parts: Linear Programming,

Unconstrained Problems, and Constrained Problems. The last two parts together

comprise the subject of nonlinear programming.

Linear Programming

Linear programming is without doubt the most natural mechanism for formulating a

vast array of problems with modest effort. A linear programming problem is charac-

terized, as the name implies, by linear functions of the unknowns; the objective is

linear in the unknowns, and the constraints are linear equalities or linear inequal-

ities in the unknowns. One familiar with other branches of linear mathematics might

suspect, initially, that linear programming formulations are popular because the

mathematics is nicer, the theory is richer, and the computation simpler for linear

problems than for nonlinear ones. But, in fact, these are not the primary reasons.

In terms of mathematical and computational properties, there are much broader

classes of optimization problems than linear programming problems that have elegant

and potent theories and for which effective algorithms are available. It seems that

the popularity of linear programming lies primarily with the formulation phase of

analysis rather than the solution phase—and for good cause. For one thing, a great

number of constraints and objectives that arise in practice are indisputably linear.

Thus, for example, if one formulates a problem with a budget constraint restricting

the total amount of money to be allocated among two different commodities, the

budget constraint takes the form x

≤ B, where x

, i = 1 2, is the amount

allocated to activity i, and B is the budget. Similarly, if the objective is, for example,

maximum weight, then it can be expressed as w

, where w

, i = 1 2,

is the unit weight of the commodity i. The overall problem would be expressed as

maximize w

subject to x

≤B

≥0x

≥0

1.2 Types of Problems 3

which is an elementary linear program. The linearity of the budget constraint is

extremely natural in this case and does not represent simply an approximation to a

more general functional form.

Another reason that linear forms for constraints and objectives are so popular

in problem formulation is that they are often the least difficult to define. Thus, even

if an objective function is not purely linear by virtue of its inherent definition (as in

the above example), it is often far easier to define it as being linear than to decide

on some other functional form and convince others that the more complex form is

the best possible choice. Linearity, therefore, by virtue of its simplicity, often is

selected as the easy way out or, when seeking generality, as the only functional form

that will be equally applicable (or nonapplicable) in a class of similar problems.

Of course, the theoretical and computational aspects do take on a somewhat

special character for linear programming problems—the most significant devel-

opment being the simplex method. This algorithm is developed in Chapters 2

and 3. More recent interior point methods are nonlinear in character and these are

developed in Chapter 5.

Unconstrained Problems

It may seem that unconstrained optimization problems are so devoid of struc-

tural properties as to preclude their applicability as useful models of meaningful

problems. Quite the contrary is true for two reasons. First, it can be argued, quite

convincingly, that if the scope of a problem is broadened to the consideration of

all relevant decision variables, there may then be no constraints—or put another

way, constraints represent artificial delimitations of scope, and when the scope

is broadened the constraints vanish. Thus, for example, it may be argued that a

budget constraint is not characteristic of a meaningful problem formulation; since by

borrowing at some interest rate it is always possible to obtain additional funds, and

hence rather than introducing a budget constraint, a term reflecting the cost of funds

should be incorporated into the objective. A similar argument applies to constraints

describing the availability of other resources which at some cost (however great)

could be supplemented.

The second reason that many important problems can be regarded as having no

constraints is that constrained problems are sometimes easily converted to uncon-

strained problems. For instance, the sole effect of equality constraints is simply to

limit the degrees of freedom, by essentially making some variables functions of

others. These dependencies can sometimes be explicitly characterized, and a new

problem having its number of variables equal to the true degree of freedom can be

determined. As a simple specific example, a constraint of the form x

=B can

be eliminated by substituting x

= B −x

everywhere else that x

appears in the

problem.

Aside from representing a significant class of practical problems, the study

of unconstrained problems, of course, provides a stepping stone toward the more

general case of constrained problems. Many aspects of both theory and algorithms

4 Chapter 1 Introduction

are most naturally motivated and verified for the unconstrained case before

progressing to the constrained case.

Constrained Problems

In spite of the arguments given above, many problems met in practice are formulated

as constrained problems. This is because in most instances a complex problem such

as, for example, the detailed production policy of a giant corporation, the planning

of a large government agency, or even the design of a complex device cannot be

directly treated in its entirety accounting for all possible choices, but instead must be

decomposed into separate subproblems—each subproblem having constraints that

are imposed to restrict its scope. Thus, in a planning problem, budget constraints are

commonly imposed in order to decouple that one problem from a more global one.

Therefore, one frequently encounters general nonlinear constrained mathematical

programming problems.

The general mathematical programming problem can be stated as

minimize fx

subject to h





=0i=1 2m





≤0j=1 2r

x ∈S

In this formulation, x is an n-dimensional vector of unknowns, x =x

x

x

,

and f , h

, i = 12m, and g

, j = 12r, are real-valued functions of the

variables x

x

x

. The set S is a subset of n-dimensional space. The function

f is the objective function of the problem and the equations, inequalities, and set

restrictions are constraints.

Generally, in this book, additional assumptions are introduced in order to

make the problem smooth in some suitable sense. For example, the functions in

the problem are usually required to be continuous, or perhaps to have continuous

derivatives. This ensures that small changes in x lead to small changes in other

values associated with the problem. Also, the set S is not allowed to be arbitrary

but usually is required to be a connected region of n-dimensional space, rather than,

for example, a set of distinct isolated points. This ensures that small changes in x

can be made. Indeed, in a majority of problems treated, the set S is taken to be the

entire space; there is no set restriction.

In view of these smoothness assumptions, one might characterize the problems

treated in this book as continuous variable programming, since we generally discuss

problems where all variables and function values can be varied continuously.

In fact, this assumption forms the basis of many of the algorithms discussed,

which operate essentially by making a series of small movements in the unknown

x vector.

1.3 Size of Problems 5

1.3 SIZE OF PROBLEMS

One obvious measure of the complexity of a programming problem is its size,

measured in terms of the number of unknown variables or the number of constraints.

As might be expected, the size of problems that can be effectively solved has been

increasing with advancing computing technology and with advancing theory. Today,

with present computing capabilities, however, it is reasonable to distinguish three

classes of problems: small-scale problems having about five or fewer unknowns

and constraints; intermediate-scale problems having from about five to a hundred

or a thousand variables; and large-scale problems having perhaps thousands or even

millions of variables and constraints. This classification is not entirely rigid, but

it reflects at least roughly not only size but the basic differences in approach that

accompany different size problems. As a rough rule, small-scale problems can be

solved by hand or by a small computer. Intermediate-scale problems can be solved

on a personal computer with general purpose mathematical programming codes.

Large-scale problems require sophisticated codes that exploit special structure and

usually require large computers.

Much of the basic theory associated with optimization, particularly in nonlinear

programming, is directed at obtaining necessary and sufficient conditions satisfied

by a solution point, rather than at questions of computation. This theory involves

mainly the study of Lagrange multipliers, including the Karush-Kuhn-Tucker

Theorem and its extensions. It tremendously enhances insight into the philosophy

of constrained optimization and provides satisfactory basic foundations for other

important disciplines, such as the theory of the firm, consumer economics, and

optimal control theory. The interpretation of Lagrange multipliers that accom-

panies this theory is valuable in virtually every optimization setting. As a basis for

computing numerical solutions to optimization, however, this theory is far from

adequate, since it does not consider the difficulties associated with solving the

equations resulting from the necessary conditions.

If it is acknowledged from the outset that a given problem is too large and

too complex to be efficiently solved by hand (and hence it is acknowledged that

a computer solution is desirable), then one’s theory should be directed toward

development of procedures that exploit the efficiencies of computers. In most cases

this leads to the abandonment of the idea of solving the set of necessary conditions

in favor of the more direct procedure of searching through the space (in an intelligent

manner) for ever-improving points.

Today, search techniques can be effectively applied to more or less general

nonlinear programming problems. Problems of great size, large-scale programming

problems, can be solved if they possess special structural characteristics, especially

sparsity, that can be explioted by a solution method. Today linear programming

software packages are capable of automatically identifying sparse structure within

the input data and take advantage of this sparsity in numerical computation. It

is now not uncommon to solve linear programs of up to a million variables and

constraints, as long as the structure is sparse. Problem-dependent methods, where

the structure is not automatically identified, are largely directed to transportation

and network flow problems as discussed in Chapter 6.

6 Chapter 1 Introduction

This book focuses on the aspects of general theory that are most fruitful

for computation in the widest class of problems. While necessary and sufficient

conditions are examined and their application to small-scale problems is illustrated,

our primary interest in such conditions is in their role as the core of a broader

theory applicable to the solution of larger problems. At the other extreme, although

some instances of structure exploitation are discussed, we focus primarily on the

general continuous variable programming problem rather than on special techniques

for special structures.

1.4 ITERATIVE ALGORITHMS

AND CONVERGENCE

The most important characteristic of a high-speed computer is its ability to perform

repetitive operations efficiently, and in order to exploit this basic characteristic, most

algorithms designed to solve large optimization problems are iterative in nature.

Typically, in seeking a vector that solves the programming problem, an initial vector x

is selected and the algorithm generates an improved vector x

. The process is repeated

and a still better solution x

is found. Continuing in this fashion, a sequence of ever-

improving points x

, x

x

, is found that approaches a solution point x

∗

. For

linear programming problems solved by the simplex method, the generated sequence

is of finite length, reaching the solution point exactly after a finite (although initially

unspecified) number of steps. For nonlinear programming problems or interior-point

methods, the sequence generally does not ever exactly reach the solution point, but

converges toward it. In operation, the process is terminated when a point sufficiently

close to the solution point, for practical purposes, is obtained.

The theory of iterative algorithms can be divided into three (somewhat

overlapping) aspects. The first is concerned with the creation of the algorithms

themselves. Algorithms are not conceived arbitrarily, but are based on a creative

examination of the programming problem, its inherent structure, and the efficiencies

of digital computers. The second aspect is the verification that a given algorithm

will in fact generate a sequence that converges to a solution point. This aspect is

referred to as global convergence analysis, since it addresses the important question

of whether the algorithm, when initiated far from the solution point, will eventually

converge to it. The third aspect is referred to as local convergence analysis or

complexity analysis and is concerned with the rate at which the generated sequence

of points converges to the solution. One cannot regard a problem as solved simply

because an algorithm is known which will converge to the solution, since it may

require an exorbitant amount of time to reduce the error to an acceptable tolerance.

It is essential when prescribing algorithms that some estimate of the time required

be available. It is the convergence-rate aspect of the theory that allows some

quantitative evaluation and comparison of different algorithms, and at least crudely,

assigns a measure of tractability to a problem, as discussed in Section 1.1.

A modern-day technical version of Confucius’ most famous saying, and one

which represents an underlying philosophy of this book, might be, “One good

theory is worth a thousand computer runs.” Thus, the convergence properties of an

剩余550页未读，继续阅读

dengcy028

粉丝: 4
资源: 44

线性与非线性编程：优化方法探索

Linear Complementarity, Linear and Nonlinear Programming

Linear complementarity, linear and nonlinear programming

《Linear and Nonlinear Programming》- Luenberger & Ye：数学规划大师之作

Linear and Nonlinear optimization

Nonlinear Programming: The Nonlinear Extension of Linear Programming for Complex Problems

MATLAB Linear and Integer Programming: The Ultimate Tool for Solving Discrete Optimization Problems

The Secret to Accelerating Linear and Quadratic Programming Solutions

Exploring Techniques for Handling Nonlinear Constraints: MATLAB Linear Programming with Nonlinear ...

Multistage Linear Programming: A Linear Programming Model for Sequential Decision Making, Solving ...

Integer Linear Programming: Solving Linear Programming Problems with Integer Variables, Expanding ...

最新资源