Computing the Subdifferential ofConvex Piecewise Linear-CubicFunctionsbyAaron Matthew MahnicA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFB.SC. COMPUTER SCIENCE HONOURSinTHE COLLEGE OF GRADUATE STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)April 2021© Aaron Matthew Mahnic, 2021The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Computing the Subdifferential of Convex Piecewise Linear-Cubic Functionssubmitted by Aaron Matthew Mahnic in partial fulfilment of the re-quirements of the degree of B.Sc. Computer Science HonoursDr. Yves Lucet, I. K. Barber School of Arts & SciencesSupervisoriiAbstractComputational Convex Analysis (CCA) studies the computation of con-vex operators commonly used in convex analysis. CCA allows researchersto visualize non-trivial convex transforms and build an intuition from theseexamples. Using the convexity and structure of piecewise linear cubic (PLC)functions as a model, the foundation for a new CCA toolbox has been im-plemented. The CCA toolbox is built in MATLAB and includes extensivetest coverage and examples. In addition, it is free and open source.The CCA toolbox provides several plotting methods to visualize PLCfunctions and their properties. Plotting the domain of a PLC function isa useful tool for both research and visualizing the correctness of computedoutput. Within a PLC function, any polyhedral set can be unbounded andplotting the domain of such a function would lead to an unbounded plotwhich cannot be displayed. We introduce a method that manipulates thePLCVC data structure in the CCA toolbox to plot an unbounded domainwithin a specified window.A convex analysis operation of considerable interest is the Legendre-Fenchel transform, also known as the Fenchel conjugate. The computationof the Fenchel conjugate can be done in linear time. As a first step inimplementing a linear time conjugate computation for the CCA toolbox, weintroduce a new class (PLCVP) that implements a method for computingthe subdifferential at any point of a PLC function.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Preliminaries . . . . . . . . . . . . . . . . . . . . . . 32.1 Piecewise Linear-Cubic Functions . . . . . . . . . . . . . . . . 5Chapter 3: Plotting Unbounded Piecewise Polynomials . . . . 73.1 PLCVC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.1.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . 73.1.2 Computing Boundedness . . . . . . . . . . . . . . . . . 93.2 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2.1 Example Plots . . . . . . . . . . . . . . . . . . . . . . 13Chapter 4: Computing the Subdifferential of PLC Functions 174.1 PLCVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Subdifferentials of PLC Functions . . . . . . . . . . . . . . . . 184.2.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . 204.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 214.2.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 25ivTABLE OF CONTENTSChapter 5: Numerical Experiments . . . . . . . . . . . . . . . . 275.0.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . 275.0.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . 295.0.3 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . 31Chapter 6: Conclusion and Future Work . . . . . . . . . . . . . 33Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34vList of TablesTable 3.1 Flag for edge . . . . . . . . . . . . . . . . . . . . . . . 9Table 4.1 Cases for the grd array . . . . . . . . . . . . . . . . . . 22viList of FiguresFigure 3.1 Extending non-extreme vertices . . . . . . . . . . . . 11Figure 3.2 Plot domain perspective . . . . . . . . . . . . . . . . 12Figure 3.3 Cubic function domain plot . . . . . . . . . . . . . . . 14Figure 3.4 Quadratic function domain plot . . . . . . . . . . . . 15Figure 3.5 Plot domain modified bounding box . . . . . . . . . . 16Figure 4.1 Point outside vs. point on the interior of a function’sdomain . . . . . . . . . . . . . . . . . . . . . . . . . . 21Figure 4.2 Point on an edge and vertex comparison . . . . . . . 23Figure 4.3 Points on the boundary . . . . . . . . . . . . . . . . . 24Figure 5.1 Plot of the l1 norm function . . . . . . . . . . . . . . 27Figure 5.2 One norm subdifferential on face . . . . . . . . . . . . 28Figure 5.3 One norm subdifferential on an edge . . . . . . . . . . 29Figure 5.4 One norm subdifferential on vertex . . . . . . . . . . 30Figure 5.5 PLC function with two faces plot . . . . . . . . . . . 30Figure 5.6 Subdifferentials on an edge . . . . . . . . . . . . . . . 31Figure 5.7 Bounded triangular function plot . . . . . . . . . . . 32Figure 5.8 Subdifferential normal cone . . . . . . . . . . . . . . . 32viiAcknowledgementsThank you to Dr. Yves Lucet for the opportunity to work and learnunder his guidance. This has been an invaluable experience in more waysthan I can put into words.viiiDedicationTo my fiance´ Nicole and my daughter Sophia.ixChapter 1IntroductionComputational Convex Analysis (CCA) has proven to be a relevant topicand has found applications in areas such as computer vision, medical imag-ing and signal/image recovery [Luc10]. There are a number of fundamentaltransforms that arise in convex analysis that are integral to these appli-cations. Robot navigation uses distance transform algorithms that are aspecial case of computing the Moreau envelope (also called the Moreau-Yosida approximate, Yosida Approximate or Moreau-Yosida regularization)[Luc10]. Medical imaging applies the Legendre-Fenchel conjugate transformto detect singularities in CT scans [Luc10, Qu11]. Lastly, signal and imagerecovery makes use of a combination of the former two transforms, called theproximal average, to recover the original signal or image from a corruptedversion [CW05].Computer-aided convex analysis focuses on visualizing fundamental trans-forms of convex analysis when applied to functions of typically one or twovariables [Haq17]. A CCA toolbox was developed to perform these trans-forms on both univariate and bivariate functions. The latest version of theCCA toolbox is built in MATLAB [MAT21]. The CCA toolbox includesextensive test coverage and examples and is free and open source.The new CCA toolbox represents bivariate piecewise linear-cubic (PLC)functions in multiple data types. The PLCVC class represents these PLCfunctions using a vertex and coefficient representation and is based on thestructure PLC functions described in [SL21]. The PLCVP class uses a point-wise representation of PLC functions to use graph-matrix calculus (GMC)algorithms. Using GMC algorithms we can compute the Legendre-Fenchelconjugate and other convex analysis transforms in linear time [Haq17, GL11].In this thesis, we characterize a data structure using vertex and coeffi-cient representation of the PLCVC class and use this data structure to plotthe domains of unbounded PLC functions in Chapter 3. In Chapter 4, wesummarize a pointwise representation of PLC functions and show how thepointwise representation can be used to compute the Fenchel conjugate. Weshow subgradient calculus rules for PLC functions and describe how theserules are applied in a new algorithm to compute the subdifferential at any1Chapter 1. Introductionpoint of a PLC function. Finally, in Chapter 5 we show several examples ofsubdifferential computations for PLC functions.2Chapter 2PreliminariesThis chapter reviews several key definitions that will be used throughoutthis paper.Definition 2.1. [Bec17] (Convex Set) A set C ∈ Rn is convex if ∀x, y ∈ Cand λ ∈ [0, 1] it holds that:λx+ (1− λ)y ∈ C.Definition 2.2. [RW98] (Convex Hull) For a set C ⊂ Rn, the convex hullof C consists of all the convex combinations of elements of C:coC = {p∑i=1λixi | xi ∈ C, λi ≥ 0,p∑i=1λi = 1, p ≥ 0}.Fact 2.3. The convex hull of a non-empty set C is the smallest convex setthat contains C.Definition 2.4. [Bec17] (Normal Cone) For a set C ⊂ Rn and a pointx ∈ C, the normal cone of C at x is defined asNC(x) = {s ∈ Rn | 〈s, z − x〉 ≤ 0, ∀z ∈ C}.Definition 2.5. (Proper Function) A function f : Rn → R ∪ {−∞,+∞},is said to be a proper function if dom(f) = {x ∈ Rn : f(x) < +∞} 6= ∅ andf(x) > −∞ for all x ∈ Rn.Definition 2.6. (Convex function) A proper function f : Rn → Rn∪{+∞}is convex if its domain is a convex set and for any two points, x1,x2 ∈ domfand θ ∈ [0, 1]f(θx1 + (1− θ)x2) ≤ θf(x1) + (1− θ)f(x2).Definition 2.7. (Subgradient) For a proper function f : Rn → (−∞,∞]with x ∈ dom(f), a vector g ∈ Rn is called a subgradient of f at x iff(y) ≥ f(x) + 〈g, y − x〉, ∀y ∈ Rn.3Chapter 2. PreliminariesDefinition 2.8. (Subdifferential) The set of all subgradients at f at x iscalled the subdifferential of f at x and denoted by∂f(x) = {s ∈ Rn | f(y) ≥ f(x) + 〈s, y − x〉,∀y ∈ Rn}.Definition 2.9. [RW98, Theorem 9.61] (Clarke Subdifferential) Let f :Rn → (−∞,∞] be a proper convex function. The Clarke subdifferential atx ∈ Rn is given by∂¯f(x) = co{ limi→∞∇f(xi) : xi → x and ∇f(xi) exists}.In addition, when f is convex then ∂¯f(x) = ∂f(x).Fact 2.10. [Bec17, Theorem 3.33] (The Subdifferential at Points of Dif-ferentiability) Let f : Rn → (∞,∞] be a proper convex function, and letx ∈ int(dom(f)). If f is differentiable at x, then ∂f(x) = {∇f(x)}.Fact 2.11. [Bec17, Theorem 3.36] (Subdifferential of the Sum) Let f1, f2 :Rn → (∞,∞] be proper convex functions, and let x ∈ dom(f1) ∩ dom(f2).(a) The following inclusion holds,∂f1(x) + ∂f2(x) ⊆ ∂(f1 + f2)(x).(b) if x ∈ int(dom(f1)) ∩ int(dom(f2)), then∂(f1(x) + f2(x)) = ∂f1(x) + ∂f2(x).Definition 2.12. (Indicator Function) For a subset C ⊂ Rn, the indicatorfunction of C is given byδC(x) ={0 x ∈ C,∞ x /∈ C.Fact 2.13. (Subdifferential of the Indicator Function) Suppose that C ⊆ Rnwith the indicator function δC . The subdifferential of δc is given by∂δC(x) = NC(x),∀x ∈ C.That is, the subdifferential of the indicator function at a point x is the normalcone NC(x) of C.Definition 2.14. [RW98] (Fenchel Conjugate) For any function f : Rn →R ∪ {+∞}, the conjugate function f∗ : Rn → R ∪ [−∞,+∞] is given byf∗(s) = supx∈Rn{〈s, x〉 − f(x)}.42.1. Piecewise Linear-Cubic Functions2.1 Piecewise Linear-Cubic FunctionsDefinition 2.15. [RW98] (Polyhedral Set) A set C ⊂ Rn is said to be apolyhedral set if it can be expressed as the intersection of a finite numberof closed half-spaces or hyperplanes. The polyhedral set can equivalently beexpressed as a finite number of linear constraints.Definition 2.16. (Polyhedral decomposition) The set C = {Ck : k ∈ K}where K is a finite index set, is called a polyhedral decomposition of D ⊂ Rnif it satisfies the following conditions(i) all of its members Ck are polyhedral sets,(ii)⋃k∈K Ck = D,(iii) for all k ∈ K, dim Ck = dim D,(iv) riCk1 ∩ riCk2 = ∅, where k1, k2 ∈ K, k1 6= k2.Definition 2.17. (Polyhedral subdivision) The set C is a polyhedral sub-division if C is a polyhedral decomposition and the intersection of any twomembers of C is either empty or a common subset of both.Definition 2.18. (Piecewise Linear-Cubic Function) A Piecewise LinearCubic function is a special case of piecewise polynomial functions with apolyhedral domain such that on each polyhedral set the function is definedby either a linear, quadratic or cubic function.Similarly, a Piecewise Linear Quadratic (PLQ) function would be definedas having either a linear or quadratic function on each polyhedral set.Definition 2.19. [Jak13, GJL14] (Edge) For any x1, x2 ∈ Rn and x1 6= x2,we define an edge by the setE = {x ∈ Rn : x = λ1x1 + λ2x2, λ1 + λ2 = 1}.We classify edges as:(i) Segment: When λ1, λ2 ≥ 0.(ii) Ray: When λ1 ≥ 0.(iii) Line: When λ1, λ2 ∈ R.Definition 2.20. (Vertex) A vertex is either a starting point of a ray, oneof the end points of a segment, or it is an isolated point.52.1. Piecewise Linear-Cubic FunctionsDefinition 2.21. (Face) A set F is a face of a polyhedral P if dim(F ) =dim(P )− 1 and there exists a linear subspace H such that F = H ∩ P .Definition 2.22. [BJS11] (Direction, Extreme Direction) Given a convexset C, a nonzero vector d is a direction of C if for each x ∈ C the ray{x+ λd : λ ≥ 0} also belongs to the set.An extreme direction of a convex set is a direction of the set that cannotbe represented as a positive combination of two distinct directions of theset.Definition 2.23. [Roc70] (Extreme Point) Given a convex set C, a pointx ∈ C is an extreme point of C if x cannot be written as λy + (1− y)z fory, z ∈ C,z 6= x, and 0 < λ < 1.Fact 2.24. [Haq17] (Representation of a Polyhedral Set) Let C be a polyhe-dral set. There exists extreme points xi and extreme directions dj such thatany x ∈ C can be written,x =k∑i=1λixi +l∑i=1µidi = 1,where∑ki=1 λi = 1, λi ≥ 0, i = 1, ..., k, µi ≥ 0, i = 1, ..., l.In addition, if C is bounded then the set of extreme directions is empty.If C is not bounded then the set of extreme directions is nonempty and hasa finite number of elements.Definition 2.25. (Planar Graph) A graph G = (V , E) is said to be a planargraph if it can be drawn in a plane with no two edges crossing each otherexcept at a vertex to which they are incident.Fact 2.26. [HL18, Proposition 2.13] Let G = (V ,E) be a connected planargraph with ne edges and nv vertices. Assume nv ≥ 3. Then ne ≤ 3nv.6Chapter 3Plotting UnboundedPiecewise Polynomials3.1 PLCVCThe PLCVC class within the CCA toolbox implements a data type forbivariate PLC functions. The class is able to represent both bounded andunbounded PLC functions.3.1.1 Data StructureTo store a PLC function, each polyhedral set is divided into vertices,edges, and faces. Vertices indicate either the intersection of edges or asingle point. Edges are either a line segment between two vertices or a raywhich extends infinitely in one direction. If the interior of the polyhedralset is non-empty it is called a face.As input, PLCVC takes in four specific matrices: V, E , f and F . Thematrix V contains the coordinates (x, y) ∈ V for each vertex. Edges arestored in the edge list E where each ei ∈ E is a pair of indices (v1, v2)that index the two endpoints of the edge in the vertex list V. If an edgeis a ray, then a binary flag for each edge ei ∈ E is set to specify that theedge extends infinitely past the vertex v2 ∈ ei. For a PLC function with npolyhedral sets, the coefficients for the polynomial function associated witheach face are provided in an n × 10 matrix f . The matrix F indexes thefunction indices from f for the faces to the left and right of each edge ei ∈ E .In matrix form, the input is given byV =x1 y1x2 y2. .. .xn yn , E =e1,1 e1,2 b1e2,1 e2,2 b2. . .. . .en,1 en,2 bn ,F =i1,1 i1,2i2,1 i2,2. .. .in,1 in,2 ,73.1. PLCVCf =c1,1 c1,2 c1,3 c1,4 q1,1 q1,2 q1,3 l1,1 l1,2 l1,3c2,1 c2,2 c2,3 c2,4 q2,1 q2,2 q2,3 l2,1 l2,2 l2,3. . . . . . . . . .. . . . . . . . . .cn,1 cn,2 cn,3 cn,4 qn,1 qn,2 qn,3 ln,1 ln,2 ln,3 .Note that not every input matrix needs to be defined with values, as longas the domain of the polyhedral partition the input represents is connected.For example, a cubic function with an infinite domain that has no verticesand no edges can be represented using an empty list for both V and E .Example 3.1. Consider the following example of a PLC functionf(x) =−x3 − y3 + x2 + y2 x ≤ 0, y ≤ 0;−x3 + 2y3x2 + 2y2 x ≤ 0, y ≥ 0;3x3 + 2y3 + 2x2 + 2y2 x ≥ 0, y ≥ 0;3x3 − y3 + 2x2 + y2 x ≥ 0, y ≤ 0.The function f is continuous with a full domain. It has four distinct poly-hedral faces. They can be represented using the V, E , f , F data structureas:V =0 0−1 00 11 00 −1 , E =1 2 01 3 01 4 01 5 0 ,f =−1 0 0 −1 1 0 1 0 0 0−1 0 0 2 1 0 2 0 0 03 0 0 2 2 0 2 0 0 03 0 0 −1 2 0 1 0 0 0 ,F =1 22 33 44 1 .If we take the first row from f as f1f1 =[−1 0 0 −1 1 0 1 0 0 0] ,83.1. PLCVCthen we can see that,f1 ∗x3x2yxy2y3x2xyy2xyconstant= −x3 − y3 + x2 + y2,which represents the first component in the PLC function f .3.1.2 Computing BoundednessThe edge list E includes a binary flag for each ei ∈ E that indicateswhether the edge is a ray or a line segment as shown in Table 3.1. Uponinstantiation this flag is used to determine if a PLC function is unboundedor not.Flag Edge type1 line segment0 rayTable 3.1: Flag for edgeProposition 3.2. For a convex piecewise polynomial function f with a listof edges E, if there exists at least one ray in E, then dom(f) is unbounded.Proof. Let C be the closed convex set dom(f). If there is at least one ray inthe edge list of f , then the set of extreme directions of C is nonempty. ByFact 2.24, if the set of extreme directions is nonempty, then C is unbounded.Thus, dom(f) is unbounded.The converse of Proposition 3.2 is not necessarily true. There are twocases of PLC functions that will have no edges in the edge list E to consider,(i) A function with a full domain.(ii) A needle function (a function whose domain is a single point).93.2. PlottingDistinguishing between these two cases is done by looking at the ver-tex matrix V . The function from (i) will have no vertex, while the needlefunction (ii) will have a single vertex.To determine if a PLC function is bounded or not, PLCVC checks forthe presence of rays by scanning the binary flags in E as defined in Table 3.1.If there are no edges in E , then the total number of vertices in V is usedto determine boundedness. As both the edge list E and vertex list V areprovided to PLCVC at input as a planar graph. The algorithm runs throughN edges and M vertices in O(N + M). For a planar graph, by Fact 2.26,we have that M ≤ 3N and thereforeO(N +M) = O(N + 3N) = O(N).Checking boundedness is performed in linear time where N is the numberof vertices in a PLC function f .3.2 PlottingPLCVC includes a function to plot bounded domain PLC functions. Weextended this function to plot functions with unbounded domains. Whenthe domain is unbounded we replace the function f with f + δD where δDis the indicator function of a box D.For any point in dom(f) ∩D, the function will be equal to f(x), whilefor any other point, it will be infinity. This gives us dom(f) ∩ D which isthe domain of f restricted to the box D. We specify D as a bounding boxof the region of interest on dom(f) that we want to plot.Example 3.3. Consider a PLC function with a vertex representation storedasV =0 0−1 00 11 00 −1 , E =1 2 01 3 01 4 01 5 0 ,f =−1 0 0 −1 1 0 1 0 0 0−1 0 0 2 1 0 2 0 0 03 0 0 2 2 0 2 0 0 03 0 0 −1 2 0 1 0 0 0 ,F =1 22 33 44 1 .103.2. Plotting(a) Graph of vertices for a PLCfunction f .(b) Vertices after non-extreme ver-tices have been extended by a fac-tor of t.Figure 3.1: Graph of vertices for a PLC function f before and after extendingnon-extreme verticesIn this example, every edge is a ray so the only extreme point is the vertex(0,0). After extending the non-extreme vertices by a magnitude t = 1000,the resulting matrix Ve will beVe =0 0−1000 00 10001000 00 −1000 .A visual representation of the non-extreme vertex extension is illustratedin Figure 3.1(b).The final step requires computing an intersection for each face. Let Bbe a matrix of points (xi, yi) that represent the size of the window to ploton such thatB =[xmin yminxmax ymax].We compute a bounding box as a polygon using the minimum and max-imum x, y coordinates in B. The bounding box polygon represents the win-dow to plot the output to. Using the extended vertex list Ve, a polygon pi isconstructed for each face. The intersection of each face polygon pi with the113.2. PlottingFigure 3.2: This figure shows how the plot unbounded domain algorithmworks on a PLC function with four unbounded faces. Each coloured polygonon the plane represents a face. The black square represents the boundingbox which is displayed as output.bounding box computed from B represents the domain of each polyhedralset in a PLC function. A visualization of the bounding box overlaying thedomain of a function that has been restricted to D is shown in Figure 3.2.Plotting each pi together shows the entire domain of a PLC function withinthe specified bounding box B.123.2. PlottingAlgorithm 1: Plot Unbounded Domaininput : P (PLCVC polyhedral set), xAxis (1x2 matrix specifyingthe boundary along the x axis to plot), yAxis (1x2 matrixspecifying the boundary along the y axis to plot)output: 2d plot of the resulting domain for Pbeginif Domain is unbounded theneV s← extendNonExtremeVertices(P );facePolygons← ∅;boundaryView = createPolygon(xAxis,yAxis);foreach facei ∈ P doCompute the indices of each vertex v ∈ P.Pi into iX, iY ;[X,Y ]← indices of each point (x, y)∀iX, iY ∈ eV s;Compute the boundary B of points (x, y) ∈ [X,Y ];boundaryFace = createPolygon(B);facePolygons ← boundaryV iew ∩ boundaryFace;endplot(each polygon f ∈ facePolygons);elseplotBoundedDomain();endendProposition 3.4. Consider a PLC function with N vertices and M faces,the plotBoundedDomain function runs in linear time O(N)Proof. The computation to restrict the function f with f|D is done in O(N)by computing a new set of vertices VD from the vertex matrix V. Computingthe intersection is done by building a polygon from the vertices in Vd andtaking the intersection of this polygon with the bounding box which requiresus to loop through the N vertices in VD. Total runtime is dominated by thenumber of vertices and thus O(N).Therefore, the algorithm runs in linear time.3.2.1 Example PlotsCubic FunctionRecall the cubic function from Example 3.1. It is comprised of fourunbounded faces. Figure 3.3(a) shows a plot of the function in R3, whileFigure 3.3(b) shows the plot of the domain for this function in R2. The133.2. Plottingfour colours of each plot each represent a face. We see the output of theplotUnboundedDomain method correlates with the function plot.(a) Plot of a cubic PLC function (b) Plotted domain of the samefunctionFigure 3.3: PLCVC plot of the function and domain of a cubic convex PLCfunction. In both plots, the different colours represent different faces.Quadratic FunctionConsider the function,f(x, y) ={x2 + y2 + 2xy x ≥ 0, y ≥ 0;∞ otherwise.A plot of this function is shown in Figure 3.4(b). The domain of f isrestricted to the first quadrant of the Cartesian plane. Using a boundingbox B = [1, 1] × [1, 1], we expect to see the domain plotted only wherex, y ≥ 0. The plot of dom(f) is shown in Figure 3.4(b). In the figure, we seedom(f) is correctly plotted on the first quadrant, while any (x, y) /∈ dom(f)are not plotted.Changing Bounding BoxThe bounding box that determines the region of interest to plot can bepassed by the user to the plotUnboundedDomain method. In this examplewe show how changing the bounding box changes the output. Consider thefunction,143.2. Plottingf(x, y) =x2 + y2 x ≥ 0, y ≥ 0;−x2 + y2 x < 0, y ≥ 0;∞ otherwise.The domain of this function is restricted to positive y values. The func-tion has two faces separated by an edge along the y-axis. For each plotin 3.5 we denote the face on the left F1 and the face on the right F2. InFigure 3.5(a) the plot of dom(f) is shown centered on the origin. In Fig-ure 3.5(a), we specify a new bounding box and shift the window along thex-axis by 0.5 units. The effect this has on the plot is that a larger area ofthe domain for the face F1 is shown while the area of the domain for faceF2 is smaller as compared to Figure 3.5(a). In Figure 3.5(c) we shift thebounding box used in Figure 3.5(a) up by one unit along the y-axis. Thefunction is defined everywhere above the x-axis and the plot shows a fulldomain in the window accordingly.(a) Plot of a quadratic PLC func-tion(b) Plotted domain showing thefunction is restricted to the firstquadrantFigure 3.4: Plot of a quadratic function and the plot of the function’s do-main.153.2. Plotting(a) Domain plot cen-tered at the origin(b) Domain plot shiftedalong the x-axis(c) Domain plot abovethe x-axisFigure 3.5: All three figures show the domain plot for the same PLC func-tion. The figures illustrate the effect of changing the bounding box of theplot domain method.16Chapter 4Computing theSubdifferential of PLCFunctions4.1 PLCVP4.1.1 MotivationWith the CCA library, we want to perform convex transformations asefficiently as possible. The conjugate transformation can be computed in lin-ear time by using the following relationship between the conjugate functionand subgradients.Theorem 4.1. [Bec17, Theorem 4.20] (Conjugate subgradient theorem).Let f : Rn → (∞,∞] be a proper convex function. The following claims areequivalent for any x ∈ Rn, y ∈ Rn.(i) 〈x, y〉 = f(x) + f∗(y).(ii) y ∈ ∂f(x).If in addition f is closed, then (i) and (ii) are equivalent to(iii) x ∈ ∂f∗(y).From Theorem 4.1 we note that if f is closed then,y ∈ ∂f(x) ⇐⇒ x ∈ ∂f∗(y). (4.1)Recall the graph of the subdifferential,(x, y) ∈ gph∂f ⇐⇒ y ∈ ∂f(x). (4.2)174.2. Subdifferentials of PLC FunctionsApplying Equations (4.1) and (4.2) then,(x, y) ∈ gph∂f ⇐⇒ y ∈ ∂f(x)⇐⇒ x ∈ ∂f∗(y)⇐⇒ (y, x) ∈ gph∂f∗.(4.3)By (4.3) we can see the domain of all subgradients in the subdifferentialof a function is the same set as the range of all subgradients in the subdif-ferential of its conjugate function. This relationship leads to graph-matrixcalculus [GL11] where numerous rules are given to transform the graph of asubdifferential of a function to the graph of a transformed function’s subdif-ferential. Here, from Goebel’s graph-matrix calculus, the Fenchel conjugatetransform is given bygph∂f∗ =[0 idid 0]gph∂f. (4.4)For a proper closed convex function f with x ∈ Rn, y = f(x) ∈ Rn, ands ∈ ∂f(x) ⊂ Rn then f∗(y) can be calculated by Fenchel’s equality,f∗(y) = 〈s, x〉 − y. (4.5)As a consequence, we can compute complex transforms such as the conjugatewith simple matrix multiplication which is both fast and easy to manipulatein MATLAB. PLCVP aims to represent PLC functions by storing the graphof the subdifferential to take advantage of graph-matrix calculus.4.2 Subdifferentials of PLC FunctionsWhen computing the subdifferential of convex PLC functions, there arethree distinct cases to consider given where a point lies on the domain of thefunction. For a convex PLC function f , either a given point f(x1, x2) = ylies outside of dom(f), somewhere on the interior of dom(f) or the pointis on the boundary of dom(f). We apply subdifferential calculus based onthese cases.Outside of the DomainThe elements of ∂f(x) are the subgradients of f at x ∈ R2 and f issubdifferentiable at x if ∂f(x) 6= ∅. By convention, when x /∈ dom(f),184.2. Subdifferentials of PLC Functionswe define ∂f(x) = ∅. This definition is consistent with the subgradientinequality,f(y) ≥ f(x) + 〈s, y − x〉, ∀y ∈ Rn. (4.6)For a proper function f , the subgradient inequality (4.6) does not hold ifx /∈ dom(f) and y ∈ dom(f). Thus, if x /∈ dom(f), f is not subdifferentiableat x.Interior of the DomainWe now consider a point on the interior of the domain. For a PLCfunction there are several cases.(i) Interior of a face: The interior of each face is a polyhedral set definedby a polynomial expression which is continuous and differentiable any-where on the interior. Let x ∈ R2, if a function f is convex and dif-ferentiable at x ∈ dom(f), then ∂f(x) = {∇f(x)}. For any point thatlies on the interior of a face, we need only to compute the gradient off at that point.(ii) On an edge: If a point x ∈ R2 is on the relative interior of an edge,then it is on the intersection of two faces. For a PLC function fwith faces F1 and F2 that share an edge ei and have the respectiveassociated functions f1 and f2 then {x ∈ ri(ei) : f1(x) = f2(x)}. From(i) we know that for x ∈ int(dom(f)) the subdifferential for each faceis ∂fi(x) = {∇fi(x)}. Since f is convex we can apply the Clarkesubdifferential from Definition 2.9 (see [RW98, Theorem 9.61]) andobtain the subdifferential at x by∂f(x) = ∂¯f(x) = co{∇fi(x) : fi(x) = f(x)}. (4.7)(iii) On a vertex: For the case when a point is on a vertex but within theinterior of a PLC function f , the formula (4.7) applies again. If a pointon the interior of f that satisfies the constraints for n polyhedral sets,we compute the gradients at the point x for each of the n faces andthen return the convex hull.On the Boundary of the DomainFor each piece of a PLC function f , we associate the function f˜k =fk + δCk , where δCk is the indicator function. By the subdifferential of the194.2. Subdifferentials of PLC Functionssum rule 2.11,∂f˜k(x) = ∂[fk(x) + δCk(x)] = ∂fk(x) + ∂δCk(x). (4.8)The subdifferential of the indicator function ∂Ck is the normal cone NCkfrom the Fact 2.13 so,∂fk(x) + ∂δCk(x) = ∇fk(x) +NCk(x). (4.9)Applying (4.9) with the definition of the normal cone (2.4), then for anyx ∈ Ck and for all z ∈ Ck, we have the subdifferential at f˜k(x) is,∂f˜k(x) = ∇fk(x) +NCk(x)= {s+∇fk(x) ∈ R2 : 〈s, z − x〉 ≤ 0}.The subdifferential on an edge of a polytope P is the normal cone of xat P . The normal cone NP will be a ray normal to the edge. For a vertexof P , each edge of the normal cone NP will be a ray normal to the incidentedges at v.Proposition 4.2. Let f be a proper PLC bivariate function having a fi-nite number of faces f1, f2, ..., fn. Assume v is a vertex of an edge on theboundary of dom(f) and that v is an extreme point. There is at least an-other edge having v as an extreme point such that v = e1 ∩ e2 where E1and e2 are edges on the boundary of dom(f). The normal cone at v isNdom(f)f(v) = Nf1(v) ∩Nf2(v) where fi is the face of f with edge ei.Proof. For v to be an extreme point, there must be two incident edges thatare on the boundary of dom(f). If there are more than two incident edges tov, only two of these edges can be on the boundary of dom(f) and any otheredge is within the interior of dom(f). An edge that is within the interior ofdom(f) then v is not an extreme point for that edge.Assume s is a subgradient of f1. If s is also a subgradient of f2 thenit is a subgradient of f . Therefore, any subgradient in the intersection ofthe subdifferentials of f1 and f2 is a subgradient of f . Conversely, anysubgradient of f is also in the intersection of f1 and f2.4.2.1 Data StructureAs input, our subdifferential algorithm uses the same data structurethat we use for PLCVC as described in Chapter 3. The input takes a vertexmatrix V, an edge matrix E , a face adjacency matrix F , and coefficient204.2. Subdifferentials of PLC Functions(a) (b)Figure 4.1: Figure (a) shows a point outside of the domain of f and (b)shows a point inside of the domain of f .matrix f . Alternatively, a PLCVC object can be provided as input to thePLCVP class and these matrices will be passed along to the subdifferentialalgorithm. The subdifferential is always a closed convex polyhedral set sothe algorithm outputs the subdifferential using the same data structure. Todifferentiate between the input and output, we will assign Vs, Es, and Fs tobe the subdifferential output matrices.4.2.2 AlgorithmFor a bivariate convex PLC function f , we can determine if a pointx ∈ R2 lies outside of the dom(f) by evaluating the function at the pointf(x). The PLCVC class implements an evaluation method (eval) that weuse for this purpose. If a point does not satisfy the constraints for any ofthe polyhedral sets in f then the value is infinity. Any finite value satisfiesat least one constraint and therefore x ∈ dom(f). In addition to returningthe function value at a point, the PLCVC eval method returns the index(es)of the face(s) containing the point in a matrix R for any polytope whichsatisfies the constraints. If the PLCVC eval method returns infinity, thenthere is no subdifferential at the point and we return an empty set. Figure 4.1compares a point outside of dom(f) to one on the interior of dom(f).When we know that a point is on the interior of the domain of f , thenext step is determine if the point is on an edge or a vertex so that wecan apply the subdifferential calculus rules. For each face Fi in the region214.2. Subdifferentials of PLC FunctionsR array, we check if the given point x lies somewhere on one of the edgesen ∈ Fi. If we find the point is on en then either the point is on one ofthe two vertices v1, v2 ∈ en or somewhere on the relative interior of en. Ifthe point lies on any edge, we store an index to en in an edge list iE. Onelimitation to note is that we are not currently handling floating point errorswhen calculating if a point is on an edge.After checking if the point lies on any edge of the faces, if the edge listiE is empty and the number of faces in R is exactly one, then we know thepoint is not any vertex or edge. We can conclude that such a point mustbe on the interior of a face. Using the face number i returned by the evalfunction, we compute the gradient of the point on the face and return thesingleton {∇fi(x1, x2)} as the subdifferential at this point. If the edge listiE is empty but the region array R had more than one element, we returnan error. This could be the case for a floating point error where a point wason an edge or a vertex but the calculation determining if the point was onan edge found it was not.For any point with at least one element in the edge list iE, we need toknow how many constraints in f the point satisfies and if this point is onthe boundary of dom(f).We perform one loop through the edge list iE to build a list of gradientsand properties of each edge in iE. We build the grd cell array as,grd = {ej ,∇fj(x1, x2), bj},where ej ∈ iE is the edge index, ∇fj(x1, x2) is the gradient for the face thatej is on, and bj is a binary flag indicating if the edge ej is on a boundary.If an edge is between two faces (equivalently not on a boundary of dom(f))then it is stored in grd twice so that the gradient of both adjacent faces ofthe edge ej are stored. Based on the number of elements in grd, we have anumber of possible cases as listed in Table 4.1.Case No. No. of gradients b flag count Case1 2 0 On an interior edge2 >2 0 On interior vertex3 1 1 On a boundary edge4 1 >1 On boundary vertex (1 face)5 >1 >1 On boundary vertex (2+ faces)Table 4.1: Cases for the grd arrayTwo possible cases are not included in Table 4.1 because they are handled224.2. Subdifferentials of PLC Functions(a) (b)Figure 4.2: Both figures show a PLC function f with four faces and fouredges. Figure (a) shows a point on an edge that is in the int(f). Figure (b)shows a point that is on a vertex and in int(f).prior to the creation of grd. If there are no subgradients then the point xwas outside of dom(f). If there was a single gradient that was not on theboundary, then the point was found to be on the interior of a face and thegradient has been returned. In either case, an error is returned if these casesare found after computing grd.For cases 1 and 2 from Table 4.1, the computation of the subdifferential issimilar. We take each gradient in grd and use them as vertices in the vertexlist Vs. If there are only two gradients, as per case 1 in Table 4.1 where thepoint is on an interior edge, then the output will be a line segment betweenthe two vertices. We add a single edge to Es between the two vertices. Weleave the face matrix Fs empty. If there are more than two elements thenthe face is on an interior vertex. In this case, we build the edge list as aconnected graph such that, if Vs has n vertices, there are exactly n edgesand each vertex is connected to exactly two edges. Vertices from adjacentfaces are connected to each other.For each of the cases 3,4,5 from Table 4.1 the point is on the boundary.In all of these cases, we compute the normal cone at the point. If the pointis on an edge and on the boundary as in case 3 of Table 4.1 and shown inFigure 4.3(a), then we know the normal cone will be a ray that is normalto the edge. In this case, we compute the normal cone which builds a rayby adding two vertices to Vs, a single edge to Es, and setting Fs = ∅. Thisrepresents the ray normal to the edge ej .234.2. Subdifferentials of PLC Functions(a) (b)Figure 4.3: Figure (a) shows a point on the boundary of dom(f) on an edge(b) shows a point on the boundary of dom(f) on the vertex.When the point is found to be on a boundary vertex of only one face,as in case 4 from Table 4.1, we compute the normal cone at the point andreturn the normal cone representation as Vs,Es,Fs.In the final case, we compute the intersection of two or more normalcones. To compute the intersection of two normal cones, we first computethe normal cone for each in the Vs,Es,Fs representation. With the twonormal cones, we note that they both share a vertex at the point we areevaluating. We compute the normalized 360 degree angle each edge makesat this point. We then evaluate where the edges lay in relation to each otherto compute the overlap. Once the overlap is determined, a new Vs,Es,Fs listis built using the edges found that overlapped. If the overlap is determinedto only be along a ray, then only a ray is returned.244.2. Subdifferentials of PLC Functions4.2.3 AlgorithmAlgorithm 2: Subdiffinput : x (1x2 matrix containing point to evaluate at), P (PLCVCpolyhedral set)output: z (1x2 matrix of the function evaluated at x), G(polyhedral set of the subdifferential at x)beginz, face← PLCV C.eval(x);if (isInfinity(z)) thenG← {}; return;endiE ← [Edges in P that x lies on];if (isEmpty(iE)) thenG← {∇fface(x)}; return;endgrd ← [ej , ∇fi(x), bj ] if edge ej ∈ iE on face i;if (all bj ∈ grd == 0) thenVs, Es, Fs ← build polyhedral set from co(∇fg(x)∀g ∈grd);else if (any bj ∈ grd == 1) thenVs, Es, Fs ← computeNormalCone(x);endG← {Vs, Es, Fs}; return;endProposition 4.3. Consider a PLC function with N faces, the Subdiff algo-rithm runs in O(N)Proof. The algorithm runs through a number of cases, and if any of the casesis satisfied along the way, the subdifferential is returned and the algorithmexits. The worst case run time requires the algorithm to pass through eachcase until the final one. The worst case occurs when a point x is on avertex on the boundary of dom(f). For every case, the PLCVC eval methodevaluates a point on a PLC function with M faces in O(M) time. Theevaluation needs to do a linear search of each of the M faces to find theright face to evaluate the function at. Once the face is found, the point isevaluated using the coefficients for that face which is an efficient calculationin O(1) time. For a point x /∈ dom(f) the subdifferential is an empty setand returned in O(1) time.We loop through the N edges in E once to build the edge list iE. Inaddition, we loop through the edges in iE to compute the gradient edge list254.2. Subdifferentials of PLC Functionsgrd. Both of these operations are computed in O(N). If a point is foundto not be on any edge then ∇f(x) is computed and returned as a singleton.Computing the gradient at x is done in O(1). Evaluating possible casesfor grd is done in O(N) as there could be N edges in grd. The worst caseruntime operation after we have checked the grd matrix is when the normalcone must be computed for two faces. The normal cone and subsequentintersection calculations are done in O(1).Therefore, the overall time complexity for the algorithm is linear.26Chapter 5Numerical ExperimentsIn this chapter we use the subdifferential method in PLCVP to find thesubdifferential at various points of a few PLC functions. We use plottingmethods from PLCVC to visualize the PLC functions and the subdifferentialat these points.5.0.1 Example 1Consider the l1 norm function,f(x1, x2) =x1 + x2 −x1 ≤ 0,−x2 ≤ 0;−x1 + x2 x1 ≤ 0, x2 ≥ 0;−x1 − x2 x1 ≥ 0, x2 ≥ 0;x1 − x2 x1 ≥ 0, x2 ≤ 0.Figure 5.1: Plot of the l1 norm function.27Chapter 5. Numerical ExperimentsA plot of the l1 norm function is shown in Figure 5.1. We evaluatethe subdifferential at three different points. At f(1, 1), the point is on theinterior of face three. The subdifferential is the gradient at the point f3(1, 1)which we compute as,∂f(1, 1) = ∇f3(1, 1) = ( ∂f∂x1(1, 1),∂f∂x2(1, 1)) = (1, 1).Accordingly, the subDiff method returns the same subgradient as thesubdifferential for the l1 norm at (1,1). The output from the subdifferentialalgorithm at (1,1) on the l1 norm is shown in Figure 5.2.(a) Domain plot of the l1 norm. (b) ∂f at (1,1).Figure 5.2: Figure (a) shows the domain of the l1 norm with the point (1,1)highlighted. Figure (b) shows the subdifferential of the l1 norm at (1,1).Next, we compute the subdifferential of the l1 norm at (1,0). This pointis on an edge between two faces. The subdifferential is computed as∂f(1, 0) = co{∇f3(1, 0),∇f4(1, 0)}= co{(1, 1), (1,−1)}= {(x1, x2) ∈ R2 : x1 = 1;−1 ≤ x2 ≤ 1}.The subdifferential algorithm computes the gradients of both faces thenadds the gradients as vertices to the VS matrix. An edge is added betweenthe two vertices to represent the interval found above and the edge is flaggedas a line segment. A plot of the output from the subdifferential algorithmfor the l1 norm at (1,0) is seen in Figure 5.3. The matrices returned by thealgorithm for the subdifferential of the l1 norm at this point are,VS =[1 11 −1], ES =[1 2 1], FS =[0 0].28Chapter 5. Numerical Experiments(a) Domain plot of the l1 norm. (b) ∂f at (1,0)Figure 5.3: Figure (a) shows the domain of the l1 norm with the edge point(1,0) highlighted. Figure (b) shows the subdifferential of the l1 norm at(1,0).A final example using the l1 norm is for the subdifferential at (0,0).This point is a vertex and all four faces are “active” at this point. Thecomputation for the subdifferential requires the gradient of all four faces,∂f(0, 0) = co{∇fi(0, 0) : fi ∈ f}= co{[−1, 1]× [−1, 1]}= {(x1, x2) ∈ R2 : −1 ≤ x1 ≤ 1;−1 ≤ x2 ≤ 1}.We find that the subdifferential algorithm correctly computes the squarearound the origin at (0,0). The algorithm finds four gradients and addsthem as vertices. A list of edges is built forming a bounded square from thevertices. The matrices returned by the algorithm are,VS =−1 −1−1 11 11 −1 , ES =1 2 12 3 13 4 14 1 1 , FS =0 10 10 10 1 .A plot of the subdifferential at (0,0) of the l1 norm is seen in Figure 5.45.0.2 Example 2To test how the algorithm computes the subdifferential on a boundaryconsider,29Chapter 5. Numerical Experiments(a) Domain plot of the l1 norm. (b) ∂f at (0,0)Figure 5.4: Figure (a) shows the domain of the l1 norm with the vertex (0,0)highlighted. Figure (b) shows the subdifferential of the l1 norm at (0,0).f(x1, x2) =x1 + x2 −x1 ≤ 0,−x2 ≤ 0;−x1 + x2 x1 ≤ 0, x2 ≥ 0;∞ otherwise.A plot of this function is shown in 5.5.Figure 5.5: Plot of a PLC function with a boundary along the x axisSince the boundary is a straight line along the x axis, the subdifferentialat any point in f will be a ray that is normal to the x axis. We compute30Chapter 5. Numerical Experimentsthe subdifferential on an edge (1,0) and at a vertex (0,0) and find in bothcases that a ray is properly returned, as shown in Figure 5.6.(a) (b)Figure 5.6: Subdifferentials on an edge5.0.3 Example 3Consider the bounded triangle,f(x1, x2) ={x21 + x22 + 2x1x2 in triangle with vertices(0, 0), (1, 0), (0.5, 1);∞ otherwise.A plot of this triangle is shown in Figure 5.7. For the subdifferential ofthe triangle at the vertex (0,0), we expect a normal cone comprised of tworays that are normal to the two edges that meet at the vertex. Indeed thisis what we get, as Figure 5.8 shows the boundary of the triangle with thenormal cone at (0,0) as returned by the subDiff algorithm. The followingvertex representation of the subdifferential at (0,0) of the triangle is returnedby the subdifferential algorithm,VS = 0 00 −1−1 0.5 , ES = [1 2 01 3 0], FS =[1 00 1].Both edges are flagged as rays in the edge list ES as noted by the zerosin column three.31Chapter 5. Numerical ExperimentsFigure 5.7: A plot of a bounded triangle with only one face.Figure 5.8: The edges in blue show the boundary of the triangle. The edgesin orange show the subdifferential of the triangle at (0,0) which is a normalcone32Chapter 6Conclusion and Future WorkTwo contributions have been made to the CCA library. A plot domainalgorithm was added to PLCVC, and a subdifferential computation algo-rithm was added as a basis for the PLCVP library. We showed how thevertex and coefficient representation of PLC functions used by the PLCVCclass could be manipulated to work with a region of interest for functionswith full domains. We used this restricted region of interest to plot thedomain of unbounded PLC functions. This method may prove useful forfuture additions to the CCA library that work with PLC functions of fulldomains.We introduced the subDiff algorithm to compute the subdifferential atany point of a PLC function. We showed how the algorithm uses subdiffer-ential calculus and the structure of PLC functions to compute the subdif-ferential. This algorithm can be used to build a pointwise representation ofPLC functions using GPH matrices.Now that the subdifferential can be computed, the PLCVP class needsan algorithm to build GPH matrices to represent PLC functions. There isstill research to be done on the optimal way to store the GPH matrices. In[Haq17] a GPH matrix was created for each entity of a PLC function and ahyper matrix was used to keep track of the entity types and arrangement.An alternative is to store the values in each GPH matrix as indices to largermatrices. For example, each xi in a GPH matrix would be stored as anindex to a matrix of all GPH matrix points X. By storing the matrix inthis way, a single matrix operation can be done to transform the graph ofthe subdifferential as opposed to looping through each GPH matrix andtransforming matrix.In addition to computing transforms, PLCVP class will need to be ableto convert back to PLCVC coefficient representations of functions. Sincethere is no unique way to store a function as a GPH matrix, we must ensurethat we accurately recover the correct function.33Bibliography[Bec17] Amir Beck. First-Order Methods in Optimization. Society forIndustrial and Applied Mathematics, Philadelphia, PA, 2017. →pages 3, 4, 17[BJS11] M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali. Linear programmingand network flows: Fourth edition. 01 2011. → pages 6[CW05] Patrick L. Combettes and Vale´rie R. Wajs. Signal recovery byproximal forward-backward splitting. Multiscale modeling simu-lation, 4(4):1168–1200, 2005. → pages 1[GJL14] Bryan Gardiner, Khan Jakee, and Yves Lucet. Computing the par-tial conjugate of convex piecewise linear-quadratic bivariate func-tions. Computational optimization and applications, 58(1):249–272, 2014. → pages 5[GL11] Bryan Gardiner and Yves Lucet. Graph-Matrix Calculus for Com-putational Convex Analysis, pages 243–259. Springer New York,New York, NY, 2011. → pages 1, 18[Haq17] Tasnuva Haque. Computation of convex conjugates in linear timeusing graph-matrix calculus. PhD thesis, University of BritishColumbia, 2017. → pages 1, 6, 33[HL18] Tasnuva Haque and Yves Lucet. A linear-time algorithm tocompute the conjugate of convex piecewise linear-quadratic bi-variate functions. Computational Optimization and Applications,70(2):593–613, 06 2018. → pages 6[Jak13] Khan M. K. Jakee. Computational convex analysis using paramet-ric quadratic programming. PhD thesis, 2013. → pages 5[Luc10] Y. Lucet. What shape is your conjugate? A survey of computa-tional convex analysis and its applications. SIAM Rev., 52(3):505–542, 2010. → pages 134Bibliography[MAT21] MATLAB. version 9.10.0 (r2021a), 2021. → pages 1[Qu11] Gang-rong Qu. Singularities of the radon transform of a class ofpiecewise smooth functions in r 2. Acta Mathematicae ApplicataeSinica, 27(2):191–208, 2011. → pages 1[Roc70] R. Tyrrell Rockafellar. Convex analysis. Princeton MathematicalSeries. Princeton University Press, Princeton, N. J., 1970.→ pages6[RW98] R.T. Rockafellar and R.J.B. Wets. Variational analysis, volume317 of Grundlehren der Mathematischen Wissenschaften [Fun-damental Principles of Mathematical Sciences]. Springer-Verlag,Berlin, 1998. → pages 3, 4, 5, 19[SL21] Shambhavi Singh and Yves Lucet. Linear-time convexity test forlow-order piecewise polynomials. SIAM Journal on Optimization,31(1):972–990, 2021. → pages 135
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Undergraduate Research /
- Computing the Subdifferential of Convex Piecewise Linear-Cubic...
Open Collections
UBC Undergraduate Research
Computing the Subdifferential of Convex Piecewise Linear-Cubic Functions Mahnic, Aaron Matthew 2021-04
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Computing the Subdifferential of Convex Piecewise Linear-Cubic Functions |
Creator |
Mahnic, Aaron Matthew |
Date Issued | 2021-04 |
Description | Computational Convex Analysis (CCA) studies the computation of convex operators commonly used in convex analysis. CCA allows researchers to visualize non-trivial convex transforms and build an intuition from these examples. Using the convexity and structure of piecewise linear cubic (PLC) functions as a model, the foundation for a new CCA toolbox has been implemented. The CCA toolbox is built in MATLAB and includes extensive test coverage and examples. In addition, it is free and open source. The CCA toolbox provides several plotting methods to visualize PLC functions and their properties. Plotting the domain of a PLC function is a useful tool for both research and visualizing the correctness of computed output. Within a PLC function, any polyhedral set can be unbounded and plotting the domain of such a function would lead to an unbounded plot which cannot be displayed. We introduce a method that manipulates the PLCVC data structure in the CCA toolbox to plot an unbounded domain within a specified window. A convex analysis operation of considerable interest is the Legendre-Fenchel transform, also known as the Fenchel conjugate. The computation of the Fenchel conjugate can be done in linear time. As a first step in implementing a linear time conjugate computation for the CCA toolbox, we introduce a new class (PLCVP) that implements a method for computing the subdifferential at any point of a PLC function. |
Genre |
Graduating Project |
Type |
Text |
Language | eng |
Series |
University of British Columbia. COSC 449 |
Date Available | 2021-06-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0398326 |
URI | http://hdl.handle.net/2429/78598 |
Affiliation |
Science, Irving K. Barber Faculty of (Okanagan) Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan) |
Peer Review Status | Unreviewed |
Scholarly Level | Undergraduate |
Copyright Holder | Aaron Matthew Mahnic |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 52966-Mahnic_Aaron_Piecewise_linear-cubic_2021.pdf [ 3MB ]
- Metadata
- JSON: 52966-1.0398326.json
- JSON-LD: 52966-1.0398326-ld.json
- RDF/XML (Pretty): 52966-1.0398326-rdf.xml
- RDF/JSON: 52966-1.0398326-rdf.json
- Turtle: 52966-1.0398326-turtle.txt
- N-Triples: 52966-1.0398326-rdf-ntriples.txt
- Original Record: 52966-1.0398326-source.json
- Full Text
- 52966-1.0398326-fulltext.txt
- Citation
- 52966-1.0398326.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.52966.1-0398326/manifest