UBC Undergraduate Research

Convexity of the Proximal Average Johnstone, Jennifer 2008-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
Thesis Jennifer Johnstone.pdf [ 1.68MB ]
Metadata
JSON: 1.0052226.json
JSON-LD: 1.0052226+ld.json
RDF/XML (Pretty): 1.0052226.xml
RDF/JSON: 1.0052226+rdf.json
Turtle: 1.0052226+rdf-turtle.txt
N-Triples: 1.0052226+rdf-ntriples.txt
Original Record: 1.0052226 +original-record.json
Full Text
1.0052226.txt
Citation
1.0052226.ris

Full Text

Convexity of the Proximal AveragebyJennifer JohnstoneA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFBACHELOR OF SCIENCE HONOURSinThe I. K. Barber School of Arts & Sciences(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Kelowna, Canada)December, 2008c Jennifer Johnstone 2008AbstractThe proximal average operator is recognized for its ability to transform twoconvex functions into another convex function. However, we prove withexamples that the proximal average operator does have limitations, withrespect to convexity. We also look at the importance of ‚ 2 [0;1] anddescribe an idea of how to plot the proximal average of two convex functionsmore e–ciently.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . ivDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Subdifierential . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Legendre-Fenchel Conjugate . . . . . . . . . . . . . . . . . . 62 The Proximal Average . . . . . . . . . . . . . . . . . . . . . . 72.1 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Convexity Results . . . . . . . . . . . . . . . . . . . . . . . . 92.2.1 Convexity with respect to x . . . . . . . . . . . . . . 92.2.2 Convexity with respect to ‚ . . . . . . . . . . . . . . 92.2.3 Convexity with respect to „ . . . . . . . . . . . . . . 102.2.4 Further Investigation . . . . . . . . . . . . . . . . . . 113 Plotting the Proximal Average . . . . . . . . . . . . . . . . . 163.1 New Plotting function . . . . . . . . . . . . . . . . . . . . . . 164 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19iiiAcknowledgementsTo start, the author would like to express her gratitude to her supervisor Dr.Yves Lucet for his constant support and guidance throughout this process.His ideas and topic suggestions made this thesis possible.The author would also like to thank all those who encouraged her totake on this project and supported her throughout.ivDedicationTo my Mother for her continuous encouragement.vChapter 1IntroductionThe purpose of this thesis is to investigate the convexity of the proximalaverage and elaborate on some of the properties of the proximal average.In this chapter, we review some of the standard facts on Convex Analysisfollowed by a review of some of the basics of the proximal average in Chapter2, in which we also provide the main results of our investigation into theconvexity of the proximal average.1.1 Convex FunctionsIn this section we recall some of the basics of Convex Analysis to help thereader better understand the results in Chapter 2. We assume that we areworking in a real Hilbert space, H, which is deflned as a complete, real, innerproduct space. The Hilbert space H is complete if all Cauchy sequences inH converge, with respect to the deflned norm, and H is an inner productspace if an inner product exists such that kxk = p< x;x >, for all x 2 H.So we deflne <¢;¢>: H £H !R such that for all x;y;z 2 H and ‚;„ 2Rwe have< x;y > = < y;x >< ‚x+„y;z > = ‚ < x;z > +„ < y;z >< x;x > ‚ 0 and < x;x >= 0 ifi x = 0:Then working in H we can extend any function g : › ‰ H ! R to~g : H !R[f+1g with~g(x) =(g(x) if x 2 ›;+1 if not:We also deflne dom ~g asdom ~g := fx 2 Hj~g(x) < +1g11.1. Convex FunctionsDeflnition 1.1 (Convex Sets). Let › ‰ H then › is a convex set if for allx1 2 › and x2 2 › it contains all pointsfix1 +(1¡fi)x2; 0 < fi < 1:Deflnition 1.2 (Convex Functions). Let C be a non-empty convex set inH. A function g : C ! R is said to be convex on C when, for all pairs(x1;x2) 2 C £C and all 0 < fi < 1, we haveg(fix1 +(1¡fi)x2) • fig(x1)+(1¡fi)g(x2):For a convex function, g, we see that the line segmentf(fix1 +(1¡fi)x2;fig(x1)+(1¡fi)g(x2) : fi 2 [0;1]gis always above the graph of g, as illustrated in Figure 1.1. On the otherhand, in Figure 1.2 we see that this is not the case for all pairs (x1;x2) 2C £C and all 0 < fi < 1.Figure 1.1: For g = x2 we see that the line segmentf(fix1 +(1¡fi)x2;fig(x1)+(1¡fi)g(x2) : fi 2 [0;1]g is always abovethe graph g thus g is a convex function.21.1. Convex FunctionsFigure 1.2: For g = x4 + 3x3 + 10 we see that the line seg-mentf(fix1 +(1¡fi)x2;fig(x1)+(1¡fi)g(x2) : fi 2 [0;1]g] is not above thegraph of g at x = ¡1 thus g is a non-convex function.We will only consider proper functions, since we are not interested indegenerate functions such as g = +1 everywhere.Deflnition 1.3 (Proper). A function g is called proper if g(x) > ¡1 forall x and g(x) < +1 for at least one x.An example of a proper function would be the indicator function whichis deflned on a nonempty set C byiC(x) =(0 if x 2 C;+1 otherwise.Deflnition 1.4 (Lower Semi-continuous). A function f is said to be lowersemi-continuous (lsc) at a point „x 2 dom f iff(„x) • lim infx!„xf(x)While continuous functions are lsc, Figure 1.3 gives an example of a lscfunction which is not continuous everywhere.31.2. SubdifierentialFigure 1.3: An example of a lower semi-continuous function (lsc): it is lscat x=5 and continuous everywhere else.1.2 SubdifierentialSince convex functions are not always difierentiable we need to introducethe concept of a subgradient.Deflnition 1.5 (Subgradients). Let g : H !R[f+1g be a proper convexfunction and let x 2 dom g. A vector s in H satisfyingg(y) ‚ g(x)+ < s;y ¡x > 8y 2 His called a subgradient of g at x.Moreover, the set of all subgradients of g at x is called the subdifierentialof g at x, denoted by @g(x) , see Figure 1.4 for a graph of a function withsome subtangent lines. We note that if g is convex and difierentiable thesubgradient of g at x is 5g(x) such that @g(x) = f5g(x)g. An example ofwhen @g(x) = f5g(x)g is represented in the tangent of Figure 1.4 when x= 3, as this function is difierentiable there.41.2. SubdifierentialFigure 1.4: An example of a convex function with both subtangents andtangents.When g is twice continuously difierentiable we denote52g(x) its Hessianat x. The Hessian of g is deflned as the following symmetric matrix:52g(x) =26666666664@2g(x)@x21@2g(x)@x1@x2 ¢¢¢@2g(x)@x1@xn@2g(x)@x2@x1@2g(x)@x22 ¢¢¢@2g(x)@x2@xn¢ ¢ ¢ ¢¢ ¢ ¢ ¢¢ ¢ ¢ ¢@2g(x)@xn@x1@2g(x)@xn@x2 ¢¢¢@2g(x)@x2n37777777775:It is also worth mentioning that if the Hessian of a function exists thenwe have the following convexity test.Fact 1.1 (Convexity Test). [7, Theorem 2.69(i)] If we assume that g : H !Ris a twice continuously difierentiable function then g is convex if and onlyif its Hessian 52g(x) is positive semi-deflnite for all x 2 H.Recall that a Hessian matrix is positive semi-deflnite if and only if all itseigenvalues are greater or equal to zero [6].51.3. Legendre-Fenchel Conjugate1.3 Legendre-Fenchel ConjugateNow that we have deflned a convex, lsc and proper function letX = ff : H !R[f+1gjf is convex, lsc and propergbe the set of functions that we are working with for the remainder of thisthesis. In this section we deflne the Fenchel Conjugate that is important inthe fleld of convex analysis.Deflnition 1.6 (Legendre-Fenchel Conjugate). The Legendre-Fenchel Con-jugate (aka convex conjugate) of f 2 X is the function f⁄ 2 X deflnedbyf⁄(s) := supxf< s;x > ¡f(x)g 8s 2 H:Furthermore, we note that the Fenchel Biconjugate Theorem, as seen in[3, 4], states thatf 2 X () f⁄⁄ = f:We also deflne the relative interior of a convex set.Deflnition 1.7. The relative interior of a convex set C ‰ H is the interiorof C for the topology relative to the a–ne hull of C.We now present the Fenchel Duality Theorem which allows us to solveconvex optimization problems.Theorem 1.1 (Fenchel Duality). [3] Given two functions f and g in Xsuch thaty = infx2Hff(x)+g(x)gis a flnite number and assume the relative interiors of dom f and dom gintersect. Then¡y = minx⁄2H[f⁄(x⁄)+g⁄(¡x⁄)]is actually attained.6Chapter 2The Proximal AverageFrom now on we will assume that f0 and f1 are in X; ‚0 and ‚1 are two realnumbers strictly greater than zero, such that ‚0 +‚1 = 1; and „ is strictlygreater than zero.2.1 Main ResultsWe flrst start by deflning the proximal average.Deflnition 2.1 (Proximal Average). The ‚ weighted proximal average off0 and f1 with parameter „ isp„(f0;f1;‚0;‚1) = 1„"¡12 kxk2 + infx1+x2=x"‚0ˆ„f0 x0‚0¶+ 12    x0‚0    2!+‚1ˆ„f1 x1‚1¶+ 12    x1‚1    2!##:(2.1)Remark 2.1 (Simpliflcation of p). Since ‚0 +‚1 = 1 we can re-write equa-tion (2.1) as follows:p„(f0;f1;‚0;‚1) = p„(f0;f1;(1¡‚1);‚1):Then for ‚ = ‚1 we havep„(f0;f1;‚) = p„(f0;f1;(1¡‚);‚)):Fact 2.1 (Reformulations). [2, Proposition 4.3] By changing variables wesee that Equation (2.1) is equivalent to the following:p„(f0;f1;‚)(x) = inf(1¡‚)x0+‚x1=x[(1¡‚)f0(x0)+‚f1(x1)+1„ ((1¡‚)q(x0)+‚q(x1)¡q(x))‚:where q(x) = kxk22 .72.1. Main ResultsOne of the immediate consequences of Deflnition 2.1, as seen in [2], isthat p„(f0;f1;‚) = „¡1p1(„f0;„f1;‚). This consequence, in conjunctionwith the deflnition of the proximal average, provides us with the followingtwo properties:p„(f0;f1;0) = f0 and p„(f0;f1;1) = f1:The above properties are similarly seen in [2] for „ = 1. As a visualizationwe see in Figure 2.1 that p„(f0;f1;‚) is the conversion of f0 into f1 over‚ 2 [0;1], with constant „.−15 −10 −5 0 5 10 15050100150200Proximal Average (Quadratic to Quadratic)xPA 0     0.25  0.5   0.75  1    Figure 2.1: Plot of p1(x2;2x2;‚), for ‚ 2 [0;1].We now state some useful and interesting properties that have be previ-ously discovered.Fact 2.2 (Domain). [2, Theorem 4.6] We have the following domain prop-ertydom p„(f0;f1;‚) = (1¡‚) domf0 +‚ domf1:Fact 2.3. [3, Proposition 2.8] Let f 2 X. Thenp1(f;f⁄; 12) = 12 k¢k2 :Fact 2.4 (Fenchel Conjugate of the Proximal Average). [2, Theorem 5.1][3,Fact 2.3](p„(f0;f1;‚))⁄ = p„¡1(f⁄0;f⁄1;‚)82.2. Convexity Results2.2 Convexity Results2.2.1 Convexity of the Proximal Average with respect to xIn this section we will show that the function `(x) := p„(f0;f1;‚)(x), withf0;f1;‚ and „ flxed, is convex lsc, and proper.Proposition 2.1. [2, Corollary 5.3] Assume that „ > 0;‚ 2 [0;1] andf0;f1 2 X. Then the function` := x 7! p„(f0;f1;‚)(x)is convex for all x 2 dom p.Proof. Applying Fact 2.4 twice, we see that(p„(f0;f1;‚))⁄⁄ = (p„¡1(f⁄0;f⁄1;‚))⁄= p(„¡1)¡1(f⁄⁄0 ;f⁄⁄1 ;‚)= p„(f0;f1;‚):Hence, by the Fenchel Biconjugate Theorem we have that `(x) is convex.2.2.2 Convexity of the Proximal Average with respect to ‚In this section we will show that the function `(‚) := p„(f0;f1;‚)(x) isconvex, with f0;f1, „ and x flxed. In order to show that `(‚) is convex weneed to flrst recall some properties of marginal and perspective functions.We start with a property pertaining to marginal functions.Fact 2.5. [8, Theorem 2.1.3 (v)] Let ›;O ‰ H. If g := ›£O 7!R[f+1gis convex then the marginal function  associated to g is convex where : O 7!R;  (y) := infx2Xg(x;y)Before we state a useful property of perspective functions we flrst needto deflne them.Deflnition 2.2 (Perspective function). The perspective function of f :Rn !R[+1 is the function from R£Rn to R[f+1g given byPersp(f)(u;x) =‰ uf¡xu¢ if u > 0+1 if not.92.2. Convexity ResultsFact 2.6. [5, Proposition IV.2.2.1] [8, Section 1.2] If f :Rn !R[f+1g isproper convex, then its perspective function Persp (f) is proper and convexon R£Rn.Now we prove our main result for this section.Proposition 2.2. [1, Proposition 6.1] Assume that the functions f0;f1 arein X, x 2 dom p„(f0;f1;‚), and „ > 0. Then the function` : ‚ 7! p„(f0;f1;‚)(x)is convex for ‚ 2 [0;1].Proof. Using Deflnition 2.1 and Remark 2.1, with x1 = x¡x0, we have` : ‚ 7! p„(f0;f1;‚)(x) = infx0[g(‚;x0)]¡ q(x)„where q(x) = kxk22 andg(‚;x0) = (1¡‚)(„f0 +q) x01¡‚¶+‚(„f1 +q) x¡x0‚¶:Now in order to apply Fact 2.5 we need to flrst show that g is convex as afunction of both x0 and ‚. We note that`(‚) = 1„ minx0[Persp(„f0 +q)(1¡‚;x0)+Persp(„f1 +q)(‚;x¡x0)]¡q(x)„based on Deflnition 2.2. So using Fact 2.6 and [5, Proposition IV.2.1.5] (thecomposition of a convex function with an a–ne mapping is convex), thefunction g is convex. Now, using the convexity of the functions f0 and f1we have that the function g is bounded below for each value of ‚. Hence,Fact 2.5 applies thereby showing that ` is convex.2.2.3 Convexity of the Proximal Average with respect to „In this section we will show that the function `(„) := p„(f;‚)(x) is convex,with f0;f1 2 X, ‚0;‚1 2 [0;1] such that ‚0 +‚1 = 1 and x flxed.Proposition 2.3. [1, Proposition 5.7] Assume „ > 0;‚0 + ‚1 = 1;‚i ‚0;fi 2 X for i = 1;2 and take x 2 dom p„(f0;f1;‚0;‚1) = ‚0 dom f0 + ‚1dom f1. Then the function` : „ 7! p„(f0;f1;‚0;‚1)(x)is convex on ]0;+1[.102.2. Convexity ResultsProof. We begin by substituting x1 = (x¡‚0x0)=„ into Equation (2.1) anduse ‚0 +‚1 = 1 to obtain`(„) = infx0g(„;x0)whereg(„;x0) = ‚0f0(x0)+‚1f1 x¡‚0x0‚1¶+ ‚02„ kx0 ¡xk2 :Now we see that the function g is lower bounded on any set f„g£ H forany „ > 0, and is convex (as a composition of convex functions). So, Fact2.5 applies thereby proving that ` is convex.2.2.4 Further Investigation of the Proximal AverageIn this section we present our results on the join convexity of the proximalaverage. We begin with a computation of the proximal average that will beused to build our examples.Lemma 2.1 (Proximal Average of energy functions). [2, Example 4.5] Letf0 = fi0q and f1 = fi1q where fi0 and fi1 are strictly positive numbers andq(x) = kxk2 =2. Thenp„(f0;f1;‚) =ˆ (1¡‚)fi0 ¡„¡1 +‚fi1 ¡„¡1¶¡1¡„¡1!q:Proof. For q(x) = kxk2 =2 in Remark 2.1 we see that using Fact 2.4 andsome basic properties of conjugacy, namely (fiq)⁄ = q⁄(fi¢), we havep„¡1(f0;f1;‚) = ((1¡‚)(fi0q +„q)⁄ +‚(fi1q +„q)⁄)⁄ ¡„q= 1¡‚fi0 +„q +‚fi1 +„q¶⁄¡„q= 1¡‚fi0 +„q +‚fi1 +„¶¡1q ¡„q:Thus,p„(f0;f1;‚) =ˆ 1¡‚fi0 ¡„¡1 +‚fi1 ¡„¡1¶¡1¡„¡1!q:112.2. Convexity ResultsWe now present the main results for this section.Proposition 2.4. The following functions are not always convex:`x‚ : (x;‚) 7! p„(f0;f1;‚)(x)`x„ : (x;„) 7! p„(f0;f1;‚)(x)`‚„ : (‚;„) 7! p„(f0;f1;‚)(x)when f0;f1 are two convex lsc proper functions, ‚ 2 [0;1] and „ > 0.Proof. We need to show that `x‚;`x„ and `‚„ are not always convex. Soconsider the following quadratic example:Let f0 and f1 be in X such thatf0 = fi0qf1 = fi1qwhere fi0 and fi1 are strictly positive numbers and q is the quadratic energyfunction: q(x) = 12x2 (when x 2R). Then using Lemma 2.1 we havep„(f0;f1;‚) =ˆ (1¡‚)fi0 ¡„¡1 +‚fi1 ¡„¡1¶¡1¡„¡1!q:To show that `x‚ (resp. `x„ and `‚„) is not convex we use Fact 1.1 and showthat the Hessian of p„(f0;f1;‚) is not positive semi-deflnite, for „ (resp. ‚and x) constant.To start, consider p„(f0;f1;‚) with „ = 1, so as to show that `x;‚(x;‚)is not convex. Now,p1(f0;f1;‚)(x) = 12ˆ (1¡‚)fi0 ¡1 +‚fi1 ¡1¶¡1¡1!x2:Then with fi0 = 2 and fi1 = 4 we have`x‚(x;‚) = p1(f0;f1;‚)(x) = 12ˆ (1¡‚)+ ‚3¶¡1¡1!x2and the Hessian of `x‚, at x = 2 and ‚ = 12, isHx‚ =• 12 33 6‚:122.2. Convexity ResultsThe determinant of Hx‚ is ¡6 which is enough to show that Hx‚ is notpositive semi-deflnite, since ¡6 implies that one of the eigenvalues of thedeterminant must be negative. Hence `x‚(x;‚) is not convex.Similarly, we can show that `x;„ is not always convex by holding ‚constant. So, let ‚ = 12 thenp„(f0;f1; 12)(x) = 120@ˆ 12fi0 ¡„¡1 +12fi1 ¡„¡1!¡1¡„¡11Ax2and when fi0 = 2 and fi1 = 4 we have`x„(x;„) = p„(f0;f1; 12)(x) = 120@ˆ 122¡„¡1 +124¡„¡1!¡1¡„¡11Ax2:Now, the Hessian of `x„, at x = 2 and „ = 1, isHx„ =• 129292 ¡192‚:The determinant of Hx„ is ¡25 so `x„(x;„) is not convex.Finally, to show that `‚„(‚;„) is not always convex we consider p„(f;‚)with f0(x) = 2q(x) and f1(x) = 4q(x), evaluated at x = 2. Then`‚„(‚;„) = p„(f0;f1;‚)(2) = 2ˆ (1¡‚)2¡„¡1 +‚4¡„¡1¶¡1¡„¡1!and the Hessian of `‚„, at „ = 1 and ‚ = 12, isH‚„ =• 6 11 ¡192‚:The determinant of H‚„ is ¡58 so `‚„(‚;„) is not convex.Altogether, we proved that each of `x‚;`x„ and `‚„ are not alwaysconvex.Corollary 2.1. The following function is not always convex:` : (x;‚;„) 7! p„(f;‚)(x)where f = (f0;f1) 2 X £X, ‚ 2 [0;1] and „ > 0.132.2. Convexity ResultsProof. Corollary 2.1 is a direct result of Proposition 2.1.Proposition 2.5. The following function is not always convex:` : (f0;f1) 7! p„(f0;f1;‚)where f0;f1 2 X, ‚ 2 [0;1] and „ > 0.Proof. In order to flnd a function `(f0;f1) which is not always convex weneed to show, by Deflnition 1.2, that there exists an x 2R such thatp„(¿(f0;f1)+(1¡¿)(g0;g1);‚)(x) > ¿p„((f0;f1);‚)+(1¡¿)p„((g0;g1);‚)(x)where f0;f1;g0 and g1 are all in X and ‚;¿ 2 [0;1]. So, letf0 = fi0qf1 = fi1qg0 = fl0qg1 = fl1qwhere q is the quadratic energy function q(x) = 12x2, when x 2R. Then forfi0 = 1;fi1 = 2;fl0 = 3 and fl1 = 4 the left-hand side isp„(¿(f0;f1)+(1¡¿)(g0;g1);‚) = p„((¿q +(1¡¿)3q;¿2q +(1¡¿)4q);‚):Then with „ = 5;¿ = 12 and ‚ = 12, we havep„((¿q +(1¡¿)3q;¿2q +(1¡¿)4q);‚) = p5¡2q;3q; 12¢ = 6527q:On the other hand, the right-hand side is¿p((f0;f1);‚)+¿p((g0;g1);‚) = ¿p((q;2q);‚)+(1¡¿)p((3q;4q);‚)= 12p((q;2q); 12)+ 12p((3q;4q); 12)= 12 2317q¶+ 12 12737 q¶= 1505629 q:Therefore,p„(¿(f0;f1)+(1¡¿)(g0;g1);‚)(x) > ¿p„((f0;f1);‚)+(1¡¿)p„((g0;g1);‚)(x)142.2. Convexity Resultssince6527 … 2:41 > 2:39 …1505629 :Hence, `(f0f1) is not always convex.To conclude this section, we show that extending the proximal averageto ‚ 2R does not provide a useful tool as the following example shows theinflmum may no longer be attained.Example 2.1. Using Deflnition 2.1, with Remark 2.1, „ = 1 and x1 =x¡x0, we havep1(f0;f1;‚) = ¡kxk22 +infx0"‚ˆf0 x0(1¡‚)¶+ 12    x0(1¡‚)    2!+‚ˆf1 x¡x0‚¶+ 12    x¡x0‚    2!##: (2.2)Then in Equation (2.2) for f0(x) = fi0x + fl and f1(x) = fi1x + fl1, withx 2R, we have¡x22 +infx0•(1¡‚) fi0 x0(1¡‚) +fl0 + x202(1¡‚)2¶+‚ fi1x¡x0‚ +fl1 + (x¡x0)22‚2¶‚which can be further reduced to¡ x22 +infx0•fi0x0 +fl0 ¡‚fl0 + x202(1¡‚) +fi1(x¡x0)+‚fl1 +x22‚ ¡x0‚ +x202‚‚:(2.3)Then the dominating term of Equation (2.3) isx202(1¡‚) +x202‚) =x20‚+x20(1¡‚)2‚(1¡‚)= x202‚(1¡‚)which requires 2‚(1¡‚) > 0 for the inflmum to be flnite. Thus we require‚ 2]0;1[.15Chapter 3Plotting the ProximalAverageGiven two functions f0 and f1 we want to plot the proximal average of thesefunctions for ‚ 2 [0;1].3.1 New Plotting functionCurrently the Computation Convex Analysis Numerical Library has Scilabfunctions that can be used to plot the proximal average of two piecewiselinear-quadratic (PLQ) functions, namely plq plotpa. A PLQ function isdeflned on a set of disjoint domains where for each domain the function iseither a linear or quadratic polynomial. The plq plotpa function is deflned toplot the proximal average curve based on ‚, as seen in Figure 3.1. However,plq plotpa is not always very e–cient as it may plot the same proximalaverage curve for a given ‚ value when the ‚ values are close together.−1.0 −0.8 −0.6 −0.4 −0.2 0.0 0.2 0.4 0.6 0.8 1.00.00.20.40.60.81.01.21.41.61.82.0 0     0.25  0.5   0.75  1    Figure 3.1: Plot of p1(x2;2x2 +1;‚), for ‚ 2 [0;1], done in Scilab using theoriginal command plq plotpa.163.1. New Plotting functionSo, we created a new plotting function, plot proxavg, that plots eachpixel of the proximal average given two PLQ functions, f0 and f1. That isto say for each (x;y) we assign the appropriate ‚ value wherey = p1(f0;f1;‚)(x); (3.1)as seen in Figure 3.2. .−1.105−0.860−0.614−0.368−0.1230.1230.3680.6140.8601.105−0.1050.1400.3860.6320.8771.1231.3681.6141.8602.105 0     0.25  0.5   0.75  1    Figure 3.2: Plot of p1(x2;2x2 +1;‚), for ‚ 2 [0;1], done in Scilab using thenew command plot proxavg .The plot proxavg command requires solving Equation (3.1) for ‚. Thishowever is not a simple task given the equation of the proximal average,which is why we have taken a difierent approach. The approach that we havetaken assumes f0, f1 are convex and f0 • f1 so that ‚ is always increasing.Then for every x value we can determine ‚ starting at y0 = f0(x) for ‚ = 0and going to y1 = f1(x) for ‚ = 1, sincep1(f0;f1;0)(x) = f0(x) and p1(f0;f1;1)(x) = f1(x):The ‚ values in between y0 and y1, for each (x;y) where y0 < y < y1, canbe determined by incrementally increasing ‚ until it generates a newy valuethat is as close to y as possible.17Chapter 4ConclusionWe have answered many of the remaining questions pertaining to the prox-imal average including showing that(x;‚;„;f) 7! p„(f;‚)(x)is always convex in x;‚ and „ but not always convex in (x;‚);(x;„), (‚;„)and (f0;f1). Our plotting algorithm needs further reflnement. It cur-rently uses a linear search to compute ‚. Implementing a binary searchwould reduce the computation time. Furthermore, the bounds used inthe binary search could be improved by using the fact that the function‚ 7! p(f0;f1;‚)(x) is convex.Future work in this area may focus on deflning a partial difierentialequation equivalent to the proximal average. It is believed that one existsas the proximal average can be described as the curve evolution from f0 tof1 over ‚ [1].18Bibliography[1] Heinz H. Bauschke, Rafal Goebel, Yves Lucet, and X. Wang. The prox-imal average: applications, extensions and computation. 2008.[2] Heinz H. Bauschke, Rafal Goebel, Yves Lucet, and X. Wang. The prox-imal average: Basic theory. SIAM J. Optim., 2008.[3] Heinz H. Bauschke, Yves Lucet, and Michael Trienis. How to transformone convex function continuously into another. SIAM Rev., 50(1):115{132, July 2008.[4] Jonathan M. Borwein and Adrian S. Lewis. Convex Analysis andNonlinear Optimization. CMS Books in Mathematics/Ouvrages deMath¶ematiques de la SMC, 3. Springer-Verlag, New York, 2000. Theoryand examples.[5] Jean-Baptiste Hiriart-Urruty and Claude Lemar¶echal. Convex Analy-sis and Minimization Algorithms, volume 305{306 of Grundlehren derMathematischen Wissenschaften [Fundamental Principles of Mathemat-ical Sciences]. Springer-Verlag, Berlin, 1993. Vol I: Fundamentals, VolII: Advanced theory and bundle methods.[6] D. C. Lay. Linear Algebra and Its Applications. Addison-Wesley Long-man Inc., Reading, Massachusetts, second edition, 2000.[7] A. Ruszczy¶nski. Nonlinear Optimization. Princeton University Press,Princeton, New York, 2006.[8] C. Z‚alinescu. Convex Analysis in General Vector Spaces. Grundlehrender Mathematischen Wissenschaften [Fundamental Principles of Mathe-matical Sciences]. World Scientiflc, New Jersey, 2002.19

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
Russia 11 0
China 7 7
United States 5 0
United Kingdom 5 0
Germany 4 3
Canada 1 0
City Views Downloads
Saint Petersburg 11 0
Shenzhen 7 7
Southend-on-Sea 5 0
Ashburn 4 0
Unknown 2 1
Heidelberg 2 2
San Francisco 1 0
Montreal 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.52966.1-0052226/manifest

Comment

Related Items