I've tried many solutions and came up with this.
Options and selections of the dropdown are cleared using this only
$("#my-multi option:selected").prop("selected", false);
$("#my-multi option").remove();
But the interface is not updated. So you have to do this
$('#my-multi').multiselect('rebuild');
Hence, the final code is
$("#my-multi option:selected").prop("selected", false);
$("#my-multi option").remove();
$('#my-multi').multiselect('rebuild');
Suggestions and improvements are welcome.