duality and nonlinear optimization

Question

If at a feasible point (x,y) we get p*=d* that means the point is optimal.

Looking at the example: min (-x-y)
subject to: xy<=4
0<=x<=4 0<=y<=8 I define X={(x,y)| 0<=x<=4, 0<=y<=8} and looking for the minimum of the Lagrangian (with one lamda for xy-4<=0) and maximum of the dual function (lamda = 0.5) I get x=y=2 which results in p*=-4=d*. But the feasible point x=0.5, y=8 yields p*=-8.5 < -4 !! What is wrong here?

Cesareo · Answer 1 · 2018-05-05T13:30:13.277

0

Consider the introduction of slack variables like $\epsilon$ With this additional variable the probem can be formulated as

$$ L(x,y,\lambda,\epsilon) = -(x+y)+\lambda(x y - 4-\epsilon^2) $$

The stationary pints can be obtained by solving

$$ \left\{ \begin{array}{rcl} \lambda y & = & 1\\ \lambda x & = & 1\\ x y -4 & = & \epsilon\\ \lambda \epsilon & = & 0 \end{array} \right. $$

Solving we get

$x=2,y=2,\lambda = 1/2,\epsilon = 0$ which indicates that the stationary point is at the boundary ($\epsilon = 0$)

but this is not the solution because $\lambda > 0$ indicating that the objective function and the restriction function grow in the same direction hence the problem has an unbounded solution

For a minimum problem with an active restriction we need

$$ -(-1,-1) + \lambda (2,2) = 0 \Rightarrow \lambda < 0 $$

edited May 05 '18 at 13:30

answered May 05 '18 at 09:11

Cesareo

33,252

The function (-x-y) and the function (xy-4) at the point (2,2) grow in exactly opposite direction. Can a solution be unbounded in a finite region? – hana paz May 05 '18 at 13:11
Minimization requires that $-(-1,-1) + \lambda(2,2) = 0$ which implies on $\lambda < 0$ to be active the restriction. – Cesareo May 05 '18 at 13:27
gradient of f(x,y) is (-1,-1). why -(-1,-1)? – hana paz May 06 '18 at 04:34
Because it is a minimization problem. – Cesareo May 06 '18 at 08:19

duality and nonlinear optimization

1 Answers1