Optimization: Coupling Variables

Question

I have formulated an optimization problem that is expressed as: $$\begin{align*} \underset{\mathbf{x}}{\text{minimize}} &&-\log(ax_1)-\log(bx_2)\\ \text{s.t.} && x_1 \leq 0.2\\ \text{} && x_2\leq x_3 \\ && x_1+x_2+x_3=1 \\ \end{align*}$$ where $a,b>0$ and $\mathbf{x} \in \mathbb{R}^3_+$. I would like to solve this problem via the Lagrange dual function. However, I can't solve it. Here's my approach. I rewrite the problem as $$ \mathfrak{L}(x,\lambda,\nu) = \{-\log(ax_1)-\log(bx_2)+\lambda_1 (x_1-0.2) + \lambda_2(x_2-x_3) + \nu (x_1+x_2+x_3-1) \} $$ $$ G(\lambda,\nu)= \underset{x}{\text{inf}} \{ \ \mathfrak{L}(x,\lambda,\nu) \ \} $$

At this point, I try to find $G(\lambda,\nu)$ by (partially) differentiating $\mathfrak{L}(x,\lambda,\nu)$ w.r.t. $\mathbf{x}$. Using this approach, I can obtain the optimal $x_1^*$ and $x_2^*$ as follows: $$x_1^*=\Big[\frac{1}{\nu-\lambda_1}\Big]^+$$ $$x_2^*=\Big[\frac{1}{\nu+\lambda_2}\Big]^+$$ but not $x_3^*$. I thought this occurs because the objective function is not related to the variable $x_3$ so there is no optimal $x_3$. Rather $x_3$ is just a variable that has to satisfy the constraint. For instance, if I extend $\mathbf{x}$ into $\mathbb{R}^4$ and change the equality constraint to $\mathbf{1}^Tx=1$, I should have a set of $(x_3,x_4)$. For the above question, the partial derivative of $\mathfrak{L}(x,\lambda)$ w.r.t. $x_3$ leads to an equation that has no $x_3$ variable, i.e. $\nu = \lambda_2$ when the derivative is set to zero. I tried to change the objective function to a linear one, i.e. without log, but I face similar problem where the derivative is not related to the optimal variable. Thus, I would like to seek for an advice on how to solve this kind of problem via the dual method.

Answer 1

I have managed to solve the above question. To solve this problem, my approach is to introduce an auxiliary variable. That is, I reformulated the question as follows: $$\begin{align*} \underset{\mathbf{x,y}}{\text{minimize}} &&-\log(ax_1)-\log(bx_2)\\ \text{s.t.} && x_1 \leq k\\ \text{} && x_2\leq x_3 \\ \text{} && x_2+x_3 = y\\ && x_1+y=1 \\ \end{align*}$$ where $\mathbf{x} \in \mathbb{R}^3_+$ and $\mathbf{y} \in \mathbb{R}_+$. Now, we can solve the above problem via decomposition as follows: $$\begin{align*} \underset{\mathbf{y}}{\text{minimize}} && f(y)\\ \end{align*}$$ $$\begin{align*} f(y)= &&\underset{\lambda_1,\nu_1}\sup\underset{x_1} \inf \{-\log(ax_1)+\lambda_1(k-x_1)+\nu_1(x_1+y-1) \} + \underset{\lambda_2}\sup\underset{x_2} \inf \{-\log(bx_2)+\lambda_2(2x_2-y) \} && \end{align*}$$ Taking the derivatives, we have $x^*_1(\lambda_1,\nu_1)= \left[ \frac{1}{\nu_1-\lambda_1}\right]^+$, $x^*_2(\lambda_2)= \left[ \frac{1}{2\lambda_2}\right]^+$, $\lambda_1 = 0$, $\nu_1=\frac{1}{1-y}$,$\lambda_2 = \left[ \frac{1}{y} \right]^+$

Substituting back, we have $$ \underset{\mathbf{y}}{\text{minimize}} -\log\left( (1-y)a \right)-\log \left(\frac{yb}{2} \right) $$ where $\mathbf{y}^* = \frac{1}{2}$

Therefore, the optimal value is $$ -\log \left( \frac{a}{2} \right)- \log \left( \frac{b}{4} \right) $$