[go: up one dir, main page]
Scribd
Upload
44 views11 pages

CS 726: Nonlinear Optimization 1 Lecture 05: Existence: Michael C. Ferris

The document summarizes key points from a lecture on existence theorems in nonlinear optimization: (1) Weierstrass' theorem states that a continuous function over a compact domain achieves its infimum. (2) The Frank-Wolfe theorem guarantees existence of a minimizer or half-line of descent for quadratic functions over polyhedral sets. (3) A continuously differentiable convex function satisfies its definition at all points in its domain.

Uploaded by

Harris
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
44 views11 pages

CS 726: Nonlinear Optimization 1 Lecture 05: Existence: Michael C. Ferris

The document summarizes key points from a lecture on existence theorems in nonlinear optimization: (1) Weierstrass' theorem states that a continuous function over a compact domain achieves its infimum. (2) The Frank-Wolfe theorem guarantees existence of a minimizer or half-line of descent for quadratic functions over polyhedral sets. (3) A continuously differentiable convex function satisfies its definition at all points in its domain.

Uploaded by

Harris
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

CS 726: Nonlinear Optimization 1

Lecture 05 : Existence

Michael C. Ferris

Computer Sciences Department


University of Wisconsin-Madison

February 3 2021

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 1/9


Existence

Theorem (Weierstrauss)
Let A ✓ Rn , A 6= ; and let f : A ! R be lower semicontinuous at all
points of A. Assume one of the following:
(a) A is compact
(b) A is closed and f is coercive (ie f (x) ! 1 when ||x|| ! 1)
(c) 9 such that the set {x 2 A|f (x)  } is non-empty and compact
Then 9x 2 A such that f (x) = inf f (z).
z2A

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 2/9


Quadratic form: f (x) = 12 x T Qx + p T x, Q 2 Rn⇥n .
We show without loss of generality, Q can be assumed symmetric. Take
x 2 Rn .
Proof.

1 T 1 1 T 1 Q + QT
x T Qx = x Qx + ( x T Qx )T = x Qx + x T Q T x = x T ( ) x.
2 2 | {z } 2 2 2
1⇥n⇥n⇥n⇥n⇥1
| {z }
symmetric

For example,
 1
✓ ◆
1 2 x1
f (x) = x12 + 2x1 x2 + 3x22 = (x1 x2 ) 2
2 0 3 x2
 1
✓ ◆
2 1 x1
= (x1 x2 ) .
1 3 x2

f is quadratic form above, then rf (x) = Qx + p. (needs Q symmetric.)

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 3/9


Theorem (Frank-Wolfe)
If f is a quadratic function as above, and C is a nonempty polyhedral set
(defined in Lecture 2), consider the following problem,

min f (x)
s.t. x 2C

then either f attains its global infimum on C , or there exists a feasible


half-line in C along which f # 1. (C 3 x0 + d, 0).

Proof.
Seen[Frank and Wolfe(1956)], but also other proofs in
[Blum and Oettli(1972), Eaves(1971)]. Some extensions can be found in
[Luo and Zhang(1999), Perold(1980)].

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 4/9


Example

min kAx bk22 0.


x2C

Then f (x) = x T AT Ax 2b T Ax + b T b 0. Thus a global minimizer


always exists by the Frank-Wolfe theorem because f is bounded below.
Contrast this with e x (strictly convex function).

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 5/9


Convex Functions and Di↵erentiability

Proposition
Suppose dom(f ) is open. f : Rn ! R̄ is di↵erentiable over dom(f ). Then
(also see figure below)

f is convex , dom(f ) is convex and


f (x) f (z) + rf (z)T (x z), 8x, z 2 dom(f )

and

dom(f ) is convex and


f (x) > f (z) + rf (z)T (x z), 8x, z 2 dom(f ) ) f is strictly convex

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 6/9


Linearization at x under-estimates f .

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 7/9


Proof.
(()Suppose x, y 2 dom(f ), ↵ 2 (0, 1), then z = ↵x + (1 ↵)y 2 dom(f ).
By assumption: (
f (x) f (z) + rf (z)T (x z)
f (y ) f (z) + rf (z)T (y z)
Multiply the first inequality by 1 ↵ and the second by ↵, then sum then
together we have

(1 ↵)f (x) + ↵f (y ) (1↵)f (z) + (1 ↵)rf (z)T (x z)


+↵f (z) + ↵rf (z)T (y z)
= f (z) + rf (z)T [(1 ↵)(x z) + ↵(y z)]
= f (z)

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 8/9


Proof.
()) Suppose x, z 2 dom(f ), x 6= z, 0 < < 1,

f (x) + (1 )f (z) f ( x + (1 )z)


) (f (x) f (z)) f ( x + (1 )z) f (z)
1 o( )
) f (x) f (z) [f (z + (x z)) f (z)] = rf (z)T (x z) +

lim as # 0, f (x) f (z) rf (z)T (x z)


The last statement follows from a simple extension of the argument
above.

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 9/9


E. Blum and W. Oettli.
Direct proof of the existence theorem for quadratic programming.
Operations Research, 20(1):165–167, 1972.
ISSN 0030364X, 15265463.
URL http://www.jstor.org/stable/169347.
B. C. Eaves.
On Quadratic Programming.
Management Science, 17:698–711, 1971.
M. Frank and P. Wolfe.
An Algorithm for Quadratic Programming.
Naval Research Logistics Quarterly, 3(1-2):95–110, Mar. 1956.
doi: 10.1002/nav.3800030109.
Z.-Q. Luo and S. Zhang.
On extensions of the frank-wolfe theorems.
Computational Optimization and Applications, 13(1-3):87–110, Apr.
1999.
A. F. Perold.
Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 9/9
A generalization of the frank-wolfe theorem.
Mathematical Programming, 18(1):215–227, dec 1980.
doi: 10.1007/BF01588315.

Michael C. Ferris (UW-Madison) CS726:Lecture 05 Existence 9/9

You might also like