Solving quadratic optimization problem(QP)

[wang lingyi]

Hi guys,

I am solving a quadratic programming problem, and  there are some optimization variables which only appear in constraints but doesn't appear in objective function. Attached below is a small example in which the optimization variable 'a'  does not enter objective function and is unbounded. I use mosek within yalmip on matlab to solve this problem, and the optimal solution of 'x' is (0.5,0.5)^T as expected, and the solution of 'a' is also (0.5,0.5) (which I get the value of 'a' by using  the command 'double(a)'). Since 'a' does not enter objective function, the problem I define in Yalmip is actually not in the form of a standard QP problem as seen in the second Figure attached. So, my question is 

(1) how the solver identifies those optimization problems that are not standard defined? 

(2) how the solver deal with those optimization variables that does not enter objective function but appear in constraints? Is it possible that for those variables, the solver just pick a random value within the feasible set and fixing this random value, search for the optimum of objective function?   Why the value of 'a' (double(a)) in  my numerical example is (0.5,0.5)^T, how does this value be obtained since it is unbounded.

 (3) What are the factors that affects the computation time of solving QP algorithm in mosek other than the number of constraints and optimization variables? And does the computation time linearly grow with the number of constraints and exponentially grow with the number of optimization variables? If I want to reduce computation, I should reduce the number of variables or the number of constraints firstly.

Thank you very much for any advice~

[Michal Adamaszek]

Hi,

The problem is a standard QP (it is rather normal that not all variables appear in quadratic terms). The solution you get is feasible. A solution with a=(10,20)^T would be just as good, there is no guarantee as to which point of the optimal set you will get. In this simple case most likely presolve identifies these bounds as redundant and then assigns to a the first good value. Try to disable presolve and maybe you get a different feasible point. But I don't think these details should be very important.

The practical factors affecting computation time are sparsity and good conditioning, keeping the problem nicely scaled etc. The number of variables/constraints are somehow related to that of course, but they are not of primary importance.  In any case you should not struggle to decrease the dimensions by all costs. Better use the energy on having a nice model. See https://docs.mosek.com/latest/toolbox/debugging-numerical.html or https://docs.mosek.com/latest/faq/faq.html#mosek-is-not-solving-my-quadratic-optimization-problem-fast-enough-what-should-i-do 

Best,

Michal