# Homework Help: Numerical Optimization ( norm minim)

1. Apr 16, 2010

### sbashrawi

1. The problem statement, all variables and given/known data

Consider the half space defined by H = {x ∈ IRn | aT x +alpha ≥ 0} where a ∈ IRn
and alpha ∈ IR are given. Formulate and solve the optimization problem for finding the point
x in H that has the smallest Euclidean norm.

2. Relevant equations

3. The attempt at a solution
I need help in this problem. I think the problem can be written as

min ||x|| sunbjected to a(transpose) x + a >= 0

am I right

2. Apr 17, 2010

### lanedance

consider the set $\left\{ x \in \mathbb{R}^n : ||x||^2 = c\}$ for some constant c, geometrically what does it represent?

now consider the half space, the boundary of which is a plane. how does the plane intersect the above set, in particular for the minimum value of c. This should lead to a simple solution

3. Apr 17, 2010

### lanedance

hint: think tangents & normals

4. Apr 17, 2010

### sbashrawi

Here is my work:

f(x) = ||x|| ^2
subjeted to c(x) = a^{T} x +$$\alpha$$$$\geq$$0

so L ( x,$$\lambda$$) = f(x) - $$\lambda$$ c(x)
gradiant L(x,$$\lambda$$) = 2x - $$\lambda$$ grad(c(x)) = 0
so 2x - $$\lambda$$a = 0
this gives that x = $$\frac{}{}[1/2]\lambda$$a
and
c(x) = 0
gives : $$\lambda$$ = -2 $$\alpha$$$$/ ||a||^2 imlpies x = - \alpha$$ a / ||a||^2

5. Apr 17, 2010

### lanedance

Lagrange multipliers ok,, though bit hard to read what is a vector

the answer makes sense to me as the boundary plane will have a as its normal, and the answer is both on the boundary plane & parallel to a