Optimizing diet / meal plan I watch my girlfriend spend an hour generating her meal plan for the week and figured I could make something that would work in seconds with C++/Qt.
The algorithm I am trying to produce is optimization based on:


*

*Per day, one meal for breakfast, lunch, dinner and a snack(s).

*Per day, a certain amount of protein, grains, fat, vegetables and dairy need to be consumed, well-defined for each meal.


From what I can tell, the situation I have is:


*

*A system of 5 equations, one for each type of nutrient type.

*Each equation has 4 variables, one for each type of meal.

*The coefficients of each variable are linked, based on the meal chosen.


\begin{equation}
P_{B}x_{B} + P_{L}x_{L} + P_{D}x_{D} + P_{S}x_{S} = R_P \\
V_{B}x_{B} + V_{L}x_{L} + V_{D}x_{D} + V_{S}x_{S} = R_V \\
D_{B}x_{B} + D_{L}x_{L} + D_{D}x_{D} + D_{S}x_{S} = R_D\\
F_{B}x_{B} + F_{L}x_{L} + F_{D}x_{D} + F_{S}x_{S} = R_F\\
G_{B}x_{B} + G_{L}x_{L} + G_{D}x_{D} + G_{S}x_{S} = R_G\\
\end{equation}
The coefficients $P, V, D, F, G$ are the serving size that a particular meal has for each nutrient type (protein, veggies, dairy, fat, grain), $B, L, D, S$ are meal types (breakfast, lunch, dinner and snack) and $R$ corresponds to required servings per day for each nutrient. The latter is of course known and constant. 
The serving size coefficients need to be chosen so that these conditions are best met, corresponding to the optimized selection of meals each day. Since the coefficients for each meal type are linked, I am not sure how to approach this problem using programming algorithms that don't involve just brute force randomization and iterations. Could anyone help me out?
 A: Kind of old, but in case you want a decent solution, here is how you look at your problem. You have a constrained optimization problem,
$$
\min \sum_i \big( r_i - \sum_j P_{ij}x_j \big)^2
$$
where $ x_j > 0 $. If you stare at your matrix equation above, note that it's in this form. You want to have $ x $ that minimizes the error.
Let me add another variable $ s_k $ into the mix and change the constraint to, $ x_j + s_j^2 = 0 $. Note that for any $ s_k \in \mathbb{R} $ this is the same constraint.
You can read about Lagrange Multipliers, but the gist is that we can take this problem with our new constraints and write a new problem,
$$
\min \mathcal{L} = \min \sum_i \big[ \lambda_i(x_i - s_i^2) + \big( r_i - \sum_j P_{ij}x_j \big)^2 \big]
$$
And now you have 3 free variables to minimize on: $ x, s, \lambda $. Simply apply gradient descent or solve analytically. In this case, you can do it relatively simply by making a realizing that optimizing on $ \lambda $ implies that $ x = s^2 $ (surprise), so just make that substitution and solve analytically.
