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$.

### 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.****