最优化期末考试

Let {x k } be a sequence in Rn that converges to x *

W e say that the convergence is Q-linear if there is a

constant r ∈0,1 such that() x -x * lim k +1≤r

Further, if

x k +1-x * lim =0 k →∞x k -x * k →∞x k -x *

the convergence is said to be Q-superlin ear

And a even more rapid convergence, Q-qu adratic

holds convergenc, is defined when the followin g inequality

x k +1-x * lim ≤M 2k →∞ x k -x *

for all k sufficiently large. where M is a positive constant, not necessarily less than 1.

P-1 Let a be a given n-vector, and A be a given nth-order sym m etric matrix. Find out the gradient and Hessian of T T f 1(x )=a x and f 2(x )=x Ax

P-2 Let f (x )=3x 2-2x 2+x 2+2x x +4x x +3x -x +2123122312

1T and assume f (x ) can be rew rited as f (x )=x Ax +bx +c 2 T then find out A , b and c , where A =A .

P-3 Com pute the gradient and Hessian of the function

2 f (x )=100(x -x 2)+(1-x )2

211

Definition: Convex combination

12k n Let x , x , , x ∈R and α1, α2, , αk be k nonnegative

k scalars and α=1, the linear combination i =1

α1x 1+α2x 2+ +αk x k

12k is defined as a convex combination of x , x , , x Definition: Convex combination

n A set D ⊆R is a convex set if for any two points x ∈D

and y ∈D , we have

αx +(1-α)y ∈D

for a arbitrary scalar α∈[0,1].

T hat is, the "line segment" joining them is still in D . ∑k

Theorem: Properties of convex sets

Let D , D 1, D 2 be three convex sets of R n , we have the

follow ing properties

(1) αD ={y y =αx , x ∈D } is a convex set for any

scalar α

(2) D 1 D 2={x x ∈D 1 and x ∈D 1} is a convex set

1212 (3) D 1+D 2=x +x x ∈D 1, x ∈D 2 is a convex set

Definition: Convex functions (4) D 1-D 2{={x 1-x 2x ∈D 1, x 12}∈D } is a convex set2

Let f (x ) be a function defined on a convex D , f (x ) is

convex if for any x , y ∈D and α∈0,1, we have

f ⎡⎣αx +(1-α)y ⎤⎦≤αf (x )+(1-α [])f (y )

Further, f (x ) is strictly convex if the above inequality

holds strictly whenever x ≠y and 0

W e say f x is concave if -f x is convex, and strictly

()()

Theorem: Properties of convex functions

Assum e f 1(x ), f 2(x ) and f (x ) are convex, then we have

(1) kf (x ) is convex for any k ≥0

(2) -f (x ) is a concave

(3) λf 1(x )+μf 2(x ) is convex for any λ≥0, μ≥0

Theorem: First-order Conditions concave if -f (x ) is strictly convex.

Suppose f (x ) is a differentiable function defined on a

convex set D . then f (x ) is convex if and only if

f (y )≥f (x )+∇f (x )T (y -x )Theorem: Second-order Conditions holds for all x , y ∈D Suppose f (x ) is twice differentiable on nonempty open

convex set D . Then f (x ) is convex if and only if its Hessian is positive semidefinite, i.e. for all x ∈D

2 ∇f (x )≥0

Theorem: Second-order Conditions

Suppose f (x ) is twice differentiable on nonem pty open

convex set D . Then f x is convex if and only if its Hessian is positive semidefinite, i.e. for all x ∈D 2 ∇f (x )≥0

Further, if ∇2f (x )>0, then f (x ) is strictly convex.

how ever, the converse is not always true.()

Questions:

f 1(x )=(x -1), x ∈R f 2(x )=e , x ∈R x 12f 3(x )=x 2, x ∈(0, +∞)f 4(x )=x 1+2x 1x 2+x 2, x ∈R 22222f 5(x )=-x 1-x 1x 2-2x 2, x ∈R 2

f 6(x )=c 1x 1+c 2x 2+ +c n x n , x ∈R Definition: Convex programming n

Let D ⊆R n be a convex set and f (x ) be a convex

function defined on D , the following math em atical program m ing is called to be convex programm ing.

⎧⎪m in f (x ) ⎨ ⎪⎩x ∈D

Theorem: Properties of convex programming

(1) The objective function f (x ) is convex when the goal

is minim ization, otherwise f x is concave.

()(2) The feasible region D is convex when D is nonempty.

(3) The optimal solution set D * is convex if D * is not

empty

(4) Any local optimal solution is also globally optimal. (5) If the objective function f (x ) is strictly convex and

the optimal solution set D * is nonem pty , then there

is just only one optimal solution.

The geometrical properties for linear programming

The feasible region D for a LP is convex if D is nonempty.

If there is a feasible solution, then there is at least one basic feasible solution.

A feasible solution is a basic feasible one if and only if it is an extreme point of the

feasible region D

If a LP has optimal solutions, then at least one such solution is a basic feasible one. If a LP is feasible and bounded, then it has at least one optimal solution.

？？？Show that the following model is convex programming

Suppose that the feasible region D is not empty and the

m athem aticl model is as

⎧m in f (x ) ⎪s . t . c i (x )=0, i ∈E ⎪⎨ ⎪ c j (x )≥0, j∈I

⎪n x ∈R ⎩

w here f (x ) is convex, all the equality constraint functions

are liner and all the inequality constraint functions are concave

？？？Show that the following results

Suppose that D 1, D 2 and D are all convex sets of R n , show that

follow ing results

(1) αD ={y y =αx , x ∈D } is a convex set for any scalar α

(2) D 1 D 2={x x ∈D 1 and x ∈D 1} is a convex set

(3) D +D ={x 1+x 2x 1∈D , x 2∈D } is a convex set1212

(4) D 1-D 2=x -x {12x ∈D 1, x ∈D 2 is a convex set12}

？？？Determine whether the following statements are true or not

• The linear programming is a kind of convex programming.

• If x* is the only optimal solution to a LP, then it is just an extreme point of the

feasible region.

• For a LP, the optimal solution must be one of extreme points of the feasible

region.

• For a LP, the optimal basic feasible solution must be one of extreme points of

the feasible region.

• For a LP, if the feasible region is nonempty , then there certainly exist at least

one optimal solution.

对偶单纯形法

The dual theorem and its consequences

T o simplify the exposition, we consider the following symmetrical dual problems*:

⎧m in Z=b ⎧m ax S=c T x ⎪T ⎪ (D )⎨A y ≥c (P )⎨A x ≤b T y

⎪x ≥0⎩⎪y ≥0⎩

D enote R P , R D as the feasible regions of the primal (P)

and the dual (D) respectively

*Remarks: for asymmetrical dual problems, the conclusions discussed are also applicable Weak Duality

T Proof : since x ≥0, y ≥0, multiplying A x ≤b by y and

A T y ≥c by x T will yield

T T ⎧⎪y A x ≤y b ⎨T T T ⎪⎩x A y ≥x c

T T ⎧⎪y A x ≤y b ⎨T T ⎪⎩y A x ≥x c this two inequalities may be written as follows

T T cx *=b y *

then x * and y * are optimal solutions of the primal (P)

and the dual (D) respectively.

Propos iton2: The primal (P) and the dual (D) have

optim al solutions if and only if they have feasible solutions sim ultaneously.

Prop osi ton3: If the primal (P) is unbounded, the dual (D) Proposition1: Let x *∈R P , y *∈R D , if

prim al (P) is infeasible.is infeasible. Also, if the dual (D) is unbound ed , then the

Theorem: The Dual Theorem

Assum e x * is a basic optimal solution for (P) with repect

to the basis B , then we have

y *=(c B B T -1 is an optimal solution to the dual (D)

Theorem: Complementary Slackness

⎛x 1 x 2Let x = ⎝x n ⎫⎛y 1⎪ y ⎪∈R , y = 2P ⎪ ⎪ ⎭⎝y m ⎫⎪⎪∈R , then x and y are optimal D ⎪⎪⎭)T

and only if solutions to the primal (P) and the dual (D) respectively if

i i

e j x j =0, for j =1, 2, , n

w here s i is the slack variable of the i th constraint for the s y =0 , for i =1, 2, , m

prim al (P), and e j is a excess variab le of the j th constrai nt

for the dual (D ).

The Dual Simplex Method

Theorem ： For the simplex tableau

Assum e all the test indicators are nonngative and some

one right-hand side b j is negative, and all coeffients

of the j the constraint are nonnegative, then the LP have

no optimal solution.

？？？Use the Dual Theorem to solve the following LP :

m in Z=c 1y 1+c 2y 2+80y 3

⎧3y 1+2y 2+y 3≥2 ⎪⎪4y 1+y 2+3y 3≥4 (P )⎨

⎪2y 1+2y 2+2y 3≥3 ⎪y ≥0, i =1, 2, 3⎩i

Where it is known that the optimal solution to the dual is:

T 2050⎫⎛⎪ x *= 033⎭⎝无约束优化Conditions for optimality

Consider the following unconstrained problem

m in f (x ) x ∈R n

T heorem (First-order necessary conditions ) If x * is a local minim izer and f is continuously differentiable

in an open neighborhood of x *, then

∇f (x *)=0

T he orem (Se cond-order necessary conditions ) 2If x * is a local minim izer and ∇f (x ) is continuous in an open

neighborhood of x *, then

∇f x *=0() 22 and ∇f (x *) is positive semidefinite.(denoted as ∇f (x *)≥0 ) T heorem (Second-order sufficient condition s ) 2Suppose that ∇f (x ) is continuous and positive definite

(i.e ∇2f (x *)>0) in an open neighborhood of x * and that ∇f (x *)=0, then x * is a strict local minim izer of f (x ).

T heorem : When f is convex, any local minim izer x * is a global minim izer of f . If in addition f is differentiable, then

any stationary point x *(i.e. ∇f (x *)=0) is a global minim izer of f .

In other wor ds, when f is convex and differentiable, x *

is a global minim izer of f if and only if ∇f (x *)=0

Exam ple : Find all the local minim izer of the following function.

13132 f (x )=x 1+x 2-x 2-x 133

Algorithm

step-1: choose the starting point x 1∈R n and tolerance δ>0 and set k =1.

k k step-2: evaluate d =-∇f (

x )

to next step .

s te p-4: make a linear search

k k

m in f λ≥0

k +1k k ste p-3: if d ≤δ, then stop and let x *=x , otherw ise turn(x +λd k )=f (x k +λk d k ) step-5: let x =x +λk d and k =k +1, turn back to step-2k

Idea of algorithm :

f (x k +λd k )=f (x k )+λd k T ∇f (x k )+ (λd k

are orthogonal mutually, i.e. )k k +1Properti e s : The two consecutive search direction d a nd d

∇f (x k )∇f (x k +1)=0

k k k +1Since m in f (x +λd k )=f (x +λk d k )=f (x )

Le t f (x k +λd k )=ϕ(λ)

T '(λ)=⎡∇f (x k +λd k )⎤d k =0 we have ϕ'(λk )=0and let ϕ ⎣⎦

T k that is, ⎡∇f (x +λk d k )⎤d k =0⎣⎦

Exam ple : U se the steepest descent method to solve the problem. ()T

min f (x )=(x -3)+(x -2)12 1 B egin at the point x 1=⎛⎫, and the tolerance δ=0. ⎪ ⎝1⎭

22

Properti es : The two consecutive search direction d and d are orthogonal mutually, i.e.

∇f T k k +1((x ))k ∇f (x )=0k +1