1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Numerical Optimization ( norm minim)

  1. Apr 16, 2010 #1
    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. jcsd
  3. Apr 17, 2010 #2


    User Avatar
    Homework Helper

    consider the set [itex] \left\{ x \in \mathbb{R}^n : ||x||^2 = c\} [/itex] 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
  4. Apr 17, 2010 #3


    User Avatar
    Homework Helper

    hint: think tangents & normals
  5. Apr 17, 2010 #4
    Here is my work:

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

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


    x = - \alpha[/tex] a / ||a||^2
  6. Apr 17, 2010 #5


    User Avatar
    Homework Helper

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook