reduce the dinamic range ratio of the solution

[Ignacio]

Hello,

I was wondering if there is a convex way to reduce the dynamic range ratio of the absolute balue of the solution provided by YALMIP.

In a simple example as

Min x.'Ax
st     Bx<0

And reducing the ratio max(abs(x))./min(abs(x)). The vector can be positive and negative, I am interested in reduce the absolute value in a convex way.

Thanks in advance,
Ignacio

[Johan Löfberg]

What do you mean with "reduce the ration"? Do you mean that you want to penalize it in the objective, or do you have a constraint on how large it can be?

What do you mean with "I am interested in reduce the absolute value in a convex way." Do you mean that you want to have a convex reformulation of your ratio (either in a constraint or in the objective, depending on the answer of the question above)

[Ignacio]

Thanks Johan for the answer,

I am interested in reducing the difference between the maximum and the minimum value of the solution vector.

I am interested in both possibilities:
     1) Use the ratio as the function to be minimized
     2) Use the ratio as a constraint fixing a maximum value.

I said "Optimal array pattern synthesis using semidefinite programming, because the direct way that I thought to that is to impose a constraint as max(abs(x))./min(abs(x))<10 for example, but that constraint would make the problem non-convex.

Thanks

[Johan Löfberg]

The ratio is nonconvex (and nonconcave) so you will never be able to construct a convex representation of this.

Just an illustration, here are the feasible points in a 2D box with a ratio less than 2.

[X,Y] = meshgrid(-1:0.011:1);

spy(max(abs(X),abs(Y))./min(abs(X),abs(Y)) <= 2)

[Johan Löfberg]

BTW, the model as you have written it is ill-posed. If x is a solution, then so is gamma*x for any arbitrarily small gamma>0.

[Ignacio]

The example that I have posted is just an example to explain the "ratio-issue", it is not the actual problem.

The ratio is not convex, but I was wondering if  I can transform that non-convex restriction into a convex one (with a similar expression or with a relaxation). But reading your comment I figure out that is not possible.

Thanks again Johan

[Johan Löfberg]

How large is your problem? If reasonably small, it is a trivial problem to solve by mixed-integer programming (random problem n=20 is solved in a second)

[Ignacio]

As it is theoretical is relatively independent of the size, but it becomes more interestig when the problem grows ( I can work whith 20-30 variables but it would be more interesting with a few hundreds).

Either way, I will take a look at mixed-integer programming.

Thanks

[Johan Löfberg]

OK

Here is the example I tested

 n = 20;

 A = randn(n);A = A*A';

 B = randn(n/2,n);

 x = sdpvar(n,1);

 solvesdp([B*x <= -1,-10 <= x <= 10, max(abs(x))<= 2*min(abs(x))],x'*A*x)

[Ignacio]

It is very interesting.

In the example that you posted (but replacing the random matrices for fixed ones).

It is equivalent to delete the last constraint (max(abs(x))<= C*min(abs(x))) that using a huge C?

Because I do not get the same results (not even close).

I do not get better results with bigger C, and I do not understand why. I should get better results if I am allowing more degrees of freedom to the problem.

Thanks


[Johan Löfberg]

What do you mean with better? For a sufficiently large C, the constraint is redundant (for instance, if you let C be the ration for the solution obtained when you don't have the constraint at all)

You are welcome to send the model to me for further analysis if you think it behaves strangely.

[Ignacio]

Thanks again,

If you run the Example.m as it is know, it works fine and it gets a maximum difference between the vector elements of near 33.
But when I introduce the constraint, if C is bigger than 10, it says that it is infeasible, if C is less I get worse results (as I expected).

Ignacio

[Johan Löfberg]

Works fine here.

Which solver are you using

[Ignacio]

I am not selecting one, I think it is using QUADPROG. Which one should I use?
This is the message I get:

* Starting YALMIP integer branch & bound.
* Lower solver   : QUADPROG
* Upper solver   : rounder
* Max iterations : 300
 Node       Upper       Gap(%)      Lower    Open
    1 :          Inf      Inf            NaN   0  Infeasible problem
+   1 Finishing.  Cost: Inf

ans =

   NaN

[Johan Löfberg]

This is double bad. To begin with, you are using the built-in absolutely last resort integer solver bnb. Never use it if there are other alternatives available for the problem class (there are, such as gurobi, cplex, mosek, xpress)

Secondly, you don't have any good QP solver either, so YALMIP and bnb has to resort to quadprog, which is very unstable and sensitive on models generated during a branch-and-bound procedure.

Conclusion: Install a real MIQP solver.

[Ignacio]

Using gurobi works great,
Thanks!