6.253 Convex Analysis and Optimization, Lecture 12

LECTURE 12 LECTURE OUTLINE • Subgradients • Fenchel inequality • Sensitivity in constrained optimization • Subdifferential calculus • Optimality conditions Reading: Section 5.4 1 SUBGRADIENTS f (z) ( g, 1) x, f (x) 0 z • Let f : be a convex function. A vector g n is a subgradient of f at a point x ⌘ dom(f ) if f (z) ≥ f (x) + (z − x) g,  z n • Support Hyperplane Interpretation: g is a subgradient if and only if f (z) − z � g ≥ f (x) − x� g,  z ⌘ �n so g is a subgradient at x if and only if the hyperplane in ��n+1 that ⇥ has normal (−g, 1) and passes through x, f (x) supports the epigraph of f . • The set of all subgradients at x is the subdifferential of f at x, denoted ◆f (x). • By convention ◆f (x) = Ø for x ⌘ / dom(f ). 2 EXAMPLES OF SUBDIFFERENTIALS • Some examples:   
=
|x| f (x) f (x) 1 0 0 x 
 -1 � ⇥ 2 

 1) 
=
max 
 f (x) 0, (1/2)(x -1 
 0  1 x    f (x) 0 -1 
 x  1 x  • If f is differentiable, then ◆f (x) = {∇f (x)}. Proof: If g ⌘ ◆f (x), then f (x + z) ≥ f (x) + g � z, � ⇥  z ⌘ �n . Apply this with z = ⇤ ∇f (x) − g , ⇤ ⌘ �, and use 1st order Taylor series expansion to obtain �∇f (x) − g�2 ⌥ −o(⇤)/⇤, 3 ⇤<0 EXISTENCE OF SUBGRADIENTS • Let f : �n ◆→ (−⇣, ⇣] be proper convex. • Consider MC/MC with M = epi(fx ), fx (z) = f (x + z) − f (x) fx (z) f (z) ( g, 1) Epigraph of f Translated Epigraph of f ( g, 1) 0 � ⇥ x, f (x) 0 z z • By 2nd MC/MC Duality Theorem, ◆f (x) is nonempty and compact if and only if x is in the interior of dom(f ). � • More generally: for every x ⌘ ri dom(f )), ◆f (x) = S ⊥ + G, where: − S is the subspace that is parallel to the a⌅ne hull of dom(f ) − G is a nonempty and compact set. 4 EXAMPLE: SUBDIFFERENTIAL OF INDICATOR • Let C be a convex set, and ⌅C be its indicator function. • For x ⌘ / C, ◆⌅C (x) = Ø (by convention). • For x ⌘ C, we have g ⌘ ◆⌅C (x) iff ⌅C (z) ≥ ⌅C (x) + g � (z − x),  z ⌘ C, or equivalently g � (z − x) ⌥ 0 for all z ⌘ C. Thus ◆⌅C (x) is the normal cone of C at x, denoted NC (x): ⇤ ⌅ � NC (x) = g | g (z − x) ⌥ 0,  z ⌘ C . x C x C NC (x) NC (x) 5 EXAMPLE: POLYHEDRAL CASE C a1 x NC (x) a2 • For the case of a polyhedral set C = {x | a�i x ⌥ bi , i = 1, . . . , m}, we have NC (x) = � {0} � if x ⌘ int(C), ⇥ cone {ai | a�i x = bi } if x ⌘ / int(C). • Proof: Given x, disregard inequalities with a�i x < bi , and translate C to move x to 0, so it becomes a cone. The polar cone is NC (x). 6 FENCHEL INEQUALITY • Let f : �n ◆→ (−⇣, ⇣] be proper convex and let f be its conjugate. Using the definition of conjugacy, we have Fenchel’s inequality: x� y ⌥ f (x) + f (y),  x ⌘ �n , y ⌘ �n . • Conjugate Subgradient Theorem: The following two relations are equivalent for a pair of vectors (x, y): (i) x� y = f (x) + f (y). (ii) y ⌘ ◆f (x). If f is closed, (i) and (ii) are equivalent to (iii) x ⌘ ◆f (y). f (x) f ⇥ (y) Epigraph of f Epigraph of f ⇥ ( y, 1) 0 0 x ( x, 1) y 2 ⇧f (x) ⇧f (y) 7 MINIMA OF CONVEX FUNCTIONS • Application: Let f be closed proper convex and let X ⇤ be the set of minima of f over �n . Then: (a) X ⇤ = ◆f (0). (b) X⇤ � ⇥ is nonempty if 0 ⌘ ri dom(f ) . y⇥and compact if and only if (c) X ⇤ is nonempt � 0 ⌘ int dom(f ) . Proof: (a) We have x⇤ ⌘ X ⇤ iff f (x) ≥ f (x⇤ ) for all x ⌘ �n . So x⇤ ⌘ X ⇤ iff 0 ⌘ ◆f (x⇤ ) iff x⇤ ⌘ ◆f (0) where: − 1st relation follows from the subgradient inequality − 2nd relation follows from the conjugate subgradient theorem � ⇥ (b) ◆f (0) is nonempty if 0 ⌘ ri dom(f ) . (c) ◆f (0) and compact if and only � is nonempty ⇥ if 0 ⌘ int dom(f ) . Q.E.D. 8 SENSITIVITY INTERPRETATION • Consider MC/MC for the case M = epi(p). • Dual function is q(µ) = inf u⌦� m ⇤ p(u) + µ� u ⌅ = −p (−µ), where p is the conjugate of p. • Assume p is proper convex and strong duality ⌅ ⇤ ⇤ ⇤ holds, so p(0) = w = q = supµ⌦�m − p (−µ) . Let Q⇤ be the set of dual optimal solutions, Q⇤ = ⇤ µ⇤ | p(0) + p (−µ⇤ ) ⌅ =0 . From Conjugate Subgradient Theorem, µ⇤ ⌘ Q⇤ if and only if −µ⇤ ⌘ ◆p(0), i.e., Q⇤ = −◆p(0). • If p is convex and differentiable at 0, −∇p(0) is equal to the unique dual optimal solution µ⇤ . • Constrained optimization example: p(u) = inf x⌦X, g(x)⌅u f (x), If p is convex and differentiable, µ⇤j = − ◆p(0) , ◆uj j = 1, . . . , r. 9 EXAMPLE: SUBDIFF. OF SUPPORT FUNCTION • Consider the support function ↵X (y) of a set X. To calculate ◆↵X (y) at some y, we introduce r(y) = ↵X (y + y), y ⌘ �n . • We have ◆↵X (y) = ◆r(0) = arg minx⌦�n r (x). • We have r (x) = supy⌦�n {y � x − r(y)}, or r (x) = sup {y � x − ↵X (y + y)} = ⌅(x) − y � x, y⌦�n ⇥ � where ⌅ is the indicator function of cl conv(X) . ⌅ ⇤ � • Hence ◆↵X (y) = arg minx⌦�n ⌅(x) − y x , or ◆↵X (y) = arg �max � ⇥y x x⌦cl conv(X) ⇥σX (y2 ) ⇥σX (y1 ) X y2 y1 0 10 EXAMPLE: SUBDIFF. OF POLYHEDRAL FN • Let f (x) = max{a�1 x + b1 , . . . , a�r x + br }. f (x) r(x) ( g, 1) ( g, 1) Epigraph of f 0 x 0 x x • For a fixed x ⌘ �n , consider ⇤ Ax = j | a�j x ⌅ + bj = f (x) ⇤ � ⌅ and the function r(x) = max aj x | j ⌘ Ax . • It can be seen that ◆f (x) = ◆r(0). • Since r is the support function of the finite set {aj | j ⌘ Ax }, we see that � ◆f (x) = ◆r(0) = conv {aj | j ⌘ Ax } 11 ⇥ CHAIN RULE • Let f : �m ◆→ (−⇣, ⇣] be convex, and A be a matrix. Consider F (x) = f (Ax) and assume that F is proper. If either f is polyhedral or else Range(A) ⌫ ri(dom(f )) ✓= Ø, then ◆F (x) = A� ◆f (Ax),  x ⌘ �n . Proof: Showing ◆F (x) ↵ A� ◆f (Ax) is simple and does not require the relative interior assumption. For the reverse inclusion, let d ⌘ ◆F (x) so F (z) ≥ F (x) + (z − x)� d ≥ 0 or f (Az) − z � d ≥ f (Ax) − x� d for all z, so (Ax, x) solves minimize f (y) − z � d subject to y ⌘ dom(f ), Az = y. ✓ Ø, by strong duality theoIf R(A) ⌫ ri(dom(f )) = rem, there is a dual optimal solution ⌃, such that ⌅ ⇤ � � (Ax, x) ⌘ arg min f (y) − z d + ⌃ (Az − y) m n y⌦� , z⌦� Since the min over z is unconstrained, we ⇤ ⌅ have d = A� ⌃, so Ax ⌘ arg miny⌦�m f (y) − ⌃� y , or f (y) ≥ f (Ax) + ⌃� (y − Ax),  y ⌘ �m . Hence ⌃ ⌘ ◆f (Ax), so that d = A� ⌃ ⌘ A� ◆f (Ax). It follows that ◆F (x) ⌦ A� ◆f (Ax). In the polyhedral case, dom(f ) is polyhedral. Q.E.D. 12 SUM OF FUNCTIONS • Let fi : �n ◆→ (−⇣, ⇣], i = 1, . . . , m, be proper convex functions, and let F = f1 + · · · + fm . • Assume that • Then � ⇥ dom(fi ) ✓= Ø. ⌫m 1=1 ri ◆F (x) = ◆f1 (x) + · · · + ◆fm (x),  x ⌘ �n . Proof: We can write F in the form F (x) = f (Ax), where A is the matrix defined by Ax = (x, . . . , x), and f : �mn ◆→ (−⇣, ⇣] is the function f (x1 , . . . , xm ) = f1 (x1 ) + · · · + fm (xm ). Use the proof of the chain rule. • Extension: If for some k, the functions fi , i = 1, . . . , k, are polyhedral, it is su⌅cient to assume ⌥ � ⌫ki=1 dom(fi ) ⌫ ⌥ � � ⇥ ✓ Ø. ⌫m = i=k+1 ri dom(fi ) 13 CONSTRAINED OPTIMALITY CONDITION • Let f : �n ◆→ (−⇣, ⇣] be proper convex, let X be a convex subset of �n , and assume that one of the following four conditions holds: � ⇥ (i) ri dom(f ) ⌫ ri(X) = ✓ Ø. (ii) f is polyhedral and dom(f ) ⌫ ri(X ) = ✓ Ø. � ⇥ (iii) X is polyhedral and ri dom(f ) ⌫ X = ✓ Ø. (iv) f and X are polyhedral, and dom(f ) ⌫ X = ✓ Ø. Then, a vector x⇤ minimizes f over X iff there exists g ⌘ ◆f (x⇤ ) such that −g belongs to the normal cone NX (x⇤ ), i.e., g � (x − x⇤ ) ≥ 0,  x ⌘ X. Proof: x⇤ minimizes F (x) = f (x) + ⌅X (x) if and only if 0 ⌘ ◆F (x⇤ ). Use the formula for subdifferential of sum. Q.E.D. 14 ILLUSTRATION OF OPTIMALITY CONDITION Level Sets of f NC (x∗ ) NC (x∗ ) Level Sets of f x∗ C x∗ C ⌃f (x∗ ) ⇧f (x∗ ) g • In the figure on the left, f is differentiable and the condition is that −∇f (x⇤ ) ⌘ NC (x⇤ ), which is equivalent to ∇f (x⇤ )� (x − x⇤ ) ≥ 0,  x ⌘ X. • In the figure on the right, f is nondifferentiable, and the condition is that −g ⌘ NC (x⇤ ) for some g ⌘ ◆f (x⇤ ). 15