Example 1

This is example 1.6 on page 21 of Introduction to Linear Optimization (Bertsimas and Tsitsiklis 1997, 27). Our aim is to minimize the function $-x_1-x_2$ subject to the following constraints:

\[\begin{align*} x_1+2x_2 \leq 3 \\ 2x_1+x_2 \leq 3 \\ x_1,\ x_2 \geq 0 \end{align*}\]

Visualizing the feasible set

First, we want to see what sorts of values the feasible set can take on. We begin by defining our objective function for later use:

#Objective function
obj.fun=function(x) -x[1] - x[2]

Next, we plot our constraints and determine which values of $x_1$ and $x_2$ fall into the feasible set. Note that both $x_1$ and $x_2$ are bounded above by $3$ and below by $0$ by the problem definition, so we restrict our attention to $x = (x_1,x_2) \in [0,3] \times [0,3]$.

We will place $x_1 \text{ and } x_2$ on the x and y axes, respectively. We draw lines between the intercepts of the constraints by noting that $x_1+2x_2=3$ at points on the line connecting $(0,1.5)$ and $(3,0)$. Likewise, we represent $2x_1+x_2=3$ by points on the line connecting $(1.5,0)$ and $(0,3)$. Since $x_1 \geq 0$ and $x_2 \geq 0$, the area between these lines and the axes represents the feasible set.

# setting up vertices for shading with polygon
x.vert=c(0,1.5,1,0)
y.vert = c(0,0,1,1.5)

plot(1,xlim=c(0,3),ylim=c(0,3),xlab="x1",ylab="x2",lty=2,lwd=1.5,
   main="feasible set for linear optimization problem")
lines(c(0,3),c(1.5,0),lwd=2,col="blue")
lines(c(0,1.5),c(3,0),lwd=2,col="blue")
polygon(x.vert,y.vert,col=rgb(1,0,0,0.5))
abline(0,-1,lty=4)
abline(1,-1,lty=4)
abline(2,-1,lty=4)
points(1,1,pch=19)
text(1.45,1,"optimal point (1,1)")
text(0.5,0.5,"feasible set")

The red shaded region represents the feasible set. The blue lines represent the two constraint inequalities.

Note that we want to minimize $-x_1-x_2$ which is equivalent to maximizing $x_1+x_2$ within the given constraints. It is clear from the plot that the point $(1,1)$ maximizes $x_1+x_2$ within the feasible set. Putting this into the original, we obtain $-x_1-x_2 = -1-1 = -2$, so $-2$ is the minimum.

Plotting this was not entirely straightforward. The textbook image is easier to read:

textbook image

In particular, I liked that the lines extended past the axes, and I thought the lines were well-labeled. That was fairly difficult for me to do in the base R plotting system. I’m sure these things can be done in the basic R plotting package. I will tackle that in a future post.

Optimizing with R’s built-in package

We conclude by quickly verifying the result we obtained through graphing by using R’s constrOptim() function.

Note that the gradient is $\nabla f(x)= \begin{pmatrix}-1\\-1\end{pmatrix}$. We choose a starting value of $\begin{pmatrix}0.1\\0.1\end{pmatrix}$ which is in the feasible set. In the constrOptim function, the constraints are defined such that ui %*% theta - ci >= 0. To put the constraints in this form, we define $\textbf{ui}=\begin{pmatrix}-2 & -1\\ -1 & -2\end{pmatrix}$ and $\textbf{ci}=\begin{pmatrix}-3\\-3\end{pmatrix}$. We these arguments, we use the constrOptim() function like so:

grad=function(x1,x2) c(-1,-1)
minim=constrOptim(theta=c(.01,.01),f=obj.fun,grad=grad,
            ui=rbind(-1*c(2,1),-1*c(1,2)),ci=-1*c(3,3))

And we obtain the following values for the minimizer and minimum.

## $par
## [1] 1 1

## $value
## [1] -2

This corresponds to what we obtained by plotting the constraints. My next post on linear optimization will look at another example and will attempt to generate a more informative plot.