Convex quadratic problem solver gives different answers?

Question

I am pretty sure that the following variance objective function should be a convex quadratic problem. My objective function is as follows:

$$ \text{argmin } \text{var }(X*L) \xi \geq 1, \text{ where } \xi \text{ are integers} $$

$\xi$ are random variables, $1 \leq i \leq 1000$ and elements of vector $X$. $L$ is a $1000\times20$ known matrix.

I tried to solve this problem with fmincon and by thresholding the final variables. However each time I run the algorithm with a different initial point, I get a different answer. The step size and tolFun are 1e-100.

Could you shed light on the problem for me?

Answer 1

You can formulate and solve this using YALMIP under MATLAB. You can download YALMIP for free http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.Download . YALMIP will do the dirty work for you. Install YALMIP, run yalmiptest to test installation, read http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics .

I generated L= rand(1000,20) and solved the following problem in under 3 sec when YALMIP selected cplex by default as the solver. It also solved it in under 3 sec using scip. These times are if I don't impose a constraint X >= 1 (see next paragraph, because I am confused as to what your optimization problem actually is).

However, and this is an important point, the problem as you have stated it always has an optimal objective value = 0, which is achieved with X = all zeros. So you need some other constraint on X or a different formulation in order to have a non-trivial problem. If you do that, it is possible that the run time could go up considerably. I have been ignoring ξ >= 1; I don't know what your problem is. I have assumed that X is a vector of the optimization (decision) variables. So you need to fix up the problem. Clearly state the objective and what the decision variables are, and what the problem inputs are. I don't know what ξ is or how it enters the objective function. O.k., here's my guess: you mean that all elements of X are >= 1. is that correct? If so, this will take a long time to run.

n = size(L,1);
X = intvar(n,1) % declares X to be an n by 1 vector of integer variables
sol = optimize([X >= 1],var(X'*L))

If you want to specify a particular solver, such as scip, rather than letting YALMIP pick what it thinks is best from among the installed solvers, use

sol = optimize([X >= 1],var(X'*L),sdpsettings('solver','scip'))

If there are any other constraints, put them inside the [] , separated by , or ;

After the problem has been solved, the optimal argument value (i.e., argmin) is obtained with

value(X)

This is being solved as a Mixed Integer QP. YALMIP is putting it into the form needed by the solver.

By the way, I believe FMINCON will ignore tolerance of 1e-100; it just can't handle that, so it will use what "it wants to".

Answer 2

In addition to the problems mentioned by the commenters above, let me comment on a few peculiar aspects of your problem:

arg min var(sum(L) + X*L) xi>=0

where xi s are random variables and elements of vector X and sum(L) is a vector which is constituted of sum of the elements in each column of L separately.

As hardmath points out, adding to $X$ any matrix whose columns are in the left nullspace of $L$ will result in an equivalent objective function value. Bilinear products of variables can indicate nonconvexity as well. Like the other commenters, I can't understand your formulation. However, if it is nonconvex, that would explain why different initial points yield different solutions.

vector X is constituted of 1000 variables and they all should be positive integers. L is a 1000*20 known matrix.

I tried to solve this problem with fmincon and round the final variables.

Do you want integer-feasible solutions or integer-optimal solutions? The latter requires mixed-integer programming, and will be more expensive. Also, fmincon won't work. In either case, rounding could also account for not obtaining the same solution every time, in pathological cases.

I tried to solve this problem with fmincon and round the final variables. However each time I run the algorithm with a different initial point,I get a different answer the step size and tolFun are 1e-100.

Setting the tolerance on function evaluations to $10^{-100}$ is probably overkill unless you expect your function evaluations to be somewhere around $10^{-90}$ or so. Convex optimization algorithms return (local) $\varepsilon$-optimal solutions for some tolerance $\varepsilon$. These algorithms will return the first iterate satisfying the termination tolerance criteria, so it could be that different initial guesses result in sequences of iterates that both satisfy the termination tolerances, just at different points in the feasible set. For instance, it could also be that the problem has multiple (local) minima, which can occur even in the convex case when the function is "flat" at the bottom. Again, hardmath's observation suggest that something like this situation might occur.