How to minimize the maximum of a vector

[Zdai]

Hello,

I am using your awesome toolbox to solve QPQC problems. Right now, I am dreaming to minimize the maximum of a vector instead of a scalar. Do you have an idea on how I might achieve this goal?

Also, thank you very much to have made my life easier by creating this Toolbox!

Have a nice day,
Zdai

[Johan Löfberg]

If you want to minimize the maximum of [a b c d] you simply introduce a new variable t, add the constraints [a b c d] <= t, and then you minimize t. Toolboxes such as cvx and yalmip (interfaced to opti) do this modelling automatically for you

[Zdai]

Thank you very much for this clear explaination. I am going to try it!

On Monday, August 25, 2014 6:59:02 PM UTC+2, Zdai wrote:

[Gael]

Hi again,

After trying to find out how to do that, I think that I am completly lost :)

When you said "add the constraints [a b c d]<= t" what does that means? Is "t" a scallar or a vector? And how can we minimize t if it has nothing to do with our solution vector x?

Thank you for your help,
Gael

[Johan Löfberg]

So normalized variables names then: If your decision variables are x in R^4 and you want to minimize the maximum of this vector, you introduce a new variable so you have 5 variables instead, and add the constraints x(1)<= x(5), x(2) <= x(5) ...., and then you minimize x(5)

If it still is complicated, I would recommend you to use a modelling language to do all this for you. YALMIP hooks up directly to the solvers in OPTI if you want to use those solvers.

[Jonathan Currie]

Hi Gael,

 

I completely agree with Johan, if you find adding the constraint below complicated then use YALMIP. It will do all the hard work for you!

 

YALMIP is free and open-source, find it online.

 

Jonathan

--
You received this message because you are subscribed to the Google Groups "OPTI Toolbox Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opti-toolbox-fo...@googlegroups.com.
To post to this group, send email to opti-tool...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gael]

Hi,

well, I think that I'am missing the point because we are speaking about 2 different problem.

Using the notation described here:
http://www.i2c2.aut.ac.nz/Wiki/OPTI/index.php/Probs/LP
http://www.i2c2.aut.ac.nz/Wiki/OPTI/index.php/Probs/QP

I would like to:
min_x maximum( H x)
with H a m*n matrix
and x a n*1 vector, here called decision variable.

If this is what you describe, can you linked an example of OPTI or YALMIP which describe it (even one not that much related)?

Thank you very much,
Gael

To unsubscribe from this group and stop receiving emails from it, send an email to opti-toolbox-forum+unsub...@googlegroups.com.

[Johan Löfberg]

So minimize x(n+1) subject to H*x(1:n) <= ones(m,1)*x(n+1), i.e, [H -ones(m,1)]*x <= 0

In YALMIP

x = sdpvar(n,1);
Objective = max(H*x);
Constraints = [some constraints since the problem is unbounded otherwise]
solvesdp(Constraints,Objective)

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics

[Gael]

Ok, I succed in using YALMIP to redo my QP problems, and I'm trying the make the new one (minimizing max(H*x) and max( sqrt( (E1a*x+E2a*x)^2+(E1b*x+E2b*x)^2+(E1c*x+E2c*x)^2 ) )) working. Still not working, but I will read more and try to find some solution :)

Thank you for your help!

[Johan Löfberg]

Are you saying you want to maximize a function involving convex quadratic function? I hope you are aware that it is a very very hard problem.

The sqrt operator in YALMIP is limited to scenarios where it can be implemented using an SOCP representation. Since you have nonconvex stuff, you don't have any solver which can mix the SOCP cone and nonconvex stuff. This is easily fixed though by using the sqrtm operator instead. With this, you allow YALMIP to model it directly as the square root (i.e., a callback in the solver) and thus simply use a nonlinear solver. No guarantees that you will find any solution though as it is a nonconvex problem (you could always thy the global solver bmibnb if the problem is small enough)

BTW, you are welcome over to the YALMIP google groups instead for further discussion (not to pollute OPTI support forum with YALMIP issues)

[Gael]

Ok, I continue the discussion over there: https://groups.google.com/d/msg/yalmip/30OpFDOs9o4/QuHXt8qORI8J

Thank you for your help!

On Friday, September 5, 2014 5:37:29 PM UTC+2, Johan Löfberg wrote:

Are you saying you want to maximize a function involving convex quadratic function? I hope you are aware that it is a very very hard problem.

The sqrt operator in YALMIP is limited to scenarios where it can be implemented using an SOCP representation. Since you have nonconvex stuff, you don't have any solver which can mix the SOCP cone and nonconvex stuff. This is easily fixed though by using the sqrtm operator instead. With this, you allow YALMIP to model it directly as the square root (i.e., a callback in the solver) and thus simply use a nonlinear solver. No guarantees that you will find any solution though as it is a nonconvex problem (you could always thy the global solver bmibnb if the problem is small enough)

BTW, you are welcome over to the YALMIP google groups instead for further discussion (not to pollute OPTI support forum with YALMIP issues)

On Friday, September 5, 2014 4:12:13 PM UTC+2, Gael wrote:

Ok, I succed in using YALMIP to redo my QP problems, and I'm trying the make the new one (minimizing max(H*x) and max( sqrt( (E1a*x+E2a*x)^2+(E1b*x+E2b*x)^2+(E1c*x+E2c*x)^2 ) )) working. Still not working, but I will read more and try to find some solution :)

Thank you for your help!

On Wednesday, September 3, 2014 12:22:37 PM UTC+2, Johan Löfberg wrote: