0
$\begingroup$

I only know of linear programming (LP) optimization by itself, and quadratic programming (QP) optimization by itself, but I have never seen them mixed within the same objective function. For example, a model that concurrently solves an outer maximization problem as well as an inner minimization one.

Say I have a "bigger picture" model that must be solved with linear programming as an outer maximization, which at the same time requires an inner minimization model to derive an optimal decision variable using quadratic programming.

Am I allowed to mix LP with QP like this in the same objective function? Could you give examples of actual models from any field that mix LP with QP? I want to know what the objective function looks like and how the notation is done

(To avoid only receiving min-max or minimax as an answer, the example I mentioned could even be outer and inner maximization.)

$\endgroup$
7
  • $\begingroup$ QP encompasses LP, so every LP is a QP. The tractability of mixed models depends on how the models interact. Do you have an example in mind of a "bigger picture" model? $\endgroup$
    – LinAlg
    Commented Oct 18, 2020 at 2:21
  • $\begingroup$ @LinAlg the bigger picture model is the optimal transport which is solved with LP, while the inner minimization model to embed in it is portfolio weight optimization which minimizes portfolio variance with QP. Optimal transport (LP) takes a source distribution/histogram $\alpha$ and minimizes the cost of transferring its mass to a target distribution/histogram $\beta$. I would like to use the portfolio weighted return distribution from the QP model and embed it as the source distribution $\alpha$ in the LP problem $\endgroup$
    – develarist
    Commented Oct 20, 2020 at 1:23
  • $\begingroup$ Can't you just solve the problems sequentially? How does the transport problem affect which portfolio you select? $\endgroup$
    – LinAlg
    Commented Oct 20, 2020 at 1:46
  • $\begingroup$ I guess it's more of a want to solve both problems concurrently rather than sequentially. The transport problem is affected by the fact that different combinations of portfolio weights from the QP model would result in a different source distribution of portfolio returns being input into the LP model $\endgroup$
    – develarist
    Commented Oct 20, 2020 at 1:48
  • 1
    $\begingroup$ Could you post your full problem? What I mean is that if you put the LP in standard form ($\min\{c^Tx : Ax=b, x\geq 0\}$), that the portfolio solution only affects $b$. $\endgroup$
    – LinAlg
    Commented Oct 20, 2020 at 19:36

1 Answer 1

2
$\begingroup$

You seen to be referring to what is called Bilevel Optimization https://en.wikipedia.org/wiki/Bilevel_optimization .

If your inner problem is a QP, you would include the KKT conditions for the QP as additional constraints to the outer problem. This overall problem would no longer be an LP due to the complementarity constraints in the KKT conditions, and is called a Mathematical Program with Equilibrium Constraints (MPEC) https://neos-guide.org/content/mathematical-programs-equilibrium-constraints or Mathematical Program with Complementarity Constraints (MPCC).

$\endgroup$
6

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .