Minimizing infinity norm squared

by farooq117
Tags: infinity, minimizing, norm, squared
 P: 6 I have to minimize an expression of the following type: min -L||x-u||_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 ||x-u||_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.
 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 ...
 P: 6 well.. the actual problem is to find the argument which maximizes the following expression: - (L/2)||x-u||_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 ||Ax-b||_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.
 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: - (L/2)||x-u||_inf^2 s.t.: x >= 0, ||x||_inf <= R. The is the same as finding the minimum of (L/2)||x-u||_inf^2 - s.t.: x >= 0, ||x||_inf <= R. I use the following trick: min t s.t.: (L/2)||x-u||_inf^2 - <= t, x >= 0, ||x_inf|| <= R. And write this as follows: min t s.t. (L/2)(xi-ui)^2 - <= 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?
 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 - (L/2)||x-u||_inf^2 s.t.: x >= 0, ||x||_inf <= R. this is the same as finding the minimum of (L/2)||x-u||_inf^2 - s.t.: x >= 0, ||x||_inf <= R. I express this as follows: min t0^2 + t1 + t2 + ... + tm s.t.: (L/2)||x-u||_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..
P: 170
Hey, sorry for not answering earlier ... I live in a different timezone :)

 Quote by farooq117 i have an approach in mind.. i thought i'd get your opinion on it.. min t s.t. (L/2)(xi-ui)^2 - <= t^2, for all i = 1,...,m x >= 0, ||x||_inf <= R.
Of course, in the second line you can write
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 ...
 P: 6 thanks..
HW Helper
Thanks
P: 5,193
 Quote by farooq117 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 - (L/2)||x-u||_inf^2 s.t.: x >= 0, ||x||_inf <= R. this is the same as finding the minimum of (L/2)||x-u||_inf^2 - s.t.: x >= 0, ||x||_inf <= R. I express this as follows: min t0^2 + t1 + t2 + ... + tm s.t.: (L/2)||x-u||_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..
You want to minimize M*||x-u||^2 - <a,x>, s.t. ||x|| <= R. Here, M = L/2 and || . || = sup-norm. This can be re-written as
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* ||x-u||^2; if, instead, you wanted to maximize the objective M*||x-u||^2 - <a,x> you would have a problem with a mixed continuous-combinatorial aspect to it, and formulation/solution would be difficult.

RGV
P: 6
 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.
in fact, in my case, a quadratic programming package isnt really an option.. the problem that i described is one sub-problem in one iteration of a gradient-based algorithm for distributed optimization.. if there is a centralized optimizer, then perhaps it can use such a quadratic programming package.. but a centralized optimizer isnt allowed..

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 sub-problem in a larger algorithm requiring many iterations..

 Related Discussions Linear & Abstract Algebra 9 Calculus 6 Calculus & Beyond Homework 7 Calculus & Beyond Homework 2