# Optimization of a convex target function with inequality constraints

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.

• 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. – daw Jun 5 '14 at 19:28
• I would recommend you to use a numerical solver. Are you familiar with Matlab? – The Pheromone Kid Jun 5 '14 at 19:35
• @Ert Yes, but I don't know how I can solve this problem with Matlab. – 0xbadf00d Jun 5 '14 at 19:47
• @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? – 0xbadf00d Jun 5 '14 at 19:49
• then the assumption that all inequalities are active is false – daw Jun 5 '14 at 19:50

## 1 Answer

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.