Skip to first unread message
Shuai Lu
Jun 17, 2019, 1:30:51 AM6/17/19
to YALMIP
For a nonconvex problem, the published papers often use convex relaxation technique. The linearization is seldom used, which seems more simply. What is the reason for this?
Johan Löfberg
Jun 17, 2019, 1:38:01 AM6/17/19
to yal...@googlegroups.com
Because convex models is much more cool according to some.
It's a very valid question. Sometimes a simple heuristic based on repeated linearization, or better yet simply using a nonlinear solver, is much more relevant than spending massive efforts on deriving some conservative/approximate convex model. If you can derive a good convex approximation, that's great, but sometimes it just doesn't make sense
Shuai Lu
Jun 17, 2019, 2:42:59 AM6/17/19
to YALMIP
Hi, Johan. Thank you for your reply.
Do you know how much faster is MILP than MISOCP?
Do you know how much faster is MILP than MISOCP?
Shuai Lu
Jun 17, 2019, 2:55:03 AM6/17/19
to YALMIP
It seems that the linearization will introduce many binary variables while the convexification will not. Is it because of this?
As far as I know, the linearization or convexification both produce errors, but the errors can be reduced by sequential optimization (maybe suboptimal). So I guess perhaps the convexification is more computationally efficient than linearization? But it does not seem like that.
As far as I know, the linearization or convexification both produce errors, but the errors can be reduced by sequential optimization (maybe suboptimal). So I guess perhaps the convexification is more computationally efficient than linearization? But it does not seem like that.
Shuai Lu
Jun 17, 2019, 2:58:27 AM6/17/19
to YALMIP
Hi, Johan. Do you know what is the best method to deal with the bilinear equality constraints? linearization by sos or convexification by McCormick relaxation, or any other methods?
Johan Löfberg
Jun 17, 2019, 3:01:54 AM6/17/19
to YALMIP
For most problems much faster, for some no difference or slower. I.e. impossible to answer
Johan Löfberg
Jun 17, 2019, 3:04:04 AM6/17/19
to YALMIP
SO you are talking about MILP-based linearization. That's a completely different story. They can become completely intractable in some cases, and thus making relaxation and/or approximations the only possible attack. But still, sometimes spending effort on a convex relaxation is silly if the linearized model leads to a trivial integer program. Some people don't like integer programming (and a problem with convex relaxations is that you solve a relaxation ,i.e. you don't solve the problem you set out to solve
Johan Löfberg
Jun 17, 2019, 3:04:56 AM6/17/19
to YALMIP
A McCormick relaxation is just a relaxation, and will not solve the problem, but will have to be used inside a global solver, and global solvers are typically slower than integer solvers
Shuai Lu
Jun 17, 2019, 3:25:31 AM6/17/19
to YALMIP
Hi, Johan. I understand. Thank you very much.
Regards.
Regards.
Reply all
Reply to author
Forward
0 new messages