Minimizing infinity norm squared

farooq117

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.

grey_earl

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

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

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

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

Hey, sorry for not answering earlier ... I live in a different timezone :)

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

thanks..

Ray Vickson

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

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..