1
$\begingroup$

I want to solve the following optimization problem: \begin{equation} \begin{split} \text{maximize} &\;\;\; \ln x_1+\ln x_2+\ln x_3+\ln x_4 \\ \text{s.t} &\;\;\; x_4\le4 \\ \text{and}&\;\;\; (5x_1+7x_3)/8\le 8 \\ \text{and}&\;\;\; x_3+4/7x_4\le 7 \\ \text{and}&\;\;\; x_1\le 5 \\ \text{and}&\;\;\; x_2\le 8 \\ \text{and}&\;\;\; (5x_1+8x_2)/11\le 11 \end{split} \end{equation} Each $x_i$ should be non-negative. Actually, since they are used as arguments of $\ln x_i$ they should be positive.

I've tried an approach using Lagrange multipliers. As I was told, since there are feasible solutions and $\ln$ is a convex function, I should be able to find optimal solutions. However, let $f(x)$ denote our target function and $g(x):=\varphi(x)-C$ describe all the inequalities $\varphi(x)\le C$, s.t. they are fulfilled iff $g(x)\le 0$ (it's a little bit imprecise, but I'm sure you know what I mean).

What I've done now was writing down the following ten equations:

\begin{equation} \begin{split} \frac{\partial}{\partial x_i}f(x)+\sum_{k=1}^6\lambda_k\frac{\partial}{\partial x_i}g_k(x) &= 0\;\;\;\;\;(i=1,\ldots, 4) \\ \lambda_kg_k(x)&=0\;\;\;\;\;(k=1,\ldots, 6) \end{split} \end{equation}

I've tried to solve them and ended up with

\begin{equation} \begin{split} \lambda_1 &=-\frac{1}{4}-\frac{4}{7}\lambda_3 \\ \lambda_2 &=-\frac{8}{33}-\frac{8}{7}\lambda_3 \\ \lambda_4 &=\frac{5}{7}\lambda_3+\frac{5}{8}\lambda_5-\frac{835}{2112} \\ \lambda_6 &=-\frac{11}{64}-\frac{11}{8}\lambda_5 \\ 0 &=-\frac{25}{7}\lambda_3+5\lambda_4-\frac{25}{8}\lambda_5-\frac{313}{2112} \\ 0 &=\frac{285}{56}\lambda_3-\frac{57}{8}\lambda_4+\frac{285}{64}\lambda_5+\frac{179}{176} \end{split} \end{equation}

As you may can see, the 3th and 5th equations cannot be fulfilled at the same time. So, something went wrong. In addition to a general procedure I would be very thankful if someone could recommend a computational way to calculate the maximum.

$\endgroup$
  • $\begingroup$ The multiplier $\lambda_i$ is non-zero only if the associated inequality constraint is fulfilled with equality (it is active). You have to try different combination of active/inactive constraints to determine a KKT point. $\endgroup$ – daw Jun 5 '14 at 19:28
  • $\begingroup$ I would recommend you to use a numerical solver. Are you familiar with Matlab? $\endgroup$ – The Pheromone Kid Jun 5 '14 at 19:35
  • $\begingroup$ @Ert Yes, but I don't know how I can solve this problem with Matlab. $\endgroup$ – 0xbadf00d Jun 5 '14 at 19:47
  • $\begingroup$ @daw For the sake of simplicity: Let's assume for a moment that all these inequalities were actually equalities. From my understanding, the procedure didn't change. So, even in this case I don't find a solution. Any idea? $\endgroup$ – 0xbadf00d Jun 5 '14 at 19:49
  • $\begingroup$ then the assumption that all inequalities are active is false $\endgroup$ – daw Jun 5 '14 at 19:50
2
$\begingroup$

there is a solution to your problem: Use the cvx interface for convex programming together with Matlab, see http://cvxr.com/cvx/. You have to download some software and read the user's guide. It's simple.

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