2
$\begingroup$

I am considering the following function $$f(x_1,\dots,x_n,y)=-\alpha \left(y-k_1\right)^2-\beta \sum_{i=1}^n\left(k_2-x_i\right)^2-\gamma \sum_{i=1}^n\left(y-x_i\right)^2 - \frac{\delta}{y-d} \sum_{i=1}^n (x_i-d)\, ,$$ where $(x_1,\dots,x_n,y)\in[d,1]^{n+1}$, $d>0$ and $\alpha$, $\beta$, $\gamma$, $\delta$, $k_1$, $k_2>0$. Moreover, $x_i\leq y$ $\forall$ $i=1,\dots,$ $n$. I'm trying to calculate the maximum of this function on that domain.

Befor using "brute force" approach (i.e. by calculating derivatives, Hessian and so on), I wonder whether it's possible to obtain the absolute maximum in a more simple way. For example, I notice that $f\leq0$...

$\endgroup$
  • $\begingroup$ without squaring that final term, this problem is not easy $\endgroup$ – LinAlg Dec 24 '18 at 16:10
  • $\begingroup$ Your "brute force" method is really quite easy. You should try it before wasting a lot of time on alternatives. First hold $y$ constant. The derivatives for the $x_i$ are independent of other terms, so you can find the $x_i$ in terms of $y$ without any need for a Hessian. Then maximize for $y$. $\endgroup$ – Paul Sinclair Dec 25 '18 at 3:11
  • $\begingroup$ @PaulSinclair, thank you. Then I should try to maximize $g(x_1,\dots,x_n):= f(x_1,\dots,x_n,\bar{y})$, where $\bar{y}$ is assumed as constant at moment. But why "without any need for Hessian"? I mean, how do I know that the point that makes to zero the partial derivatives of $g$ is exactly a maximum point for $g$, without Hessian? $\endgroup$ – Mark Dec 28 '18 at 8:05
  • $\begingroup$ I was talking about finding the maximum, not proving that it was a maximum. However, I was also confusing the Jacobian (which identifies extrema) with the Hessian (which classifies the extrema when found), so the statement is not correct. However, I re-iterate that the Hessian and Jacobian here are easy to calculate. $\endgroup$ – Paul Sinclair Dec 29 '18 at 15:34
2
+50
$\begingroup$

Consider $y$ fixed as Paul Sinclair suggested. Your objective function is now separable: you can optimize each $x_i$ independently. It is also concave in $x_i$ (since the second derivative is negative), so it is maximized when the derivative is 0: $$-2\beta (k_2-x_i) - 2\gamma(y-x_i) - \frac{\delta}{y-d} = 0$$ which can be written as $$2(\beta + \gamma)x_i = 2\beta k_2 + 2\gamma y + \frac{\delta}{y-d}$$ so the solution is $$x_i = \frac{\beta k_2 + \gamma y}{\beta + \gamma} + \frac{\delta}{2(\beta + \gamma)(y-d)}$$ You can plug this in and maximize over just $y$. Since the last term in your objective is not squared, maximizing over $y$ is not simple: there are probably multiple local optima. You could perform grid search for $y$, or apply a gradient based optimization algorithm and try multiple starting points.

$\endgroup$
  • $\begingroup$ Note that all the $x_i$ are the same at any stationary point. Plugging the expression for $x_i$ into $f$ gives a function of $y$ only that is a rational function of degree $2$. It's maxima are not hard to find. $\endgroup$ – Paul Sinclair Dec 30 '18 at 18:42
1
$\begingroup$

Are really the derivatives way the bruit force?

The derivates of $$f(x_1,\dots,x_n,y)=-\alpha \left(y-k_1\right)^2-\beta \sum_{i=1}^n\left(k_2-x_i\right)^2-\gamma \sum_{i=1}^n\left(y-x_i\right)^2 - \frac{\delta}{y-d} \sum_{i=1}^n (x_i-d)\, $$ are zeros in the stationary points, $$\begin{cases} f''_{x_j}(x_1,\dots,x_n,y)=2\beta \left(k_2-x_j\right)+2\gamma \left(y-x_j\right) - \dfrac{\delta}{y-d}\, =0\\ f'_y(x_1,\dots,x_n,y)=-2\alpha \left(y-k_1\right)-2\gamma \sum\limits_{i=1}^n\left(y-x_i\right) - \dfrac{\delta}{y-d} \sum\limits_{i=1}^n (x_i-d)\, =0, \end{cases}$$ or, for $y\not=d,$ $$\begin{cases} 2\beta (y-d)\left(k_2-x_j\right)+2\gamma (y-d) \left(y-x_j\right) - \delta\, =0, \quad j=1\dots n\\ -2\alpha (y-d)^2\left(y-k_1\right)-\gamma (y-d)^2\sum\limits_{i=1}^n\left(y-x_i\right) - \delta \sum\limits_{i=1}^n (x_i-d)\, =0, \end{cases}$$ so $$\begin{cases} -2(\beta+\gamma) (y-d)x_j + 2(y-d)(\beta k_2+\gamma y) - \delta\, =0, \quad j=1\dots n\\ -2(\beta+\gamma) (y-d)\sum\limits_{i=1}^n x_i + 2n(y-d)(\beta k_2+\gamma y) - n\delta\, =0\\ (\gamma-\delta)(y-d)^2\sum\limits_{i=1}^nx_i + (2\alpha k_1 - \gamma y)n(y-d)^2 +n\delta d\, =0. \end{cases}$$ Summation of the second and third equations factors $2(\gamma-\delta)(y-d)$ and $(\beta+\gamma)$ gives $$\begin{cases} -2(\beta+\gamma) (y-d)x_j + 2(y-d)(\beta k_2+\gamma y) - \delta\, =0, \quad j=1\dots n\\ 2(\gamma-\delta)(2n(y-d)(\beta k_2+\gamma y) - n\delta) + ((2\alpha k_1 - \gamma y)n(y-d)^2 +n\delta d)(\beta-\gamma)\, =0, \end{cases}$$ and this leads to the cubic equation for $y$ and explicit expressions for $x_j.$

$\endgroup$

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.