Share
VIDEOS 1 TO 50
17 - Convex functions
17 - Convex functions
Published: 2015/03/22
Channel: Learning Advisors AUT
Concave and convex functions
Concave and convex functions
Published: 2012/08/14
Channel: learnittcom
Lecture 3 | Convex Optimization I (Stanford)
Lecture 3 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Lecture-01  Convex Sets and Functions
Lecture-01 Convex Sets and Functions
Published: 2017/07/07
Channel: Nonlinear Programming
Lecture 4-5: Convex sets and functions
Lecture 4-5: Convex sets and functions
Published: 2012/02/12
Channel: Technion
03F Convex Set & Convex Function
03F Convex Set & Convex Function
Published: 2017/03/19
Channel: Yong Wang
Lecture-02 Properties of Convex Functions-I
Lecture-02 Properties of Convex Functions-I
Published: 2017/07/07
Channel: Nonlinear Programming
Mod-05 Lec-08 Convex Functions
Mod-05 Lec-08 Convex Functions
Published: 2012/07/03
Channel: nptelhrd
Intermediate Microeconomics: Convex and Concave functions
Intermediate Microeconomics: Convex and Concave functions
Published: 2014/01/20
Channel: Department of Economics
Inflection Points and Concavity Intuition
Inflection Points and Concavity Intuition
Published: 2010/01/22
Channel: Khan Academy
Lecture 2 | Convex Optimization I (Stanford)
Lecture 2 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Convex function
Convex function
Published: 2014/09/02
Channel: Audiopedia
10-801 Lecture 2: Convex Functions
10-801 Lecture 2: Convex Functions
Published: 2014/01/24
Channel: 10-801-s14-cmu
Convex optimization
Convex optimization
Published: 2013/04/15
Channel: Network20Q
difference between convex and concave functions
difference between convex and concave functions
Published: 2015/04/10
Channel: manik seth
10B Hessian Matrix, Convex & Concave Functions
10B Hessian Matrix, Convex & Concave Functions
Published: 2017/04/19
Channel: Yong Wang
3.1 Continuity of Convex Functions - Pt 1
3.1 Continuity of Convex Functions - Pt 1
Published: 2016/01/28
Channel: Nam Nguyen
Convex Functions - Pt 1
Convex Functions - Pt 1
Published: 2015/03/16
Channel: Nam Nguyen
Subgradients of Convex Functions - Pt 1
Subgradients of Convex Functions - Pt 1
Published: 2015/08/28
Channel: Nam Nguyen
Lecture 1 | Convex Optimization I (Stanford)
Lecture 1 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Convex Functions - Pt 1
Convex Functions - Pt 1
Published: 2016/06/21
Channel: Nam Nguyen
Convex function
Convex function
Published: 2016/01/22
Channel: WikiAudio
Mod-01 Lec-12 Post optimality analysis, convex function and its properties (Contd.)
Mod-01 Lec-12 Post optimality analysis, convex function and its properties (Contd.)
Published: 2014/12/30
Channel: nptelhrd
concavity and convexity[in hindi ]
concavity and convexity[in hindi ]
Published: 2017/02/12
Channel: Manisha Marwaha
L3.8 - Connection between concave and convex function
L3.8 - Connection between concave and convex function
Published: 2016/12/31
Channel: Amit Goyal
EXAMPLE: Proving that a set is convex
EXAMPLE: Proving that a set is convex
Published: 2013/04/21
Channel: Maths Learning Centre UofA
2   Convex sets
2 Convex sets
Published: 2015/06/09
Channel: mathapptician
Convex Function (Basic Properties)
Convex Function (Basic Properties)
Published: 2013/03/12
Channel: ousam2010
positive second derivative means convex function
positive second derivative means convex function
Published: 2013/10/15
Channel: Anish Turlapaty
Quasi Concave and Quasi Convex Functions
Quasi Concave and Quasi Convex Functions
Published: 2014/08/17
Channel: EurekaWow
Convex Sets - Introduction
Convex Sets - Introduction
Published: 2012/08/31
Channel: mathapptician
What Is A Convex Function?
What Is A Convex Function?
Published: 2017/07/13
Channel: sparky SPARKS
Convexity vs. Strict Convexity in economics
Convexity vs. Strict Convexity in economics
Published: 2014/07/11
Channel: Free Econ Help
Lecture 8 | Convex Optimization I (Stanford)
Lecture 8 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Directional Derivatives of Convex Functions - Pt 1
Directional Derivatives of Convex Functions - Pt 1
Published: 2016/03/24
Channel: Nam Nguyen
Lecture-05 Convex Programming Problems
Lecture-05 Convex Programming Problems
Published: 2017/07/10
Channel: Nonlinear Programming
Convex and Nonconvex
Convex and Nonconvex
Published: 2014/09/10
Channel: Aaron Bucko
Lecture 4 | Convex Optimization I (Stanford)
Lecture 4 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Lecture 16 | Convex Optimization I (Stanford)
Lecture 16 | Convex Optimization I (Stanford)
Published: 2008/07/09
Channel: Stanford
Part Z: Convex Functions (Part A)
Part Z: Convex Functions (Part A)
Published: 2013/09/26
Channel: Network20Q
Mod-01 Lec-01  Convex Optimization
Mod-01 Lec-01 Convex Optimization
Published: 2013/03/20
Channel: nptelhrd
Concave and convex functions part 2
Concave and convex functions part 2
Published: 2012/08/14
Channel: learnittcom
CONCAVE AND CONVEX CURVES MATHEMATICAL DERIVATION FOR ECONOMICS BY SOURAV SIR
CONCAVE AND CONVEX CURVES MATHEMATICAL DERIVATION FOR ECONOMICS BY SOURAV SIR'S CLASSES 9836793076
Published: 2016/08/09
Channel: SOURAV SIR'S CLASSES
Application of derivatives - Convex and concave functions
Application of derivatives - Convex and concave functions
Published: 2016/11/15
Channel: Ganesh Kumar
Convex, nonconvex, and concave preferences
Convex, nonconvex, and concave preferences
Published: 2017/10/09
Channel: joonbug11
Convex Optimization and Applications - Stephen Boyd
Convex Optimization and Applications - Stephen Boyd
Published: 2015/08/28
Channel: Calit2ube
Concave Convex Rule
Concave Convex Rule
Published: 2014/08/28
Channel: Louis Davis
Role of L2 Regularization in Convexifying Non-convex Functions
Role of L2 Regularization in Convexifying Non-convex Functions
Published: 2015/11/18
Channel: ML Refined
Convex and Concave Water Lenses
Convex and Concave Water Lenses
Published: 2013/05/17
Channel: NASA Video
Quasiconcavity - A simple example
Quasiconcavity - A simple example
Published: 2016/12/13
Channel: Nash
NEXT
GO TO RESULTS [51 .. 100]

WIKIPEDIA ARTICLE

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Convex function on an interval.
A function (in black) is convex if and only if the region above its graph (in green) is a convex set.
A graph of the bivariate convex function x2 + xy + y2.

In mathematics, a real-valued function defined on an n-dimensional interval is called convex (or convex downward or concave upward) if the line segment between any two points on the graph of the function lies above or on the graph, in a Euclidean space (or more generally a vector space) of at least two dimensions. Equivalently, a function is convex if its epigraph (the set of points on or above the graph of the function) is a convex set. For a twice differentiable function of a single variable, if the second derivative is always greater than or equal to zero for its entire domain then the function is convex.[1] Well-known examples of convex functions include the quadratic function and the exponential function .

Convex functions play an important role in many areas of mathematics. They are especially important in the study of optimization problems where they are distinguished by a number of convenient properties. For instance, a (strictly) convex function on an open set has no more than one minimum. Even in infinite-dimensional spaces, under suitable additional hypotheses, convex functions continue to satisfy such properties and as a result, they are the most well-understood functionals in the calculus of variations. In probability theory, a convex function applied to the expected value of a random variable is always less than or equal to the expected value of the convex function of the random variable. This result, known as Jensen's inequality, underlies many important inequalities (including, for instance, the arithmetic–geometric mean inequality and Hölder's inequality).

Definition[edit]

Let be a convex set in a real vector space and let be a function.

  • f is called convex if:
  • f is called strictly convex if:
  • A function f is said to be (strictly) concave if f is (strictly) convex.

Properties[edit]

Functions of one variable[edit]

1. Suppose f is a function of one real variable defined on an interval, and let

(note that R(x1, x2) is the slope of the purple line in the above drawing; note also that the function R is symmetric in (x1, x2)). f is convex if and only if R(x1, x2) is monotonically non-decreasing in x1, for every fixed x2 (or vice versa). This characterization of convexity is quite useful to prove the following results.

2. A convex function f of one real variable defined on some open interval C is continuous on C and Lipschitz continuous on any closed subinterval. f admits left and right derivatives, and these are monotonically non-decreasing. As a consequence, f is differentiable at all but at most countably many points. If C is closed, then f may fail to be continuous at the endpoints of C (an example is shown in the examples section).

3. A differentiable function of one variable is convex on an interval if and only if its derivative is monotonically non-decreasing on that interval. If a function is differentiable and convex then it is also continuously differentiable.

4. A differentiable function of one variable is convex on an interval if and only if the function lies above all of its tangents:[2]:69

for all x and y in the interval. In particular, if f ′(c) = 0, then c is a global minimum of f(x).

5. A twice differentiable function of one variable is convex on an interval if and only if its second derivative is non-negative there; this gives a practical test for convexity. Visually, a twice differentiable convex function "curves up", without any bends the other way (inflection points). If its second derivative is positive at all points then the function is strictly convex, but the converse does not hold. For example, the second derivative of f(x) = x4 is f ′′(x) = 12x2, which is zero for x = 0, but x4 is strictly convex.

6. If f is a convex function of one real variable, and f(0) ≤ 0, then f is superadditive on the positive reals.

Proof: Since f is convex, letting y = 0 we have
From this we have:

Functions of n variables[edit]

1. A function is midpoint convex on an interval C if

This condition is only slightly weaker than convexity. For example, a real-valued Lebesgue measurable function that is midpoint-convex will be convex by the Sierpinski theorem.[3] In particular, a continuous function that is midpoint convex will be convex.

2. A continuous, twice differentiable function of several variables is convex on a convex set if and only if its Hessian matrix of second partial derivatives is positive semidefinite on the interior of the convex set.

3. Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.[4]

4. For a convex function f, the sublevel sets {x | f(x) < a} and {x | f(x) ≤ a} with aR are convex sets. However, a function whose sublevel sets are convex sets may fail to be a convex function. A function whose sublevel sets are convex is called a quasiconvex function.

5. Jensen's inequality applies to every convex function f. If X is a random variable taking values in the domain of f, then E(f(X)) ≥ f(E(X)). (Here E denotes the mathematical expectation.)

Convex function calculus[edit]

  • If f and g are convex functions, then so are and .
  • If f and g are convex functions and g is non-decreasing over a univariate domain, then is convex. As an example, if f(x) is convex, then so is , because is convex and monotonically increasing.
  • If f is concave and g is convex and non-increasing over a univariate domain, then is convex.
  • Convexity is invariant under affine maps: that is, if f is convex with domain , then so is , where with domain .
  • If f(x, y) is convex in x then is convex in x provided for some x, even if C is not convex.
  • If f(x) is convex, then its perspective (whose domain is ) is convex.
  • The negative of a convex function is a concave function.
  • If is a convex real valued function, then for a countable collection of real numbers

Strongly convex functions[edit]

The concept of strong convexity extends and parametrizes the notion of strict convexity. A strongly convex function is also strictly convex, but not vice versa.

A differentiable function f is called strongly convex with parameter m > 0 if the following inequality holds for all points x, y in its domain:[5]

or, more generally,

where is any norm. Some authors, such as [6] refer to functions satisfying this inequality as elliptic functions.

An equivalent condition is the following:[7]

It is not necessary for a function to be differentiable in order to be strongly convex. A third definition[7] for a strongly convex function, with parameter m, is that, for all x, y in the domain and ,

Notice that this definition approaches the definition for strict convexity as m → 0, and is identical to the definition of a convex function when m = 0. Despite this, functions exist that are strictly convex but are not strongly convex for any m > 0 (see example below).

If the function f is twice continuously differentiable, then f is strongly convex with parameter m if and only if for all x in the domain, where I is the identity and is the Hessian matrix, and the inequality means that is positive semi-definite. This is equivalent to requiring that the minimum eigenvalue of be at least m for all x. If the domain is just the real line, then is just the second derivative , so the condition becomes . If m = 0, then this means the Hessian is positive semidefinite (or if the domain is the real line, it means that ), which implies the function is convex, and perhaps strictly convex, but not strongly convex.

Assuming still that the function is twice continuously differentiable, one can show that the lower bound of implies that it is strongly convex. Start by using Taylor's Theorem:

for some (unknown) . Then

by the assumption about the eigenvalues, and hence we recover the second strong convexity equation above.

A function f is strongly convex with parameter m if and only if the function is convex.

The distinction between convex, strictly convex, and strongly convex can be subtle at first glance. If f is twice continuously differentiable and the domain is the real line, then we can characterize it as follows:

f convex if and only if for all x.
f strictly convex if for all x (note: this is sufficient, but not necessary).
f strongly convex if and only if for all x.

For example, consider a function f that is strictly convex, and suppose there is a sequence of points such that . Even though the function is not strongly convex because will become arbitrarily small.

A twice continuously differentiable function f on a compact domain that satisfies for all is strongly convex. The proof of this statement follows from the extreme value theorem, which states that a continuous function on a compact set has a maximum and minimum.

Strongly convex functions are in general easier to work with than convex or strictly convex functions, since they are a smaller class. Like strictly convex functions, strongly convex functions have unique minima on compact sets.

Uniformly convex functions[edit]

A uniformly convex function,[8][9] with modulus , is a function f that, for all x, y in the domain and t ∈ [0, 1], satisfies

where is a function that is non-negative and vanishes only at 0. This is a generalization of the concept of strongly convex function; by taking we recover the definition of strong convexity.

Examples[edit]

Functions of one variable[edit]

  • The function has at all points, so f is a convex function. It is also strongly convex (and hence strictly convex too), with strong convexity constant 2.
  • The function has , so f is a convex function. It is strictly convex, even though the second derivative is not strictly positive at all points. It is not strongly convex.
  • The absolute value function is convex (as reflected in the triangle inequality), even though it does not have a derivative at the point x = 0. It is not strictly convex.
  • The function for 1 ≤ p is convex.
  • The exponential function is convex. It is also strictly convex, since , but it is not strongly convex since the second derivative can be arbitrarily close to zero. More generally, the function is logarithmically convex if f is a convex function. The term "superconvex" is sometimes used instead.[10]
  • The function with domain [0,1] defined by for is convex; it is continuous on the open interval (0, 1), but not continuous at 0 and 1.
  • The function x3 has second derivative 6x; thus it is convex on the set where x ≥ 0 and concave on the set where x ≤ 0.
  • Examples of functions that are monotonically increasing but not convex include and
  • Examples of functions that are convex but not monotonically increasing include and .
  • The function has which is greater than 0 if x > 0, so is convex on the interval (0, +∞). It is concave on the interval (−∞, 0).
  • The function with , is convex on the interval (0, +∞) and convex on the interval (−∞,0), but not convex on the interval (−∞, +∞), because of the singularity at x = 0.

Functions of n variables[edit]

  • The function on the domain of positive-definite matrices is convex.[2]:74
  • Every real-valued linear transformation is convex but not strictly convex, since if f is linear, then This statement also holds if we replace "convex" by "concave".
  • Every real-valued affine function, i.e., each function of the form , is simultaneously convex and concave.
  • Every norm is a convex function, by the triangle inequality and positive homogeneity.

See also[edit]

Notes[edit]

  1. ^ "Lecture Notes 2" (PDF). www.stat.cmu.edu. Retrieved 3 March 2017. 
  2. ^ a b Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011. 
  3. ^ Donoghue, William F. (1969). Distributions and Fourier Transforms. Academic Press. p. 12. ISBN 9780122206504. Retrieved August 29, 2012. 
  4. ^ "If f is strictly convex in a convex set, show it has no more than 1 minimum". Math StackExchange. 21 Mar 2013. Retrieved 14 May 2016. 
  5. ^ Dimitri Bertsekas (2003). Convex Analysis and Optimization. Contributors: Angelia Nedic and Asuman E. Ozdaglar. Athena Scientific. p. 72. ISBN 9781886529458. 
  6. ^ Philippe G. Ciarlet (1989). Introduction to numerical linear algebra and optimisation. Cambridge University Press. ISBN 9780521339841. 
  7. ^ a b Yurii Nesterov (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers. pp. 63–64. ISBN 9781402075537. 
  8. ^ C. Zalinescu (2002). Convex Analysis in General Vector Spaces. World Scientific. ISBN 9812380671. 
  9. ^ H. Bauschke and P. L. Combettes (2011). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer. p. 144. ISBN 978-1-4419-9467-7. 
  10. ^ Kingman, J. F. C. (1961). "A Convexity Property of Positive Matrices". The Quarterly Journal of Mathematics. 12: 283–284. doi:10.1093/qmath/12.1.283. 

References[edit]

  • Bertsekas, Dimitri (2003). Convex Analysis and Optimization. Athena Scientific. 
  • Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer.
  • Donoghue, William F. (1969). Distributions and Fourier Transforms. Academic Press. 
  • Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). Fundamentals of Convex analysis. Berlin: Springer.
  • Krasnosel'skii M.A., Rutickii Ya.B. (1961). Convex Functions and Orlicz Spaces. Groningen: P.Noordhoff Ltd. 
  • Lauritzen, Niels (2013). Undergraduate Convexity. World Scientific Publishing. 
  • Luenberger, David (1984). Linear and Nonlinear Programming. Addison-Wesley. 
  • Luenberger, David (1969). Optimization by Vector Space Methods. Wiley & Sons. 
  • Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. 
  • Thomson, Brian (1994). Symmetric Properties of Real Functions. CRC Press. 
  • Zălinescu, C. (2002). Convex analysis in general vector spaces. River Edge, NJ: World Scientific Publishing  Co., Inc. pp. xx+367. ISBN 981-238-067-1. MR 1921556. 

External links[edit]

Disclaimer

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Powered by YouTube
Wikipedia content is licensed under the GFDL and (CC) license