或る大学院生のメモ帳: Optimization

Let f (x) be a twice differentiable function in n variables defined on an open convex set S. Then we have:

1. f''(x) is positive semidefinite for all x ∈ S ⇔ f is convex in S
2. f''(x) is negative semidefinite for all x ∈ S ⇔ f is concave in S
3. f''(x) is positive definite for all x ∈ S ⇔ f is strictly convex in S
4. f''(x) is negative definite for all x ∈ S ⇔ f is strictly concave in S

http://home.bi.no/a0710194/Teaching/BI-Mathematics/GRA-6035/2010/lecture5-hand.pdf

Extremum Value Theorem

If an objective function is continuous and its domain is compact, there exists the global max and min points.

http://en.wikipedia.org/wiki/Extreme_value_theorem

2012年3月21日水曜日

Bellman Principle of Optimality

An optimal policy has the property that, whatever the initial state and decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

2012年3月19日月曜日

Minimization/ Maximization Necessary Conditions

1. Minimization Problem

If f(x) is quasiconvex, gi(x) is quasiconvex and hj(x) is affine (linear), then the necessary conditions are also sufficient conditions.

2. Maximization Problem

If f(x) is quasiconcave, gi(x) is quasiconvex and hj(x) is affine (linear), then the necessary conditions are also sufficient conditions.

objective function: f(x)
inequality constraints: gi(x)≦0
equality constraints: hj(x)=0

符号に注意!!

http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions

http://en.wikipedia.org/wiki/Convex_optimization

Concave is Negative Convex

A function f(x) is concave over a convex set if and only if the function −f(x) is a convex function over the set.

http://en.wikipedia.org/wiki/Concave_function

Concave/ Quasi-Concave

1. A (strictly) concave function is (strictly) quasi-concave.

2. A (strictly) convex function is (strictly) quasi-convex.

3. A linear function is both concave and convex.

Source:
https://files.nyu.edu/caw1/public/UMath/Handouts/ums11h22convexsetsandfunctions.pdf

Properties of Convex Functions

1. Positive multiple of convex function is convex

2. Sum of convex functions is convex

...

Source:
www.ee.ucla.edu/ee236b/lectures/functions.pdf

登録: 投稿 (Atom)