Linear program with bounds on the optimization variable

Question

I am trying to maximize the following function

$$f(x)=-x$$

subject to $0 \leq x < c$, where $c > 0$ is a constant.

If I write out the Lagrangian and take the first-order condition, I get a $\lambda = -1$, but this violates the non-negativity of $\lambda \ge 0$ and complementary slackness $\lambda(c-x)=0$. Does this imply the constraint is slack/nonbinding ?

Lastly had the constraint looked like $x > c$, then $\lambda =1$ would have been the case.

But the constraint cannot bind because of strict inequality! Which implies $\lambda = 0$ must be true. Which is a contradiction.

The solution is obvious, I am simply wondering why common optimization techniques are not working with these two constraints for a linear objective function with a boundary solution.

Answer 1

To enforce the non-negativity constraint, let $x =: t^2$. To enforce the strict inequality constraint $x \leq c$, introduce a slack variable $s$ such that $t^2 + s^2 = c$. We then have the following QCQP

$$\begin{array}{ll} \text{maximize} & -t^2\\ \text{subject to} & t^2 + s^2 = c\end{array}$$

which can be rewritten as follows

$$\boxed{\begin{array}{ll} \text{minimize} & t^2\\ \text{subject to} & t^2 + s^2 = c\end{array}}$$

Define the Lagrangian

$$\mathcal L (t, s, \lambda) := t^2 + \lambda (t^2 + s^2 - c)$$

Taking the partial derivatives and finding where they vanish,

$$\begin{array}{rl} (1 + \lambda) t &= 0\\ \lambda s &= 0 \\ t^2 + s^2 &= c\end{array}$$

which produces two solutions

• $\color{blue}{(t, s, \lambda) = (0, \pm \sqrt c, 0)}$, which corresponds to $\color{blue}{x = 0}$, where the minimum is attained.

• $\color{blue}{(t, s, \lambda) = (\pm \sqrt c, 0,-1)}$, which corresponds to $\color{blue}{x = c}$, where the maximum is attained.

Answer 2

We have the following linear program (LP) in $x \in \mathbb R$

$$\begin{array}{ll} \text{maximize} & -x\\ \text{subject to} & 0 \leq x \leq c\end{array}$$

where $c > 0$. Rewriting the LP above in minimization form,

$$\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & 0 \leq x \leq c\end{array}$$

Introducing a (nonnegative) slack variable $s \in \mathbb R$

$$\begin{array}{ll} \text{minimize} & x\\ \text{subject to} & x + s = c\\ & x, s \geq 0\end{array}$$

Let $\color{blue}{x_1 := \frac{x}{c}}$ and $\color{blue}{x_2 := \frac{s}{c}}$. Hence, we have the following LP

$$\begin{array}{ll} \text{minimize} & c x_1\\ \text{subject to} & x_1 + x_2 = 1\\ & x_1, x_2 \geq 0\end{array}$$

whose feasible region is the $1$-simplex, i.e., the line segment whose endpoints are $(1,0)$ and $(0,1)$. Since $c > 0$, the minimum is attained at $(x_1, x_2) = (0,1)$, which corresponds to $\color{blue}{x = 0}$ and $\color{blue}{s = c}$.