# Feasibility and boundedness of non-linear programming

In linear programming, we have the following results:

• primal problem infeasible --> dual problem infeasible or unbounded
• dual problem infeasible --> primal problem infeasible or unbounded
• primal problem unbounded --> dual problem infeasible
• dual problem unbounded --> primal problem infeasible

For a non-linear convex optimization problem, the last 2 items still hold, since the weak duality $d^* \le p^*$ ($d^*$ is dual optimal and $p^*$ is primal optimal).

Then, for a non-linear programming problem, do the first 2 items hold?

• Have you considered that constraint qualifications are needed in nonlinear programmng duality theory but not in LP duality theory? – Brian Borchers Dec 19 '17 at 18:47
• @BrianBorchers That is exactly what confused me. For a convex problem, if the Slater's condition is satisfied (of course this requires the primal problem to be feasible), then $d^* = p^*$, making the dual problem feasible and bounded. But what if Slater's condition not satisfied? – Alexander Zhang Dec 21 '17 at 11:54
• Slaters condition can be satisfied in a problem which is primal unbounded and dual infeasible. The point is that any counterexample will have to be one where Slater's condition is not satisfied and yet the primal objective is bounded. – Brian Borchers Dec 21 '17 at 17:23

Here's an example involving a primal-dual pair of semidefinite programming problems in which the primal has multiple optimal solutions but the dual is infeasible.

Our SDP primal-dual pair has the primal problem:

$\min \mbox{tr}(CX)$

subject to

$\mbox{tr}(A_{i}X)=b_{i}$, $i=1, 2, \ldots, m$

$X \succeq 0$

with the dual problem:

$\max b^{T}y$

subject to

$\sum_{i=1}^{m} y_{i}A_{i} + Z = C$

$Z \succeq 0$.

Consider the primal-dual pair with

$C=\left[ \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]$

$A_{1}=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 \end{array} \right]$

$b_{1}=0$

$A_{2}=\left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]$

$b_{2}=0$

Since $X \succeq 0$, we must have $X_{i,i} \geq 0$, $i=1, 2, 3, 4$. From the second primal constraint, $X_{1,1}+X_{3,3}=0$, so $X_{1,1}=0$ and $X_{3,3}=0$. From the first primal constraint, $X_{2,2}=X_{4,4} \geq 0$. If $X_{i,i}=0$ and $X$ is positive semidefinite, then $X_{i,j}=X_{j,i}=0$. Thus the feasible solutions to the primal problem are of the form:

$X=\left[ \begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & X_{2,2} & 0 & X_{2,4} \\ 0 & 0 & 0 & 0 \\ 0 & X_{4,2} & 0 & X_{4,4} \end{array} \right]$

where $X_{2,2}=X_{4,4}\geq 0$.

Note that all of these primal feasible solutions are singular matrices. Thus we have no solutions that are strictly feasible with respect to the positive semidefiniteness constraint and Slater's condition is not satisfied.

Because $C$ has $0$ entries in the relevant positions, all solutions of this form have the primal optimal objective function value of $0$.

Next, consider the dual constraints

$y_{1}A_{1}+y_{2}A_{2}+Z=C$

$Z \succeq 0$.

Since the (1,2) and (2,1) entries in $A_{1}$ and $A_{2}$ are 0, we must have $Z_{1,2}=Z_{2,1}=1$. Since $Z$ is positive semidefinite, we must have $Z_{1,1} > 0$ and $Z_{2,2}>0$ (in fact, $Z_{1,1}Z_{2,2} \geq 1$.) Note that these are strict inequalities! From the (2,2) position in the dual constraints, we have $y_{1}+Z_{2,2}=C_{2,2}=0$. Thus $y_{1}<0$.

From the (4,4) position in the dual constraint, we have $-y_{1}+Z_{4,4}=C_{4,4}=0$. However, since $Z$ is positive semidefinite we must also have $Z_{4,4} \geq 0$. We can't simultaneously have $-y_{1}>0$ and $Z_{4,4} \geq 0$ and $-y_{1}+Z_{4,4}=0$. Thus the dual problem is infeasible.