Register to reply 
Minimizing infinity norm squared 
Share this thread: 
#1
Jun611, 03:43 AM

P: 6

I have to minimize an expression of the following type:
min <a,x>Lxu_inf^2 s.t.: x_inf <= R, where a is a vector of coefficients, x is the vector of decision variables, <.,.> denotes the scalar product, R and L are scalars, u is some constant (known) vector, and 'inf' denotes the infinity norm. I know how to deal with the situation where the expression is of the type xu_inf. But, I do not know how to approach the expression when the infinity norm is squared. I hope someone out there can suggest some ideas, or a book that I can consult, etc. 


#2
Jun611, 12:34 PM

P: 170

A hint that might be useful: if x_inf <= R, then x_inf^2 <= R^2. You should then be able to proceed just as in your other case. If not, you need to show us more ...



#3
Jun711, 05:10 AM

P: 6

well.. the actual problem is to find the argument which maximizes the following expression:
<a,x>  (L/2)xu_inf^2, s.t.: x >= 0, x_inf <= R, where a and u are known vectors, x is the vector of decision variables, and R and L are known scalars. Furthermore, the vector u satisfies the following: u >= 0, u_inf <= R. I know of a simple trick for dealing with the minimization of an expression of the form Axb_inf. But I cannot figure out how to approach the situation where the infinity norm expression is squared and where the scalar product adds a linear term as well. 


#4
Jun711, 05:54 AM

P: 6

Minimizing infinity norm squared
i have an approach in mind.. i thought i'd get your opinion on it..
the problem is to find the maximum of the following: <a,x>  (L/2)xu_inf^2 s.t.: x >= 0, x_inf <= R. The is the same as finding the minimum of (L/2)xu_inf^2  <a,x> s.t.: x >= 0, x_inf <= R. I use the following trick: min t s.t.: (L/2)xu_inf^2  <a,x> <= t, x >= 0, x_inf <= R. And write this as follows: min t s.t. (L/2)(xiui)^2  <a,x> <= t^2, for all i = 1,...,m x >= 0, x_inf <= R. This gives me a quadratic cost with quadratic and linear constraints. And the constraints are coupled. Do you think that a) the above is correct; and b) if it's possible to have a formulation where the constraints are linear or uncoupled? 


#5
Jun711, 06:47 AM

P: 6

there is another approach.. this gives a quadratic cost with coupled linear constraints.. i'd be very grateful if you could check the working..
the problem is to find the maximum of <a,x>  (L/2)xu_inf^2 s.t.: x >= 0, x_inf <= R. this is the same as finding the minimum of (L/2)xu_inf^2  <a,x> s.t.: x >= 0, x_inf <= R. I express this as follows: min t0^2 + t1 + t2 + ... + tm s.t.: (L/2)xu_inf^2 <= t0^2, ai*xi <= ti, i = 1,...,m, x >= 0, x_inf <= R. I express the first constraint as follows: (L/2)(xi  ui)^2 <= t0^2, i = 1,...,m. I express these constraints as follows: ui  sqrt(2/L)*t0 <= xi <= ui + sqrt(2/L)*t0, i = 1,...,m. The optimization problem is given by: min t0^2 + t1 + ... + tm s.t.: xi  sqrt(2/L)*t0 <=  ui, i = 1,...,m xi  sqrt(2/L)*t0 <= ui, i = 1,...,m ai*xi ti <= 0, i = 1,...,m 0 <= xi <= R, i = 1,...,m i don't think i can uncouple the constraints somehow.. 


#6
Jun711, 09:05 AM

P: 170

Hey, sorry for not answering earlier ... I live in a different timezone :)
s.t. 0 <= x_i <= R for all i as you did in your other example. The calculation you did seems fine to me, but I don't know either how to uncouple your constraints ... 


#7
Jun711, 10:03 AM

P: 6

thanks..



#8
Jun711, 11:39 AM

Sci Advisor
HW Helper
Thanks
P: 5,030

min M*z^2  <a,x> s.t. z >= x(i)u(i), z >= u(i)x(i) for all i R <= x(i) <= R for all i. This has just one single quadratic term in the objective, but is otherwise linear. Somehow, one feels there must be a better way to solve it than using a standard quadratic programming package, although that would certainly work in this case, because we have a convex quadratic programming problem. This only works because we are *minimizing* xu^2; if, instead, you wanted to maximize the objective M*xu^2  <a,x> you would have a problem with a mixed continuouscombinatorial aspect to it, and formulation/solution would be difficult. RGV 


#9
Jun711, 05:12 PM

P: 6

perhaps, relaxing the coupling constraints using Lagrange multipliers could be an alternative to a quadratic programming package.. but i doubt the efficacy of such an approach.. it may still require global coordination.. moreover, it may be too slow for what is essentially one subproblem in a larger algorithm requiring many iterations.. 


Register to reply 
Related Discussions  
Squared norm in Clifford Algebras  Linear & Abstract Algebra  9  
L2 norm = +Infinity  Calculus  6  
Infinity norm  Calculus & Beyond Homework  7  
Distance of infinity norm  Calculus & Beyond Homework  2 