Minimizing infinity norm squared


by farooq117
Tags: infinity, minimizing, norm, squared
farooq117
farooq117 is offline
#1
Jun6-11, 03:43 AM
P: 6
I have to minimize an expression of the following type:

min <a,x>-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.
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
grey_earl
grey_earl is offline
#2
Jun6-11, 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 ...
farooq117
farooq117 is offline
#3
Jun7-11, 05:10 AM
P: 6
well.. the actual problem is to find the argument which maximizes the following expression:

<a,x> - (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.

farooq117
farooq117 is offline
#4
Jun7-11, 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)||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 - <a,x> s.t.: x >= 0, ||x||_inf <= R.

I use the following trick:

min t
s.t.: (L/2)||x-u||_inf^2 - <a,x> <= t,
x >= 0, ||x_inf|| <= R.

And write this as follows:

min t
s.t. (L/2)(xi-ui)^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?
farooq117
farooq117 is offline
#5
Jun7-11, 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)||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 - <a,x> 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..
grey_earl
grey_earl is offline
#6
Jun7-11, 09:05 AM
P: 170
Hey, sorry for not answering earlier ... I live in a different timezone :)

Quote Quote by farooq117 View Post
i have an approach in mind.. i thought i'd get your opinion on it..

min t
s.t. (L/2)(xi-ui)^2 - <a,x> <= 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 ...
farooq117
farooq117 is offline
#7
Jun7-11, 10:03 AM
P: 6
thanks..
Ray Vickson
Ray Vickson is offline
#8
Jun7-11, 11:39 AM
HW Helper
Thanks
P: 4,670
Quote Quote by farooq117 View Post
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)||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 - <a,x> 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
farooq117
farooq117 is offline
#9
Jun7-11, 05:12 PM
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..


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