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