Programación no lineal

LECTURE SLIDES ON NONLINEAR PROGRAMMING BASED ON LECTURES GIVEN AT THE MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MASS DIMITRI P. BERTSEKAS These lecture slides are based on the book: “Nonlinear Programming,” Athena Scientific, by Dimitri P. Bertsekas; see http://www.athenasc.com/nonlinbook.html for errata, selected problem solutions, and other support material. The slides are copyrightedbut may be freely reproduced and distributed for any noncommercial purpose. LAST REVISED: Feb. 3, 2005

6.252 NONLINEAR PROGRAMMING LECTURE 1: INTRODUCTION LECTURE OUTLINE • Nonlinear Programming • Application Contexts • Characterization Issue • Computation Issue • Duality • Organization

NONLINEAR PROGRAMMING min f (x),

x∈X

where • f : n → is a continuous (and usually differentiable)function of n variables • X = n or X is a subset of ous” character. • If X =
n, n

with a “continu-

the problem is called unconstrained

• If f is linear and X is polyhedral, the problem is a linear programming problem. Otherwise it is a nonlinear programming problem • Linear and nonlinear programming have traditionally been treated separately. Their methodologies have gradually come closer.TWO MAIN ISSUES • Characterization of minima − Necessary conditions − Sufficient conditions − Lagrange multiplier theory − Sensitivity − Duality • Computation by iterative algorithms − Iterative descent − Approximation methods − Dual and primal-dual methods

APPLICATIONS OF NONLINEAR PROGRAMMING • Data networks – Routing • Production planning • Resource allocation • Computer-aided design •Solution of equilibrium models • Data analysis and least squares formulations • Modeling human or organizational behavior

CHARACTERIZATION PROBLEM • Unconstrained problems − Zero 1st order variation along all directions • Constrained problems − Nonnegative 1st order variation along all feasible directions • Equality constraints − Zero 1st order variation along all directions on the constraintsurface − Lagrange multiplier theory • Sensitivity

COMPUTATION PROBLEM • Iterative descent • Approximation • Role of convergence analysis • Role of rate of convergence analysis • Using an existing package to solve a nonlinear programming problem

POST-OPTIMAL ANALYSIS • Sensitivity • Role of Lagrange multipliers as prices

DUALITY • Min-common point problem / max-intercept problemduality
Min Common Point S S Min Common Point

0 Max Intercept Point Max Intercept Point

0

(a)

(b)

Illustration of the optimal values of the min common point and max intercept point problems. In (a), the two optimal values are not equal. In (b), the set S, when “extended upwards” along the nth axis, yields the set ¯ ¯ S = {¯ | for some x ∈ S, xn ≥ xn , xi = xi , i = 1, . . . , n − 1} x ¯which is convex. As a result, the two optimal values are equal. This fact, when suitably formalized, is the basis for some of the most important duality results.

6.252 NONLINEAR PROGRAMMING LECTURE 2 UNCONSTRAINED OPTIMIZATION OPTIMALITY CONDITIONS

LECTURE OUTLINE • Unconstrained Optimization • Local Minima • Necessary Conditions for Local Minima • Sufficient Conditions for Local Minima •The Role of Convexity

MATHEMATICAL BACKGROUND • Vectors and matrices in
n

• Transpose, inner product, norm • Eigenvalues of symmetric matrices • Positive definite and semidefinite matrices • Convergent sequences and subsequences • Open, closed, and compact sets • Continuity of functions • 1st and 2nd order differentiability of functions • Taylor series expansions • Mean value theoremsLOCAL AND GLOBAL MINIMA

f(x)

x Strict Local Minimum Local Minima Strict Global Minimum

Unconstrained local and global minima in one dimension.

NECESSARY CONDITIONS FOR A LOCAL MIN • 1st order condition: Zero slope at a local minimum x∗ ∇f (x∗ ) = 0 • 2nd order condition: Nonnegative curvature at a local minimum x∗ ∇2 f (x∗ ) : Positive Semidefinite • There may exist points that satisfy...