Arts and Sciences, Irving K. Barber School of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Singh, Shambhavi
Master of Science - MSc
University of British Columbia
First, we consider how to efficiently determine whether a piecewise-defined function in 2D is convex. For a piecewise linear quadratic (PLQ) function, convexity can be characterized with a linear number of constraints with respect to the number of edges of the partition defining the domain. The number of constraints in 2D is in fact linear with respect to the number of vertices in the domain. A similar characterization is given for piecewise cubic functions in 2D. We then consider the set of convex PLQ functions, which can be split into sub-classes based on how neighbouring pieces interact with each other. The sub-class of difference-definite functions on boxes is shown to be characterized by a quasi-separable structure. This in turn gives a parametrization that is linear with respect to the number of grid points in the domain, while the general case requires a quadratic number of parameters. The characterization of convexity is finally used in optimization algorithms under convex constraints. We make the connection with previous work, and show our results are much more general. We illustrate the results by computing the closest convex function.
Convexity and structure of piecewisepolynomial functions on polyhedraldomainsbyShambhavi SinghBachelor of Science, Indian Institute of Technology Kanpur, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)June 2019c© Shambhavi Singh, 2019The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Convexity and structure of piecewise polynomial functionson polyhedral domainssubmitted by Shambhavi Singh in partial fulfilment of the requirements ofthe degree of Master of ScienceDr. Yves Lucet, Irving K. Barber School of Arts and SciencesSupervisorDr. Heinz Bauschke, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Warren Hare, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Abbas Milani, School of EngineeringUniversity ExamineriiAbstractFirst, we consider how to efficiently determine whether a piecewise-defined function in 2D is convex. For a piecewise linear quadratic (PLQ)function, convexity can be characterized with a linear number of constraintswith respect to the number of edges of the partition defining the domain.The number of constraints in 2D is in fact linear with respect to the numberof vertices in the domain. A similar characterization is given for piecewisecubic functions in 2D.We then consider the set of convex PLQ functions, which can be splitinto sub-classes based on how neighbouring pieces interact with each other.The sub-class of difference-definite functions on boxes is shown to be charac-terized by a quasi-separable structure. This in turn gives a parametrizationthat is linear with respect to the number of grid points in the domain, whilethe general case requires a quadratic number of parameters.The characterization of convexity is finally used in optimization algo-rithms under convex constraints. We make the connection with previouswork, and show our results are much more general. We illustrate the resultsby computing the closest convex function.iiiLay SummaryThe notion of convexity appears in many fields. Convex optimizationstarts with the very assumption that the functions and sets involved areconvex. In this thesis, we try to answer whether a function given to us isconvex. The functions we answer this for are piecewise polynomial functionson polyhedral domains, which means they consist of several pieces, eachof which is a polyhedral set and on each polyhedral set it is defined as apolynomial of a given degree. In our case, we only consider, quadratic andcubic polynomials.This is useful because once we approximate an arbitrary function withthis kind of piecewise polynomial, we can manipulate the approximationmuch more easily. This can be used to give solutions to optimization prob-lems which have constraints that do not seem so intuitive initially.ivPrefaceThe proof of Lemma 3.1 is a cleaned up version of a preliminary sketchdrafted by Heinz H. Bauschke, Hung M. Phan, and Yves Lucet at the endof their collaboration on [BLP16].vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Chapter 2: Preliminaries and Notations . . . . . . . . . . . . . 42.1 General Convex Analysis . . . . . . . . . . . . . . . . . . . . . 42.2 Polynomials and Piecewise Functions . . . . . . . . . . . . . . 72.3 Triangulations: Special case of Polyhedral Division . . . . . . 11Chapter 3: Linear-time convexity test for low-order piece-wise polynomials . . . . . . . . . . . . . . . . . . . . 133.1 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2.1 Convexity in R . . . . . . . . . . . . . . . . . . . . . . 153.2.2 Convexity of PLQ functions in R2 . . . . . . . . . . . 163.2.3 Cubic Functions in R2 . . . . . . . . . . . . . . . . . . 203.3 Implementation of the characterization . . . . . . . . . . . . . 27Chapter 4: Difference Definite Functions . . . . . . . . . . . . 30viTABLE OF CONTENTS4.1 Properties of convex PLQ functions . . . . . . . . . . . . . . . 314.2 Quasi-Separability . . . . . . . . . . . . . . . . . . . . . . . . 364.3 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 394.3.1 DD Functions on boxes . . . . . . . . . . . . . . . . . 394.3.2 General 2D PLQ Function . . . . . . . . . . . . . . . . 41Chapter 5: Parametrization and Modelling of convexity con-straints . . . . . . . . . . . . . . . . . . . . . . . . . . 445.1 Representing PLQ Functions . . . . . . . . . . . . . . . . . . 445.1.1 DD functions on a grid . . . . . . . . . . . . . . . . . 445.1.2 DI Functions on a grid . . . . . . . . . . . . . . . . . . 525.2 Representing Convexity Constraints in Optimization Problems 595.2.1 Equivalence of convexity characterization . . . . . . . 595.2.2 Convexity Constraints . . . . . . . . . . . . . . . . . . 62Chapter 6: Conclusions and Future Work . . . . . . . . . . . . 676.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.1.1 Extending PLQ to Rd . . . . . . . . . . . . . . . . . . 686.1.2 Applications of DD functions . . . . . . . . . . . . . . 686.1.3 Using parametrization as a tool to generate convexPLQ functions . . . . . . . . . . . . . . . . . . . . . . 68Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72Appendix A: Conjugation of DD functions . . . . . . . . . . . . . . 73Appendix B: isConvex() . . . . . . . . . . . . . . . . . . . . . . . . 75B.1 PLQ Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 75B.2 PC Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 79viiList of FiguresFigure 3.1 Examples of convex and nonconvex piecewise quadraticfunctions . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 3.2 The types of polyhedra . . . . . . . . . . . . . . . . . 20Figure 3.3 Cubic convexity: cases when ∇f2−∇f1 is not quadratic 23Figure 3.4 Cubic convexity: case when δi ≥ 0, aj=0 . . . . . . . 24Figure 3.5 Cubic convexity: cases where aj , δ1, δ2 ≥ 0 . . . . . . 25Figure 4.1 A difference-definite function . . . . . . . . . . . . . . 30Figure 4.2 Checking DD in all pairs of neighbours using Corol-lary 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 33Figure 4.3 Checking DD in all pairs of neighbours using Corol-lary 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . 34Figure 4.4 Difference-indefinite function . . . . . . . . . . . . . . 35Figure 4.5 The function stored in the DD data structure . . . . 39Figure 4.6 Defining all pieces using q, g1 and g2 . . . . . . . . . . 40Figure 4.7 The significance of each element in the data structure 42Figure 5.1 Degree of freedom assuming no relation between thepieces . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Figure 5.2 Grid displaying the degree of freedom for a difference-definite PLQ on each piece . . . . . . . . . . . . . . . 46Figure 5.3 Defining a DD function . . . . . . . . . . . . . . . . . 47Figure 5.4 DD function with 2 boundaries defined . . . . . . . . 48Figure 5.5 Defining pieces of g1 and g2 . . . . . . . . . . . . . . . 49Figure 5.6 Parametrizing a DD function . . . . . . . . . . . . . . 50Figure 5.7 An example of the parametrization in 3 dimensions . 51Figure 5.8 Grid displaying the degree of freedom for a difference-indefinite PLQ on each piece . . . . . . . . . . . . . . 52Figure 5.9 Defining pieces of a 2D DI function . . . . . . . . . . 53Figure 5.10 Difference between defining an interior piece in a DIand a DD function . . . . . . . . . . . . . . . . . . . . 54viiiLIST OF FIGURESFigure 5.11 Grid displaying the degree of freedom for a 3D difference-indefinite PLQ on each piece . . . . . . . . . . . . . . 55Figure 5.12 Defining pieces of a 3D DD function . . . . . . . . . . 56Figure 5.13 An unbounded triangulation . . . . . . . . . . . . . . 61Figure 5.14 The projection problem in 1D . . . . . . . . . . . . . 64Figure 5.15 The triangulation used to optimize the funciton in 2D 65Figure 5.16 The projection problem in 2D . . . . . . . . . . . . . 66Figure A.1 The conjugate of a 2D DD PLQ . . . . . . . . . . . . 74ixAcknowledgementsI will take this opportunity to thank Dr. Yves Lucet, for his constantguidance and encouragement throughout my graduate studies. The constantencouragement and comprehensive feedback made my time as his studentreally enjoyable. I am immensely grateful for his amazing eye for detailwhich made the Herculean task of writing easier. I would also like to extendmy gratitude towards the members of my supervisory committee, Dr. HeinzBauschke and Dr. Warren Hare for taking out time to read my thesis andprovide useful feedback that helped me make my results robust and freeof errors I might have missed. I am also thankful to all of my committeemembers for the insightful questions asked during the defense that helpedme see the impact of my results.I would also like to thank to the University of British Columbia, Okana-gan and the Natural Sciences and Engineering Research Council of Canada(NSERC) and MITACS Globalink Graduate Fellowship for financial assis-tance. Their contribution was instrumental in helping me concentrate onmy research.This work was supported in part by Discovery Grants #298145-2013(Lucet) from NSERC, and The University of British Columbia, Okanagancampus. Part of the research was performed in the Computer-Aided ConvexAnalysis (CA2) laboratory funded by a Leaders Opportunity Fund (LOF,John R. Evans Leaders Fund—Funding for research infrastructure) fromthe Canada Foundation for Innovation (CFI) and by a British ColumbiaKnowledge Development Fund (BCKDF).xTo my family,for believing I could do the mathand Rahul Gargfor making me believe it myselfxiChapter 1IntroductionConvexity of a function has very practical consequences. While it makesoptimization problems easier as local minima (if found) are also the globalminima, it also forces the function to be continuous on the interior of thedomain. We also see convexity imposed as a constraint in optimizationalgorithms. Hence characterizing the convexity of a class of functions ishighly useful. In a computational setting, convexity constraints are harderto implement than in the theoretical sense. As mentioned by [Obe13] thecone of convex functions is not polyhedral, it is not possible to represent theset using finitely many linear inequalities.The application of such approximation is seen in several fields. Themonopolist problem as described in [Eke02, Section 1.1.1], which maximizesthe profit in a monopolistic setting by using buyers’ preferences requires thefunctions over which the value is being calculated to be convex. Newton’sproblem of least resistance, which was published in 1687 in his book PrincipiaMathematica [New87] tries to find a convex body that experiences the leastamount of resistance when travelling through a sparse medium. Assumingthe body has length L > 0 and base Ω ={x ∈ R2 : |x| ≤ 1}, the problemcan be modelled asMinimize∫Ω11 + |∇u(x)|2dxsuch that u : Ω→ R is convexand 0 ≤ u ≤ L.When solving the problem, Newton assumed that the object would be rota-tionally symmetric. Removing this constraint actually gave better solutionsto the problem and the global solution is still unknown. The problem isdiscussed in [BK93]. Another interesting problem is the projection problem,as seen in [CLRM99]. It tries to find the closest convex function to a givenfunction in terms of a norm. One can approximate the function to class offunctions whose convexity constraints are easier to represent. The first classthat intuitively comes to mind is the class of piecewise linear functions over apolyhedral set. However [CJ01] proved that this class is actually not dense1Chapter 1. Introductionin the class of convex functions and that for a given triangulation, therewould be some function that they will not be able to represent. Also, sincethe representation is supposed to approximate convexity constraints, theconvexity of the approximate function is crucial. [Wac17] approximates thefunction by piecewise polyhedral functions, whereas [Obe13] tries to approx-imate the set of convex functions by a polyhedral set. [EMB10] constructsa non-linear program to find an interior approximation of the problem.Several papers discuss the approximation of the set of convex functionin order to use in optimisation problems. While [Wac17] concentrates onapproximating the function using a class of functions whose convexity iseasier to characterize and then uses it in well known algorithms, [Mir16]and [CD17] construct algorithms on the discrete set itself. The former usesstencils to only check a subset of points resulting in linear constraints forconvexity and has a time complexity of O(n log n), where n is the numberof points at which the function is sampled. The latter enforces convexityin all directions available on a grid and has a time complexity of approxi-mately O(n2)1. The algorithm in [Obe13] also attempts to check convexityin all directions and represents the convexity constraints as linear inequali-ties and gives a quadratic or linear program with linear constraints. Ekeland[EMB10] finds an interior approximation of the solution to the problem byapproximating function values at a single point on each cell of the grid andsolves a non-linear program to approximate the solution of the actual prob-lem. While each method has merits, in the end the efficient representationof convexity is ultimately difficult.We will discuss the characterization of a few classes of piecewise polyno-mial functions over a polyhedral domain, namely piecewise linear-quadratic(PLQ) and piecewise cubic (PC) functions. The (continuous) PLQ case inRd can be done by checking the Hessian once in the interior of each celland then at the extremities of each boundary. This is possible because forquadratic functions, the Hessian is a constant and the gradient is a linearfunction. This gives us O (ne) inequalities, where ne is the number of edgesin the polyhedral subdivision. In 2D, this is equivalent to O (nv) inequali-ties, where nv is the number of vertices due to the planarity of the domain.Similarly a continuous 2D PC function will require a check on the Hessianat each point that is used to represent the polyhedral set. The check on thegradient jump will require more work as the gradients are now quadratic.The trend suggests extending these results to polynomials of higher degree1It was pointed out in [Mir16] that the approximation was slightly erronously statedas O(n1.8) in the original paper21.1. Objectivewould probably be harder to characterize. These characterizations are usedto construct an algorithm, which can be used to check convexity of a PLQor PC function. They can also be incorporated in optimization algorithmsthat use these functions.As convex functions are continuous on the relative interior of their do-mains, the structure of the function on each polyhedral set is somehowrelated to other pieces. In fact, the nature of the polyhedral set also de-cides the structure of the convex PLQ functions. The class of convex PLQfunctions can be split into further subclasses depending on how the piecesinteract with the neighbouring pieces. The subclass known as difference-definite functions was shown to have a quasi-separable structure by [Sun92]when the domain is a grid. Separability is considered ideal when talkingabout piecewise functions as most of the operators then can be applied oneach coordinate separately to obtain the result, which also reduces the timerequired to compute these results. This structure has its advantages; it en-ables us to parametrize the function using fewer coefficients than a regularPLQ function and enables us to store the function using fewer coefficientsthan in the general case.1.1 ObjectiveIn the thesis, we discuss several results over a few chapters. They havebeen summarized with respect to the chapters below.1. The convexity of a few piecewise polynomial functions is characterizedin an efficient manner in Chapter 3;2. next, a subclass of convex PLQ functions is considered and their struc-ture is characterized in Chapter 4. We also define data structures tohelp us implement algorithms from Chapter 3;3. finally, using the structure of the subclass of functions from Chap-ter 4, the function is parametrized efficiently in Chapter 5. The char-acterization from Chapter 3 is used to model convexity constraints inoptimization problems.3Chapter 2Preliminaries and NotationsThis chapter covers the basic terminology that will help understand thecontents of the thesis.2.1 General Convex AnalysisDefinition 2.1 (Convex set). A set Ω in Rd is convex if for all x, y ∈ Ω andfor all λ ∈ [0, 1], we have(1− λ)x+ λy ∈ Ω.Equivalently, the set Ω is convex if for all finite subsets {ω1, . . . , ωn} of Ωwith n ∈ N and for λi ≥ 0, i = 1, . . . , n such that∑ni=1 λi = 1, we haven∑i=1λiωi ∈ Ω.This helps us define the convex hull of the set.Definition 2.2 (Convex hull). [RW98, Theorem 2.27] The convex hull of anonempty set Ω, denoted by conv(Ω), is the smallest convex set that containsΩ, equivalentlyconv(Ω) ={n∑i=1λiωi∣∣∣∣∣ n ≥ 1, ωi ∈ Ω, λi ≥ 0,n∑i=1λi = 1}.Definition 2.3 (Affine set). [RW98, Example 2.10] A set Ω is affine if forall x, y ∈ Ω and for all λ ∈ R(1− λ)x+ λy ∈ Ω.Definition 2.4 (Affine hull). [Roc70, Corollary 1.4.1] The affine hull of anonempty set Ω, denoted by aff(Ω), is the smallest affine set that containsΩ, or equivalentlyaff(Ω) ={n∑i=1λiωi∣∣∣∣∣ n ≥ 1, ωi ∈ Ω, λi ∈ R,n∑i=1λi = 1}.42.1. General Convex AnalysisDefinition 2.5 (Normal cone). The normal cone for a set Ω in Rd at apoint x ∈ Ω is defined asNΩ(x) ={y ∈ Rd∣∣∣ 〈y, ω − x〉, ∀ ω ∈ Ω}Definition 2.6 (Relative interior). The relative interior of a set is definedas the largest open set with respect to its affine hull that is contained in theset. So formallyri Ω = {x | x ∈ C such that ∃ > 0, B[x, ] ∩ aff(C) ⊂ C} .Definition 2.7 (Effective domain). For a function f : Rd → R∪{+∞}, theeffective domain is defined asdom f = {x | f(x) < +∞}.Definition 2.8 (Epigraph). The epigraph of a function is defined graphi-cally as all the area above the graph of the function. Formally, it is a subsetof Rd × R defined asepi f = {(x, r) : f(x) ≤ r} .Definition 2.9 (Closed function). A function f : Rd → R∪{+∞} is closedif epi f is a closed subset of Rd × R.Definition 2.10 (lsc function). A function f : Rd → R ∪ {+∞} is lowersemi-continuous or lsc at x iff(x) ≤ lim infn→∞ f(xn) for every sequence xn → x.Fact 2.11. [RW98, Theorem 1.6] For a function f : Rd → R ∪ {+∞}, thefollowing are equivalent1. f is lower semicontinuous on Rd;2. the set epi f is closed in Rd × R.Definition 2.12 (Proper function). A function f : Rd → R ∪ {+∞} isproper if dom f 6= ∅.Definition 2.13 (Subdifferential). The subdifferential of a proper functionf : Rd → R ∪ {+∞} is a set defined for each point x ∈ Rd as∂f(x) ={s ∈ Rd∣∣∣ f(x) + 〈s, y − x〉 ≤ f(y), ∀ y ∈ Rd} .Each point s ∈ ∂f(x) is called a subgradient of f at x.52.1. General Convex AnalysisThe definition of a subgradient actually simplifies to that of a gradientwhen a convex function is differentiable at x.Fact 2.14. [Roc70, Theorem 25.1] Let f : Rd → R ∪ {+∞} be a convexfunction. Then f is at differentiable at x if and only if ∂f(x) is a singleton.In this case ∂f(x) = {∇f(x)}.Definition 2.15 (Fenchel conjugate). Given a function f : Rd → R∪{+∞},the Fenchel conjugate f∗ : Rd → [−∞,+∞] is defined asf∗(y) = supx∈Rd{〈y, x〉 − f(x)} .Definition 2.16. A matrix A ∈ Rd×d is called positive semidefinite if A issymmetric (A> = A) andx>Ax ≥ 0, ∀ x ∈ Rd. (2.1)The shorthand to denote A is positive semi definite is A  0 and the setof positive semidefinite matrices in Rd is denoted by Sd+. If the inequality in(2.1) is strictly greater than 0 except when x = 0, then the matrix is positivedefinite, denoted by A 0. Negative semidefinite and negative definite aredefined similarly. The set of positive semidefinite matrices is actually closedin the set of symmetric matrices.Proposition 2.17 (Closure of PSD matrices). [O’P18] The set Sd+ is closedin the set of matrices Rd×dProof. Consider the matrix functionsF :Rd×d → Rd×dA 7→ A−A>, andpx :Rd×d → RA 7→ x>Ax.Both the maps are continuous as they are linear, hence their kernels (in-verse image of {0}) and inverse image of closed sets will be closed [Rud76,Corollary to Theorem 4.8]. Clearly kerF is the set of symmetric functions,and p−1x [0,+∞) is the set of matrices satisfying (2.1), i.e.Sd+ = kerF ∩ ⋂x∈Rdp−1x [0,+∞)and as the intersection of closed sets, it is always closed in Rd×d.62.2. Polynomials and Piecewise FunctionsSince we will be dealing with convex functions extensively, we start bydefining a general convex function.Definition 2.18 (Convex function). A function f : Rd → R ∪ {+∞} isconvex iff(λx+ (1− λ)y) ≤ λf(x) + (1− λ)f(y)for all x, y ∈ dom f and for all λ ∈ [0, 1].Fact 2.19. [Za˘l02, Theorem 2.4.1(iii)] For a proper function f : Rd →R ∪ {+∞}, such that dom f is closed and convex and f is continuous ondom f , the following are equivalent:1. The function f is convex;2. the set epi f is convex in Rd × R;3. the set ∂f(x) is non-empty everywhere in ri dom f .Fact 2.20. [RW98, Theorem 2.14(c)] For a function f : Rd → R ∪ {+∞}that is twice differentiable everywhere in dom f such that dom f is open, thefunction is convex if and only if the Hessian ∇2f of the function is positivesemidefinite everywhere in dom f .2.2 Polynomials and Piecewise FunctionsDefinition 2.21 (Hyperplanes and Half-spaces). Take a ∈ Rd\{0} andβ ∈ R. The sets of the form {x ∈ Rd : a>x− β = 0} are called hyperplanes,and the sets of the form {x ∈ Rd : a>x− β ≤ 0} or {x ∈ Rd : a>x− β ≥ 0}are called closed half-spaces.Definition 2.22 (Polyhedral set). A set Ω ∈ Rd is polyhedral if it canbe denoted as the intersection of finitely many closed half-spaces or hyper-planes.This makes a polyhedral set inherently convex, as the intersection ofconvex sets is convex. This leads to the polyhedral division of a polyhedraldomain.Definition 2.23 (Polyhedral Subdivision). We call the setP = {P1, . . . , Pn}a polyhedral subdivision of the convex set Ω ⊂ Rd if1. each Pi is a polyhedral set,72.2. Polynomials and Piecewise Functions2.⋃ni=1 Pi = Ω,3. dimPi = d for all i = 1, . . . , n, and4. intPi ∩ intPj = ∅ for all i, j = 1, . . . , n such that i 6= j.Due to 2, the (convex) set Ω is implicitly polyhedral. Using this, we candefine the class of functions which we will focus on.Definition 2.24 (Piecewise polynomial functions). We denote Pk(P) asthe class of piecewise polynomial functions such that for each P ∈ P, therestriction to P is a polynomial function of degree at most k. The familyof polynomial functions of degree over Rd will be denoted as Pk(Rd). Thenotation f|P (x) will be used to denote the restriction of the function f onP .Note that the values have to agree at the boundaries, to define a (con-tinuous) well-defined function. When we talk about a piecewise function,we put certain restrictions on the function and its domain. Without loss ofgenerality we assume1. The dimension of dom f is d, and2. dom f is the union of a finite number of convex polyhedral set ofdimension d such that dom f = P1 ∪ . . . ∪ Pn, and intPi ∩ intPj =∅, for i 6= j.These restrictions are fairly general because anything less than an d- di-mensional domain can be formulated as a problem in lower dimension, andhence can be studied in a different coordinate system. In addition, if thedimension of any polyhedral set is less than d, we can simply remove it asit will be contained in a polyhedral set of dimension d and that portion canhence be recovered by continuity of f on the relative interior of dom f .Proposition 2.25 (Minimum number of points for a k-degree polynomial).The minimum number of points required to define a polynomial of degree kin Rd arek∑m=0(m+ d− 1m)82.2. Polynomials and Piecewise FunctionsProof. A k-degree polynomial in Rd can be written ask∑m=0nm∑i=1αim d∏j=1xaijj︸ ︷︷ ︸m power terms︸ ︷︷ ︸summing over all powerswhered∑j=1aij∈Naij = m, ∀ i, (2.2)where nm is the total number of ways to get the power m using differentcombination of variables and will be calculated later. This expression basi-cally sums over all possible combinations of the variables, up to the powerk. So when trying to define a polynomial at given points, one is solvingfor the unknowns αim , we will have equations of the form (2.2)= c wherec ∈ R. As these are linear equations in the unknowns, we will require asmany equations as there are unknowns. So we need∑km=0 nm equations,and hence the value of the function at these many points. The value of nmcan be obtained by calculating the total number of combinations possiblefor the set {li1, . . . , lid} such thatlij ∈ N,d∑j=1lij = m,or in other words, how many ways can we get the power m, by multiplyingdifferent variables. This can be answered easily by the multinomial theoremwhich answers the question of how many terms would there be in the ex-pression (x1 + · · ·+ xd)m, which is(m+d−1m). So the total number of pointsrequired arek∑m=0(m+ d− 1m)Definition 2.26 (poised for k-polynomial interpolation). The set of pointsX = {x1, . . . xn} ⊂ Rd, where n =∑km=0(m+d−1m)are said to be poised forthe interpolation of a polynomial of degree k, if the set of equationsf(x1) = 0,f(x2) = 0,...f(xn) = 0. f ∈ Pk(Rd) (2.3)has a unique solution f0 ∈ Pk(Rd).92.2. Polynomials and Piecewise FunctionsFor defining cubic functions, we will need to use tensors to generalizethe matrix notation used to represent quadratic functions. In our notations,when we first multiply x with a 3rd order tensor, we would be multiplyingit to the third dimension. So for C ∈ Rd×d×d and x ∈ Rd, we denote thedifferent expressions as follows.Cx>′ = Aij =d∑k=1Cijkxk ∈ Rd×d,Cx>′x = Ax = d∑j=1(d∑k=1Cijkxk)xj ∈ Rdandx>Cx>′x = x>Ax = d∑i=1 d∑j=1(d∑k=1Cijkxk)xjxi ∈ Rwhere >′ is used to denote transposing a column vector to a vector alongthe third dimension.Definition 2.27 (Indicator functions). The indicator function of a set Ω ⊆Rd is given byIΩ(ω) ={0 ω ∈ Ω+∞ otherwiseDefinition 2.28 (Quadratic and cubic polynomials). A quadratic polyno-mial q : Rd → R can be represented by12x>Qx+ l>x+ κwhere Q ∈ Rd×dsym (the set of symmetric matrices), l ∈ Rd and κ ∈ R. A cubicpolynomial will be denoted as16x>Cx>′x+ 12x>Qx+ l>x+ κDefinition 2.29 (PLQ and PC function). A Piecewise Linear Quadratic(PLQ) function is a special case of piecewise polynomial functions with apolyhedral domain, such that on each polyhedral set, the function is de-fined by a quadratic expression. Piecewise cubic (PC) functions are definedsimilarly, where the function is defined using a cubic expression on eachpolyhedral set.102.3. Triangulations: Special case of Polyhedral DivisionThe class of convex PLQ functions is an interesting class of functionsand will be discussed in detail. The class can be split further based on howthe functions on neighbouring pieces interact with each other.Definition 2.30 (Neighbours and Common Boundaries). Polyhedral setsPi and Pj are said to be neighbours if the affine hull of Pi∩Pj is of dimensiond − 1. The affine hull of the intersection is a hyperplane and can hence berepresented as {x|aTx = b} and it is called the common boundary.2.3 Triangulations: Special case of PolyhedralDivisionWe will consider a special case of a polyhedral division for discussing afew results from [Wac17] in Chapter 5. For ease of understanding, we willassume X ⊆ Rd to avoid using complex measure theory in our definitions.Definition 2.31. [AF03, Definition 2.1,2.3][Lp spaces and p-norm] A mea-surable function f : X → R is said to belong to the space of functions Lp(X)for 1 ≤ p < +∞ if‖f‖p =(∫X|f |pdx)1/p< +∞. (2.4)For p = +∞, L∞ is defined as the set of functions that are bounded almosteverywhere and the norm used is‖f‖∞ = inf {c ≥ 0| |f(x)| ≤ c for almost every x ∈ X} .The elements of Lp(X) are equivalence classes of measurable functionssatisfying (2.4), where two functions are equivalent if they are equal almosteverywhere in X.Definition 2.32 (Sobolev Spaces). A function f : X → R is said to be inthe space W k,p(X), where k ∈ N and 1 ≤ p ≤ +∞ if f as well as its weakderivatives[Leo09, Definition 10.1] up to k are in Lp(X).Definition 2.33. [Wac17, Definition 2.1] A finite set of d-dimensional sim-plices T = {T1, . . . , Tn} is a triangulation of Ω, if the following are true.1. int(Ti) ∩ int(Tj) = ∅ for all 1 ≤ i < j ≤ n2. Ω =⋃ni=1 Ti, and112.3. Triangulations: Special case of Polyhedral Division3. Ti ∩ Tj is either empty or a common face of both Ti and Tj for all1 ≤ i < j ≤ n.We use F(T ) to denote the set of common boundaries of the form Ti ∩ Tjthat are affine and of dimension d− 1.Piecewise polynomial functions on a triangulation T will be denoted asPk(T ). An initial assumption on the triangulation is to prevent it frombeing trivial. Here, diam stands for the largest distance between the pointsused to represent T .Assumption 2.34. [Wac17, Assumption 2.3] A family of triangulations{Th}h∈(0,1] is non-degenerate if there exists ρ1 > 0 such thatdiamT ≤ h diam Ω,diamBT ≥ ρ1 diamTholds for all T ∈ Th, h ∈ (0, 1]. Here, BT is the largest ball in T . If thereexists ρ2 > 0, such that additionallydiamT ≥ ρ2h diam Ωholds for all T ∈ Th, h ∈ (0, 1], then {Th} is called quasi-uniform.This ensures that the triangulation is slowly becoming ‘smaller’ and willhence approximate any function more precisely as h approaches 0. As wetalk about conforming approximations, we will define the set of interpolationfunctions.Definition 2.35. [Wac17, Definition 2.2] The global interpolant in Pk(T )of a continuous function u : X → R is the funtion IkT u ∈ Pk(T ). Theinterpolant is unique for a fixed k because it satisfiesIkT u(x) = u(x)for a set of poised points x ∈ T, T ∈ T .Interpolation on triangulations would result in piecewise functions thatmight not be differentiable at the boundaries hence will have a jump in thegradient.Definition 2.36. [Wac17, Definition 2.5] Let T be a triangulation andF ∈ F be an interior facet. Fix a normal unit vector nF of F . For afunction u ∈ C(Ω) which is differentiable on both cells adjacent to F , thegradient jump is defined asr∇u>nFzF(x) = lim→0(∇u(x+ nF )−∇u(x− nF ))>nF (2.5)12Chapter 3Linear-time convexity testfor low-order piecewisepolynomialsIn this chapter we characterize the convexity of PLQ and PC functions.We reduce checking for continuity and convexity to only checking a fixednumber of inequalities at a finite number of points. The number of pointsused are shown to be linearly proportional with respect to the number ofvertices, hence the test will be in linear-time with respect to the number ofvertices in the domain. We first deal with continuity.3.1 ContinuityChecking continuity of a PLQ function requires only checking the conti-nuity of the pieces at the common boundaries, as we know that the interiorof the pieces are polynomial expressions, which are continuous in Rd. Wewill first prove checking the continuity at the boundaries can be done in lin-ear time with respect to the number of edges in 2-dimensions and generalizeto checking the continuity of any piecewise polynomial expression in Rd.Lemma 3.1. Let P1 = {x : a>x ≤ β} ⊂ Rd, and P2 = {x : a>x ≥ β} ⊂ Rd.For x ∈ Rd, define fi(x) = 12x>Qix+ (qi)>x+κi and f(x) = fi(x) if x ∈ Pifor i = 1, 2.Assume there are m = d(d + 1)/2 points xi ∈ P1 ∩ P2 with xi 6= xj fori 6= j, such that f(xj) = f1(xj) = f2(xj) and the points xi are poised forquadratic interpolation with respect to P1 ∩ P2. Then f1(x) = f2(x) for allx ∈ P1 ∩ P2; hence f is a continuous function on P1 ∪ P2.Proof. We only need to check continuity on the hyperplane H = P1 ∩ P2.The function fi is quadratic on H and its restriction to H is uniquely definedby d(d + 1)/2 parameters. (When d = 2, dim H = 1 and the restrictionis a univariate quadratic function uniquely defined by 3 parameters.) Since133.1. Continuitythe set {x1, . . . , xm} is poised for quadratic interpolation, there is a uniquequadratic function going through all points xi so f1 and f2 can only differoutside H. Consequently, f is a continuous function on H and so on P1 ∪P2.For PLQ functions of fixed dimensions, if we check a finite number ofpoints on each common boundary, we can ensure continuity of the function.Note that this proof can be extended to piecewise functions on polyhedralsets such that each piece is defined by a polynomial expression in Rd.Corollary 3.2. Under the same assumptions as Lemma 3.1, if there is asufficient number of points xi ∈ P1 ∩ P2 that are poised for k-degree polyno-mial interpolation with respect to P1∩P2, such that f(xj) = f1(xj) = f2(xj).Then f1(x) = f2(x) for all x ∈ P1 ∩P2; hence f is a continuous function onP1 ∪ P2.Using the results from above, we obtain a linear-time algorithm withrespect to the number of edges.Theorem 3.3. Given a list of polyhedral sets P = {Pi | 1 ≤ i ≤ n} forminga polyhedral subdivision of Rd, and quadratic functions qi : Rd → R∪{+∞}such that f(x) = qi(x) on Pi, checking whether f is a continuous functioncan be done in O (ne) time where ne is the number of edges of the polyhedralsubdivision.The points used to check continuity are the 2 points used to denote theedge along with their mid-point. In fact, in the 2-dimensional case, the checkcan be done in linear time with respect to the number of vertices that areused to define the domain, by using the following fact.Fact 3.4 ([AMO93, Property 8.7]). Let G = (V, E) be a connected planargraph with ne edges and nv vertices. Assume nv ≥ 3. Then ne ≤ 3nv.Since the domain of a 2 dimensional PLQ function is in R2 it is a planargraph, and hence the check is linear in the number of the vertices.Corollary 3.5. Given a list of polyhedral sets P = {Pi | 1 ≤ i ≤ n}forming a polyhedral subdivision of R2, and quadratic functions qi : R2 →R ∪ {+∞}, such that that f(x) = qi(x) on Pi, checking whether f is acontinuous function can be done in O (nv) time where nv is the number ofvertices in the polyhedral subdivision.143.2. Convexity3.2 ConvexityFor convexity, we will approach the problem by splitting it into differentcases.3.2.1 Convexity in RConvexity of a function f : R→ R ∪ {+∞} can be checked in 3 steps.First, we check convexity of the function on each interval that is definedby a polynomial, which can simply be done by checking if the second deriva-tive of the function is nonnegative on the given interval. This is easy forquadratics and cubic functions since for quadratics, the second derivativeis constant, while for cubics it is a linear function, which only needs to bechecked at the extremities of the interval.Second, we check for any violation of continuity at the breakpoints{x1, . . . , xm},where m is finite.Third, we verifylimx↗xif ′(x) ≤ limx↘xif ′(x),which reduces to f ′i−1(xi) ≤ f ′i(xi),where fi is the polynomial on the piece [xi, xi+1].This ensures that the subdifferential at xi is nonempty. Hence, if we fixthe maximum degree of the polynomials on the pieces, checking convexityfor R1 can be done in linear time with respect to the number of breakpoints.This is because− the convexity of the interior can be checked in constant time for eachpiece and hence in linear time with respect to the number of break-points, and− the convexity at the boundary simply requires checking if the left handderivative is lesser or equal to the right hand derivative at each breakpoint, which can also be done in linear time.Using the arguments from above, convexity of a piecewise function in R canbe characterized as follows.153.2. ConvexityProposition 3.6. A piecewise polynomial (continuous) function f : R →R∪ {+∞} with breakpoints at x1 . . . xm ∈ dom f is convex if and only if forall i = 1, . . . ,m− 1f ′′i (x) ≥ 0 for all x ∈ (xi, xi+1), and (3.1)f ′i−1(xi) ≤ f ′i(xi). (3.2)3.2.2 Convexity of PLQ functions in R2For PLQ functions, checking the convexity at any point in the interiorof each polyhedral set can be done by checking whether the Hessian of thefunction defined on each piece is positive semidefinite. The edges require alittle more work.Lemma 3.7. Using the same notations as Lemma 3.1, define f˜i = fi + IPiand assume f is continuous on P1 ∪ P2. In addition, assume Q1, Q2 arepositive semidefinite, and for i = 1, 2∂f˜1(xi) ∩ ∂f˜2(xi) 6= ∅. (3.3)Then(i) there exist δi ≥ 0, i = 1, 2 with(Q2 −Q1)xi + q2 − q1 = δiaand (3.3) holds for all x ∈ [x1, x2].(ii) if δ1 ≤ δ2 then (3.3) holds for all x ∈ x1 + R+(x2 − x1).(iii) if δ1 ≥ δ2 then (3.3) holds for all x ∈ x2 + R+(x1 − x2).Proof. Apply [HUL93, Corollary 3.1.2, p. 114] to obtain ∂f˜i(x) = ∇fi(x) +NPi(x). Because H = P1 ∩P2 is a hyperplane, we have NP1(x) = {x+ γ1a :γ1 ≥ 0} and NP2(x) = {x− γ2a : γ2 ≥ 0}. Note that∂f˜1(x) ∩ ∂f˜2(x) 6= ∅ ⇔ ∃γ1, γ2 ≥ 0, ∇f1(x) + x+ γ1a = ∇f2(x) + x− γ2a,⇔ ∃γ1, γ2 ≥ 0, (Q2 −Q1)x+ q2 − q1 = (γ1 + γ2)a,⇔ ∃δ ≥ 0, (Q2 −Q1)x+ q2 − q1 = δa,which proves the existence of δ1, δ2 and the first part of (i). Take x =(1− α)x1 + αx2, we have(Q2−Q1)x+q2−q1 = (1−α)[(Q2 −Q1)x1 + q2 − q1]+α[(Q2−Q1)x2+q2−q1].163.2. ConvexitySince (3.3) holds for x = x1, x = x2, we have(Q2 −Q1)x+ q2 − q1 = [(1− α)δ1 + αδ2]a.Now the remaining of (i) follows as do (ii) and (iii) since in all those casesx belong to a set that ensures that (1−α)δ1 +αδ2 = δ1 +α(δ2−δ1) ≥ 0.So if the subdifferential is nonempty at 2 points on the boundary, thesame can be said at every point between them. Moreover, if δ2 < δ1 , thefunction is convex along the whole ray starting at x2 and pointing towardsx1 and along the ray starting at x1 and pointing towards x2 when δ2 > δ1.Equality means it can be extended in both directions. Thus for 2 dimensionalPLQ functions, the check on convexity can be summarised by the followingtheorem.Theorem 3.8. Assume f : R2 → R ∪ {+∞} is piecewise defined withf = mini f˜i, f˜i = fi + IPi, and fi =12x>Qix+ (qi)> + κi with Pi polyhedralsets defining a subdivision of R2, then(i) the mapping f is a well-defined function if, and only if, for any edgese separating Pi and Pj, there exist 3 points x1, x2, and x3 that arepairwise distinct, at which fi(xk) = fj(xk) for k = 1, 2, 3. In that case,f is a PLQ function so it is lsc and continuous on ri dom f .(ii) If f is a PLQ function and all matrices Qi are positive semidefinitethen f is convex if, and only if, for any edge e separating Pi and Pjwithe = Pi∩Pj ⊂ {x : a>x = β}, Pi ⊂ {x : a>x ≥ β}, Pj ⊂ {x : a>x ≤ β},there exist 2 distinct points x1, x2 ∈ e and δ1, δ2 ∈ R with(Qi −Qj)xk + qi − qj = δka (3.4)for k = 1, 2. When e is the bounded segment [x1, x2], we must haveδ1, δ2 ≥ 0 while when e is the ray x1 + R+(x2 − x1), we must have0 ≤ δ1 ≤ δ2.Proof. Continuity follows from Lemma 3.1 while [BLP16, Theorem 5.1] re-duces checking for convexity to verifying the subdifferential is non-empty onthe edges, which is ensured by Lemma 3.7.Corollary 3.9. Checking whether a given piecewise quadratic function f :R2 → R ∪ {+∞} is continuous or convex requires O(n) worst-case timeasymptotic complexity, where n is the number of vertices in the partitiondefining dom f .173.2. ConvexityProof. Theorem 3.8 shows checking continuity or convexity takes constanttime for each edge while Fact 3.4 shows the number of edges is upper-bounded by a linear function of the number of vertices.Algorithm 1: Checking the convexity of a bivariate PLQ function1 procedure isConvex(P , f)2 isContinuous = true; isConvex = true;3 forall Edge e starting at x1 and going through x2 that separatesPi from Pj do4 x3 = (x1 + x2)/2;5 a = (x12 − x22, x21 − x11);6 β = x12x21 − x11x22;7 // Pi has edge e and is contained in {x : a>x ≥ β}8 // Pj has edge e and is contained in {x : a>x ≤ β}9 if not[∧3k=1(fi(xk) = fj(xk))]then10 isContinuous = false; isConvex = false; return11 if not [Qi  0∧Qj  0] then12 isConvex = false; return13 for k = 1, 2 compute δk such that (Qi−Qj)xk + qi− qj = δka;14 if not[∧2k=1 ∃ (δk ≥ 0)]then15 isConvex = false; return16 if e is unbounded and δ1 > δ2 then17 isConvex = false; return18 // if e is bounded, the convexity test is true19 return // isConvex=trueExample 3.10 ([Sun92, Example p. 505]). Consider the functionf(x) =f1(x) = x21 + x22, when x1 ≤ 0 and x2 ≥ 0,f2(x) = x21 + x22 + x1x2, when x1 ≥ 0 and x2 ≥ 0,+∞, otherwisewhich is shown in Figure 3.1(a).Take x1 = (0, 0), x2 = (0, 1), and x3 = (0,−1) and verify that f1(xi) =f2(xi), so f is continuous. For convexity, we have Q1 =[2 00 2], Q2 =183.2. Convexity(a) Example 3.10 (b) Example 3.11Figure 3.1: Examples of convex and nonconvex piecewise quadratic functions[2 11 2], a> = (1, 0), and β = 0. So Equation (3.4) for x1 becomes(00)=(δ10)whose only solution is δ1 = 0. Similarly, Equation (3.4) for x2 is(10)=(δ20)with unique solution δ2 = 1. Since δ1, δ2 ≥ 0, ∂f is nonempty on [x1, x2].In addition, since δ1 = 0 ≤ 1 = δ2, ∂f is nonempty on x1 + R+(x2 − x1) ={0} × R+. Consequently, f is convex.Example 3.11 ([Sun92, Example p. 505]). Now consider the functionf(x) ={f1(x) = x21 + x22, when x1 ≤ 0,f2(x) = x21 + x22 + x1x2, when x1 ≥ 0which is depicted in Figure 3.1(b). Continuity follows from the same com-putation as the previous example. As for convexity, we find again that ∂fis nonempty on {0} × R+. However, δ1 6≥ δ2 and ∂f is empty at any point(−, 0) for any  > 0. Hence, the function f is not convex.193.2. Convexity(a) Bounded (b) UnboundedFigure 3.2: The types of polyhedraRemark 3.12. Theorem 3.8 gives a practical technique to apply Corollary 4.3,which provides a necessary and sufficient condition to check for PLQ difference-definite functions. This can be done by checking a finite number of pointsto determine whether a convex piecewise quadratic function is difference-definite.3.2.3 Cubic Functions in R2With cubic functions, the convexity test has more factors to consider.The representation of the cubic function isf˜(x) =16x>Cx>′x+ 12x>Qx+ l>x+ κ (3.5)where C ∈ R2×2×2 is a third order tensor, Q ∈ R2×2 is a symmetric matrixand l ∈ R2. The gradient of these functions is∇f(x) = 12Cx>′x+Qx+ l,which is a vector of length d where each row is a quadratic function of x.For checking the convexity in the interior, we need to be able to defineevery point in a polyhedral set using a finite set of vertices and directionpoints that are used to define the set. Using [RW98, Corollary 3.53] we candescribe a bounded polytope in Rd as the convex hull of its vertices. SoP ={m1∑i=1λivi∣∣∣ m1∑i=1λi = 1, λi ≥ 0}= conv({v1, . . . , vm1}),203.2. Convexitywhere vi are the vertices of the polytope. For an unbounded polyhedral set,we also need to add the directions to consider all the points for the edgesthat are unbounded. SoP =m1∑i=1λixi +m2∑j=1λ′jγjdj∣∣∣ m1∑i=1λi = 1,m1∑i=1λ′i = 1, λi ≥ 0, λ′j ≥ 0, γj ≥ 0 ,=m1∑i=1λixi +m2∑j=1δjdj∣∣∣ m1∑i=1λi = 1, λi ≥ 0, δj ≥ 0 , (3.6)where δj = λ′jγj and dj are the directions for the unbounded components ofthe polyhedron. In our case, as we store the unbounded edges as rays suchas (v1, v2) like in Figure 3.2(b), dj will be of the form v2 − v1.Lemma 3.13. Let P ⊆ Rd be a polyhedral set that is defined by the verticesV = {v1 . . . vm1} and directions D = {d1, . . . , dm2} where each di ∈ D is ofthe form x′i − v′i for some v′i ∈ V and some x′i ∈ Rd. For x ∈ Rd, definef|P (x) =16x>Cx>′x+ 12x>Qx+ l>x+ κ and f˜(x) = f|P (x) + δP (x). Thenthe function f˜(x) is convex if and only if the matrix Cx>′ + Q is positivesemidefinite for all the vertices v ∈ V and Cd>′ is positive semidefinite forall d ∈ D.Proof. Note that Cx>′ +Q is the Hessian of the function f|P (x)(⇐)Note that for a set of positive semidefinite matrices {Ai|i = 1, . . . , n}, anymatrix A ∈ A = {∑ni=1 λiAi|λi ≥ 0 < +∞} will be positive semidefinite.For any point x in the interior of the polyhedral set, the Hessian is∇2f˜(x) = ∇2f|P (x) = Cx>′ +Q.Using (3.6), this is the same asCm1∑i=1λivi +m2∑j=1δjdj+ 1(Q)for some λi, δj ≥ 0. Opening the bracket gives usm2∑j=1δjCd>′j +m1∑i=1λiCv>′i +m1∑i=1λi(Q),=m2∑j=1δj(Cd>′j ) +(m1∑i=1λi(Cv>′i +Q)).213.2. ConvexitySo for pieces that are bounded polytopes, if Cv>′i +Q is positive semidefinitefor all vertices, any point in the piece has a positive semidefinite Hessian.For unbounded polyhedral sets, in addition to the Hessian at the vertices,if Cd>′j is positive semidefinite for all directions dj ∈ D the function hasa positive semidefinite Hessian everywhere in the set. As in our case, thedirection points are of the form v2−v1 for an infinite edge v1 +R+(v2−v1),we will have to check C(v2 − v1)>′  0 in addition to the vertex checks.Hence the function f˜ has a positive semidefinite Hessian everywhere inint dom f˜ . Consequently, f˜ is convex.(⇒)By contradiction, suppose f˜ is convex and there exists a point x ∈ D∪Vsuch that Cx>′ +Q  0. The function f˜ is convex if and only if the Hessianis positive semidefinite everywhere in the interior of its domain. As x ∈ Pthere exists a sequence of points {xn}n∈N ⊂ intP such that xn → x. As theHessian is a linear function from Rd to Rd×d and is hence continuous, thisimplies Cx>′n +Q→ Cx>′ +Q. Using Proposition 2.17 the set of semidefinitematrices Sd+ is closed in the set of matrices Rd×d. As Cx>′n + Q ∈ Sd+, thisimplies Cx>′ +Q ∈ Sd+ which is a contradiction. Hence the function cannothave a positive semidefinite Hessian everywhere in ri dom f˜ and hence f˜ isnot convex.Lemma 3.14. Let P1 = {x : a>x ≤ β} ⊂ R2, and P2 = {x : a>x ≥β} ⊂ R2. For x ∈ R2, define fi(x) = 16x>Cix>′x+ 12x>Qix+ l>i x+ κi andf(x) = fi(x) if x ∈ Pi for i = 1, 2. Define f˜i = fi + IPi and assume f iscontinuous on P1∪P2. In addition, assume the functions f˜i are convex, andfor i = 1, 2∂f˜1(xi) ∩ ∂f˜2(xi) 6= ∅. (3.7)then(i) there exist δi ≥ 0 for i = 1, 2 with(∇f2 −∇f1)xi = δia.If (∇f2−∇f1)(x) does not change sign of any row for all x ∈ [x1, x2],then (3.7) holds for all x ∈ [x1, x2].(ii) If (∇f2−∇f1)(x) does not change sign of any row for all x1 +R+(x2−x1), then (3.7) holds for all x1 + R+(x2 − x1).If (∇f2−∇f1)(x) does not change sign of any row for all x2 +R+(x1−x2), then (3.7) holds for all x2 + R+(x1 − x2).223.2. Convexity(a) (∇f2 −∇f1)j is a constant (b) (∇f2−∇f1)j is a linear expres-sionFigure 3.3: Cubic convexity: cases when ∇f2 −∇f1 is not quadraticProof. Apply [HUL93, Corollary 3.1.2, p. 114] to obtain ∂f˜i(x) = ∇fi(x) +NPi(x). Because H = P1 ∩P2 is a hyperplane, we have NP1(x) = {x+ γ1a :γ1 ≥ 0} and NP2(x) = {x− γ2a : γ2 ≥ 0}. Note that∂f˜1(x) ∩ ∂f˜2(x) 6= ∅ ⇔ ∃γ1, γ2 ≥ 0, ∇f1(x) + x+ γ1a = ∇f2(x) + x− γ2a,⇔ ∃γ1, γ2 ≥ 0, (∇f2 −∇f1)x = (γ1 + γ2)a,⇔ ∃δ ≥ 0, (∇f2 −∇f1)x = δa, (3.8)which proves the existence of δ1, δ2 for x1, x2.For the second part of (i), we will prove it for an arbitrary row j of∇f2 − ∇f1. Notice that on the hyperplane a>x = β, the expressions ineach row of ∇f2 −∇f1 are at most quadratics in one dimension, which areparabolas.So far, we know that δ1 and δ2 exist. Graphically, the significance of δifor row j is checking the possibility of shifting the parabola ∇f2 down (orup if aj < 0 ) by a certain scalar multiple of |aj | to make xi the solution, asshown in Figure 3.4 and 3.5.For the rows of (∇f2 −∇f1)(x) that are constant with respect to x, weare done as we know that (∇f2 −∇f1)j cannot change sign on a>x− β, asshown in Figure 3.3(a).For rows that are linear expressions, as shown in Figure 3.3(b), we haveexactly the same check as in the PLQ case. So as δ1 and δ2 exist, forany point x = (1− α)x1 + αx2, we can show the existence of a δx such that(∇f2−∇f1)j(x) = δxa. Hence the expression doesn’t change sign for [x1, x2].233.2. Convexity(a) xi are the roots of (∇f2 −∇f1)i, (∇f2 −∇f1)(x1+x22 ) < 0(b) xi are the roots of (∇f2 −∇f1)i, (∇f2 −∇f1)(x1+x22 ) ≥ 0Figure 3.4: Cubic convexity: case when δi ≥ 0, aj=0If δ1 ≤ δ2, then the expression doesn’t change sign for the ray starting at x1and pointing towards x2. Similarly if δ1 ≥ δ2, then the expression doesn’tchange sign for the ray starting at x2 and pointing towards x1.For the case where the row is a quadratic expression, we will considerdifferent cases. :Let s1j , s2j be the roots the row on the hyperplane a>x = β.Case 1: aj = 0As (3.7) holds for x1 and x2, (∇f2−∇f1)(xi) = 0, hence this is equivalentto the case{s1j , s2j} = {x1, x2},=⇒ [s1j , s2j ] = [x1, x2]As the only places where ∇f2 − ∇f1 changes signs is at the roots, if thereexists a point x3 ∈ [x1, x2] such that((∇f2 −∇f1)(x3))j≥ 0, then (∇f2 −∇f1)(x) ≥ 0 for all x ∈ [x1, x2]), If no such point exists, we are dealing witha case like Figure 3.4(a) and thus the function is not convex on this edge.Case 2: aj 6= 0.As (3.8) holds for x1 and x2, it means they lie in the region whereaj(∇f2−∇f1)(x) ≥ 0, hence they cannot be the roots and will have furthersub-cases. The first is when the roots are not real, as shown in Figure 3.5(a).Case 2.(a): s1j , s2j are complex or s1j = s2j . This means the expression243.2. Convexity(a) ∇f2 ≥ ∇f1 everywhere (b) ∇f2 > ∇f1 outside the rootsand xi on the same side(c) ∇f2 > ∇f1 between the roots (d) ∇f2 > ∇f1 outside the rootsbut xi not on the same sideFigure 3.5: Cubic convexity: cases where aj , δ1, δ2 ≥ 0253.2. Convexity(∇f2 −∇f1)(x) has the same sign for all x ∈ {x : a>x = β}. We know thataj(∇f2 −∇f1)(xi) ≥ 0, i = 1, 2 (3.9)=⇒ aj(∇f2 −∇f1)(x) ≥ 0, ∀x ∈ [x1, x2] (3.10)If the roots are real, the interval [s1j , s2j ] will be non empty. Since for theintervals [s1j , s2j ] and [x1, x2] are on the hyperplane a>x = β, the intersectionwill result in further sub-cases, as shown in Figure 3.5.Case 2.(b): [s1j , s2j ] ∩ (x1, x2) = ∅. Here, at most one of x1, x2 can be aroot. So this covers the cases where[s1j , s2j ] ∩ [x1, x2] = ∅ or [s1j , s2j ] ∩ [x1, x2] = {s1} or [s1j , s2j ] ∩ [x1, x2] = {s2}.In this case, clearly none of the roots lie in the interior of [x1, x2] hencethe expression will not change sign inside the interval. So, once again, (3.9)follows from (3.10)Case 2.(c): [x1, x2] ( [s1j , s2j ]. Here, at most one of x1, x2 can be theroots. In this case, once again, the expression will not change sign in theinterior of the interval. Hence (3.9) follows from (3.10).Case 2.(d): [s1j , s2j ] ( [x1, x2] . Here, at most one of x1, x2 can bethe roots. Since at least one root will lie in the interior of [x1, x2] theexpression will change sign at least once. As (3.10) holds, for any x ∈(s1j , s2j ), aj(∇f2 −∇f1)(x) < 0.Case 2.(e): [s1j , s2j ] = [x1, x2]. This case follows from Case 1.Theorem 3.15. Assume f : R2 → R∪ {+∞} is piecewise defined with f =mini f˜i, f˜i = fi+ IPi, and fi = fi(x) =16〈x, x>Cix〉+ 12〈x,Qix〉+ 〈li, x〉+κiwith Pi polyhedral sets defining a subdivision of R2. Let s1k, s2k be the rootsof the kth row of ∇fi −∇fj, then(i) the mapping f is a well-defined function if, and only if, for any edgese separating Pi and Pj, there exist 4 points x1, x2, x3 and x4 that arepairwise distinct, at which fi(xk) = fj(xk) for k = 1, 2, 3, 4. In thatcase, f is a piecewise cubic function so it is lsc and continuous onri dom f .(ii) If f is a piecewise cubic function, then f is convex in the interior of Piif and only if the matrix Civ+Qi is positive semidefinite for all verticesv that define Pi and Cid is positive semidefinite for all directions d thatdefine Pi263.3. Implementation of the characterization(iii) If f is a piecewise cubic function and is convex in the interior of eachPi, then f is convex if, and only if, for any edge e separating Pi andPj with e = Pi ∩ Pj ⊂ {x : a>x = β}, Pi ⊂ {x : a>x ≥ β}, Pj ⊂ {x :a>x ≤ β}, there exist 2 distinct points x1, x2 ∈ e and δ1, δ2 ∈ R with(∇fi −∇fj)(xk) = δka (3.11)for k = 1, 2. When e is the bounded segment [x1, x2], we must haveδ1, δ2 ≥ 0 and for each j, [s1j , s2j ]∩[x1, x2] is either empty, a singleton or[x1, x2] along with (∇f2−∇f1)(x3) ≥ 0, where x3 ∈ (x1, x2). When e isthe ray x1+R+(x2−x1), we must have 0 ≤ δ1 ≤ δ2 and [s1j , s2j ]∩[x1, x2]to be empty or a singleton.Proof. Continuity follows from Corollary 3.2. The convexity on the interioris reduced to checking for positive semidefiniteness of the Hessian at a fi-nite number of points by Lemma 3.13 while [BLP16, Theorem 5.1] reduceschecking for convexity to verifying the subdifferential is nonempty on theedges, which is ensured by Lemma 3.14.3.3 Implementation of the characterizationThe characterization is used to construct an algorithm that gives aboolean result depending on whether the input function is convex or not.While Algorithm 1 is used for PLQ functions in 2D, Algorithm 2 is used totest convexity of a PC function. Algorithm 3 is a subroutine used in thePC function case and deals with convexity checks on the boundaries. Thedata structure uses a list of edges to define the function and is explainedin detail in Section 4.3. Different types of convex and non-convex functionswere used as input. A few examples are shown in Appendix B.273.3. Implementation of the characterizationAlgorithm 2: Checking the convexity of a bivariate PC function1 procedure isConvex(P , f)2 isContinuous = true; isConvex = true;3 foreach Edge e starting at x1 and going through x4 thatseparates Pi from Pj do4 // Select points poised for cubic interpolation5 xk = ((1− i−13 )x1 + ( i−13 )x4) for k = 1, 2, 3, 4;6 // Continuity Check7 if not [∧4k=1(fi(xk) = fj(xk))] then8 isContinuous = false; isConvex = false; return9 // Interior Convexity Check10 if not [∧k∈{1,4}((2Cixk +Qi  0) ∧ (2Cjxk +Qj  0))]then11 isConvex = false; return12 // Interior Convexity Check for unbounded edges13 if e is unbounded andnot[(Ci(x4 − x1)  0) ∧ (Cj(x4 − x1)  0)] then14 isConvex = false; return15 isConvex=CheckBoundaryConvexity(e,fi,fj);16 return // isConvex=true283.3. Implementation of the characterizationAlgorithm 3: Checking the convexity of the boundaries of a bi-variate PC function1 procedure CheckBoundaryConvexity(e,f1,f2)2 edge e starting at x1 going through x2;3 isConvex = true;4 ∇f1(x) = Gradient of f1(x); // f1 in {x : a>x ≥ β}5 ∇f2(x) = Gradient of f2(x); // f2 in {x : a>x ≤ β}6 a = (x22 − x12, x21 − x11);7 β = a1x11 + a2x12;8 for k = 1, 2 compute δk such that (∇f1 −∇f2)(xk) = δka;9 if not [there exist δ1 ≥ 0, δ2 ≥ 0] then10 isConvex = false; return11 // Edge Convexity Check12 foreach Expression exi in ∇f2 −∇f1 do13 if exi is quadratic for a>x− β then14 (s1i , s2i ) = Roots of quadratic equation exi = 0 in theplane a>x− β;15 // Finding relative position of vertices withrespect to the roots16 for k = 1, 2 compute λki such that (1− λki )s1i + λki s2i = xk;17 // No real roots or unique root will be convexon the whole edge and beyond18 if (si1 and s2i are complex) ∨ (s1i = s2i ) then19 Set λ1i = λ2i ;20 // Special case- vertices are roots; checkconvexity at mid point21 if({λ1i , λ2i } = {0, 1}) ∧ ((∇f2 −∇f1)(x1+x22 )>a < 0)then22 isConvex=false; return23 if not[(λ1i , λ2i ≤ 0) ∨ (0 ≤ λ1i , λ2i ≤ 1) ∨ (λ1i , λ2i ≥ 1)] then24 isConvex=false; return25 else if exi is linear for a>x− β then26 // Only need to take care of unbounded edge27 Set λki = 1 + δi ;28 else exi is constant29 // Convex on whole edge and beyond30 Set λ1i = λ2i = λ1i−1;31 // Unbounded Edge Convexity Check32 if e is unbounded and not[(λ2i ≤ λ1i ≤ 0 ∨ λ2i ≥ λ1i ≥ 1) ∀i] then33 isConvex=false; return34 return // isConvex=true29Chapter 4Difference Definite FunctionsWith a way to characterize convexity of a PLQ function, we will narrowdown our class of functions to convex PLQ functions. The class can bedivided into difference-definite and indefinite functions based on how theyinteract with their neighbouring pieces.Definition 4.1. [Sun92, Definition 2.2] A convex PLQ function is said to bedifference-definite if the difference between the expression in any two neigh-bouring polyhedral sets in the domain has a positive or negative semidefiniteHessian. If this is not the case, the function is said to be difference-indefinite.Formally, if Pi and Pj are neighbours withf|Pi(x)− f|Pj (x) =12xTAx+ bTx+ c,then for all x ∈ Rn, (−1)ki,jxTAx ≥ 0,where ki,j is 0 or 1 depending on the pieces being considered. Naturally,ki,j = 0 if and only if kj,i = 1.Figure 4.1: A difference-definite functionWhen restricted to a grid, the class of difference-definite functions ischaracterized by an almost separable representation. For ease of notation,304.1. Properties of convex PLQ functionswe will denote difference-definite convex PLQ functions simply as difference-definite or DD functions and difference-indefinite convex PLQ functions asdifference-indefinite or DI functions.4.1 Properties of convex PLQ functionsThe motivation behind creating these classes is to identify a subclass ofconvex PLQ functions that are almost separable and hence easier to manip-ulate.Proposition 4.2. [Sun92, Proposition 2.1] Let f be a convex PLQ function.Let P1 and P2 be 2 neighbouring polyhedral sets in dom f with commonboundary in {x|a>x = β}. Let f1 and f2 be the quadratic expressions of fon P1 and P2. Then there exists a vector a¯ and b¯ such thatf2(x) = f1(x) + [a>x− b][a¯>x− b¯] (4.1)If f is difference-definite, then a and a¯ are linearly dependent. If f isdifference-indefinite, then there exists a neighbouring pair of polyhedral setssuch that a¯ is linearly independent of a.This also gives us another way to show that all the convex PLQ functionsin 1D are difference-definite, as no real number is linearly independent ofthe other. It is interesting to see that the difference-definite and difference-indefinite functions have properties of a and a¯ that are complementary logi-cal statements which is also in line with the way they are defined. The nextcorollary helps us characterize difference-definite functions.Corollary 4.3. [Sun92, Corollary 2.1] A convex PLQ function is difference-definite if and only if for any neighbouring P1, P2 in dom f , the functionf¯(x) ≡{f|P1(x), x is on P1’s side of the common boundaryf|P2(x), x is on P2’s side of the common boundary(4.2)is a convex function.Note that dom f¯ is split into 2 faces separated by a hyperplane evenwhen the boundary between P1 and P2 in dom f is bounded. It is worthnoting that Proposition 4.2 can be used to give another criterion for checkingdifference-definiteness.314.1. Properties of convex PLQ functionsCorollary 4.4. Let f be a convex PLQ function. Then f is difference-definite if and only if for all P1 and P2 that are neighbouring polyhedralsets in dom f with common boundary included in {x|a>x = β}, there existsλ ∈ R such thatf2(x) = f1(x) + [a>x− b][a¯>x− b¯], a = λa¯, (4.3)where f1 and f2 are the quadratic expressions of f on P1 and P2. Similarly,f is difference-indefinite if and only if there exists a neighbouring pair ofpolyhedral sets where (4.3) holds and a¯ is linearly independent of a.Proof. (⇒)Let f be a difference-definite function. Then using Corollary 4.3for arbitrary neigbouring pieces P1 and P2, the function f¯ defined asf¯(x) ={f1(x), x is on P1’s side of the common boundaryf2(x), x is on P2’s side of the common boundary(4.4)is convex. In fact, since f1 and f2 are defined on neighbouring pieces ina difference-definite function to begin with, the new function is difference-definite as well. Hence using Proposition 4.2, there exists λ ∈ R such thata¯ = λa andf2(x) = f1(x) + [a>x− b][a¯>x− b¯].Since P1 and P2 were arbitrary neighbouring pieces, this is true for all neigh-bouring polyhedral sets.(⇐) For the converse, assume the function satisfies (4.3). Then take anarbitrary pair of neighbouring pieces P1 and P2. Using (4.3),f2(x)− f1(x) = [a>x− b][a¯>x− b¯], a = λa¯, λ ∈ R.If λ = 0 we havef2(x)− f1(x) = [a>x− b][−b¯], so∇2(f2 − f1)(x) = 0,Hence ∇2(f2 − f1)(x)  0If λ 6= 0, let b¯ = λb′. Thenf2(x)− f1(x) = λ[a>x− b][a>x− b′], so∇2(f2 − f1)(x) = 2λaa>,324.1. Properties of convex PLQ functions(a) x2 + xy + y2 andx2 + xy + 2y2 + yfor x ≤ 0, y = 0(b) x2 + xy + 2y2 + y and2x2 + xy + 2y2 + 2x + yfor x = 0, y ≥ 0(c) 2x2 +xy+ 2y2 + 2x+ y and2x2 + xy + y2 + 2for x ≥ 0, y = 0(d) 2x2 + xy + y2 + 2 andx2 + xy + y2for x = 0, y ≤ 0Figure 4.2: Checking DD in all pairs of neighbours using Corollary 4.3which is a positive or negative semidefinite matrix as for any x,x>(2λaa>)x = 2λ(a>x)>(a>x) = 2λ‖a>x‖2,so this will either always be nonnegative or always nonpositive. Hence thefunction is difference-definite.The two corollaries also give us a graphical way of visualizing differ-ence definite and indefinite functions, which is illustrated by the followingexamples.334.1. Properties of convex PLQ functions(a) x2 + xy + y2 andx2 + xy + 2y2 + yfor x ≤ 0, y = 0(b) x2 + xy + 2y2 + y and2x2 + xy + 2y2 + 2x + yfor x = 0, y ≥ 0(c) 2x2 +xy+ 2y2 + 2x+ y and2x2 + xy + y2 + 2for x ≥ 0, y = 0(d) 2x2 + xy + y2 + 2 andx2 + xy + y2for x = 0, y ≤ 0Figure 4.3: Checking DD in all pairs of neighbours using Corollary 4.4Example 4.5. Consider the functionf(x) =x2 + xy + y2 x ≤ 0, y ≤ 0x2 + xy + 2y2 + y x ≤ 0, y ≥ 02x2 + xy + 2y2 + 2x+ y x ≥ 0, y ≥ 02x2 + xy + y2 + 2x x ≥ 0, y ≤ 0(4.5)which is shown in Figure 4.1.This is a difference definite function because if we look at the Hessiansof the difference between the pieces that share a common boundary, they344.1. Properties of convex PLQ functionswill always be of the form [a 00 b],where either a or b is 0. This matrix is always positive or negative semidef-inite. Hence the function is difference definite. Alternatively, we can applyCorollary 4.3. When one tries to extend the function as shown in Figure 4.2,it is clear that convexity will not break. Figure 4.3 helps in verifying Corol-lary 4.4. It takes a pair of neigbouring pieces and plots both the functions inboth the pieces in R2. We can see that the 2 planes at which the quadraticsintersect in any of the pairs are actually parallel to each other which meansthat a¯ and a are linearly dependent in all of them. This means the twopieces will not cross each other anywhere when the common boundary isextended and hence will remain convex.An example for a difference-indefinite function can be given in a similarfashion.(a) The function (b) Extending the func-tion along the commonboundary(c) Plotting both piecesin R2Figure 4.4: Difference-indefinite functionExample 4.6. Recall Example 3.10 wheref(x) =f1(x) = x21 + x22, x1 ≤ 0 and x2 ≥ 0,f2(x) = x21 + x22 + x1x2, x1 ≥ 0 and x2 ≥ 0,+∞, otherwise(4.6)was shown to be convex. The function in (4.6) is actually a difference-indefinite function because f1(x)− f2(x) = −x1x2 has Hessian[0 −1−1 0],354.2. Quasi-Separabilitywhich is neither positive nor negative semidefinite. Hence the function isdifference-indefinite. In fact, upon extending the function along the commonboundary like in Figure 4.4(b) or in Example 3.11 the functionf(x) ={f1(x) = x21 + x22, x1 ≤ 0,f2(x) = x21 + x22 + x1x2, x1 ≥ 0is not convex. Another way to understand the loss of convexity is by Fig-ure 4.4(c), where clearly the planes where the two quadratics intersect arenot parallel hence a¯ and a are linearly independent and the function losesconvexity when the boundary is extended.4.2 Quasi-SeparabilitySeparability of a function makes it easier to perform operations like con-jugation on a function as then it can be individually applied to each co-ordinate to yield the result. In fact for a class of functions that only hasquadratics, separability would mean each piece looks likexTDix+ qTi x+ ti,where Di is a diagonal d× d matrix depending on piece Pi. A convex PLQfunction with such pieces is called diagonal.Proposition 4.7. [Sun92, Proposition 3.1] If f : Rd → R ∪ {+∞} is a di-agonal convex PLQ function defined on boxes, then f is separable. Formallyf(x) =d∑i=1fi(xi),where fi : R → R ∪ {+∞}, i = 1, . . . , d are convex PLQ function in 1dimension.This leads to the main result which defines the structure of a difference-definite function defined on a grid.Proposition 4.8. [Sun92, Proposition 3.2] Assume f : Rd → R∪ {+∞} isa DD function defined on boxes. Then f can be expressed as the sum of aseparable convex PLQ and a convex quadratic. Thereforef = q + g, (4.7)where q(x) = 12xTAx+ bTx+ c, A  0 and g(x) is a diagonal convex PLQ.In fact, the function q(x) is actually the expression on one of the boxes indom f364.2. Quasi-SeparabilityTo be able to construct difference-definite functions from scratch, weneed a sufficient condition. It turns out that the structure given in Propo-sition 4.8 can be shown to be necessary and sufficient with a little morework.Theorem 4.9 (Difference-definiteness of separable functions). Assume thefunction f : Rd → R ∪ {+∞} is a proper diagonal convex PLQ on boxes.Then f is difference-definite.Proof. Using Proposition 4.2, the function f being diagonal on boxes meansit is separable. Consider 2 neighbouring pieces in the domain, say P1 andP2. We need to show that f|P1 − f|P2 is a convex or concave quadratic (asthe Hessian is positive or negative semidefinite). Definef|P1 = x>Qx+ p>x+ κ,we have f|P1 = x>q11 . . .qddx+p1...pd>x+ κ,and f|P1 =d∑i=1qiix2i +d∑i=1pixi + κ.Similarly, f|P2 =d∑i=1q′iix2i +d∑i=1p′ixi + κ′.As we are dealing with box-like pieces, the common boundary will be of theform xj = β, β ∈ R, j ∈ {1, . . . , d}. Without loss of generality, let j=1. Thenby continuity of a convex PLQ,f|P1(β, x2, . . . , xd)=f|P2(β, x2, . . . , xd),q11β2 + p1β +d∑i=2qiix2i +d∑i=2pixi + dκ=q′11β2 + p′1β +d∑i=2q′iix2i +d∑i=2p′ixi + dκ′,d∑i=2qiix2i +d∑i=2pixi + κ˜=d∑i=2q′iix2i +d∑i=2p′ixi + κ˜′,where κ˜ = q11β2 + p1β+ dκ and κ˜′ = q′11β2 + p′1β+ dκ′. For the expressionsto match on both sides for all possible (x2, . . . , xd) ∈ Rd−1 they need to be374.3. Data Structurethe same quadratic (as we need only a finite number of points to define aquadratic in Rn). By equating the coefficients of the polynomials, we getqii = q′ii, pi = p′i, κ˜ = κ˜′, i = 2, . . . , d.Consequently, when we calculate f|P1 − f|P2 , the quadratic coefficient of allthe terms will cancel out except x1. Hence, the Hessian of f|P1 − f|P2 willlook like l0. . .0where l = q11 − q′11 ∈ R; it is either positive or negative semidefinite. Sincethis will hold true for any arbitrary neighbouring pieces, f is difference-definite.Since we have proven that all 1D convex PLQ are actually difference-definite, we can characterize difference-definite functions as follows.Corollary 4.10 (Quasi-separability of difference-definite functions). Thefunction f : Rd → [−∞,+∞] is difference-definite on boxes if and only if itis of the formq(x) + g(x),where q(x) = 12xTQx+ pTx+ κ,Q  0 and g(x) is a diagonal convex PLQon boxes.Proof. As adding a convex quadratic to the whole expression would notchange any of the differences between neighbouring pieces and will preserveconvexity, using Theorem 4.9, f is difference-definite. Note that the expres-sion will still satisfy Proposition 4.8 because we can simply pick the boxrepresenting the function with the smallest coefficients of the square termsof each coordinate and add it to the function q to recover the q we had inthe Proposition.The consequences of the result can be seen when defining a data structureto store such function as well as when trying to calculate the minimumnumber of parameters required to define the function uniquely in Chapter 5.384.3. Data StructureFigure 4.5: The function stored in the DD data structure4.3 Data Structure4.3.1 DD Functions on boxesAs seen in Corollary 4.10, difference-definite functions can be character-ized as quasi-separable of the formq(x) +d∑i=1gi(xi)when defined on boxes. So to define a data structure for such functions wewill need lesser data than in the general case. The structure comprisesG,Q and F.In Rd, G stores d arrays which represent the grid points in each dimension.So for example in 2D if the grid points in x are at {−∞, x11, . . . , x1m1 ,+∞}and the grid points in x2 are {−∞, x21, . . . , x2m2 ,+∞}, Then G is a list ofvectors. SoG =([x11 x12 . . . x1m1],[x21 x22 . . . x2m2])The array Q will store the coefficients of q. For functions in R2 the coeffi-cients are stored in the order q1x21 + q2x1x2 + q3x22 + q4x1 + q5x2 + q6. The394.3. Data StructureFigure 4.6: Defining all pieces using q, g1 and g2set F will store d matrices that represent gi, each gi : R → R as a mi × 3matrix  gi11 gi12 gi13...gimi1 gimi2 gimi3for i = 1, . . . , d withgi(t) =gi11t2 + gi12t+ gi13 xi ≤ xi1gi21t2 + gi22t+ gi23 xi1 ≤ xi ≤ xi2...gimi1t2 + gimi2t+ gimi3 ximi ≤ xi.Example 4.11. Consider the function from Example 4.5. Sof(x) =x2 + xy + y2 x ≤ 0, y ≤ 0x2 + xy + 2y2 + y x ≤ 0, y ≥ 02x2 + xy + 2y2 + 2x+ y x ≥ 0, y ≥ 02x2 + xy + y2 + 2x x ≥ 0, y ≤ 0The proof for Proposition 4.8 given by Sun showed that q is actually thequadratic with the least coefficients for the square terms in all coordinates404.3. Data Structureamong the ones defined in the pieces, q(x, y) = x2 + xy + y2. Hence, g1(x)and g2(y) can be calculated asg10(t) = 0,g11(t) = t2 + 2tand g20(t) = 0, g21(t) = t2 + tThere is only one grid point on each of the coordinates, that is at x = 0 andy = 0. So to store this function,G =([0],[0]), Q =[1 1 1 0 0 0], F =g1 =[0 0 01 2 0]g2 =[0 0 01 1 0] . (4.8)The function can be represented using q, g1 and g2 as shown in Figure 4.6.If we want to store a bounded domain function, the first and last elementof each gi should be set to[+∞ +∞ +∞]. From the structure, we cansee the space complexity is linear with respect to the total number of gridpoints in all the coordinate directions.Proposition 4.12. Storing a DD function f : Rd → R takes O(∑di=1mi)space.Proof. The listG has to store∑di=1mi integers. To store the global quadraticQ we require 1+d+ (d+1)d2 integers. Finally, for F , we require 3∑di=1(mi+1)integers. As the dimension d is fixed, total space complexity is O(∑di=1mi)4.3.2 General 2D PLQ FunctionEdgelistWe store the function as an array of edges with the expression of thefunction that lies on either side of the function. The structure comprisesE, b, F and f, P ;where E is the matrix that stores the edges, b is a vector of indicators forwhether the edge is a line segment (1) or a ray (0) and F stores the functionindices that are to the left and right of the edge; f stores the coefficients ofthe quadratic functions on each piece and P stores the indices of the edges414.3. Data Structurethat make the polyhedral set on which the function is defined. The edgesneed to be stored such that they represent the face in a clockwise fashion.The number of columns in E, b and F will always be the same and thenumber of columns in f will be the same as P .(a) Structure of edge using E, b, F (b) Structure of face using f, PFigure 4.7: The significance of each element in the data structureExample 4.13. Consider the function from Example 4.11 again. The func-tion would be stored asE =0 0 −1 00 0 0 10 0 1 00 0 0 −1 , b =0000 , F =1 22 33 44 1f =1 0 1 0 0 01 0 2 0 0 02 0 2 0 0 02 0 1 0 0 0 , P =−1 41 −2−3 2−4 3 ,where the negative sign in P indicates the order of the edge in the face isthe opposite of that in E. To explain this take the first row in E. It says theedge from (0, 0) to (−1, 0) is a ray (b1 = 0) and the function to the left andright of the ray (see Figure 4.7) is the first and second row of f respectively(F1 =[1 2]), i.e. the ray is [0, 0] + R+([−1, 0] − [0, 0]) so x2 + y2 is in424.3. Data Structurex ≤ 0, y ≤ 0 while x2 + 2y2 is for x ≤ 0, y ≥ 0. Similarly, for the first row off the face that has the function x2 +0.xy+y2 +0x+0y+0 is represented bythe edges in first and fourth row of E (P1 =[−1 4]), but the direction inwhich the first row is stored is anticlockwise, hence the negative sign. Noticethat for the same function, the amount of data needed to store it increaseswhen storing general PLQ functions. This is because, here the functionsmay not be as simplified as a DD function. In fact, there is no restriction oncontinuity or convexity. This is done in order to be able to use this structureto store functions in order to check whether they are convex.The space required to store this data structure increases by a significantamount when compared to the DD structure.Proposition 4.14. The edgelist data structure takes O (m1m2) space tostore a function f : R2 → R ∪ {+∞} defined on a grid with mi grid pointsin each coordinate directionProof. Clearly, we will need to store the function on each pieces separately,so the dimension of f would be m1m2× 6 since each cell would be stored inP , we will need a m1m2 × 4 matrix for that. The edge list would basicallystore every edge of each cell, and as the domain is a planar graph, usingFact 3.4 that would be O (m1m2). Since the number of columns of b andF are constant and their rows are equal to the rown of E, the total spacecomplexity is O (m1m2).Note that the space required may be more for higher dimensions as thenthe domain will not remain a planar graph.43Chapter 5Parametrization andModelling of convexityconstraints5.1 Representing PLQ FunctionsThe minimum number of coefficients needed to define a piecewise func-tion determines the amount of data we need to store to define the functionuniquely. If you start on a grid-like domain in R2 and attempt to define aPLQ function on it, every cell would require 6 coefficients. In fact, for agrid in Rd with ci constraints in the ith dimension, you will need n∏di=1 ciparameters to uniquely define the PLQ function, where n =∑2m=0(m+1m)using Proposition 2.25, as shown in Figure 5.1.Requiring the constraint of continuity will reduce the number of coeffi-cients because now the pieces will have to agree at the boundaries so theywill not be entirely independent of their neighbouring pieces. Requestingconvexity on top of continuity may further reduce the number of coeffi-cients. We start with the case of a difference-definite function on a grid andtry to generalize the result to other PLQ functions.5.1.1 DD functions on a gridRecall the characterization of DD functions on boxes from Chapter 4.The result actually helps us show that once we define 2 adjacent boundarieson the grid, the whole function is completely defined. We begin by provingthat fact for difference-definite functions in 2D and then generalize to thehigher dimensional case.Theorem 5.1 (2D difference-definite degree of freedom). Given a difference-definite PLQ function defined on boxes f : R2 → R∪{+∞}, the total numberof parameters required to uniquely define the function is 6 + 2c1 + 2c2 where445.1. Representing PLQ Functions(a) A general PLQ on a grid in R2 (b) A general PLQ on a grid in R3Figure 5.1: Degree of freedom assuming no relation between the piecesc1 is the number of lines that are used to form a grid in the first coordinateand c2 is the number of lines in the second coordinate.We present 2 proofs. The first one is easy to visualize while the secondgeneralizes to higher dimension.Proof. We will split our proof into steps to make it easier to comprehend,namely defining the first piece (Step 1), defining the other boundary piecesrecursively (Step 2) and defining any other piece in the domain (Step 3).Step 1: Without loss of generality, we will start defining our functionfrom the left bottom cell coordinate (0, 0). This cell requires 6 parameters.Step 2: For the bottom boundary (x-axis), we begin with the cell ad-jacent to the corner most cell (coordinate (1, 0)), as shown in Figure 5.3(a).This will give us a cell with a known expression in one of its neighbouringpieces. We then use Proposition 4.2 to getfP2 = fP1 + [a>x− b][λa>x− b¯], (5.1)where a>x − b is the common boundary, which in this case will be of theform x1 − b. So a =[1 0]>, andfP2 = fP1 + [x1 − b][λx1 − b¯]. (5.2)455.1. Representing PLQ FunctionsFigure 5.2: Grid displaying the degree of freedom for a difference-definitePLQ on each pieceThe only coefficients that can be manipulated here are λ and b¯ as everythingelse is defined. So that gives a degree of freedom of 2 when defining pieceswith one neighbouring piece defined. Using recursion, all the pieces in thehorizontal boundary have 2 free parameters more than the piece on theirleft, see Figure 5.3(b). Hence the bottom boundary without the first cellrequires 2c1 coefficients. Similarly, the vertical boundary without the firstcell requires 2c2 coefficients to be defined.Step 3: Once we have the first row and column boundaries completelydefined, the remaining cells are shown in Figure 5.3(c). To find the ex-pression on each of the cells, we will use Corollary 4.10, and hence our DDfunction has an expression of the formp(x) + f1(x1) + f2(x2),where p is a convex quadratic, and f1 and f2 are 1 dimensional DD PLQfunctions. We will rearrange the expression a little bit to give usq(x) + g1(x1) + g2(x2),where q only contains the non-separable terms in the functions, and g1 andg2 are 1 dimensional DD PLQ functions. From the cells defined till now,we can define the three functions using a similar approach used to proveProposition 4.8 in [Sun92]. To define q, simply extract the non-separableterm from the expressions as it will be exactly the same in all the cells asshown in Figure 5.4. For g1 and g2, let the grid lines in x1 and x2 be at465.1. Representing PLQ Functions(a) The first boundarycell(b) Defining boundarycells recursively(c) All other cellsFigure 5.3: Defining a DD functionthe points {x11, . . . x1c1} and {x21, . . . x2c2} respectively. Using the bottomboundary, where the functions defined so far look likeh0(x) + q(x) x1 ≤ x11h11(x) + q(x) x11 ≤ x1 ≤ x12...h1c1(x) + q(x) x1c1 ≤ x1x2 ≤ x21,we can defineg1(x1) =h0(x1, 0) x ≤ x11h11(x1, 0) x11 ≤ x ≤ x12...h1c1(x1, 0) x1c1 ≤ x. (5.3)Similarly, for the vertical boundary, we haveh0(x) + q(x) x2 ≤ x21h21(x) + q(x) x21 ≤ x2 ≤ x22...h2c1(x) + q(x) x2c2 ≤ x2x1 ≤ x11,475.1. Representing PLQ FunctionsFigure 5.4: DD function with 2 boundaries definedNote that the first expression is the same as in (5.3) as it corresponds to thesame cell. This can be used to define g2 asg2(x2) =h0(0, x2)− h0(0, 0) x2 ≤ x21h21(0, x2)− h0(0, 0) x21 ≤ x2 ≤ x22...h2c1(0, x2)− h0(0, 0) x2c2 ≤ x2, (5.4)The reason h0(0, 0) has to be subtracted is because the constant term isalready accounted for in g1. Using q, g1 and g2 we can now define any cellin the domain.Another proof is by directly defining the separable functions and theconvex quadratic.Alternate Proof. Using Corollary 4.10, the function f has the formq(x, y) + g1(x) + g2(y),where g1 and g2 are 1-dimensional difference-definite PLQ and q is a convexquadratic that is actually an expression on one of the cells. So if we canprove that defining q, g1 and g2 requires only 6 + c1 + c2 coefficients, we aredone. To start with, q being a (convex) quadratic requires 6 coefficients. Thefunctions g1 and g2 have c1 + 1 and c2 + 1 pieces to be defined respectively.Since q is exactly the expression in one of the cells, one of the pieces of485.1. Representing PLQ Functions(a) Defining the neighbouring pieces (b) Defining others recursivelyFigure 5.5: Defining pieces of g1 and g2g1 and g2 will be exactly 0 to reflect that. Hence, we only define c1 + c2pieces in total. For g1, select the piece in which you wish the function to bedefined as 0. So we now have a piece whose function expression is known.Using a similar strategy as in Step 2 of the previous proof, we can defineeach piece starting from the neighbours of the piece with 0, as shown inFigure 5.5. Hence we need 2c1 coefficients to define g1. Similarly, we require2c2 coefficients to define g2.Now, as all of q, g1 and g2 are defined, we can use these to define anycell in the domain.Example 5.2. Consider the functionf(x) =x2 + xy + y2 x ≤ 0, y ≤ 0x2 + xy + 2y2 + y x ≤ 0, y ≥ 02x2 + xy + 2y2 + 2x+ y x ≥ 0, y ≥ 02x2 + xy + y2 + 2x x ≥ 0, y ≤ 0(5.5)This was proven to be difference-definite in Example 4.5. We will usethe first proof to parametrize the function. Now if the left bottom cell ischosen as the starting point, the parametrization can be seen as show inFigure 5.6(b). Note that any cell can be chosen as the starting quadratic,the only difference will be in the parameters used to define the function.So if the right top cell was chosen as the starting cell, the parametrizationwould be as shown in Figure 5.6(c).Clearly, q(x, y) = xy, so removing that and the y coefficients from the495.1. Representing PLQ Functions(a) The function (b) Parametrization (c) AlternateparametrizationFigure 5.6: Parametrizing a DD functionbottom most row gives usg1(x) ={x2 x < 02x2 + 2x x ≥ 0and removing q(x, y) and the x coefficients from the leftmost rows gives usg2(x) ={y2 y < 02y2 + y y ≥ 0which we can use to define all the cells.Once we have the proof for 2D difference-definite functions, we can provethe same for d-dimensional difference-definite PLQ.Corollary 5.3 (d-dimensional difference-definite degree of freedom). Givena difference-definite PLQ function defined on boxes f : Rd → R ∪ {+∞},the total number of parameters required to uniquely define the function isd(d+ 1)2+ d+ 1 + 2∑di=1 ci where ci is the number of grid points in the ithcoordinate.Proof. We can extend the alternate proof for Theorem 5.1 to the d-dimensionalcase easily. So the function can be expressed asq(x) +d∑i=1gi(xi),505.1. Representing PLQ Functions(a) The cells that will define every othercell in the domain(b) Example of a cell being defined by theboundary cellsFigure 5.7: An example of the parametrization in 3 dimensionswhere q : Rd → R ∪ {+∞} is a convex quadratic, and gi are convex DDPLQ in 1 dimension. Using Proposition 2.25, the function q will required(d+ 1)2+ d+ 1 coefficients. Using the same arguments as in the alternateproof, each gi will have a piece with the 0 function defined on it. Hence eachgi will require 2ci coefficients to define it, as shown for 3D in Figure 5.7(a).Hence the total number of coefficients required is(d(d+ 1)2)+ d+ 1 + 2d∑i=1ci.An example of the pieces that will have non-zero number of definablecoefficients is shown in Figure 5.7(a). The cells that are empty will becompletely dependent on the defined pieces. Note that in the DD case, thepieces on the boundary become similar to a coordinate system that helpdefine every other piece in the domain.515.1. Representing PLQ Functions5.1.2 DI Functions on a gridRecall that any function that does not fall in the category of difference-definite functions is a difference-indefinite function. So computing the coef-ficients required to uniquely define functions in this class should give us theparametrization for all types of convex PLQ functions.Theorem 5.4 (Difference Indefinite on Boxes). Given a difference-indefinitePLQ function defined on boxes f : R2 → R ∪ {+∞}, the total number ofparameters required to uniquely define the function is 6 + 3c1 + 3c2 + c1c2where c1 is the number of lines that are used to form a grid in the firstcoordinate and c2 is the number of lines in the second coordinate.Figure 5.8: Grid displaying the degree of freedom for a difference-indefinitePLQ on each pieceProof. We will again split our proof into 3 steps, defining the first piece (Step1), defining the other boundary pieces recursively (Step 2) and defining anyother piece in the domain (Step 3).Step 1: Starting from the left bottom corner in the domain, we need 6coefficients to define our quadratic function. Now we will define the pieceson the boundary along the coordinate directions.Step 2: For every other piece along the boundaries, using Proposi-tion 4.2, assuming the piece before it is defined can be written asf2 = f1 + [a>x− b][a¯>x− b¯]Since a and b are defined by the line separating the two pieces, the only freecoefficients are (a¯1, a¯2) and b¯. Hence that gives us 3 coefficients needed todefine each piece in the boundary once the preceding piece is defined. So wecan define all the pieces along the bottom and left boundaries recursively.525.1. Representing PLQ Functions(a) Defining pieces onone boundary(b) Defining pieces onthe other boundary(c) Defining pieces inthe interiorFigure 5.9: Defining pieces of a 2D DI functionStep 3: Once the boundary is defined, the pieces in the interior needto be defined. Pick a piece of the form shown in Figure 5.9(c), that is, ithas pieces to the bottom, left and diagonally-downward defined. Assumewithout loss of generality that the boundary separating this piece from thedefined pieces are x2 = 0 and x1 = 0. Then there are two ways to representthis piece;f =f2 + [x2 − 0][a¯1>x− b¯1], andf =f3 + [x1 − 0][a¯2>x− b¯2].In fact using Proposition 4.2 on f2 and f3, these pieces can be further brokendown asf =f1 + [x1 − 0][a>1 x− b1] + [x2 − 0][a¯1>x− b¯1], andf =f1 + [x2 − 0][a>2 x− b2] + [x1 − 0][a¯2>x− b¯2].As f1, f2 and f3 are known, the values of a1, a2, b1 and b2 are also known.Now as both expressions represent the same function, we have[x1][a>1 x− b1] + [x2][a¯>1 x− b¯1] = [x2][a>2 x− b2] + [x1][a¯2>x− b¯2],⇔ a11x21 + a12x1x2 − b1x1 + a¯11x1x2 + a¯12x22 − b¯1x2= a21x1x2 + a22x22 − b2x2 + a¯21x21 + a¯22x1x2 − b¯2x1,which on rearranging givesa11x21 + a¯12x22 + (a12 + a¯11)x1x2 − b1x1 − b¯1x2= a¯21x21 + a22x22 + (a21 + a¯22)x1x2 − b¯2x1 − b2x2.535.1. Representing PLQ FunctionsSince this is true for all (x1, x2) ∈ R2,a¯21 = a11, a¯12 = a22, (a21 + a¯22) = (a12 + a¯11), b¯2 = b1, b¯1 = b2and the only equation that leaves room for adjusting the values is the onefor the non-separable terms, a¯11 or a¯22. When one of a¯11 or a¯22 is fixed,the value of the other is automatically fixed, the degree of freedom of anyother piece except those in the left and bottom boundaries is 1, as shown inFigure 5.8. Hence using recursion, all other pieces in the domain will require1 coefficient each, which gives us a total of6 + 3(c1 + c2) + c1c2coefficients.Remark 5.5. The proof for DI functions is different from DD because onceyou have defined the boundaries, you still need to define all the cells in orderto reach the cell that we want to actually define, as shown in Figure 5.10.(a) DI Case (b) DD CaseFigure 5.10: Difference between defining an interior piece in a DI and a DDfunctionNotice that the degree of freedom increases because of the ability tochange the coefficient of the non-separable term xy in the neighbouringpieces. One might think this would scale accordingly in the higher dimen-sions, with coefficients being required for each non-separable term in eachpiece. This is actually not the case.545.1. Representing PLQ FunctionsCorollary 5.6. Given a function f : Rd → R ∪ {+∞} that is a difference-indefinite PLQ defined on boxes. Then the total number of parameters re-quired to uniquely define the function isd(d+ 1)2+ (d+ 1)d∑i=1ci +∑∑1≤i<j≤dcicjwhere ci is the number of lines that are used to form a grid in the ith coor-dinate.Figure 5.11: Grid displaying the degree of freedom for a 3D difference-indefinite PLQ on each pieceProof. We consider cases with respect to the number of neighbouring piecesdefined for the piece being definedCase 0: The first cell has to be completely defined, hence requiresd(d+1)2 + d+ 1 coefficients.Case 1: For a piece with one adjacent piece with common boundarya>x− b defined , we havef = f1 + [a>x− b][a¯>x− b¯]Since a¯ and b¯ are completely undefined, that gives us d + 1 coefficients todefine. So each piece along the coordinate axes would require d + 1 extracoefficients, giving a total of (d+ 1)∑di=1 ci more coefficients.555.1. Representing PLQ Functions(a) Defining coordinate axes (b) Defining coordinate planesFigure 5.12: Defining pieces of a 3D DD functionCase 2: For pieces with two neigbouring pieces defined, without loss ofgenerality, assume the piece being defined has neighbouring pieces definedwith the common boundaries x1 = 0, x2 = 0.f =f2 + [x2 − 0][a¯1>x− b¯1], andf =f3 + [x1 − 0][a¯2>x− b¯2].In fact using Proposition 4.2 on f2 and f3, these pieces can be further brokendown asf =f1 + [x1 − 0][a>1 x− b1] + [x2 − 0][a¯1>x− b¯1],f =f1 + [x2 − 0][a>2 x− b2] + [x1 − 0][a¯2>x− b¯2].As f1, f2 and f3 are known, the values of a1, a2, b1 and b2 are also known.Now as both the expressions represent the same function, we have[x1][a>1 x− b1] + [x2][a¯1>x− b¯1] = [x2][a>2 x− b2] + [x1][a¯2>x− b¯2]⇒a11x21 +d∑i=1i 6=1a1ix1xj − b1x1 +d∑i=1i 6=2a¯1ix2xi + a¯12x22 − b¯1x2= a22x22 +d∑i=1i 6=2a2ix2xi − b2x2 +d∑i=1i 6=1a¯2ix1xi + a¯21x21 − b¯2x1565.1. Representing PLQ Functions⇒a11x21 + a¯12x22 + (a12 + a¯11)x1x2 +d∑i=3(a1ix1xi + a¯1ix2xi)− b1x1 − b¯1x2= a¯21x21 + a22x22 + (a21 + a¯22)x1x2 +d∑i=3(a¯2ix1xi + a2ix2xi)− b¯2x1 − b2x2Since this is true for all (x1, . . . , xd) ∈ Rda¯2j = a1j ∀ j 6= 2,a¯1i = a2i ∀ i 6= 1,a21 + a¯22 = a12 + a¯11, (5.6)b¯2 = b1, andb¯1 = b2.Once again, all values except that of a¯11 or a¯22 are fixed. Hence the degreeof freedom for any cell with 2 neighbours defined is 1. Using this, we candefine pieces in the 2D plane formed using any two coordinates using 1 extracoefficient for each, as shown in the 3D case in Figure 5.12(b). So this givesus∑∑1≤i<j≤d cicj more coefficients.Case 3+: Assume without loss of generality that the third piece thatis defined has the common boundary x3 = 0 with the piece being definedand is defined as f4. For a piece with at least 3 adjacent pieces defined, thepiece will be completely defined. This is because using 2 adjacent pieces, wecan show that there is only one coefficient that is free, sof(x) =f2(x) + [x2 − 0][a¯1>x− b¯1],which on replacing the known values gives us=f2(x) + [x2 − 0]a¯11a22...a2d>x− b2 .575.1. Representing PLQ FunctionsFor x3 = 0,fx1x20...xd =f2x1x20...xd+ [x2 − 0]a¯11a22a23...a2d> x1x20...xd− b2f(x3 = 0) =f(x2 = 0) + [x2 − 0]a¯11x1 + d∑i=2i 6=3a2ixi . (5.7)Alsof4 =f2 + [x3 − 0][a>4 x− b4] + [x1 − 0][a>3 x− b3]f4(x3 = 0) =f2(x3 = 0) + [x1 − 0][a>3 x− b3] (5.8)Now at x3 = 0 as the function has to be continuous,f(x3 = 0) =f4(x3 = 0)x2a¯11x1 + d∑i=2i 6=3a2ixi =x1[ d∑i=1a3ixi − b3]a¯11x1x2 + ... =a32x1x2 + ...,where ‘...’ are the coefficients of other variables. Since this is true for allx ∈ Rd such that x3 = 0a¯11 =a32So even a¯11 is defined now. This leaves us with no other coefficient to defineas anything with more than 3 adjacent pieces defined has been completelydefined.So in total, the number of coefficients needed to be defined ared(d+ 1)2+ d+ 1 + (d+ 1)d∑i=1ci +d∑i=1 d∑j=i+1cicj .Since difference-definite and difference-indefinite are an exhaustive rep-resentation of convex PLQ functions, for a function on a grid, the maximumnumber of coefficients required for a convex PLQ on a grid would be thesame as in the difference-indefinite case.585.2. Representing Convexity Constraints in Optimization Problems5.2 Representing Convexity Constraints inOptimization ProblemsIn optimization problems, convexity is not easy to implement as a con-straints numerically. As the set of convex functions is not polyhedral, itis not possible to represent the set using finitely many linear inequalities.There are several ways to model convexity constraints. While each methodhas merits, in the end the representation of convexity is complex. In [Wac17],it is proven that for a given function in W k+1,+∞, a sequence of piecewisepolynomial functions can be given that converge to the actual function.Assumption 5.7. [Wac17, Assumption 3.1] There are constants ckink, Ckink >0 such that for h ∈ (0, 1], there exists a function ψh ∈ P1(Th) with ‖ψh‖H1(Ω) <Ckink and rψ>h nFzF≥ ckinkhat all the common boundaries.The assumption enforces the existence of a piecewise linear function fon the triangulation such that f is convex, bounded and the linear functionon a given piece is different from the neighbouring pieces. The lower limiton the difference between the slopes of the other pieces with the currentone is determined by ckink. With this assumption on the triangulations, theexistence and convergence of the sequence of piecewise polynomial functionsis shown as follows.Theorem 5.8. [Wac17, Theorem 3.2] Let Assumption 5.7 be satisfied.Then for a convex function u ∈ W k+1,∞(Ω) for some k ≥ 2, there existconvex functions uh ∈ Pk(Th) such that‖u− uh‖H1(Ω) ≤ Chk−1‖u‖Wk+1,∞(Ω)holds for all h ∈ (0, 1].For the case of piecewise quadratic functions, the convergence is linear.5.2.1 Equivalence of convexity characterizationWachsmuth [Wac17] characterizes convexity constraints for polynomialfunctions as follows.595.2. Representing Convexity Constraints in Optimization ProblemsTheorem 5.9. [Wac17, Theorem 2.6] A function f ∈ Pk(T ) is convex ifand only if∇2f(x)  0, ∀x ∈ int(T ), T ∈ T (5.9)lim→0(∇f(x+ nF )−∇f(x− nF ))>nF ≥ 0,∀x ∈ ri(F ), F ∈ F(T ) (5.10)where F is an interior common boundary and nF is a unit vector normal toF .For piecewise quadratic functions in Rd, the number of semidefinite in-equalities is equal to the total number of triangles in T for (5.10) and thetotal number of linear inequalities is dNF , where NF is the total number ofcommon boundaries in the interior of the domain. For the special case ofthe domain being considered, the theorem can be proved to be equivalentto Theorem 3.8.Proposition 5.10. Let f : Rd → R∪{+∞} ∈ P2(T ), where T is the trian-gulation of a bounded polyhedral domain Ω, such that dom f = Ω. AssumeCondition (5.9) holds, then Condition (5.10) is equivalent to (3.4).Proof. As P2(T ) ⊂ C(Ω), we do not have to check for continuity of thefunction f . Condition (5.9) is equivalent to the precondition for checking(3.4). Since that is assumed to hold, all that remains to be done is to proveon the triangulation considered that (5.9) is equivalent to (3.4).For (5.9) , we will prove this for arbitrary triangles T1 and T2 in thedomain such that T1 ∩ T2 ⊂ {x : a>x = β} is a common boundary, andT1 ⊂ {x : a>x ≤ β}, T2 ⊂ {x : a>x ≥ β}. Let f1(x) = f|T1 , f2(x) = f|T2 .Since the function is piecewise quadratic, the gradient is affine and henceonly needs to be checked at the vertices that define the common boundary.Let the vertices defining the common boundary be x1, . . . , xd. Since thefunctions is piecewise polynomial and hence continuously differentiable intheir triangles, for a point on the boundary of the piece. Without loss ofgenerality, assume a is a unit vector. Since a is normal to the commonboundary, by (5.10),lim→0(∇f(xi + a)−∇f(xi − a))> a ≥ 0, ∀i = 1, . . . , d. (5.11)As a>xi = β, xi + a ∈ T2 and xi − a ∈ T1 for all  < 0 for a sufficientlysmall 0, (5.11) is equivalent tolim→0(∇f2(xi + a)−∇f1(xi − a))> a ≥ 0, ∀i = 1, . . . , d⇔ (∇f2(xi)−∇f1(xi))> a ≥ 0,∀i = 1, . . . , d.605.2. Representing Convexity Constraints in Optimization ProblemsAs the gradient of a polynomial functions is parallel to the normal,⇔ lim→0(γi2a− γi1a)>a ≥ 0,∀i = 1, . . . , dfor some γi1, γi2 ∈ R dependent on xi. Hence,⇔ (γi2 − γi1) ‖a‖2 ≥ 0,∀i = 1, . . . , d⇔(γi2 − γi1) ≥ 0, ∀i = 1, . . . , d.Let γi2 − γi1 = δi. Then⇔ (∇f2(xi)−∇f1(xi)) = δia, δi ≥ 0,∀i = 1, . . . , d,which is exactly the same as (3.4) when the functions f1 and f2 are repre-sented as fj(x) =12x>Qjx+ qj + κj for j = 1, 2. Since we are dealing witha bounded domain, we will not have any unbounded edges, hence we do notneed to check for those.Figure 5.13: An unbounded triangulationIn fact, the characterization given by Wachsmuth can be extended to thecase when an unbounded domain that can be represented by a triangulationis considered. Here we assume that in our triangulation, we have trianglesthat are unbounded. For example, to represent the third quadrant in R2,we can use the triangulation shown in Figure 5.13.Corollary 5.11. For an unbounded polyhedral set Ω with triangulation T ,let Jf>nF KF = lim→0(∇f(x + nF ) − ∇f(x − nF ))>nF . A function f ∈615.2. Representing Convexity Constraints in Optimization ProblemsP 2(T ) is convex if and only if it satisfies (5.9) and (5.10), and for unboundedcommon boundaries in the domain of the form x1 + R+(x2 − x1)Jf>nF KF (x2)− Jf>nF KF (x1) ≥ 0 (5.12)Proof. If you consider arbitrary unbounded edges of the form x1 +R+(x2−x1), then for the bounded set represented by the convex hull of all thepoints in the triangulation, including the direction points x2, the convexitycan be characterized by (5.9) and (5.10). For the unbounded part, usingProposition 5.10, we know that (5.10) is equivalent to(∇f2(xi)−∇f1(xi)) = δia, δi ≥ 0 ∀ i = 1, 2.Hence,Jf>nF KF (x2)− Jf>nF KF (x1) ≥ 0⇔ (∇f2(x2)−∇f1(x2))> a− (∇f2(x1)−∇f1(x1))> a = (δ2 − δ1)‖a‖2 ≥ 0 (5.13)As for the unbounded edges, using Theorem 3.8, we know that the functionis convex if and only if δ1 ≤ δ2. Hence, (5.13) is true and consequently, so is(5.12) for all unbounded edges in T if and only if the function is convex.5.2.2 Convexity characterization of the projection problemOnce we are able to approximate the function using a piecewise polyno-mial approximation, we can add the convexity constraints to any optimiza-tion algorithm. To illustrate this, we consider a convex projection problem[CLRM99]. The problem is to find the closest convex function to a givenfunction with respect to a given norm. Let C(Ω) denote the set of convexfunctions of the form c : Ω → R, where Ω is a bounded convex set. For afunction f such that dom c = Ω. the projection problem can be stated asminc∈C(Ω)‖f − c‖ (P)where ‖ · ‖ is a function norm. Typically, the 1, 2 or infinity norms are usedfor the objective function. Now since we aim to use piecewise quadraticfunctions to approximate the convex projection, we have to reformulate theproblem. Let C2(Ω) denote the set of piecewise linear quadratic convexfunctions defined on a polyhedral division P of the set Ω. In addition to625.2. Representing Convexity Constraints in Optimization Problemsthe feasibility constraints, the convexity constraints add an additional set oflinear and semidefinite inequalities. So the problem.minc∈C2(P)‖f − c‖ (P′)can be reformulated asminc∈H10 (P)‖f − c‖ (P′)such thatContinuity: c|Pi(xk) = c|Pj (xk), xk ∈ Fij , ∀ k ∈ {1, 2, 3}, Fij ∈ F ,Int. convexity: ∇2c|Pi(x)  0 ∀ Pi ∈ PBdry. convexity:[∇c|Pi(xk)−∇c|Pj (xk)]>a ≥ 0, ∀ xk ∈ bdFij , Fij ∈ F ,where a is a vector such that Pi ∩ Pj ⊆ {x : a>x = β}This problem can be solved with a constrained optimization solver to giveus the solution for (P′).As for 1D functions, we can always come up with a converging sequenceof piecewise linear functions, we only consider piecewise linear functions fornow. For piecewise linear functions, the interior of each piece is alwaysconvex, so we only need to check at the break points.Example 5.12. Consider the functionf(x) ={1− |x| |x| ≤ 1|x| − 1 1 ≤ |x| ≤ 3 , (5.14)which is shown in Figure 5.14(b). Upon using the builtin constrained opti-mization function in Matlab, with boundary constraints due to the gradientjump, the projection is numerically calculated by taking a sufficient num-ber of points in the domain. We start with the constant function that is 0for x ∈ [−3, 3] and we approximate the problem by an integral. So for aset of points X = {x1, . . . , xm} such that xi < xi+1, xi+1 − xi = l for alli = 1, . . . ,m and x1 = −3, xm = 3 the new problem becomesminfproj∈P1(X)m∑i=1|f(xi)− fproj(xi)|l635.2. Representing Convexity Constraints in Optimization Problems(a) The original function (b) L1 projection onto the set of P1functions(c) Intermediate solutions with starting function c0 = 0Figure 5.14: The projection problem in 1D645.2. Representing Convexity Constraints in Optimization Problemssuch thatfproj(xi+3)− fproj(xi+2)xi+3 − xi+2 ≤fproj(xi+1)− fproj(xi)xi+1 − xi ,which represents the gradient jump. When the problem is sampled at onepoint for every 0.01 units on [−3, 3] and plugged into the fmincon function,the solution provided would be the numeric value of the function at eachpoint at which the function was sampled. The intermediate solutions con-verge to the final (red) function as shown in Figure 5.14(c). The blue-greensolutions are the piecewise linear functions obtained as intermediate solu-tions. The darker colour indicate that the iteration at which the solutionwas plotted is higher than the lighter one. Notice that with the number ofiterations, the violation of convexity decreases. Since the problem returnsan array of points, are able to plot it. The expression for the function canbe extracted from these points and comes out to bec(x) ={0.33 |x| ≤ 1.33|x| − 1 1.33 ≤ |x| ≤ 3Figure 5.15: The triangulation used to optimize the funciton in 2DThe problem can be extended to higher dimensions, but then, the con-vergence of the solution to the original problem becomes dependent on thenature of the triangulation used. For the thesis, we will assume the trian-gulation is suitable for the function being considered.655.2. Representing Convexity Constraints in Optimization Problems(a) L1 projection onto the set of P1functions and the original function(b) The definition of the final projec-tionFigure 5.16: The projection problem in 2DExample 5.13. Consider the functionf(x) = ||x1 + x2| − 2|, x ∈ [−3, 3]× [−3, 3].The triangulation of the domain that we consider is shown in Figure 5.15.The constraints are coded for every edge and plugged into fmincon in Mat-lab. For 2D, the input is changed to an matrix of piecewise linear function’scoefficients, where each column in the 3 × n matrix defines the coefficientsof the linear function a1(x1) + a2(x2) + a3 as[a1 a2 a3]>. We do thisas calculating the function expression from 3 points for each piece is timeconsuming. So now we need to explicitly specify continuity constraints.The continuity constraints are input as equality constraints and convexityconstraints are stored as inequality constraints like before.Once again, we take the zero function on [−3, 3]× [−3, 3] as our startingfunction. The final function we obtain is defined in Figure 5.16(b). It isconvex as it is the maximum of two convex functions, |x1 + x2| − 2 and theconstant function 0.8.66Chapter 6Conclusions and FutureWorkWe provided a way to characterize the convexity of piecewise quadraticfunctions and gave Algorithm 1, which runs in linear time with respect tothe number of edges. In the 2D case it also runs in linear time with respectto the number of vertices because of the planarity of the domain. Similarly,Algorithm 2 is constructed for cubic piecewise functions. The algorithmswere implemented in MATLAB 2018b and the code is available under theLGPL from GitHub2. The edgelist data structure described in Section 4.3.2is used to store the functions. Different cases where convexity fails wereconsidered and used to test the algorithm. A few examples have been shownin AppendixB.These algorithms can be incorporated in optimization algorithms to rep-resent convexity constraints. Work in the same direction was shown byWachsmuth in [Wac17]. We showed that the conditions used in [Wac17] areactually a special case of Theorem 3.8 (when the domain is bounded andthe polyhedral division can only have triangulations).We discuss a subclass of convex PLQ functions, namely difference-definitefunctions, that were shown to have a quasi separable structure by [Sun92]when the domain is restricted to a grid form. We show that this structureis actually a characterization of the class in Corollary 4.10 by showing thatall 1D convex PLQ functions are actually DD functions. In Chapter 5, thisstructure is used to show that the parametrization of this class on boxesrequires O(∑di=1 ci)coefficients with respect to the number of grid lines inthe domain, which is significantly less compared to the general case, which isO(∏di=1 ci). DI functions are shown to require O(∑∑1≤i<j≤d cicj)coef-ficients, which is still fewer coefficients than defining all pieces with arbitrarycoefficients.2https://github.com/shambhavis/isConvex676.1. Future Work6.1 Future WorkSeveral results can be extended to higher dimensions or can be used aftersome work is done.6.1.1 Extending PLQ to RdThe extension to Rd comes naturally from Algorithm 1. Continuity canbe checked using Lemma 3.1. For convexity, we would need to check at leastd + 1 points on the common boundary to ensure that the subdifferential ismonotone. The same test that was used for the 2 dimensional case can beused.For cubic polynomials, the convexity check will become more complexas the type of quadratics in Rd is not just restricted to paraboloids. Also theroots will become uncountable which will affect efficiency unless a workaroundis found.6.1.2 Applications of DD functionsDifference-definite functions demonstrated several useful properties whenrestricted to boxes. It is possible that the class is closed under severalcommon operations in convex analysis. Although it can be shown that theclass of DD functions on boxes is not closed under conjugation, work is stillneeded to see if this is also true for general DD functions. See Appendix Afor an example of DD function on a box whose conjugate is not DD on a box.An open question for the structure used to store DD functions on boxes isif it can be normalized to easily compare different DD functions.6.1.3 Using parametrization as a tool to generate convexPLQ functionsParametrization of convex PLQ functions clearly reduced the amountof data being used to define the function, in fact, in the case of difference-definite functions, the number of parameters is reduced to the sum of thenumber of constraints instead of the product. With further restrictions onthe admissible parameters, one can generate convex PLQ functions over thegiven domain. One source of future work is to prove convergence and errorbounds to approximate DI functions by DD functions.68Bibliography[AF03] Robert A. Adams and John J. F. Fournier. Sobolev spaces, vol-ume 140 of Pure and Applied Mathematics (Amsterdam). El-sevier/Academic Press, Amsterdam, second edition, 2003. →pages 11[AMO93] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.Network flows. Prentice Hall Inc., Englewood Cliffs, NJ, 1993.Theory, algorithms, and applications. → pages 14[BH08] Jonathan M. Borwein and Chris H. Hamilton. Symbolic Fenchelconjugation. Math. Program., 116(1):17–35, 2008. → pages 73[BK93] Giuseppe Buttazzo and Bernhard Kawohl. On Newton’s problemof minimal resistance. Math. Intelligencer, 15(4):7–12, 1993. →pages 1[BLP16] Heinz H. Bauschke, Yves Lucet, and Hung M. Phan. On the con-vexity of piecewise-defined functions. ESAIM: Control, Optimi-sation and Calculus of Variations (ESAIM: COCV), 22(3):728–742, 2016. → pages v, 17, 27[CD17] Guillaume Carlier and Xavier Dupuis. An Iterated ProjectionApproach to Variational Problems Under Generalized ConvexityConstraints. Applied Mathematics and Optimization, 76(3):565–592, 2017. → pages 2[CJ01] Philippe Chone´ and Herve´ V J Le Meur. Non-convergence resultfor conformal approximation of variational problems subject toa convexity constraint. Numerical Functional Analysis and Op-timization, 22(6):529–547, 2001. → pages 1[CLRM99] Guillaume Carlier, Thomas Lachand-Robert, and BertrandMaury. H1-projection into the set of convex functions: a saddle-point formulation. In CEMRACS 1999 (Orsay), volume 10 of69BibliographyESAIM Proc., pages 277–289. Soc. Math. Appl. Indust., Paris,1999. → pages 1, 62[Eke02] Ivar Ekeland. Two problems in economics. Jahresber. Deutsch.Math.-Verein., 104(2):51–58, 2002. → pages 1[EMB10] Ivar Ekeland and Santiago Moreno-Bromberg. An algorithm forcomputing solutions of variational problems with global convex-ity constraints. Numerische Mathematik, 115(1):45–69, 2010. →pages 2[HUL93] Jean-Baptiste Hiriart-Urruty and Claude Lemare´chal. Con-vex Analysis and Minimization Algorithms II, volume 306 ofGrundlehren der Mathematischen Wissenschaften [FundamentalPrinciples of Mathematical Sciences]. Springer-Verlag, Berlin,1993. Vol II: Advanced theory and bundle methods. → pages16, 23[Leo09] Giovanni Leoni. A first course in Sobolev spaces, volume 105of Graduate Studies in Mathematics. American MathematicalSociety, Providence, RI, 2009. → pages 11[Mir16] Jean-Marie Mirebeau. Adaptive, anisotropic and hierarchicalcones of discrete convex functions. Numerische Mathematik,132(4):807–853, 2016. → pages 2[New87] Isaac Newton. Philosophiae naturalis principia mathematica.William Dawson & Sons Ltd., London, 1687. → pages 1[Obe13] Adam M. Oberman. A Numerical Method for Variational Prob-lems with Convexity Constraints. SIAM Journal on ScientificComputing, 35(1):A378–A396, 2013. → pages 1, 2[O’P18] Saucy O’Path. Set of symmetric positive semidefinite matri-ces is closed. Mathematics Stack Exchange https://math.stackexchange.com/q/2904562, 2018. → pages 6[Roc70] R. T. Rockafellar. Convex Analysis. Princeton University Press,1970. → pages 4, 6[Rud76] Walter Rudin. Principles of mathematical analysis. McGraw-HillBook Co., New York-Auckland-Du¨sseldorf, third edition, 1976.International Series in Pure and Applied Mathematics. → pages670Bibliography[RW98] R. T. Rockafellar and Roger J-B Wets. Variational Analysis.Springer-Verlag, Berlin, 1998. → pages 4, 5, 7, 20[Sun92] J. Sun. On the structure of convex piecewise quadratic functions.Journal of Optimization Theory and Applications, 72(3):499–510, 1992. → pages 3, 18, 19, 30, 31, 36, 46, 67[Wac17] Gerd Wachsmuth. Conforming approximation of convex func-tions with the finite element method. Numerische Mathematik,137(3):741–772, 2017. → pages 2, 11, 12, 59, 60, 67[Za˘l02] Constantin Za˘linescu. Convex Analysis in General VectorSpaces. World Scientific Publishing Co., Inc., River Edge, NJ,2002. → pages 771Appendix72Appendix AConjugation of DD functionsThe SCAT Package3 was extensively studied and extended to Rn in[BH08] for functions of a certain form. For the thesis it suffices to know thatconvex PLQ are a subset of these functions. Since the package computesconjugates, conjugation of difference-definite CPQF was attempted to checkif it satisfies closure. Explicit use of Conj failed, however quasi automatedpartial conjugation worked. It was input in a structure used by SCAT, calledthe PWF and was plotted.The function used to check if difference-definite CPQF are closed underconjugation wasx2 + xy + y2 +{3x2 x < 0x2 x ≥ 0 +{2y2 y < 03y2 y ≥ 0 .The output suggested convexity of the whole structure and did not seemto violate any of the conditions required to make the input feasible for SCAT.Since it is the sum of convex functions, it will remain convex. However, directConjugation gave an error. So we had to partially conjugate with respectto each coordinate one by one. So the steps taken were in the formf(x, y)Partial Conj−−−−−−−→ f(x, t) Partial Conj−−−−−−−→ f(s, t).The error was caused due to the fact that in the portions where the vari-able t was a constant value, it was not assigned the value and was resultingin the SCAT being unable to Partially Conjugate the second time. So thepiece where t was constant was manually fixed and it was Partially Conju-gated with respect to the second variable. The final function resulting from3http://ddrive.cs.dal.ca/projects/scat/73Appendix A. Conjugation of DD functionscomplete conjugation wascconj :=323s2 − 123st+ 223 t2 t ≤ 6s347s2 − 147st+ 447 t2 6s ≤ t ≤ s8463s2 − 163st+ 463 t2 s8 ≤ ts ≤ 0323s2 − 123st+ 223 t2 t ≤ s4431s2 − 131st+ 231 t2 s4 ≤ t ≤ 8s463s2 − 163st+ 463 t2 8s ≤ t0 ≤ sand depicted in Figure A.1.(a) The domain of the conjugate (b) The conjugateFigure A.1: The conjugate of a 2D DD PLQAs can be seen from the domain structure in Figure A.1(a) the regionsare not boxes any more. Hence difference-definite functions defined on boxesare not closed under Conjugation. More work could be done to see if thefunction is closed under conjugation for difference-definite.The quasi-manual conjugation was done using PartialConj function.After pivoting and negating, the pieces causing problem were manually fixedand partial conjugation was done on the other variable. The domain inFigure A.1(a) was shown by tilting the graph.74Appendix BisConvex()All the code for characterization of convexity of 2D PLQ and PC func-tions was implemented in Matlab 2018b and uses the edgelist data structuredefined in Section 4.3 to make it easy to traverse through the edges in thedomain. The function plotf is used to plot the piecewise functions usingthe edgelist data structure.B.1 PLQ FunctionsThe function constructed for PLQ functions is IsConvex2Dquad whichis of the form[isconv,iscts,flag]=IsConvex2Dquad(E,F,f,b).The first 2 return values are booleans, and flag is a string. The booleanisconv returns true if the function is convex, and iscts returns true ifthe function is continuous. The string flag is used to provide some detailswith respect to the step at which the function lost convexity.We will first consider an example which has been shown to be convex inthe thesis.Example B.1. Consider (4.5) from Example 4.5f(x) =x2 + xy + y2 x ≤ 0, y ≤ 0x2 + xy + 2y2 + y x ≤ 0, y ≥ 02x2 + xy + 2y2 + 2x+ y x ≥ 0, y ≥ 02x2 + xy + y2 + 2x x ≥ 0, y ≤ 0Upon storing it as shown in Example 4.13 and calling IsConvex2Dquad, theresult obtained is as shown.1 E=[ 0 0 −1 0 ;2 0 0 0 1 ;3 0 0 1 0 ;4 0 0 0 −1];75B.1. PLQ Functions5 f =[ 1 1 1 0 0 0 ;6 1 1 2 0 0 0 ;7 2 1 2 0 0 0 ;8 2 1 1 0 0 0 ] ;9 F=[ 1 2 ;10 2 3 ;11 3 4 ;12 4 1 ] ;13 P={ [−1 4 ]14 [ 1 −2]15 [−3 2 ]16 [−4 3 ] } ;17 b = [ 0 ; 0 ; 0 ; 0 ] ;1819 [ c1 , c2 , r e s u l t ]=IsConvex2Dquad (E, F , f , b ) ;2021 p l o t f (E, f ,P,[−1 1] , [−1 1 ] )22 di sp ( [ c1 c2 r e s u l t ] )Output"true" "true" "Passed"So the code finds the function to be continuous as well as convex, and hencereturns “Passed” as a result.The second example is the extension of a DI function along its commonboundary, which was shown to be non-convex in Example 3.11.Example B.2. Consider the functionf(x) ={f1(x) = x21 + x22, when x1 ≤ 0,f2(x) = x21 + x22 + x1x2, when x1 ≥ 076B.1. PLQ FunctionsThe code for this looks as follows. Note that although we only have 1 edge,it is unbounded on both sides, so to use our algorithm, we split it into 2rays and proceed to check convexity along those.1 E=[ 0 0 0 1 ;2 0 0 0 −1];3 f =[ 3 1 1 0 0 0 ;4 1 2 1 0 0 0 ] ;5 F=[ 1 2 ;6 2 1 ] ;7 b = [ 0 ; 0 ] ;89 [ c1 , c2 , f l a g ]=IsConvex2Dquad (E, F , f , b ) ;1011 p l o t f (E, f ,P,[−1 1] , [−1 1 ] )12 di sp ( [ c1 c2 r e s u l t ] )13Output"false" "true" "Convexity Lost on a vertex of edge 2"In our data, edge 2 is the edge that shows up when the function is extendedalong the common boundary, which is where the function loses convexity.Also, since the function is not convex on the vertex of this edge, the solutionfor delta would be negative and hence it will fail the convexity test there.So this is confirmed by the function as well. Note that since continuity isnot lost, c2 is still true.We will consider another example where the convexity is lost in the77B.1. PLQ Functionsinterior. For simplicity, we will take the initial function and simply flip it.So now the very first piece that the function encounters will be non-convex.Example B.3. We will now negate the function from Example B.1.f(x) = −x2 + xy + y2 x ≤ 0, y ≤ 0x2 + xy + 2y2 + y x ≤ 0, y ≥ 02x2 + xy + 2y2 + 2x+ y x ≥ 0, y ≥ 02x2 + xy + y2 + 2x x ≥ 0, y ≤ 0The only change in the data structure would be that now, f will be thenegative of the matrix in Example B.1. The result obtained is as shown.1 E=[ 0 0 −1 0 ;2 0 0 0 1 ;3 0 0 1 0 ;4 0 0 0 −1];5 f =−[1 1 1 0 0 0 ;6 1 1 2 0 0 0 ;7 2 1 2 0 0 0 ;8 2 1 1 0 0 0 ] ;9 F=[ 1 2 ;10 2 3 ;11 3 4 ;12 4 1 ] ;13 P={ [−1 4 ]14 [ 1 −2]15 [−3 2 ]16 [−4 3 ] } ;17 b = [ 0 ; 0 ; 0 ; 0 ] ;1819 [ c1 , c2 , r e s u l t ]=IsConvex2Dquad (E, F , f , b ) ;2021 p l o t f (E, f ,P,[−1 1] , [−1 1 ] )22 di sp ( [ c1 c2 r e s u l t ] )23Output78B.2. PC Functions"false" "true" "Convexity Lost in interior of oneof the pieces containing edge 1"So the code finds the function to be continuous but not convex which is clearfrom the plot.B.2 PC FunctionsThe IsConvex2Dcubic uses Algorithm 2 to return 2 booleans as in theIsConvex2Dquad.[isconv,iscts,flag]=IsConvex2Dcubic(E,F,f,b).Example B.4. Consider the functionf(x) =−x3 − y3 + x2 + y2 x ≤ 0, y ≤ 0−x3 + 2y3 + x2 + 2y2 x ≤ 0, y ≥ 03x3 + 2y3 + 2x2 + 2y2 x ≥ 0, y ≥ 03x3 − y3 + 2x2 + y2 x ≥ 0, y ≤ 01 E=[ 0 0 −1 0 ;2 0 0 0 1 ;3 0 0 1 0 ;4 0 0 0 −1];5 f =[ −1 0 0 −1 1 0 1 0 0 0 ;6 −1 0 0 2 1 0 2 0 0 0 ;7 3 0 0 2 2 0 2 0 0 0 ;8 3 0 0 −1 2 0 1 0 0 0 ] ;9 P={[−1 4 ]79B.2. PC Functions10 [ 1 −2]11 [−3 2 ]12 [−4 3 ] } ;1314 F=[ 1 2 ;15 2 3 ;16 3 4 ;17 4 1 ] ;18 b = [ 0 ; 0 ; 0 ; 0 ] ;1920 [ c1 , c2 , r e s u l t ]= isConvex2Dcubic (E, F , f , b ) ;2122 p l o t f (E, f ,P, [ −10 ,10 ] , [ −10 ,10 ] ) ;23 di sp ( [ c1 , c2 , r e s u l t ] )Output"true" "true" "Passed"Now we will consider a non-convex example where convexity is lost inthe interior of one of the pieces.Example B.5. Consider the functionf(x) =−x3 − y3 + x2 + y2 x ≤ 0, y ≤ 0−x3 + 2y3 + x2 + 2y2 x ≤ 0, y ≥ 03x3 − 4x2y − 3xy2 + 2y3 + 2x2 + 2y2 x ≥ 0, y ≥ 03x3 − y3 + 2x2 + y2 x ≥ 0, y ≤ 01 E=[ 0 0 −1 0 ;2 0 0 0 1 ;80B.2. PC Functions3 0 0 1 0 ;4 0 0 0 −1];5 f =[ −1 0 0 −1 1 0 1 0 0 0 ;6 −1 0 0 2 1 0 2 0 0 0 ;7 3 −4 −3 2 2 0 2 0 0 0 ;8 3 0 0 −1 2 0 1 0 0 0 ] ;9 P={[−1 4 ]10 [ 1 −2]11 [−3 2 ]12 [−4 3 ] } ;1314 F=[ 1 2 ;15 2 3 ;16 3 4 ;17 4 1 ] ;18 b = [ 0 ; 0 ; 0 ; 0 ] ;1920 [ c1 , c2 , r e s u l t ]= isConvex2Dcubic (E, F , f , b ) ;2122 p l o t f (E, f ,P, [ −10 ,10 ] , [ −10 ,10 ] ) ;23 di sp ( [ c1 , c2 , r e s u l t ] )24Output"false" "true" "Convexity Lost in interior of oneof the pieces containing edge 2"Notice that edge 2 is the positive x−axis, which is indeed adjacent to thepiece defined as 3x3− 4x2y− 3xy2 + 2y3 + 2x2 + 2y2 which is not convex ascan be seen from the plot.81
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Convexity and structure of piecewise polynomial functions on polyhedral domains
Text