Convexity and Concavity

10 Key excerpts on "Convexity and Concavity"

• 

  eBook - ePub

  Mathematics for Economics and Finance

  • Michael Harrison, Patrick Waldron(Authors)
  • 2011(Publication Date)
  • Routledge

    (Publisher)

  Convexity and optimization

  DOI: 10.4324/9780203829998-12

  10.1 Introduction

  Much of economics and decision theory reduces to making optimal choices. This requires specifying the decision-maker’s objective as a mathematical function, depending on one or more choice variables. The mathematical theory of optimization tells us whether the decision-maker’s problem will have a solution or solutions, and how to find a solution if one exists. The objective of this chapter is to provide the reader with all the tools necessary to solve any optimization problem that may be encountered in economics or finance.

  The chapter begins with an extended discussion of Convexity and Concavity, concepts that are important in determining whether a solution to an optimization problem exists or is unique. The next three sections discuss the solution of optimization problems, first when all choice variables are free to vary independently, then when the choice variables are subject to equality constraints, and finally when there are inequality constraints. The chapter concludes with a section on the duality between the maximization of an objective function subject to a constraint and the minimization of the constraint function subject to the objective function taking on a particular value.

  Chiang and Wainwright (2005,Chapter 11 –Chapter 13 ) cover some of the material in this chapter at a more elementary level. More advanced treatments can be found in de la Fuente (2000, Chapter 6 ) and Takayama (1994).

  10.2 Convexity and Concavity

  10.2.1 Convex and concave functions

  We have already encountered the concept of a convex function in Definition 7.3.4. Roughly speaking, a function of n variables is convex if the set above its graph is a convex subset of ℝ

  n+1

  and concave if the set below its graph is a convex subset of ℝ

  n+1

  . From this rough description, it should already be clear that the concepts of concave and convex functions are broadly analogous. It is important to bear in mind, however, that there is no such thing as a concave set. For this reason, this branch of mathematics is usually described as convexity

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Pseudolinear Functions and Optimization

  • Shashi Kant Mishra, Balendu Bhooshan Upadhyay(Authors)
  • 2014(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1 Basic Concepts in Convex Analysis 1.1 Introduction Optimization is everywhere, as nothing at all takes place in the universe, in which some rule of maximum or minimum does not appear. It is the human nature to seek for the best among the available alternatives. An optimiza-tion problem is characterized by its specific objective function that is to be maximized or minimized, depending upon the problem and, in the case of a constrained problem, a given set of constraints. Possible objective functions include expressions representing profits, costs, market share, portfolio risk, etc. Possible constraints include those that represent limited budgets or resources, nonnegativity constraints on the variables, conservation equations, etc. The concept of convexity is of great importance in the study of optimiza-tion problems. It extends the validity of a local solution of a minimization problem to global one and the first order necessary optimality conditions be-come sufficient for a point to be a global minimizer. We mention the earlier work of Jensen [112], Fenchel [80, 81] and Rockafellar [238]. However, in several real-world applications, the notion of convexity does no longer suffice. In many cases, the nonconvex functions provide more accurate representation of real-ity. Nonconvex functions preserve one or more properties of convex functions and give rise to models which are more adaptable to the real-world situations, than convex models. This led to the introduction of several generalizations of the classical notion of convexity. In 1949, the Italian mathematician Bruno de Finetti [62] introduced one of the fundamental generalized convex functions, known as quasiconvex function having wider applications in economics, management sciences and engineering. Mangasarian [176] introduced the notion of pseudoconvex and pseudoconcave functions as generalizations of convex and concave functions, respectively.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Network Economics of Marine Ecosystems and their Exploitation

  • Christian Mullon(Author)
  • 2013(Publication Date)
  • CRC Press

    (Publisher)

  Chapter 5 Convexity and Optimization 5.1 Convex Sets 5.1.1 Convex Sets A large part of mathematical optimization theory relies on the idea of convex sets (figure 5.1) and convex functions. Definition 5.1.1 A subset K ⊂ R n is convex if for all pairs of points X ∈ K, Y ∈ K the line segment joining X and Y is included in K : for all α ∈ [0 , 1] , αX + (1 -α ) Y ∈ K . 5.1.2 Examples Let us give some basic examples of convex sets (see figure 5.2). A line L in the plane R 2 has an equation ax + by = c ; it splits the whole plane into half planes: H = { ( x, y ) | ax + by ≥ c } and L = { ( x, y ) | ax + by ≤ c } . Both half planes are convex subsets of R 2 (figure 5.2, top, left). Let us remark that the vector A with components ( a, b ) is orthogonal to the line L . We generalize this definition in arbitrary dimensions. An affine hyper space H , orthogonal to a vector A = ( a 1 , . . . , a n ) is defined by an equation { ( x 1 , . . . , x n ) | a 1 x 1 + · · · + a n x n = c } Definition 5.1.2 A half space in R n is defined as H = { ( x 1 , . . . , x n ) | a 1 x 1 + · · · + a n x n ≥ c } 54 5.1 Convex Sets 55 Figure 5.1: Convexity. Top: examples of convex sets in the plane R 2 : (a) a polyhedron; (b) a line. Middle: examples of non-convex sets in the plane: (c) set with a “concavity”, (d) set with several disjoint parts. Bottom: (e) a convex set in R 3 , (f) a non-convex set in 3d. Definition 5.1.3 A convex polyhedron is an intersection of half spaces (figure 5.2, top, right). It is defined by a finite number of linear equations: H = { ( x 1 , . . . , x n ) | a k 1 x 1 + · · · + a k n x n ≥ c k } Definition 5.1.4 A cone K ⊂ R n is a convex subset that for all X ∈ K , all λ ≥ 0 , λX ∈ K (figure 5.2, bottom, left). Definition 5.1.5 The generators of a cone (figure 5.2, bottom, right) are a set of vectors X 1 , .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Convex Functions

  Constructions, Characterizations and Counterexamples

  • Jonathan M. Borwein, Jon D. Vanderwerff(Authors)
  • 2010(Publication Date)
  • Cambridge University Press

    (Publisher)

  1 Why convex? The first modern formalization of the concept of convex function appears in J. L. W. V. Jensen, “Om konvexe funktioner og uligheder mellem midelvaerdier.” Nyt Tidsskr. Math. B 16 (1905), pp. 49–69. Since then, at first referring to “Jensen’s convex functions,” then more openly, without needing any explicit reference, the definition of convex function becomes a standard element in calculus handbooks. (A. Guerraggio and E. Molho) 1 Convexity theory . . . reaches out in all directions with useful vigor. Why is this so? Surely any answer must take account of the tremendous impetus the subject has received from outside of mathematics, from such diverse fields as economics, agriculture, military planning, and flows in networks. With the invention of high-speed computers, large-scale problems from these fields became at least potentially solvable. Whole new areas of mathematics (game theory, linear and nonlinear programming, control theory) aimed at solving these problems appeared almost overnight. And in each of them, convexity theory turned out to be at the core. The result has been a tremendous spurt in interest in convexity theory and a host of new results. (A. Wayne Roberts and Dale E. Varberg) 2 1.1 Why ‘convex’? This introductory polemic makes the case for a study focusing on convex functions and their structural properties. We highlight the centrality of convexity and give a selection of salient examples and applications; many will be revisited in more detail later in the text – and many other examples are salted among later chapters. Two excellent companion pieces are respectively by Asplund [15] and by Fenchel [212]. A more recent survey article by Berger has considerable discussion of convex geometry [53]. It has been said that most of number theory devolves to the Cauchy–Schwarz inequality and the only problem is deciding ‘what to Cauchy with’. In like fashion, much mathematics is tamed once one has found the right convex ‘Green’s function’.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Decision Sciences

  Theory and Practice

  • Raghu Nandan Sengupta, Aparna Gupta, Joydeep Dutta, Raghu Nandan Sengupta, Aparna Gupta, Joydeep Dutta(Authors)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  We discuss this is more detail in the next section. Our symbols are standard and follow largely Borwein and Lewis [2]. 1.2 Convex Functions: Fundamental Properties 1.2.1 Examples of Convex Functions Convexity is a great property to use if one, somehow, knows beforehand the convexity of the func-tion. Is it easy to detect whether a function is convex? The answer is, in general, it is not. One of the important rules for characterizing a twice continuously differentiable convex function is to check whether its Hessian matrix is positive semidefinite. This might not be an easy task always and fur-ther convex functions may not even be differentiable and thus the above tool may not be handy. It is now a growing theme in mathematics and other science when the analytical approach on paper is making no headway or giving any clue one has to turn to the computer for visualization using some computer algebra system (CAS) such as MAPLE or MATHEMATICA. We shall show the use of CAS using MAPLE. Now let us look at the real-valued convex functions on R or some subset of R . Consider the function f : R → R given as f ( x ) = x 6 + x 5 + x 4 + x 3 + x 2 + 1. It is not so easy to believe that the function is convex even if it is an even-degree polynomial. If we attempt to prove that it is convex, we need to check whether the second-order derivative is nonnegative on R . In this particular case, we have f ( x ) = 30 x 4 + 20 x 3 + 12 x 2 + 6 x + 12. It is not easy to immediately check that the second derivative is nonnegative on R . Thus, the first approach is to try and plot the graph of f , which is given in Figure 1.1. The graph definitely looks like the graph of a convex function; however, the region between x = − 2 and x = 2 is not clear. Thus, let us zoom in on the graph in the interval [ − 2, 2].

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematical Programming

  An Introduction to Optimization

  • Melvyn Jeter(Author)
  • 2018(Publication Date)
  • Routledge

    (Publisher)

  7 Convex and Concave Functions

  Chapter 2 contained an introduction to convex analysis and its applications to linear programming. This chapter is an extension of that introduction to include convex functions and their applications to mathematical programming. Section 1 begins with the basic definition and examples of a convex function. This is followed by a brief study of convex functions of a real variable. Then after a brief calculus review a similar study is made for functions of several variables. In Section 4 some basic results concerning the optimization of convex functions are presented. The last section deals with some of the popular generalizations of this topic and their applications.

  1.    INTRODUCTION

  Let K be a convex subset of R

  n×1

  . A function of f: K → R is a convex function if and only if f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y) whenever x,y ∈ K and α ∈ [0,1]. Figure 1(a) is an example of a convex function while Figure 1(b) is an example of a function that is not convex. Notice that in Figure 1(a) , the point (αx1 + (1 − α)x2 ,f(αx1 + (1 − α)x2 )), where 0 < α < 1, is not above the corresponding point (αx1 + (1 − α)x2 , αf(x1 ) + (1 − α)f(x2 )) on the chord that connects the points (x1 , f(x1 )) and (x2 , f(x2 )).

  The following function are examples of convex functions.

  1.  Any linear function

  f

  ( x )

  =

  c T

  x =

  Σ

  i = 1

  n

  c i

  x i

  over K = R

  n×1

  . Here, x = [x1 … xn ]

  T

  and c = [c1 … cn ]

  T

  (see Chapter 2 ).

  2.  Any quadratic function q(x) = ax2 + bx + c, where a, b and c are constants, a > 0 and K = R.

  3.  f(x) = |x|, where x ∈ K = R.

  4.  f(x) = x3 , where x ∈ K = [0, ∞).

  5.  

  f

  (

  [

  x 1

  x 2

  ]

  T

  )

  = 4

  x 1 2

  + 25

  x 2 2

  , where [x1 x2 ]

  T

  ∈ K = R2×1 (Notice that the graph of f is an elliptic paraboloid.)

  Figure 1

  Again consider a function f:K → R, where K is a convex subset of R

  n×1

  . The function f is concave if and only if f(αx1 + (1 − α)x2 ) ≥ αf(x1 ) + (1 − α)f(x2 ), whenever x,y ∈ K and α ∈ K and α ∈ [0,1], It is a simple exercise to show that f is a concave function if and only if −f is a convex function. A function that is both convex and concave over K is said to be affine. Any linear function over K is both convex and concave and, hence, affine

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Generalized Convexity, Nonsmooth Variational Inequalities, and Nonsmooth Optimization

  • Qamrul Hasan Ansari, C. S. Lalitha, Monika Mehta(Authors)
  • 2013(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1 Elements of Convex Analysis 1.1 Introduction Convex functions play a vital role in almost all the branches of mathematics as well as other areas such as science, economics, and engineering. The main reason for this being that they are very well suited to extremum problems as necessary conditions for the existence of a minimum also become sufficient in the presence of convexity. Convex functions were introduced in the beginning of the 20th century by Jensen [111] and more than forty years later a thorough study of conjugate functions was initiated by Fenchel [76, 77]. The lecture notes by Fenchel [77] led to the classic book Convex Analysis by Rockafellar [182]. However, since not all real life problems can be formulated as a convex model it becomes a necessity to extend the study to deal with nonconvex problems. Some of the nonconvex functions studied in literature preserve cer-tain properties of convex functions, which in turn help to study the optimality conditions. One of the well-known classes of functions, occurring in various fields such as economics, engineering, management science, probability theory, and various applied sciences, is the class of quasiconvex functions. Although in most of the literature de Finetti [68] is mentioned as the first author to introduce quasiconvex functions, these functions were previously considered by von Neumann [168] and by Popoviciu [177] independently. Another class of functions for which necessary optimality conditions also become sufficient is the class of pseudoconvex functions. These functions were introduced by Man-gasarian [152]. The class of pseudoconvex functions includes the class of all differentiable convex functions and is included in the class of all differentiable quasiconvex functions. The first volume [189] devoted exclusively to generalized convexity was published in 1981 followed by the monograph Generalized Concavity by Avriel, Diewert, Schaible, and Zang [28].

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Convex Analysis

  • Steven G. Krantz(Author)
  • 2014(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 2 Characterization of Convexity Using Functions Prologue: Now we begin our analytic studies. The chapter begins with a concept that will be new for many readers: the idea of defining function. This is a key epistemological point in the book— to associate to any reasonable domain a function. The idea is that the function contains all the geometric information about that domain. There are no obvious algebraic operations on domains, but there are many such operations on functions. We can take good advantage of that observation. Using the defining function, we can finally give an analytic definition of convex set. Advantages now are (i) that we can distinguish analytically convex boundary points from non-convex boundary points and (ii) that we have a notion of weak analytic convexity and a notion of strong analytic convexity. These are all new ideas, with no precedent in the classical theory of Chapter 1. We finish the chapter with another new idea—that of exhaus-tion function. This is a way to characterize a convex set with a function that is defined on the interior of the set only—not on the boundary. From the point of view of intrinsic geometry this is a very natural idea. This discussion rounds out our picture of the study of convex sets using convex functions, and prepares us for deeper explorations in the next chapter. 21 22 CHAPTER 2. FUNCTIONS + -0 Figure 2.1: The concept of defining function. 2.1 The Concept of Defining Function Let Ω ⊆ R N be a domain with continuously or C 1 differentiable boundary. A continuously differentiable function ρ : R N → R is called a defining function for Ω if 1. Ω = { x ∈ R N : ρ ( x ) < 0 } ; 2. c Ω = { x ∈ R N : ρ ( x ) > 0 } ; 3. ∇ ρ ( x ) negationslash = 0 ∀ x ∈ ∂ Ω. We note that conditions 1 and 2 certainly entail that ∂ Ω = { x ∈ R N : ρ ( x ) = 0 } . See Figure 2.1. In case k ≥ 2 and ρ is C k (that is, k times continuously differentiable), then we say that the domain Ω has C k boundary.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Undergraduate Convexity: From Fourier And Motzkin To Kuhn And Tucker

  From Fourier and Motzkin to Kuhn and Tucker

  • Niels Lauritzen(Author)
  • 2013(Publication Date)
  • World Scientific

    (Publisher)

  Even though (7.3) predates and in-spired the theory of convex functions, we will view it in this more modern context. Convex functions 143 7.1 Basics Consider a function f : C → R , where C is a subset of R n . The graph of f is the subset of R n +1 given by { ( x, y ) | x ∈ C, y ∈ R , and y = f ( x ) } . The epigraph of f is the subset epi( f ) = { ( x, y ) | x ∈ C, y ∈ R and y ≥ f ( x ) } of R n +1 . Figure 7.1: The epigraph of f ( x ) = x 2 is the set of points above the graph of f . Definition 7.1. Let C ⊆ R n be a convex subset. A convex function is a function f : C → R such that f ((1 -λ ) x + λy ) ≤ (1 -λ ) f ( x ) + λf ( y ) (7.4) and a concave function is a function f : C → R , such that f ((1 -λ ) x + λy ) ≥ (1 -λ ) f ( x ) + λf ( y ) for every x, y ∈ C and every λ ∈ R with 0 ≤ λ ≤ 1 . A convex (concave) function f : C → R is called strictly convex ( strictly concave ) if f ((1 -λ ) x + λy ) = (1 -λ ) f ( x ) + λf ( y ) implies that x = y , for every x, y ∈ C and every λ ∈ R with 0 < λ < 1 . Notice that a strictly convex function satisfies f ((1 -λ ) x + λy ) < (1 -λ ) f ( x ) + λf ( y ) for x 6 = y and 0 < λ < 1 and that -f is (strictly) concave if and only if f is (strictly) convex. 144 Undergraduate Convexity —From Fourier and Motzkin to Kuhn and Tucker Our main emphasis will be on convex functions. The convexity of a function has a rather simple interpretation in terms of its epigraph. Lemma 7.2. Let C ⊆ R n be a convex subset. A function f : C → R is convex if and only epi( f ) is a convex subset of R n +1 . Proof. Suppose epi( f ) is a convex subset. For ( x, f ( x )) , ( y, f ( y )) ∈ epi( f ) we have (1 -λ )( x, f ( x )) + λ ( y, f ( y )) = ((1 -λ ) x + λy, (1 -λ ) f ( x ) + λf ( y )) ∈ epi( f ) , for every 0 ≤ λ ≤ 1 and ux, y ∈ C . Therefore f ((1 -λ ) x + λy ) ≤ (1 -λ ) f ( x ) + λf ( y ) and f is convex. If ( x 0 , y 0 ) , ( x 1 , y 1 ) ∈ epi( f ) , then f ( x 0 ) ≤ y 0 and f ( x 1 ) ≤ y 1 .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Linear Algebra Tools For Data Mining

  • Dan A Simovici(Author)
  • 2012(Publication Date)
  • World Scientific

    (Publisher)

  The converse is also true; namely, if f is differentiable everywhere and its derivative is an increasing function, then f is convex. Indeed, let a,b,c be three numbers such that a 0 convex for r ≥ 1 ln x − 1 x 2 concave x ln x 1 x convex e x e x convex is convex. Clearly, under the same conditions of differentiability as above, if the second derivative is non-positive everywhere, then f is concave. The functions listed in the Table 7.1, defined on the set R ≥ 0 , provide examples of convex (or concave) functions. Definition 7.16. Let D ⊆ R n and let f : D −→ R be a function. A level set for a function f is a set of the form L f,a = { x ∈ R n | f ( x ) ≤ a } . Theorem 7.41. Let D ⊆ R n and let f : D −→ R be a function. If f is convex, then every level set L f,a is convex set. Proof. Let x 1 ,x 2 ∈ L f,a . We have f ( x 1 ) ≤ a and f ( 2 1 ) ≤ a so f ( tx 1 + (1 − t ) x 2 ) ≤ tf ( x 1 ) + (1 − t ) f ( x 2 ) ≤ a, which implies tx 1 + (1 − t ) x 2 ∈ L f,a for every t ∈ [0 , 1]. This shows that L f,a is convex. square Theorem 7.42. Let C be a convex subset of R n , b be a number in R , and let F = { f i | f i : C −→ R ,i ∈ I } be a family of convex functions such that f i ( x ) ≤ b for every i ∈ I and x ∈ C . Then, the function f : C −→ R defined by f ( x ) = sup { f i ( x ) | i ∈ I } for x ∈ C is a convex function.

  Sign up to read

  Learn more about book