Fundamental of Optimalizaton

Consider the optimalization problem

  • f(x):R^n \mapsto R
  • \Omega \subset R^n

$latex
Min: f(x)
$
$latex
s.t.\ x \in \Omega
$

Defination

feasible point

point satisty the constrian

feasible direction

A vector d∈R^n, d≠0, is a feasible direction at x ∈ \Omega
if there exists \alpha_0 > 0 such that x + αd ∈ \Omega for all α ∈[0,α_0]

local minimizer

  • f(x) : R^n → R is a real-valued function defined on some \Omega∈R^n .
  • A point x^∗ \in \Omega is a local minimizer of f over \Omega if f(x) ≥ f(x^∗) for all x ∈ \Omega − {x^∗} and there exist ε > 0 such that \| x−x^∗\| < ε

global minimizer

A point x^* is a global minimizer of f over \Omega if f(x) \geq f(x^∗) for all x \in \Omega−{x^∗}

convex set

A set S is convex if, for any elements x and y of S, αx+(1−α)y∈S for all 0≤α≤1 .

convex function

A function f is convex on a convex set S if for all 0 ≤ α ≤ 1 such that f(αx + (1 − α)y) ≤ α f(x) + (1 − α)f(y) and for all x, y ∈ S .

concave function

convex optimization problem

Min: f_0 (x)

s.t. \ f_i(x) ≤ 0, i = 1,...,m

a^T_i x=b_i, i=1,...,p

where f_0 , . . . , f_m are convex functions.

  • the objective function must be convex,
  • the inequality constraint functions must be convex,
  • the equality constraint functions h_i(x) = a^T_i x-b_i must be affine.

Rate of converge

  • A sequnce \{x_k\} converges to x^∗
  • A sequnce of error \{e_k=x_k-x^*\} and lim_{k \to \infty}=0

This sequence {x_k} converges to x^∗ with rate r and rate constant C if lim_{k \to \infty}=\frac{\| e_{k+1} \|}{\| e_k \|}=C and C \leq \infty .

  • superlinearly: r=1 & c=0
  • special superlinearly: 1< r < 2
  • quadratic: r=2

stationary point

A point x^∗ satisfying ∇f ( x^∗ ) = 0 is called a stationary point of f.

Procedure

check convex function-1

In the multidimensional case the Hessian matrix of second derivatives must be positive semidefinite; that is, at every point x \in S, y^T∇^2f(x)y \geq 0 for all y.

check convex function-2

Now we consider another characterization of convexity that can be applied to functions that have one continuous derivative. In this case a function f is convex over a convex set S if and only if it satisfies
f(y) ≥ f (x) + ∇f(x)^T(y − x) for all x,y ∈ S .

Theorm

Global Solutions of Convex Optimization Problems

  • Let x^∗ be a local minimizer of a convex optimization problem. Then x^∗ is also a global minimizer.
  • If the objective function is strictly convex, then x^∗ is the unique global minimizer.
    (notes: ch2 習題有函數convex證明練習)

First Order Necessary Condition

  • Let f(x)\in C^1 be a real-valued function on \Omega \subset R^n .
  • If x^* is a local minimizer of f over \Omega ,then for any feasible direction d at x^∗ , we have∇f(x^∗)^t d \geq 0 .

Corollary

  • Let f(x)\in C^1 be a real-valued function on \Omega \subset R^n .
  • If x^∗ is a local minimizer of f over \Omega \subset R^n and x^∗ is an interior point of \Omega , then ∇f(x^∗) = 0 .

Second Order Necessary Condition

  • Let f(x)∈C2 be a real-valued function on \Omega \subset R^n
  • x^∗ is a local minimizer of f over \Omega
  • d is a feasible direction at x^∗ .

If ∇f(x^∗)^t d = 0 , then d^t ∇^2f(x^∗)d \geq 0 , where ∇^2f(x^∗) is the Hessian of f at x^∗ .

Corollary

  • Let x^∗ be an interior point of \Omega \subset R^n .
  • If x^∗ is a local minimizer of f(x):\Omega → R , f ( x) ∈ C^2 , then ∇f(x^∗) = 0 and ∇^2 f(x^∗) is positive semidefinite.

Second Order Sufficient Condition

  • Let f (x)∈C2 be defined on a region in which x^∗ is an interior point.
  • Suppose that ∇f(x^∗)= 0 and ∇^2 f(x^∗) is positive definite. Then, x^∗ is a strictly local minimizer of f.****
廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

在WordPress.com寫網誌.

向上 ↑

%d 位部落客按了讚: