2
$\begingroup$

The problem is to

minimize $ f(x_1, x_2 ,x_3, x_4):= - \Big[ \log ({\frac{1}{4} + x_1}) + \log ({\frac{1}{2} + x_2})+ \log ({\frac{1}{5} + x_3})+ \log ({\frac{3}{4} + x_4}) \big]$

such that $x_1 +x_2 +x_3 +x_4 =1, \quad x_i \geq 0$.

I formulated the Lagrangian $L(x, \lambda) = f(x_1, x_2 ,x_3, x_4) - \lambda(x_1 +x_2 +x_3 +x_4 -1)$.

Optimizing over the four variables respectively give $$ x_1 = -\frac{1}{\lambda} - \frac{1}{4}, \, x_2 = -\frac{1}{\lambda} - \frac{1}{2}, \, x_3 = -\frac{1}{\lambda} - \frac{1}{5}, \, x_4 = -\frac{1}{\lambda} - \frac{3}{4},$$ so $\lambda \geq - \frac{4}{3}$ ( for $x_4$ to be nonnegative). But plugging in to the feasible set gives $\lambda = - \frac{40}{27} < - \frac{4}{3}$. Hence, the Lagrange method does not work. Can we proceed as in LP, i.e. consider only the vertices of the feasible set, so at least one of $x_1, \ldots, x_4$ is zero?

$\endgroup$
  • $\begingroup$ There is a simple solution I think: $\log a + \log b \le 2\log \frac{a+b}{2}$. $\endgroup$ – Khue May 26 '15 at 0:29
  • $\begingroup$ but $=$ can't be had since it lead to $x_i< 0$ $\endgroup$ – DeepSea May 26 '15 at 0:35
  • 1
    $\begingroup$ If you're going to use a Lagrangian method you can't ignore the nonnegativity constraints. This is the correct Lagrangian: $$L(x,\lambda,z) = -\sum_i\log(x_i+b_i) - \lambda(\sum_i x_i - 1) - \sum_i z_i x_i$$ where $b=(1/4,1/2,1/5,3/4)$ and $z_i$ are the Lagrange multipliers for $x_i\geq 0$. These multipliers must be nonnegative. $\endgroup$ – Michael Grant May 26 '15 at 0:44
  • $\begingroup$ @NotALoner: if we apply the inequality $\log a + \log b +\log c \le 3\log \frac{a+b+c}{3}$ for the first three terms, then we get a function of $x_4$, which is easy to minimize. $\endgroup$ – Khue May 26 '15 at 1:19
  • $\begingroup$ @Khue: Sure is. Haven't thought about it yet. Nice try.... $\endgroup$ – DeepSea May 26 '15 at 1:20
2
$\begingroup$

If you're going to use a Lagrangian method you can't ignore the nonnegativity constraints. This is the correct Lagrangian: $$L(x,\lambda,z) = -\sum_i\log(x_i+b_i) - \lambda(\sum_i x_i - 1) - \sum_i z_i x_i$$ where $b=(1/4,1/2,1/5,3/4)$ and $z_i$ are the Lagrange multipliers for $x_i\geq 0$. These multipliers must be nonnegative. The optimality conditions are $$-\frac{1}{x_i+b_i} = \lambda + z_i, ~~ i=1,2,3,4, \quad \sum_i x_i = 1, \quad x_i\geq 0,~~i=1,2,3,4$$ Now here's a bit of a trick. Because $z_i\geq 0$, we can treat it like a slack variable and write those first equations as inequalities: $$-\frac{1}{x_i+b_i} \geq \lambda, ~~ i=1,2,3,4, \quad \sum_i x_i = 1, \quad x_i\geq 0,~~i=1,2,3,4$$ Solving for $x_i$ gives us $$ x_i \geq \max\{0, -\frac{1}{\lambda}-b_i\}, ~~ i=1,2,3,4, \quad \sum_i x_i = 1$$ Now, it takes a bit of a leap of faith, but if you assume equality here: $$ x_i = \max\{0, -\frac{1}{\lambda}-b_i\}, ~~ i=1,2,3,4, \quad \sum_i x_i = 1$$ what you can consider is sweeping $\lambda$ from $-\infty$ to $0$, and eventually you'll hit $\sum_i x_i = 1$. That's your answer! It's helpful to define $\sigma=-1/\lambda$, and sweep from $0$ to $+\infty$: $$ x_i = \max\{0, \sigma-b_i\}, ~~ i=1,2,3,4, \quad \sum_i x_i = 1$$ I found that $\sigma=0.65$, corresponding to $\lambda=-20/13$, gives me $x=(0.4,0.15,0.45,0)$. I can verify that this satisfies all of the optimality constraints in their original forms for appropriate choices of $z_i$, and I'm done.

$\endgroup$
0
$\begingroup$

The vector $ x $ is constrained to belong to the probability simplex, and it's possible to project onto the probability simplex efficiently. Thus it would be possible to solve this problem using the projected gradient method. Details can be found in Vandenberghe's 236c notes.

$\endgroup$
  • $\begingroup$ I haven't heard of the projected gradient method. So could I consider the vertex points of this feasible set? $\endgroup$ – Richard May 26 '15 at 0:19
  • $\begingroup$ The answer Maple gave was (0.4,0.15,0.55,0), which is clearly a vertex point. So is this a sufficient condition? $\endgroup$ – Richard May 26 '15 at 0:23
  • $\begingroup$ That can't be right anyway, it doesn't sum to 1. $\endgroup$ – Michael Grant May 26 '15 at 0:55
0
$\begingroup$

hint:Observe the function is convex in each of the variables separately, hence the extrema occurs at the end points. Does this ring a bell??

$\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.