Feasibility and boundedness of non-linear programming

Question

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?

Answer 1

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.