Minimize $z=2x_1+3x_2-x_1^2-2x_2^2$ subject to $x_1+3x_2\le 6$, $5x_1+2x_2\le 10$, and $x_1,x_2\ge 0$

Question

How can we minimize $z=2x_1+3x_2-x_1^2-2x_2^2$ subject to $x_1+3x_2\le 6$, $5x_1+2x_2\le 10$, and $x_1,x_2\ge 0$?

I need to know the steps to solve or at least the guidelines as I am really new to nonlinear equations and I am trying this on my own.

Please place your latex code in between $ $ signs. You can get help if you write your partial solution or what you tried. — Ram, Jan 04 '13 at 09:18
Did you want to minimize the expression: $2x_1+3x_2-x_1^2-2x_2^2$.? What is $z$? — Tomás, Jan 04 '13 at 10:24
Well ok. One way to solve your problem is by using this :http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions — Tomás, Jan 04 '13 at 13:27

score 2 · Answer 1 · answered Jan 11 '13 at 07:55

The constraints describe a closed region bounded by a quadrilateral with vertices $$(0,0),\ (0,2),\ (2,0),\ (18/13,20/13).$$ The objective function, using $x,y$ for your $x_1,x_2$, is $$z=2x+3y-x^2-2y^2.$$ The standard technique for such problems is to find the critical point(s) of $z$ which lie in the interior of the region, and then the min/max must occur either at such a critical point, or else at a boundary point of the constraint region.

NOTE: critical points are where both partials of $z$ w.r.t $x,y$ are zero, in case that idea is new to you.

This $z$ has one critical point at $(x,y)=(1,3/4)$ where $z=17/8$, but that isn't the min since at $(0,0)$ we have $z=0$. So the min is on the boundary.

The next step is to make up functions describing each segment on the boundary, plug each one into the $z$ formula and minimize. I won't do this part, but note that at $(x,y)=(0,2)$ we have $z=-2$, and at least this is the min among the vertices of the quadrilateral. There may be a smaller value along one of the sides of the quadrilateral.

score 1 · Answer 2 · answered Jan 11 '13 at 09:26

This are just some thoughts. You can refer to coffemath's answer for an analytical approach. This is from an optimization point of view.

Your problem can be re-written as \begin{align} \min_{\mathbf{x}~\in~R^2}~&\mathbf{x}^T\mathbf{Q}\mathbf{x}+\mathbf{r}^T\mathbf{x} \\~subject~to~&\mathbf{Ax\leq b} \\ &\mathbf{x\geq 0} \end{align}

where \begin{align} \mathbf{ x = \begin{bmatrix} \textit{x}_1 \\ \textit{x}_2 \end{bmatrix}~~Q = \begin{bmatrix}-1 & 0 \\ 0 & -2\end{bmatrix}~~r = \begin{bmatrix}2 \\ 3 \end{bmatrix}~~A = \begin{bmatrix}1 & 3 \\ 5 & 2\end{bmatrix}~~b = \begin{bmatrix}6 \\ 10 \end{bmatrix} } \end{align}

This is the well-known Quadratic Programming with linear inequality constraints which you can find in many textbooks on optimization.

Minimize $z=2x_1+3x_2-x_1^2-2x_2^2$ subject to $x_1+3x_2\le 6$, $5x_1+2x_2\le 10$, and $x_1,x_2\ge 0$

2 Answers2