最適化

最適化問題 †

最適化問題は、一般に次のように定式化される。

min　f(x) xはベクトル
gi(x) = 0 i = 1, . . . ,me
gi(x) < 0 i = me + 1, . . . ,m
xl < x < xu

• 制約式のない場合は、制約のない最適化問題とよぶ

The general optimization problem has the form:

min　f(x)

subject to:

gi(x) = 0 i = 1, . . . ,me
gi(x) < 0 i = me + 1, . . . ,m
xl < x < xu

In particular, if m = 0, the problem is called an unconstrained optimization problem.

解とアルゴリズムの基本的性質：Basic Properties of Solutions and Algorithms †

ミニマム点の定義

• Definition:A point x* is said to be a relative minimum point or a local minimum point of f if there is an ε > 0 such that f(x*) =< f(x) for all x such that　||x-x*||<ε. If the inequality is strict for all x ><x* then　x* is said to be a strict relative minimum point.
• Definition: A point x* is said to be a global minimum point of f if f(x*) < f(x) for all x . If the inequality is strict for all x without x* then x* is said to be a strict global minimum point.

定理１：1次元の最少値の必要条件　First-order necessary conditions †

fがスカラー関数の場合、もしx*がローカルに最少であるならば、任意のベクトルｄに対して内積f'(x*)・dが正または０である。

• Let f in C1. If x* is a relative minimum, then for any vector d which is feasible at x*, we have f'(x)d >= 0. (f'(x) is the gradient, i.e. the vector of partial derivatives of f at x.)
• f'(x)は勾配ベクトル

[証明] h(t) = f(x* + td)をテーラー展開すると

h(t) = h(0) + t・h'(0) +o(t)

となる。t=０がミニマム値であるから任意のtに対してt・h'(0)>=である。

By a one-sided Taylor expansion of the function h(t) = f(x* + td), which is defined in the interval [0, α], we obtain that h(t) = h(0) + t・h'(0) +o(t). Since 0 is a relative minimum of h we obtain that th'(0) >= 0, for all　t small enough, which implies that h'(0) >= 0. The claim now follows from the chain rule.

補題 †

もしx*が最少の極値を与えるならば、f'(x*) = 0が成り立つ。

If x* is a local minimum then f'(x*) = 0.

勾配：ベクトル †

The gradient of f is defined to be the vector field whose components are the partial derivatives of f. That is:

Here the gradient is written as a row vector, but it is often taken to be a column vector.

例題 †

Example: Consider the function f(x, y) = x2 −xy +y2 −3y. From the first order conditions we get that x* = 1 and y*= 2. This is a global minimum. (Why?)