I have read a paper where, at some point, the following optimization problem appears: max x w T x subject to ‖ x ‖ ∞ ≤ ϵ where x and w are real vectors and ϵ is some given positive constant. The authors claim that the solution for this problem is x = sign ( w ), which seems clearly wrong to me, since then we would have ‖ x ‖ ∞ = 1.I believe the correct answer is x = ϵ sign ( w ). However, I am not being able to prove it. I have tried KKT multipliers, with no success. Any ideas?

Question

I have read a paper where, at some point, the following optimization problem appears:                                            max          x                          w          T                x                                  subject to                               ‖            x            ‖                                ∞                          ≤        ϵ            where   x and   w are real vectors and   ϵ is some given positive constant. The authors claim that the solution for this problem is   x  =  sign  (  w  ), which seems clearly wrong to me, since then we would have             ‖      x      ‖              ∞        =  1.I believe the correct answer is   x  =  ϵ    sign  (  w  ). However, I am not being able to prove it. I have tried KKT multipliers, with no success. Any ideas?

graffus1hb30 · Accepted Answer

The       ℓ    1   and       ℓ    ∞   norms are duals of each order in the sense that   ‖  w      ‖    1    =      max          ‖      x              ‖        ∞            ≤      1            w    T    x. Thus for any   ϵ  &amp;gt;  0, by an trivial change of variable, you have      max          ‖      x              ‖        ∞            ≤      ϵ            w    T    x  =  ϵ  ‖  w      ‖    1    .Taking   x  =  ϵ  sign  ⁡  (  w  ), clearly attains this maximum, since   ⟨  ϵ  sign  ⁡  (  w  )  ,  w  ⟩  =  ϵ      ∑          i            |        w    i        |    :=  ϵ  ‖  w      ‖    1  . Conclude.

kwisangqaquqw3 · Accepted Answer

Hints:1. What is the relation between infinity norm and the largest absolute value among the entries for a vector? From this, can you convince your self that   0  ≤      |        x    i        |    ≤  ϵ?2. Convince yourself about the sum                              w          1                          x          1                         +                 …                 +                           w          n                          x          n                                    =                  ∑                      i            ,                          w              i                        ≥            0                                    |                          w          i                          |                          x          i                         −                           ∑                      i            ,                          w              i                        &amp;lt;            0                                    |                          w          i                          |                          x          i                    3. Given above two, can you figure out the values for       x    i   that will maximize your dot product?Update: OP asked for using KKT multipliersConvince yourself that each constraint   0  ≤      |        x    i        |    ≤  ϵ is equivalent to the linear constraints       x    i    ≥  −  ϵ and       x    i    ≤  ϵ. Now your optimization problem is a linear program. Thus KKT conditions are necessary and sufficient. Can you prove the result you require now?

I have read a paper where, at some point, the following optimization problem appears: <mtable

Answered question

Answer & Explanation

New Questions in High school geometry