Thread Subject:

Constrained vs. unconstrained optimization

Hi, newsreaders.

I am solving this simple asset allocation problem given N<50 number of assets, maximizing the Sharpe ratio of the final portfolio. The weird problem I am facing is that when I constrain one of the asset weights to 0, I sometimes obtain a higher resulting Sharpe ratio (that is, fval) than when I don't give any constraint. And this cannot be true because it 0 was indeed the optimal weight for that asset, than the unconstrained problem could have given it too in the first place.

Fyi, this problem is a very small-scale problem with some of the portfolio weights resulting in the range of 1e-6 or 1e-8 and the Sharpe ratios (or the fvals) change in miniscule magnitudes; often the difference in the Sharpe ratios of the constrained and unconstrained problem such as above occurs only at the 12th decimal point. In fact, often the optimization is not solved at all, being terminated early by the MaxIter which is already quite high and already taking an infinitely long time.

I am using knitro and my optimset is:
options = optimset('TolX',1e-12,'TolFun',1e-16,'GradObj','off','AlwaysHonorConstraints','none','MaxIter',1e06)

I would greatly appreciate any advice on this!

you could try the following things:
- provide an analytical gradient. this might take quite some time to program, but it will greatly enhance the convergence (especially given small portfolio weights and small change in sharpe ratio). i would seriously recommend this, if feasible

- if you dont want this, at least use central difference ('FinDiffType', 'central'). this takes more calculations per step, but the convergence is faster (quadratic compared to linear)
- scale problem (in sqp: 'ScaleProblem', 'obj-and-constr' or you can do this yourself. try to get the magnitudes of the gradients to be similar)
- it may also help to set the size of the finite difference steps. check the DiffMinChange and FinDiffRelStep (this last one was only recently introduced in matlab, in 2011 or 2012 i think)

"werting" wrote in message <jqbipu$oqd$1@newscl01ah.mathworks.com>...
> Hi, newsreaders.
>
> I am solving this simple asset allocation problem given N<50 number of assets, maximizing the Sharpe ratio of the final portfolio. The weird problem I am facing is that when I constrain one of the asset weights to 0, I sometimes obtain a higher resulting Sharpe ratio (that is, fval) than when I don't give any constraint. And this cannot be true because it 0 was indeed the optimal weight for that asset, than the unconstrained problem could have given it too in the first place.
>
> Fyi, this problem is a very small-scale problem with some of the portfolio weights resulting in the range of 1e-6 or 1e-8 and the Sharpe ratios (or the fvals) change in miniscule magnitudes; often the difference in the Sharpe ratios of the constrained and unconstrained problem such as above occurs only at the 12th decimal point. In fact, often the optimization is not solved at all, being terminated early by the MaxIter which is already quite high and already taking an infinitely long time.
>
> I am using knitro and my optimset is:
> options = optimset('TolX',1e-12,'TolFun',1e-16,'GradObj','off','AlwaysHonorConstraints','none','MaxIter',1e06)
>
> I would greatly appreciate any advice on this!

Have you solved the reformulated Sharpe ratio problem which is a simple QP? If not, you are likely experiencing numerical problems and/or local minimizers etc. Hence, reformulate as a QP to begin with.

"Sargondjani" wrote in message <jqc7lh$f9e$1@newscl01ah.mathworks.com>...
> you could try the following things:
> - provide an analytical gradient. this might take quite some time to program, but it will greatly enhance the convergence (especially given small portfolio weights and small change in sharpe ratio). i would seriously recommend this, if feasible
>
> - if you dont want this, at least use central difference ('FinDiffType', 'central'). this takes more calculations per step, but the convergence is faster (quadratic compared to linear)
> - scale problem (in sqp: 'ScaleProblem', 'obj-and-constr' or you can do this yourself. try to get the magnitudes of the gradients to be similar)
> - it may also help to set the size of the finite difference steps. check the DiffMinChange and FinDiffRelStep (this last one was only recently introduced in matlab, in 2011 or 2012 i think)

Thanks for your advice! Providing the analytical gradient helped reduce instances of error, and I actually scaled the whole problem by multiplying 1e12 to the obj fcn so that the fvals were not moving at something less than machine epsilon, and this reduced the errors a lot too. But for some combinations of assets, the problem still exists :(

"Johan Löfberg" wrote in message <jr4917$9km$1@newscl01ah.mathworks.com>...
> "werting" wrote in message <jqbipu$oqd$1@newscl01ah.mathworks.com>...
> > Hi, newsreaders.
> >
> > I am solving this simple asset allocation problem given N<50 number of assets, maximizing the Sharpe ratio of the final portfolio. The weird problem I am facing is that when I constrain one of the asset weights to 0, I sometimes obtain a higher resulting Sharpe ratio (that is, fval) than when I don't give any constraint. And this cannot be true because it 0 was indeed the optimal weight for that asset, than the unconstrained problem could have given it too in the first place.
> >
> > Fyi, this problem is a very small-scale problem with some of the portfolio weights resulting in the range of 1e-6 or 1e-8 and the Sharpe ratios (or the fvals) change in miniscule magnitudes; often the difference in the Sharpe ratios of the constrained and unconstrained problem such as above occurs only at the 12th decimal point. In fact, often the optimization is not solved at all, being terminated early by the MaxIter which is already quite high and already taking an infinitely long time.
> >
> > I am using knitro and my optimset is:
> > options = optimset('TolX',1e-12,'TolFun',1e-16,'GradObj','off','AlwaysHonorConstraints','none','MaxIter',1e06)
> >
> > I would greatly appreciate any advice on this!
>
> Have you solved the reformulated Sharpe ratio problem which is a simple QP? If not, you are likely experiencing numerical problems and/or local minimizers etc. Hence, reformulate as a QP to begin with.

Hi. Scaling the whole problem by 1e12 and providing an analytical gradient reduced instances of such problem, but still for some combination of assets, the problem remains the same. By reformulating the problem as a QP, do you mean to change the objective function, for instance, make it minimize the stdev of the portfolio (the denominator of Sharpe ratio) while putting in some extra constraints with regard to the portfolio mean..?

To begin with, if you scale the problem by 1e12, it means there is something absolutely wrong in the formulation of the problem. Think of it in terms of what the numbers represent. If your numbers represent dollars invested, you are multiplying or dividing with a number which represents 1 million million dollars, i.e. one trillion. Does not make sense typicallly.

By reformulating, I mean that the standard Sharpe portfolio problem can be cast as a very simple quadratic program by making a suitable variable change. I don't have any reference at hand, but if you email me we can take the discussion off-line and I can provide some ready-to-run code in YALMIP.

"werting" wrote in message <jraidj$dda$1@newscl01ah.mathworks.com>...
> "Johan Löfberg" wrote in message <jr4917$9km$1@newscl01ah.mathworks.com>...
> > "werting" wrote in message <jqbipu$oqd$1@newscl01ah.mathworks.com>...
> > > Hi, newsreaders.
> > >
> > > I am solving this simple asset allocation problem given N<50 number of assets, maximizing the Sharpe ratio of the final portfolio. The weird problem I am facing is that when I constrain one of the asset weights to 0, I sometimes obtain a higher resulting Sharpe ratio (that is, fval) than when I don't give any constraint. And this cannot be true because it 0 was indeed the optimal weight for that asset, than the unconstrained problem could have given it too in the first place.
> > >
> > > Fyi, this problem is a very small-scale problem with some of the portfolio weights resulting in the range of 1e-6 or 1e-8 and the Sharpe ratios (or the fvals) change in miniscule magnitudes; often the difference in the Sharpe ratios of the constrained and unconstrained problem such as above occurs only at the 12th decimal point. In fact, often the optimization is not solved at all, being terminated early by the MaxIter which is already quite high and already taking an infinitely long time.
> > >
> > > I am using knitro and my optimset is:
> > > options = optimset('TolX',1e-12,'TolFun',1e-16,'GradObj','off','AlwaysHonorConstraints','none','MaxIter',1e06)
> > >
> > > I would greatly appreciate any advice on this!
> >
> > Have you solved the reformulated Sharpe ratio problem which is a simple QP? If not, you are likely experiencing numerical problems and/or local minimizers etc. Hence, reformulate as a QP to begin with.
>
> Hi. Scaling the whole problem by 1e12 and providing an analytical gradient reduced instances of such problem, but still for some combination of assets, the problem remains the same. By reformulating the problem as a QP, do you mean to change the objective function, for instance, make it minimize the stdev of the portfolio (the denominator of Sharpe ratio) while putting in some extra constraints with regard to the portfolio mean..?