Question

A quadratic programming problem seeks to maximize a quadratic objective function (with terms like $\mathbf{3}{\mathit{x}}_{\mathbf{1}}^{\mathbf{2}}\mathbf{}\mathbf{}\mathit{o}\mathit{r}\mathbf{}\mathbf{}\mathbf{5}{\mathit{x}}_{\mathbf{1}}{\mathit{x}}_{\mathbf{2}}$) subject to a set of linear constraints. Give an example of a quadratic program in two variables x₁, x₂ such that the feasible region is nonempty and bounded, and yet none of the vertices of this region optimize the (quadratic) objective.

Short answer

The required better fit example is shown below:

max x₁x₂ subject to

$\begin{array}{rcl}{x}_1+x_2& \le & 1\\ x_1,x_2& \ge & 0\end{array}$.

Step-by-step solution

Consider an example

Consider the maximum condition $x_1{x}_2$.

Subject to, $\begin{array}{rcl}{x}_1+x_2& \le & 1\\ x_1,x_2& \ge & 0\end{array}$.

Solve the quadratic programming

It is known that, maxx₁x₂ subject to

$\begin{array}{rcl}{x}_1+x_2& \le & 1\\ x_1,x_2& \ge & 0\end{array}$.

The constraints can be written as,

$$\begin{gathered} g_1=-x_1-x_2+1\ge 0 \\ {g}_2=x_1\ge 0 \\ {g}_3=x_2\ge 0 \end{gathered}$$

It can be easily observed that the maximum is obtained at the point $(x_1,x_2)=\left(\frac{1}{2},\frac{1}{2}\right)$, which implies that,

$\begin{array}{rcl}{x}_1{x}_2& =& \frac{1}{2}.\frac{1}{2}\\ & =& \frac{1}{4}\end{array}$

Where the vertices of the feasible region are (0,0),(1,0),(0,1).