3
$\begingroup$

Consider two sample portfolio optimizations:

Optimization 1:
$\begin{matrix} \\ \min \frac{1}{2} w'\Sigma w \\ w'\mu = r \\ Aw = 0 \\ w_l \le w \le w_u \end{matrix}$

Optimization 2:
$\begin{matrix} \\ \min \frac{1}{2} w'\Sigma w - \lambda_1 (w'\mu - r)^2 - \lambda_2 w'(A'A)w \\ w_l \le w \le w_u \end{matrix}$

In both cases (wherever applicable):
$\begin{matrix} \\ w, w_l, w_u \in \mathbb{R}^{N\times 1} \\ \Sigma \in \mathbb{R}^{N \times N} \\ A \in \mathbb{R}^{m \times N} \\ r, \lambda_1, \lambda_2 \in \mathbb{R}^{1 \times 1} \end{matrix}$

Where $N$ is the number of instruments and $m$ is the number of constraints

Question - Calibration of $\lambda_1$ and $\lambda_2$

  1. In the first Optimization, which uses hard constraints, we don't have to calibrate any $\lambda_1$, $\lambda_2$, however there is a possibility that the optimization is infeasible, or the constraints are too binding (causing the optimal answer to be very poor compared to practically desired portfolios)

  2. In the second Optimization, the soft constraints can ensure the optimization is feasible and the constraints are also not overly binding if necessary, but it is not clear how to calibrate or set reasonable values of $\lambda_1$ or $\lambda_2$ so that there is a balance between the original objective function $w'\Sigma w$ and the penalties? Example, in this case, too small values of $\lambda_1$ and $\lambda_2$ will make the objective function equivalent to $w'\Sigma w$, and too large values will ignore the original objective function altogether.

Has this sort of problem been looked at before?

Does this sort of problem have a name?

Are there any papers or academic work related to this?

Any work that has evaluated such pros and cons in more detail?

$\endgroup$
1
$\begingroup$

Your two problems are highly related. See perhaps Boyd and Vandenberghe Chapter 5 on Lagrangian duality.

Let $\mathcal{W} = \left\{ \mathbf{w}: \mathbf{w}_l \leq \mathbf{w} \leq \mathbf{w}_u \right\}$

Optimization 1:
\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{w}$)} & \frac{1}{2} \mathbf{w}'\Sigma\mathbf{w} \\ \mbox{subject to} & \mathbf{w}'\boldsymbol{\mu} = r \\ & A \mathbf{w} = \mathbf{0} \\ & \mathbf{w} \in \mathcal{W} \end{array} \end{equation}

Let me define an optimization problem 2b (similar to your optimization problem 2) to more closely match Lagrangian duality.

Optimization 2b:
\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{w}$)} & \frac{1}{2} \mathbf{w}'\Sigma\mathbf{w} + \lambda \left( \mathbf{w}'\boldsymbol{\mu} - r \right) + \mathbf{v}' A \mathbf{w} \\ \mbox{subject to} & \mathbf{w} \in \mathcal{W} \end{array} \end{equation}

Lagrangian duality

Problem 1 and problem 2b are highly related problems. Define the Lagragian function as:

$$ \mathcal{L}\left(\mathbf{w}, \lambda, \mathbf{v} \right) = \frac{1}{2} \mathbf{w}'\Sigma\mathbf{w} + \lambda \left( \mathbf{w}'\boldsymbol{\mu} - r \right) + \mathbf{v}' A \mathbf{w} $$

where scalar $\lambda$ and vector $\mathbf{v}$ are Lagrange multipliers.

Your optimization problem 1 is: $$\min_{\mathbf{w} \in \mathcal{W}} \max_{\lambda, \mathbf{v}} \mathcal{L}(\mathbf{w}, \lambda, \mathbf{v}) $$.

Min-max interpretation: First you pick $\mathbf{w}$ (to minimize the objective), and then (after observing your choice) I get to pick penalties $\lambda$ and $\mathbf{v}$ to maximize the objective. If you violate the constraints, I can choose arbitrarily large penalties so the objective is $\infty$!

This is a convex problem. If furthermore the feasible set has a non-empty relative interior then Slater's condition holds and then the duality gap is zero. We then have: $$\min_{\mathbf{w} \in \mathcal{W}} \max_{\lambda, \mathbf{v}} \mathcal{L}(\mathbf{w}, \lambda, \mathbf{v}) = \max_{\lambda, \mathbf{v}}\min_{\mathbf{w} \in \mathcal{W}} \mathcal{L}(\mathbf{w}, \lambda, \mathbf{v}) $$.

Interpretation: If the duality gap is zero (i.e. the saddle point property), then the order doesn't matter! The max of the min is the same as the min of the max. The primal problem (the left hand side) is the same as the dual problem (on the right hand side).

Define the Lagrangian dual function as:

$$ g(\lambda, \mathbf{v}) = \min_{w \in \mathcal{W}} \mathcal{L}(\mathbf{w}, \lambda, \mathbf{v}) $$

Note that the dual function is the value obtained from solving optimization problem 2b. The dual problem is known as:

$$ \max_{\lambda, \mathbf{v}} g(\lambda, \mathbf{v}) $$

Summary

Define the Lagrangian dual function $g(\lambda, \mathbf{v}$) as value obtained from solving optimization problem 2b. If Slater's condition holds, then your optimization problem 1 is equivalent to the dual problem $\max_{\lambda, \mathbf{v}} g( \lambda, \mathbf{v})$.

There exists a $\lambda^*$ and a $\mathbf{v}^*$ such that solving problem 2b gives the same answer as problem 1.

Perhaps the real issue (as I go into in the comments) is in carefully defining your problem. If constraints really are hard constraints, then you can't violate them period. End of story. Where you seem to be going though is that perhaps some of these constraints are more goals than requirements. What's the right penalty then for violating these soft constraints? I don't know?

References

Boyd, Stephen and Lieven Vandenberghe, Convex Optimization, 2004

Rockafellar, R. T., Conjugate Duality and Optimization, 1974

$\endgroup$
  • $\begingroup$ So, what you are suggesting is that I should first solve for $w$ for some $\lambda$ and $v$, and then search over $\lambda$ and $v$? $\endgroup$ – uday Sep 27 '17 at 17:08
  • $\begingroup$ @uday This post is basically about the mathematics of solving constrained optimization problems and the relationship between: (i) constrained optimization, (ii) unconstrained optimization with penalties for violating vaious conditions, and (iii) the min-max interpretation and Lagrangian duality. $\endgroup$ – Matthew Gunn Sep 27 '17 at 17:16
  • $\begingroup$ @uday To me, it sounds like the issue is in precisely defining your optimization problem? If it's not instant death to violate a hard constraint, then it really isn't a hard constraint is it? Ad-hoc adding of hard constraints, arbitrary and manually fiddling around with penalty weights $\lambda$ suggests to me that you have some sense of what's a sensible answer but that you don't have a clean, precise definition of the problem you're trying to solve? $\endgroup$ – Matthew Gunn Sep 27 '17 at 17:23
  • $\begingroup$ Should you formulate your optimization problem as a problem with hard constraints? Or a problem with soft constraints and prices for violating those soft constraints? That depends on your problem? If violating the constraints is really the end of the world, then you can't violate them, period, and they should be formulated as hard constraints. If you can violate the constraint, then they shouldn't be hard constraints! Be aware that there exist $\lambda^*$ and $\mathbf{v}^*$ such the 2 approaches are equal. Solve problem 1 or solve p2 with $\lambda^*$ and $\mathbf{v}^*$ gives the same answer. $\endgroup$ – Matthew Gunn Sep 27 '17 at 17:34

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.