How to optimize with "if" constraints

Question

The minimizing problem is the following : $$ \underset{w}{\operatorname{argmin}} \sum_{i=1}^{n}\left[w_{i}\times (\frac{Vw}{\sigma})_{i} - b_{i}\right]^{2}$$ with $V$ a $n\times n$ matrix (covariance matrix) which depends on the vector $w$ of size $n$, $\sigma$ is a scalar which is equal to $\sigma = \sqrt{w^\top Vw}$.

For $i=1,\ldots,n$, the quantity $w_{i}\times\left(\frac{Vw}{\sigma}\right)_{i}$ has a meaning in finance and I want the vector to be as close as possible to the target vector $b$. That's why I am minimizing this function.

I have a function that uses scipy.minimize to solve this problem and it returns the optimal weights $\tilde{w}=(w_{i})$ of a portfolio of 500+ stocks. However, some of these weights are very low and I would like the weights $w_{j}$ that are under a certain thresold $\rm thr$ to be set to 0.

One way to have this would be to run my function, then manually set such weights to 0 with if conditions, and finally rescale the weights so the sum equals one. The problem with this method is that the final vector $w$ will not be the optimal vector $\tilde{w}$ anymore.

Do you know any way to minimize a function while having such conditions ?

what is the function you are minimizing? can you write down your model? — user3680510, Jun 19 '20 at 12:57
Welcome to OR.SE! Please take a look at these questions and answers, and see whether they answer your question: https://or.stackexchange.com/questions/76/in-an-integer-program-how-can-i-activate-a-constraint-only-if-a-decision-vari and https://or.stackexchange.com/questions/33/in-an-integer-program-how-i-can-force-a-binary-variable-to-equal-1-if-some-cond — LarrySnyder610, Jun 19 '20 at 13:05
Thank you @LarrySnyder610 ! I checked your links, unfortunately I don't think my problem can be solved with the answers. — FredNgu, Jun 19 '20 at 13:10
OK -- in that case, it would be good if you can put your problem statement into your question rather than in the comments. Hopefully someone will have a good answer for you. Thanks! — LarrySnyder610, Jun 19 '20 at 13:11
Ok. Perhaps it could be a dumb suggestion but iiuyr then you are looking for optimal values of wj. But you have some constraints in your problem. I do not know how you can do it in Scipy. Pyomo can handle it easily. Will it work if you initialize your variables to 0 and keep their lower limit to the threhold that are referring to. — chupa_kabra, Jun 19 '20 at 13:17
The $w_i$ are semicontinuous variables https://or.stackexchange.com/questions/1512/linear-programming-with-additional-if-then-default-to-zero-constraints/2529#2529 . Any MIQP solver should be able to handle this, whether handled directly as semicontinuous variables, or handled by binary variables Believe me when I say you are not the first person in the history of portfolio optimization who has done this. — Mark L. Stone, Jun 19 '20 at 13:17
Hello again, given that my optimization problem is not linear nor quadratic (because of the $\sigma$ that depends on the weights $w$) I couldn't use MIP/MIQP. I tried to use scipy.minimize with the big-M constraints in the link @MarkL.Stone gave me but unfortunately it didn't work because it seems like scipy.minimize can't set values to exactly 0 and therefore it adds error to the objective function.
Is there any mixed-integer programs that solves non-linear/non-quadratic functions ? — FredNgu, Jun 22 '20 at 13:35
is there a reason you don't or can't formulate this as an MIQP or MISOCP, as is standard? If somehow your formulation is different and fundamentally better, mixed-integer nonlinaer programming (optimization) is referred to as MINLP. Global solvers for MINLP include BARON, COUENNE, ANTIGONE, BMIBNB (YALMIP's own), SCIP. Local solvers (which are global if continuous relaxation is convex) include KNITRO. MISOCP can be handled by Mosek, CPLEX, Gurobi, and others, as well as MINLP solvers. MINLP problems can be very difficult to solve. — Mark L. Stone, Jun 22 '20 at 13:58

score 1 · Answer 1 · answered Jun 19 '20 at 13:26

with optimization engines like CPLEX you can model this if with logical constraints:

For instance, (x<=2) implies (y>=3) can be written in OPL, which is one of CPLEX APIs

(x<=2) => (y>=3);

Now for your portfolio example if you start with the standard Markowitz example

you may easily add if constraints or logical constraints:

{string} Investments = ...;
float Return[Investments] = ...;
float Covariance[Investments][Investments] = ...;
float Wealth = ...;
float Rho = ...;  // Variance Penalty (increasing rho from 0.001 to 1.0 
                  //                   produces a distribution of funds 
                  //                   with smaller and smaller variability).
/******************************************************************************

MODEL DECLARATIONS

******************************************************************************/
range float FloatRange = 0.0..Wealth;
dvar float  Allocation[Investments] in FloatRange;  // Investment Level
/******************************************************************************

MODEL

******************************************************************************/
// Minimal Investment
float minimalInvestment=0.01;
// max nb assets
float nbAssetsMax=5;
dexpr float Objective =
  (sum(i in Investments) Return[i]Allocation[i])
    - (Rho/2)(sum(i,j in Investments) Covariance[i][j]Allocation[i]Allocation[j]);
maximize Objective;
subject to {
  // sum of allocations equals amount to be invested
  allocate: (sum (i in Investments) (Allocation[i])) == Wealth;
sum(i in Investments) (Allocation[i]>=minimalInvestment)<=nbAssetsMax;
forall(i in Investments) (Allocation[i]>=minimalInvestment) || (Allocation[i]==0);
}
tuple AllocationSolutionT{ 
    string Investments; 
    float value; 
};
{AllocationSolutionT} AllocationSolution = {<i0,Allocation[i0]> | i0 in Investments};
float TotalReturn = sum(i in Investments) Return[i]Allocation[i];
float TotalVariance = sum(i,j in Investments) Covariance[i][j]Allocation[i]*Allocation[j];
execute DISPLAY {
  writeln("Total Expected Return: ", TotalReturn);
  writeln("Total Variance       : ", TotalVariance);
}

in particular

forall(i in Investments) (Allocation[i]>=minimalInvestment) || (Allocation[i]==0);

makes sure that an allocation is either 0 or more than a minimum level

NB:

I gave an example in OPL but that 's the same in C, python, java ...

How to optimize with "if" constraints

1 Answers1