0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If $X$ is simply variables that you control, there will be more than one choice of variables that gives minimum variance. In multiplying $X*L$, the left nullspace of $L$ provides variations in $X$ that do not affect the final evaluation. $\endgroup$ – hardmath Jun 4 '15 at 12:06
  • $\begingroup$ Same confusion here. Please write your opt formula clearly. You have capital X and small x. Is x>0 a constraint? Are you sure it is not x>=0? var(constant + x) = var(x), why is sum(L) here? $\endgroup$ – jf328 Jun 5 '15 at 11:54
  • $\begingroup$ Thank you for your comments. I made some changes hope it's clarified now. $\endgroup$ – sarah daneshvar Jun 10 '15 at 5:12
0
$\begingroup$

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".

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much Geoff for your time and comments. I made some changes to the question think it's more clear now. So you think this new form is convex ? BTW I'm looking for the optimal solution and I totally agree, fmincon does not work for this problem and it has to be a mixed interger solver. $\endgroup$ – sarah daneshvar Jun 10 '15 at 5:08
  • $\begingroup$ @sarahdaneshvar: I don't know. I can't tell what your decision variables are, and it's also not clear to me how your formula for variance will give you a scalar output. Do you mean that $\mathbf{x}$ is a vector whose entries are a collection of samples from a random variable? If so, then the variance function would be the sample variance formula. Is there an upper bound on the entries of $\mathbf{x}$? If they should be integer-valued, your formulation should state that also. $\endgroup$ – Geoff Oxberry Jun 10 '15 at 5:44
  • $\begingroup$ Yes, vector X has samples from a random variable and the variance formula is the sample variance. No there's not currently any upper bound, I'd like to check what the optimal answer is, and if it's necessary I'd add constrains of upper bound on the entries of X. $\endgroup$ – sarah daneshvar Jun 10 '15 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.