Skip to main content

Documentation Index

Fetch the complete documentation index at: https://feasible-1447f9c5.mintlify.app/llms.txt

Use this file to discover all available pages before exploring further.

Let’s continue from the porfolio optimization example. Now, what if we instead want to maximize expected returns, while keeping the risk limited? Here’s a reformulation:
Problem statement for limited risk
I have want to optimize my portfolio. I have 1000 USD to invest in 3 stocks, IBM, WMT, and SEHI, or keep as cash. I want to hold them for 1 month and then sell again. I can buy/sell fractions of stocks. There's no dividend during that time.

Historical stock prices for the past months are given in the following table:
| **IBM** | **WMT** | **SEHI** |
|--------:|--------:|---------:|
|  93.043 |  51.826 |    1.063 |
|  84.585 |  52.823 |    0.938 |
| 111.453 |  56.477 |      1.0 |
|  99.525 |  49.805 |    0.938 |
|  95.819 |  50.287 |    1.438 |
| 114.708 |  51.521 |      1.7 |
| 111.515 |  51.531 |     2.54 |
| 113.211 |  48.664 |     2.39 |
| 104.942 |  55.744 |     3.12 |
|  99.827 |  47.916 |     2.98 |
|  91.607 |  49.438 |      1.9 |
| 107.937 |  51.336 |     1.75 |
|  115.59 |  55.081 |      1.8 |

I want to maximize the expected returns while keeping the standard deviation of the portfolio below 100 USD.
The changes to the previous formulation are:
  • We changed the last line of the prompt to ask for a maximization of returns
  • It is explicitly allowed to keep some of the budget as cash, with zero return, and no risk. This is to make sure there exists a solution with the given risk limit.
This translates to the following changes in the model:
  • The expected returns, previously a constraint, become the objective. Further, the target changes from min to max.
  • The variance, previously the objective, becomes a constraint. We have to specify a maximum acceptable variance.
Note: The unit of variance is squared USD. Its square root, the standard deviation, is in USD and easier to reason about. So if you have a a requirement of a 100 USD standard deviation, the limit would be a 10,000 USD^2 variance.
Example completed workflow: Open in Feasible
So the new formulation looks something like this: maxr1x1+r2x2+r3x3s.t.xTQx≤Varmaxx1+x2+x3≤1000\begin{align*} \text{max} \quad r_1 x_1 & + r_2 x_2 + r_3 x_3 \\ \text{s.t.} \quad x^T Q x &\leq \text{Var}_\text{max} \\ x_1 + x_2 + x_3 &\le 1000 \end{align*} where you as a user have to define Varmax\text{Var}_\text{max} as the maximum acceptable variance. The returns rir_i and covariances QQ are computed by Feasible from the data.
The term xTQxx^T Q x is a way of writingq11⋅x12+2q12⋅x1⋅x2+...+2q23⋅x2⋅x3+q33⋅x32q_{11}\cdot x_1^2 + 2q_{12}\cdot x_1 \cdot x_2 + ... + 2q_{23}\cdot x_2 \cdot x_3 + q_{33}\cdot x_3^2 and calculates the variance of the combined portfolio with investments xix_i and covariance between the stocks QQ.
But now we have a quadratic function in the constraints! This is a different situation from before, where all constraints were linear, but the objective was quadratic. And even more so from previous examples, were both objective and constraints were purely linear. Thankfully, there are algorithms for each of these situations. Feasible will automatically choose a suitable one for your problem. You can investigate the effect in the Solver panel on the right hand side in the example workflow. In previous examples with linear constraints, Feasible selected HiGHS as the solver. And HiGHS is able to prove that the solution is actually optimal, and thus retuns OPTIMAL as status. But in this problem, Feasible used SCS (splitting conic solver). The difference is this:
  • SCS supports quadratic constraints, which HiGHS does not.
  • HiGHS, however, can handle integer variables like in the Queens variables, which SCS cannot.
  • SCS is also able to handle nonconvex problems, even though it might not find a globally optimal solution.
Problems with linear objective and linear constraints are (not surpringsingly) called linear programs (LP). Problems with quadratic objective and linear constraints, such as the previous example of risk minimization in a portfolio, are called quadratic programs (QP). And problems with linear objective and quadratic constraints, like this example, are called second-order cone programs (SOCP).The reason for distinguishing them is that, while the math might look similar, a solver will use different algorithms to solve each of them. And Feasible will make its choice of solver based on problem characteristics:
  • HiGHS for linear or quadratic convex problems (with or without integers)
  • SCS for nonconvex quadratic problems, or problems with quadratic constraints, without integers
  • Ipopt for other nonlinear problems without integers
  • Juniper/Ipopt for nonlinear problems with integers

​
What if no solution exists

Remember how we added a “cash” option, with zero risk? This is because all 3 stock investments carry risk, so below a certain risk limit, there will be no possible solution if the whole budget gets invested. Such a case, where there is no possible solution that fulfills all the constraints, is called an infeasible problem. A very simple example would be minxsubject tox>2x<1\begin{align*} \mathrm{min} \quad & x \\ \mathrm{subject\,to} \quad & x > 2 \\ & x < 1 \end{align*} Since no xx can be both greater than 2 and lesser than 1, no solution exists. In the example above, this is easy to see from the problem statement. But in more realistic cases, with many variables, one cannot see it from the mathematical formulation. However, for some types of problems, e.g. linear or quadratic ones, the solver can find a proof that no solution exists for an infeasible problem. But for the general case, this will unfortunately not be possible to prove.