0
$\begingroup$

I have optimization that goes the followings:

\begin{equation} \begin{aligned} &\max_{x_1,\dots,x_k} &&f_1(x_1)+f_2(x_2)+\dots+f_k(x_k)\\ &\text{subject to} &&x_1 + \dots + x_k = M\\ &&& x_1,\dots,x_k > 0 \end{aligned} \end{equation}

All $f_i(x_i)$ are strictly concave and continuous real function on the feasible region. I just wonder if we can see this optimization problem as function on $M$. In other word, to see it as a continuous mapping $H$ that map a given constraint $M$ to the optimal value.

If so, could we property apply property such as derivative/gradient on this function $H$?

$\endgroup$
8
  • $\begingroup$ If there is no optimal value, then the relation's range is empty, so cannot be a function. $\endgroup$ – David P Apr 26 '20 at 16:33
  • $\begingroup$ The pseudo-inverse is a linear function that can be defined as an optimization function. $\endgroup$ – NicNic8 Apr 26 '20 at 16:48
  • $\begingroup$ @DavidPeterson all fi are strictly concave and the domain is a convex set. This is convex-optimization problem and therefore admit unique otpimal solution/value. $\endgroup$ – Junwei su Apr 26 '20 at 16:52
  • 1
    $\begingroup$ Yes, this is something that Lagrange multipliers do for us. There's a good discussion of this in Boyd and Vandenberghe (free online). See section 5.6 ("Perturbation and sensitivity analysis.") "When strong duality obtains, the optimal dual variables give very useful information about the sensitivity of the optimal value with respect to perturbations of the constraints." See eq. 5.58 in particular. $\endgroup$ – littleO Apr 26 '20 at 17:04
  • 1
    $\begingroup$ A relevant line from Boyd and Vandenberghe (p. 253, in the "shadow price interpretation" paragraph): "In other words, $\lambda_i$ tells us approximately how much more profit the firm could make, for a small increase in availability of resource $i$." This is a classic reason that a business or economist might want to know the Lagrange multipliers. $\endgroup$ – littleO Apr 26 '20 at 17:11
0
$\begingroup$

Dynamic programming often applies to problems with similar structure to this. Let $g(k,M)$ denote the maximum value and note the recursion: $$g(k,M) = \max_{0<y<M} \{f_k(y) + g(k-1,M-y)\}$$

$\endgroup$
1
  • $\begingroup$ I don't quite see how this related to the question I ask. Could you elaborate on this? Thanks. $\endgroup$ – Junwei su Apr 26 '20 at 16:53

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.