Jump to content

Convex function

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
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.

수학(mathematics)에서, n-차원 구간(n-dimensional interval)에서 정의된 실수-값 함수(real-valued function)는, 만약 함수의 그래프(graph of the function) 위의 임의의 두 점 사이의 선분(line segment)이 그래프 위쪽 또는 그래프 위에 놓이면, 볼록(convex) (또는 아래로 볼록(convex downward) 또는 위로 오목(concave upward))으로 불립니다. 동등하게, 함수는, 만약 그의 에피그래프(epigraph) (함수의 그래프 위에 또는 위쪽에 있는 점들의 집합)가 볼록 집합(convex set)이면, 볼록입니다. 단일 변수의 두번-미분가능 함수가 볼록인 것과 그것의 이차 도함수가 그것의 전체 도메인 위에 항상 비-음수인 것은 필요충분(iff) 조건입니다.[1] 단일 변수의 볼록 함수의 잘-알려진 예제는 제곱하는 함수(squaring function) 지수 함수(exponential function) 를 포함합니다.

볼록 함수는 수학의 많은 분야에서 중요한 역할을 합니다. 그것들은 최적화(optimization) 문제의 연구에서 특히 중요하며, 여기서 그들은 여러 편리한 속성에 의해 구별됩니다. 예를 들어, 열린 집합 위에 엄격하게 볼록 함수는 하나 이상의 최솟값을 가지지 않습니다. 심지어 무한 차원 공간에서, 적절한 추가 가설 아래에서, 볼록 함수는 그러한 속성을 계속 만족시키고 그 결과로써, 그들은 변화의 계산법(calculus of variations)에서 가장 잘-이해된 함수입니다. 확률 이론(probability theory)에서, 확률 변수(random variable)기댓값(expected value)에 적용되는 볼록 함수는 확률 변수의 볼록 함수의 기댓값에 의해 항상 위로 경계집니다. 옌센 부등식(Jensen's inequality)으로 알려진, 이 결과는 산술–-기하 평균 부등식(arithmetic–geometric mean inequality)횔더 부등식(Hölder's inequality)과 같은 부등식을 추론하기 위해 사용될 수 있습니다.

Definition

를 실수 벡터 공간(vector space)에서 볼록 집합(convex set)으로 놓고 를 함수로 놓습니다.

  • f는 만약 다음이면 볼록이라고 불립니다:
  • f는 만약 다음이면 엄격하게 볼록이라고 불립니다:
  • 함수 f는, 만약 f가 (엄격하게) 볼록이면, (엄격하게) 오목(concave)이라고 말합니다.

Properties

Functions of one variable

  • 를 구간 위에 정의된 하나의 실수(real) 변수의 함수로 가정하고, 다음을 놓습니다:
(R(x1, x2)는 상기 그림에서 자주색 직선의 기울기임을 주목하십시오; 함수 R은 (x1, x2)에서 대칭(symmetric)입니다). 가 볼록인 것과 R(x1, x2)가 모든 각 고정된 x2에 대해 x1에서 단조적으로 비-감소하는(monotonically non-decreasing) (또는 반대도 마찬가지임) 것은 필요충분 조건입니다. 볼록성의 이 특징은 다음 결과를 입증하기 위해 매우 유용합니다.
동등하게, 한 변수의 미분-가능 함수가 볼록인 것과 그것의 에피그래프가 볼록 집합인 것은 필요충분 조건입니다. 특히, 만약 이면, c전역 최솟값(global minimum)입니다.
  • 한 변수의 두번 미분-가능 함수는 구간 위에 볼록인 것과 그것의 이차 도함수(second derivative)가 그곳에서 비-음수인 것은 필요충분 조건입니다; 이것은 볼록성에 대해 실용적인 테스트를 제공합니다. 시각적으로, 두번 미분-가능 볼록 함수는 다른 방법으로 임의의 굽음 (변곡점(inflection point))없이 "위로 휘어집니다". 만약 이차 도함수가 모든 점에서 양수이면, 함수는 엄밀하게 볼록하지만, 전환(converse)은 유지되지 않습니다. 예를 들어, f(x) = x4의 이차 도함수는 f ′′(x) = 12x2이며, x = 0에 대해 0이지만, x4은 엄격하게 볼록입니다.
  • 만약 가 한 실수 변수의 볼록 함수이고, 이면, 양의 실수(positive reals) 위에 초-덧셈적(superadditive)입니다.
증명. 가 볼록이므로, y = 0을 설정하면 우리는 다음을 가집니다:
이것으로부터, 우리는 다음을 가집니다:
  • 함수는 만약 다음이면 구간 C 위의 중간점 볼록입니다:
이 조건은 볼록성보다 단지 약간 더 약한 것입니다. 예를 들어, 중간점-볼록인 실수-값 르베그 측정-가능 함수(Lebesgue measurable function)는 볼록입니다: 이것은 시에르핀스키(Sierpiński)의 정리입니다.[3] 특히, 중간-점 볼록인 연속 함수는 볼록일 것입니다.

Functions of several variables

Operations that preserve convexity

  • 가 오목인 것과 가 볼록인 것은 필요충분 조건입니다.
  • 비-음의 가중된 합:
    • 만약 가 모두 볼록이면, 따라서 입니다. 특히, 두 볼록 함수의 합은 볼록입니다.
    • 이 속성은 무한 합, 적분과 (그들이 존재한다는 조건으로 하여) 마찬가지로 기댓값으로 확장됩니다.
  • 원소별 최대: 를 볼록 집합의 모음으로 놓습니다. 그런-다음 는 볼록입니다. 의 도메인은 표현이 유한인 곳의 모음입니다. 중요한 특별한 경우:
    • 만약 이 볼록 함수이면 따라서 입니다.
    • 만약 x에서 볼록이면 는 심지어 C가 볼록 집합이 아니더라도 x에서 볼록입니다.
  • 합성:
    • 만약 fg가 볼록 함수이고 g가 일변수 도메인에 걸쳐 비-감소하는 것이면, 가 볼록입니다. 예제처럼, 만약 가 볼록이면, 따라서 인데, 왜냐하면 가 볼록이고 단조적으로 증가하는 것이기 때문입니다.
    • 만약 f가 볼록이고 g가 볼록이고 일변수 도메인에 걸쳐 비-증가하는 것이면, 가 볼록입니다.
    • 볼록성은 아핀 맵 아래에서 불면입니다: 즉, 만약 f가 도메인 을 갖는 볼록이면, 따라서 이며, 여기서 도메인 을 갖는 입니다.
  • 최소화: 만약 에서 볼록이면, x에서 볼록이며, C가 볼록 집합이고 이라는 조건으로 합니다.
  • 만약 가 볼록이면, 도메인 을 갖는 그것의 원근 은 볼록입니다.

Strongly convex functions

강한 볼록성의 개념은 엄격한 볼록성의 개념을 확장하고 매개변수화합니다. 강력하게 볼록 함수는 역시 엄격하게 볼록이지만, 그 반대는 아닙니다.

미분-가능 함수 가 만약 다음 부등식이 그것의 도메인에서 모든 점 x, y에 대해 유지되면 매개-변수 m > 0를 갖는 강한 볼록이라고 불립니다:[6]

또는, 보다 일반적으로,

여기서 는 임의의 노름(norm)입니다. 차일릿과 같은,[7] 일부 저자는 타원형(elliptic) 함수로 이 부등식을 만족시키는 함수를 참조합니다.

동등한 조건은 다음입니다:[8]

미분-가능인 함수에 대해 강하게 볼록이기 위해 미분-가능일 필요는 없습니다. 강하게 볼록 함수에 대해, 매개-변수 m을 갖는 세 번째 정의는[8] 도메인의 모든 x, y에 대해 다음인 것입니다:

이 정의는 m → 0으로 엄격한 볼록성에 대해 정의에 접근하고, m = 0일 때 볼록 함수의 정의와 동일함에 주의하십시오. 이것에도 불구하고, 함수는 임의의 m > 0에 대해 엄격하게 볼록이지만 강하게 볼록이 아닌 것이 존재합니다 (아래 예제를 참조하십시오).

만약 함수 가 두번 연속적으로 미분-가능이면, 그것이 매개-변수 m을 갖는 강하게 볼록인 것과 도메인에서 모든 x에 대해 인 것은 필요충분 조건이며, 여기서 I는 항등원이고 헤세 행렬(Hessian matrix)이고, 부등호 양의 반-한정(positive semi-definite)임을 의미합니다. 이것은 의 최소 고윳값(eigenvalue)이 모든 x에 대해 적어도 m인 것을 요구하는 것과 동등합니다. 만약 그 도메인이 단지 실수 직선이면, 가 단지 이차 도함수 이므로, 조건은 이 됩니다. 만약 m = 0이면, 이것은 헤세가 양의 반-한정임을 의미하며 (또는 만약 그 도메인이 실수 직선이면, 그것은 임을 의미하며), 이것은 그 함수가 볼록임을 의미하고, 아마도 엄격하게 볼록이지만, 강하게 볼록은 아닙니다.

여전히 함수가 두번 연속적으로 미분-가능이라고 가정하면, 우리는 의 아래쪽 경계가 엄격하게 볼록인 것을 의미하는 것으로 볼 수 있습니다. 테일러의 정리(Taylor's Theorem)를 사용하면, 다음을 만족하는

다음이 존재합니다:

그런-다음, 고윳값에 대한 정의에 의해,

그리고 따라서 우리가 위의 두 번째 강한 볼록성 방정식을 회복합니다.

함수 가 매개-변수 m을 갖는 강하게 볼록인 것과 다음 함수가 볼록인 것은 필요충분 조건입니다:

.

볼록, 엄격하게 볼록, 및 강하게 볼록 사이에 구별은 언뜻 보기에 미묘할 수 있습니다. 만약 가 두번 연속적으로 미분-가능이고 도메인이 실수 직선이면, 우리는 다음처럼 그것을 특성화할 수 있습니다:

가 볼록인 것과 모든 x에 대해 인 것은 필요충분 조건입니다.
가 만약 모든 x에 대해 이면 엄격하게 볼록입니다 (주목: 이것은 충분이지만, 필요는 아닙니다).
가 강하게 볼록인 것과 모든 x에 대해 인 것은 필요충분 조건입니다.

예를 들어, 를 엄격하게 볼록인 것으로 놓고, 를 만족하는 점 의 수열이 있음을 가정합니다. 심지어 일지라도, 함수는 강하게 볼록인데 왜냐하면 가 임의적으로 작게 될 것이기 때문입니다.

모든 에 대해 를 만족시키는 컴팩트 도메인 위에 두번 연속적으로 미분-가능 함수 는 강하게 볼록입니다. 이 명제의 증명은 극단 값 정리(extreme value theorem)로부터 따르며, 이것은 컴팩트 집합 위에 연속 함수가 최댓값 및 최솟값을 가짐을 말합니다.

강하게 볼록 함수는 일반적으로 볼록 또는 엄격하게 볼록 함수보다 다루기가 더 쉬운데, 왜냐하면 그들은 더 작은 클래스가 있기 때문입니다. 엄격하게 볼록 함수와 마찬가지로, 강하게 볼록 함수는 컴팩트 집합 위에 고유한 최솟값을 가집니다.

Uniformly convex functions

모듈러스 와 함께, 균등하게 볼록 함수는[9][10] 도메인에서 모든 x, yt ∈ [0, 1]에 대해, 다음을 만족시키는 함수 입니다:

여기서 는 비-음수 및 오직 0에서 사라지는 함수입니다. 이것은 강하게 볼록 함수의 개념의 일반화입니다; 를 취함으로써 우리는 강한 볼록성의 정의를 회복합니다.

Examples

Functions of one variable

  • 함수 를 가지므로, f는 볼록 함수입니다. 그것은 강한 볼록성 상수 2와 함께, 역시 강하게 볼록입니다 (그리고 따라서 역시 엄격하게 볼록입니다).
  • 함수 를 가지므로, f는 볼록 함수입니다. 그것은 심지어 이차 도함수가 모든 점에서 엄격하게 양수가 아닐지라도 엄격하게 볼록입니다. 그것은 강하게 볼록은 아닙니다.
  • 절댓값(absolute value) 함수 는 심지어 점 x = 0에서 도함수를 가지지 않을지라도 (삼각형 부등식(triangle inequality)에 반영된 것처럼) 볼록입니다. 그것은 엄격하게 볼록은 아닙니다.
  • 함수 에 대해 볼록입니다.
  • 지수 함수(exponential function) 는 볼록입니다. 그것은 역시 엄격하게 볼록인데, 왜냐하면 이기 때문입니다. 그러나 강하게 볼록은 아닌데, 왜냐하면 이차 도함수가 임의적으로 영에 가깝지 않기 때문입니다. 보다 일반적으로, 함수 는 만약 f가 볼록 함수이면 로그적으로 볼록(logarithmically convex)입니다. 용어 "초볼록(superconvex)"은 때때로 대신에 사용됩니다.[11]
  • 에 대해 에 의해 정의된 도메인 [0,1]을 갖는 함수 는 볼록입니다; 그것은 열린 구간 (0, 1) 위에 연속이지만, 0과 1에서 연속이 아닙니다.
  • 함수 x3는 이차 도함수 6x를 가집니다; 따라서 그것은 x ≥ 0인 집합 위에 볼록이고 x ≤ 0인 집합 위에 오목(concave)입니다.
  • 단조적으로 증가하지만 볼록이 아닌 함수의 예제는 을 포함합니다.
  • 볼록이지만 단조적으로 증가하지 않는 함수의 예제는 를 포함합니다.
  • 함수 을 가지며 만약 x > 0이면 영보다 크므로, 는 구간 위에 볼록입니다. 그것은 구간 위에 오목입니다.
  • 을 갖는 함수 는 구간 위에 볼록이고 구간 위에 볼록이지만, 구간 위에 볼록은 아닌데, 왜냐하면 x = 0에서 특이점 때문입니다.

Functions of n variables

See also

Notes

  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. ^ Altenberg, L., 2012. Resolvent positive linear operators exhibit the reduction phenomenon. Proceedings of the National Academy of Sciences, 109(10), pp.3705-3710.
  6. ^ Dimitri Bertsekas (2003). Convex Analysis and Optimization. Contributors: Angelia Nedic and Asuman E. Ozdaglar. Athena Scientific. p. 72. ISBN 9781886529458.
  7. ^ Philippe G. Ciarlet (1989). Introduction to numerical linear algebra and optimisation. Cambridge University Press. ISBN 9780521339841.
  8. ^ a b Yurii Nesterov (2004). Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers. pp. 63–64. ISBN 9781402075537.
  9. ^ C. Zalinescu (2002). Convex Analysis in General Vector Spaces. World Scientific. ISBN 9812380671.
  10. ^ 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.
  11. ^ 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.
  12. ^ Cohen, J.E., 1981. Convexity of the dominant eigenvalue of an essentially nonnegative matrix. Proceedings of the American Mathematical Society, 81(4), pp.657-658.

References

  • 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