Register to reply

Minimizing infinity norm squared

by farooq117
Tags: infinity, minimizing, norm, squared
Share this thread:
farooq117
#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
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
grey_earl
#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
#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
#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
#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
#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
#7
Jun7-11, 10:03 AM
P: 6
thanks..
Ray Vickson
#8
Jun7-11, 11:39 AM
Sci Advisor
HW Helper
Thanks
P: 4,959
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
#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