Find a rectangular box with maximum volume inside a 3D zonotop

[Thịnh Nguyễn]

Dear all,

I am trying to solve a problem which is to find a rectangular box with maximum volume inside a 3D polytop

I have implemented a problem as follow:

1) Describe the polytop AX<=b (X is a 3-dimensional vector)

2) Define a sdpvar as [Xmin,Xmax,Ymin,Ymax,Zmin,Zmax]

3) Impose the constraints as follow:

- [Xmin<=Xmax,Ymin<=Ymax,Zmin<=Zmax]

- [A[Xmin;Ymin;Zmin]<=b,A[Xmin;Ymin;Zmax]<=b,A[Xmin;Ymax;Zmin]<=b,A[Xmin;Ymax;Zmax]<=b,....] (similarly for Xmax)

4) Describe the objective function as: J=-(Xmax-Xmin)(Ymax-Ymin)(Zmax-Zmin). (maximize the volume of the box)

5) Run yalmip and let it choose automatically the solver (I have cplex).

The algorithm works well for the similar 2-D problem but with the proposed 3-D problem, Yalmip gives the answer that:

============================================================================================

Initial point is a local minimum that satisfies the constraints.

Optimization completed because at the initial point, the objective function is non-decreasing  

in feasible directions to within the selected value of the function tolerance, and 

constraints are satisfied to within the selected value of the constraint tolerance.

============================================================================================

And the result contains all zero. 

Is there any one has experience in the similar problem with me? Can you give me some direction?

All the best,

Thinh.

[Johan Löfberg]

With that objective, you're definitely not using cplex. My guess is that fmincon is used. It is a nonconvex problem, and the solver has simply terminated prematurely

Sounds like a well-established classical problem, and my guess is that there are much better methods than trying to attack it using nonlinear nonconvex programming. I would not be surpised if the general n-D problem is computationally intractable (just a hunch though)

[Mark L. Stone]

Try a non-default starting value for the nonlinear optimizer.  

assign the starting value and put 'usex0',1 in sdpsettings.

The vector of zeros is the default starting value, and it is not a good starting value for your problem.

[Johan Löfberg]

Instead of parameterizing the bo in terms of corners, parameterize in terms of center and width. With that, you get a variant of a Chebyshev ball problem. Instead of maximizing the product, maximize the log of the product, which is convex

YALMIP can derive the problem automatically by posing it as a robust optimization problem.

A = randn(10,2);

b = rand(10,1)*5;

x = sdpvar(2,1);

clf

plot(A*x <= b)

% Width of box

r = sdpvar(2,1);

% Center of box

xc = sdpvar(2,1);

% Uncertainty to span box

z = sdpvar(2,1);

Model = [A*(xc + r.*z) <= b, uncertain(z), -1 <= z <= 1];

Model = robustmodel(Model)

optimize(Model,-sum(log(r)))

hold on;

plot(-value(r) <= z-value(xc) <= value(r),[],'yellow')

[Thịnh Nguyễn]

Thank you so much for your suggestions. 

However, I can not run this line 

"Model = robustmodel(Model)"

Can you tell me which toolbox I am lacking of?

[Thịnh Nguyễn]

Thank you. I will look for assigning the starting value. 

[Johan Löfberg]

You're using an old version of YALMIP

[Johan Löfberg]

command robustify should work also as an alternative

[Thịnh Nguyễn]

Thank you. I can run the code. I am studying it. 

[Thịnh Nguyễn]

Thank you very much. In fact, I didn't expect to be possible to solve the problem as soon as we have done. 

All my best wishes for you and your work.