I'm looking at optimising weightings over a set of different amounts to achieve a total, whilst minimising the amount over the total these are.

Think: I have macronutrient targets, I want to make sure I hit them but don't go over by an excessive amount so what 'weight' of each meal would I want.

So the constraint is:

$\left( \begin{array} QP_{11} & P_{12} & P_{13} \\ P_{21} & P_{22} & P_{23} \\ P_{31} & P_{32} & P_{33} \\ P_{41} & P_{42} & P_{43} \end{array}\right) \cdot \left(\begin{array} Qw_1 \\ w_2 \\ w_3 \end{array} \right) \ge \left( \begin{array} QT_1 \\ T_2 \\ T_3 \\ T_4 \end{array} \right)$

Whilst we want to minimise:

$\mathrm{min} \left[\left( \begin{array} QP_{11} & P_{12} & P_{13} \\ P_{21} & P_{22} & P_{23} \\ P_{31} & P_{32} & P_{33} \\ P_{41} & P_{42} & P_{43} \end{array}\right) \cdot \left(\begin{array} Qw_1 \\ w_2 \\ w_3 \end{array} \right) - \left( \begin{array} QT_1 \\ T_2 \\ T_3 \\ T_4 \end{array} \right)\right]$

I'm having a bit of trouble on where to start with this though. I know that for a problem with two objectives I could just make one objective as efficient as possible, but not really sure where to start here. And of course if the matrix P was 3x3 if it has an inverse the problem is automatically solved.

I'd also possibly want to expand this to more than three weightings. So any algorithm would need to be extendable to n-objectives and indeed m payoffs.

Are there any names of specific algorithms for this? Ideally something that is suitable for automation given a P matrix and a T vector.

  • $\begingroup$ are you just looking for any Pareto Solution? $\endgroup$ – LinAlg Jan 3 '19 at 12:44
  • $\begingroup$ Any efficient solution would suffice, from there it should be possible to extend to all efficient solutions. $\endgroup$ – user403033 Jan 3 '19 at 14:40
  • $\begingroup$ Is $w_1+w_2+w_3=1$ and addtionally $w_i\geq 0 \ \ \forall \ i \in \{1,2,3 \} $? $\endgroup$ – callculus Jan 3 '19 at 19:05
  • $\begingroup$ No, the weights would not have to sum to 1 but they would need to be positive. $\endgroup$ – user403033 Jan 4 '19 at 9:45

Your problem can be summarized as $\min_{s,x}\{s : Ax+s\geq b, s\geq 0\}$. Weighted sum optimization gives a Pareto Solution as long as each weight is strictly positive: $\min_{x,s}\{w^Ts : Ax+s\geq b, s\geq 0\}$. These problems can be solved with the simplex method (available with linprog in scipy or Matlab).

  • $\begingroup$ I assume in this instance $s$ is the vector of my minimisation condition and $w$ are the weights I'm applying to each? So that I'm then left with a scalar to minimise? $\endgroup$ – user403033 Jan 4 '19 at 9:48
  • $\begingroup$ @user403033 that is correct! $\endgroup$ – LinAlg Jan 4 '19 at 14:20
  • $\begingroup$ Thanks, I'll give it a go with weightings of 1 across the board to start. A scalar condition will be much easier to deal with though. I assume if a particular entry of the P matrix is dominating the solution (due to relative size etc), to avoid this the problem is going to need to be reformulated? $\endgroup$ – user403033 Jan 4 '19 at 15:03
  • $\begingroup$ @user403033 you can either adjust the weights, or constrain two values of $P$ while optimizing the third value $\endgroup$ – LinAlg Jan 16 '19 at 20:06

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.