Constrainted optimization involving logarithms

84 Views Asked by At

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?

3

There are 3 best solutions below

0
On BEST ANSWER

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.

3
On

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.

0
On

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??