Exercise 8.16

Answers

(a)

(8.30) minimizes w.r.t.

w, b, ξ

, so the optimization variable is

u = [\begin{matrix} b \\ w \\ ξ \end{matrix}] .

(b)

There are

N

constraints for

y_{n} (w^{T} x_{n} + b) \geq 1 - ξ_{n}

, and

N

constraints for

ξ \geq 0

. It’s easy to see that RHS has

c = [\begin{matrix} 1_{N} \\ 0_{N} \end{matrix}]

On the LHS, $A = [\begin{matrix} Y X & I_{N} \\ 0_{N \times (d + 1)} & I_{N} \end{matrix}]$ where

Y X = [\begin{matrix} y_{1} & y_{1} x_{1}^{T} \\ \dots & \dots \\ y_{n} & y_{n} x_{n}^{T} \\ \dots & \dots \\ y_{N} & y_{N} x_{N}^{T} \end{matrix}]

as in exercise 8.4

The $p^{T} u$ term is $C \sum ξ_{n}$ , so we have

p = [\begin{matrix} 0_{(d + 1) \times 1} \\ C_{N \times 1} \end{matrix}] .

And finally the

Q = [\begin{matrix} 0 & 0_{d}^{T} & 0_{N}^{T} \\ 0_{d} & I_{d} & 0_{d \times N} \\ 0_{N} & 0_{N \times d} & 0_{N \times N} \end{matrix}]

with some work.

(c)

Once we have

u^{∗}

, then

b^{∗} = u_{0}^{∗}, w^{∗} = u_{1 : d + 1}^{∗}, ξ^{∗} = u_{d + 2 : d + 1 + N}^{∗} .

(d)

Any point with

ξ_{n} > 0

violates the margin. The points with

y_{n} (w^{T} x_{n} + b) = 1

are on the margin, and the points with

y_{n} (w^{T} x_{n} + b) > 1

are correctly separated and outside the margin.

niuers

2021-12-08 10:17