A two-dimensional toy optimization problem

As a toy example of an optimization problem in two variables, consider the problem

 displaystylemin_x : 0.9 x_1^2 - 0.4 x_1x_2 - 0.6x_2^2 - 6.4 x_1 - 0.8 x_2  ~:~ -1 le x_1 le 2, ;; 0 le x_2 le 3 .

(Note that the term ‘‘subject to’’ has been replaced with the shorthand colon notation.)

The problem can be put in standard form

 p^ast := displaystylemin_x : f_0(x) ~:~ f_i(x) le 0, ;; i=1,ldots, m ,

where:

  • the decision variable is (x_1,x_2) in mbox{bf R}^2;

  • the objective function f_0 : mbox{bf R}^2 rightarrow mbox{bf R} , takes values

 f_0(x) := 0.9 x_1^2 - 0.4 x_1x_2 - 0.6x_2^2 - 6.4 x_1 - 0.8 x_2;
  • the constraint functions f_i : mbox{bf R}^n rightarrow mbox{bf R}, i=1,2,3,4 take values

 begin{array}[t]{rcl} f_1(x) &:=& -x_1 -1 ,  f_2(x) &:=& x_1 -2 ,  f_3(x) &:=& -x_2 ,  f_4(x) &:=& x_2-3 . end{array}
  • p^ast is the optimal value, which turns out to be p^ast = -10.2667.

  • The optimal set is the singleton mathbf{X}^{rm opt} = {x^{ast}}, with

 x^{ast} = left( begin{array}{c} 2.00  1.33 end{array} right) .

Since the optimal set is not empty, the problem is attained.

We can represent the problem in epigraph form, as

 displaystylemin_{x,t} : t ~:~ t ge 0.9 x_1^2 - 0.4 x_1x_2 - 0.6x_2^2 - 6.4 x_1 - 0.8 x_2, ;; -1 le x_1 le 2, ;; 0 le x_2 le 3 .
alt text 

Geometric view of the toy optimization problem above. The level curves (curves of constant value) of the objective function are shown. The problem amounts to find the smallest value of t such that t = f_0(x) for some feasible x. The plot also shows the unconstrained minimum of the objective function, located at hat{x} = (4,2). An epsilon-sub-optimal set for the toy problem above is shown (in darker color), for epsilon = 0.9. This corresponds to the set of feasible points that achieves an objective value less or equal than p^ast+epsilon.