Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints

Abstract

We consider in this paper a separable and nonconvex quadratic program (QP) with a quadratic constraint and a box constraint that arises from application in optimal portfolio deleveraging (OPD) in finance and is known to be NP-hard. We first propose an improved Lagrangian breakpoint search algorithm based on the secant approach (called ILBSSA) for this nonconvex QP, and show that it converges to either a suboptimal solution or a global solution of the problem. We then develop a successive convex optimization (SCO) algorithm to improve the quality of suboptimal solutions derived from ILBSSA, and show that it converges to a KKT point of the problem. Second, we develop a new global algorithm (called ILBSSA-SCO-BB), which integrates the ILBSSA and SCO methods, convex relaxation and branch-and-bound framework, to find a globally optimal solution to the underlying QP within a pre-specified $\epsilon$-tolerance. We establish the convergence of the ILBSSA-SCO-BB algorithm and its complexity. Preliminary numerical results are reported to demonstrate the effectiveness of the ILBSSA-SCO-BB algorithm in finding a globally optimal solution to large-scale OPD instances.

Appendix: Proofs of Propositions

Proof of Proposition 1

Since the feasible set of problem (1) is compact, there exists an optimal solution $y^*=(y^*_1,\ldots ,y^*_m)^T$. Now suppose that $g(y^*)< 0$. Denote

Clearly, $0\not \in I(y^*)$. It is thus easy to see that the gradients $\nabla g_i(y^*)$, $i\in I(y^*)$ are linear independent. According to the first order optimality condition, there exists $\mu ^*=(\mu ^*_0,\mu ^*_1,\ldots ,\mu ^*_m,\mu ^*_{m+1},\ldots ,\mu ^*_{2m})^T\ge 0$ such that

Since $g(y^*)< 0$, we have $\mu ^*_0=0$. Thus, equality (52a) becomes

$$\begin{aligned}{} & {} 2\delta _iy^*_i+\xi _i+\mu ^*_i-\mu ^*_{m+i}=0,~~i=1,\ldots ,m. \end{aligned}$$

(53)

Since $\alpha <\beta$, it is easy to see from (52c) and (52d) that $\mu ^*_i$ and $\mu ^*_{m+i}$, $1\le i \le m$, cannot be positive simultaneously. We consider the following cases:

Case (i): $\mu ^*_i=0$, $\mu ^*_{m+i}\ne 0$. From (52d), $y^*_i=\alpha _i$. If $1\le i \le r$, then by condition (A1), $2\delta _i\alpha _i+\xi _i<0$. If $r+1\le i \le m$, then by condition (A1), $\delta _i\ge 0$ and $2\delta _i\beta _i+\xi _i<0$, which by $\alpha _i<\beta _i$, implies $2\delta _i\alpha _i+\xi _i<0$. It then follows from (53) that $\mu ^*_{m+i}=2\delta _i\alpha _i+\xi _i<0$, which contradicts to the requirement that $\mu ^*\ge 0$.

Case (ii): $\mu ^*_i=\mu ^*_{m+i}=0$. If $r+1\le i \le m$, then by condition (A1), $\delta _i\ge 0$ and $2\delta _i\beta _i+\xi _i<0$. Note that $y^*\le \beta$. From (53), we follow that $0=2\delta _i y^*_i+\xi _i\le 2\delta _i\beta _i+\xi _i<0$, which gives a contradiction. If $1\le i \le r$, then by condition (A1), $\delta _i<0$ and $2\delta _i\alpha _i+\xi _i<0$. Since $y^*\ge \alpha$, we follow from (53) that $0=2\delta _i y^*_i+\xi _i\le 2\delta _i\alpha _i+\xi _i<0$, which also gives a contradiction.

Since for any $1\le i\le m$, the above cases are not possible, we must have $\mu ^*_i\ne 0$, $\mu ^*_{m+i}= 0$ for all $1\le i\le m$. Then from (52c), $y^*=\beta$. Thus, by condition (A3), $0\ge {g}(y^*)={g}(\beta )>0$, this is a contradiction. $\square$

Proof of Proposition  6

The proof is similar to the proof of Proposition 1. We mention here the major differences in the proof of Proposition 1. We first have expressions (52a)-(52d), where $g(y^*)$ is replaced with $g_z(y^*)$. We then replace (53) by

By condition (A1), $\delta _i<0$ and $2\delta _i\alpha _i+\xi _i<0$ for $i=1,\ldots ,r$. Note that $z_i\in [\alpha _i,\beta _i]$. If $\mu ^*_i=0$, $\mu ^*_{m+i}\ne 0$, then it follows from $\mu ^*\ge 0$ and (54a) that

$$\begin{aligned} 0<\mu ^*_{m+i}=2\delta _i z_i+\xi _i\le 2\delta _i\alpha _i+\xi _i<0 \end{aligned}$$

for $i=1,\ldots ,r$, which gives a contradiction.

If $\mu ^*_i=\mu ^*_{m+i}=0$, then for $i\in \{1,\ldots ,r\}$, from (54a), we get $z_i=-\frac{\xi _i}{2\delta _i}<\alpha _i$ due to (A1), which contradicts to the requirement that $z_i\ge \alpha _i$.

If $\mu ^*_i\ne 0$, $\mu ^*_{m+i}= 0$ for all $1\le i\le m$. Then from (52c), $y^*_i=\beta _i$, $i=1,\ldots ,m$. Thus $g_z(y^*)\le 0$ implies

$$\begin{aligned} 0\ge & {} g_z(y^*)=\sum ^m_{i=s+1}\left( \theta _i\beta _i^2+\eta _i\beta _i\right) + \sum _{i=1}^s \left[ \theta _i(2z_i\beta _i -z_i^2)+\eta _i\beta _i\right] +\sigma \\\ge & {} \sum ^m_{i=s+1}\left( \theta _i \beta _i^2+\eta _i\beta _i\right) + \sum _{i=1}^s \left( \theta _i \beta _i^2+\eta _i\beta _i\right) +\sigma =g(\beta )>0, \end{aligned}$$

where the second inequality follows from the fact that $\beta _i^2\ge 2z_i\beta _i -z_i^2$ by (19) and $\theta _i<0$ for $i=1,\ldots ,s$ by (A2), while the last inequality is due to (A3). This gives a contradiction. $\square$

Proof of Proposition 8

The proof is similar to the proof of Proposition 6. We mention here the major differences in the proof of Proposition 6. We first have expressions (52a)-(52d), where $g(y^*)$ is replaced with $g_{[l, u]}(y^*)$, and

$$\begin{aligned}{} & {} g_i(y)=y_i-u_i,~i=1,\ldots ,r,\quad g_i(y)=y_i-\beta _i,~ i=r+1,\ldots ,m,\\{} & {} g_{m+i}(y)=-y_i+l_i,~i=1,\ldots ,r,\quad g_{m+i}(y)=-y_i+\alpha _i,~ i=r+1,\ldots ,m. \end{aligned}$$

We then replace (54a) by

$$\begin{aligned} \delta _i (l_i+u_i)+\xi _i+\mu ^*_i-\mu ^*_{m+i}=0,~~i=1,\ldots ,r. \end{aligned}$$

(55)

By condition (A1), $\delta _i<0$ and $2\delta _i\alpha _i+\xi _i<0$ for $i=1,\ldots ,r$. Note that $\alpha _i\le l_i\le u_i\le \beta _i$. If $\mu ^*_i=0$, $\mu ^*_{m+i}\ne 0$, then it follows from $\mu ^*\ge 0$ and (55) that

$$\begin{aligned} 0<\mu ^*_{m+i}=\delta _i (l_i+u_i)+\xi _i\le 2\delta _i\alpha _i+\xi _i<0 \end{aligned}$$

for $i=1,\ldots ,r$, which is a contradiction.

If $\mu ^*_i=\mu ^*_{m+i}=0$, then for $i\in \{1,\ldots ,r\}$, from (55), we get $l_i+u_i=-\frac{\xi _i}{\delta _i}<2\alpha _i$ due to (A1), which contradicts to the fact that $l_i+u_i\ge 2\alpha _i$.

If $\mu ^*_i\ne 0$, $\mu ^*_{m+i}= 0$ for all $1\le i\le m$. Then from (52c), $y^*_i=u_i$, $i=1,\ldots ,r$, $y^*_i=\beta _i$, $i=r+1,\ldots ,m$. From (A2) and $(\textrm{A2})^\prime$, $\theta _i<0$ and $2\theta _i\alpha _i+\eta _i<0$ for $i=1,\ldots ,s$, and $\theta _i\ge 0$ and $2\theta _i\beta _i+\eta _i<0$ for $i=s+1,\ldots ,r$. We then infer that the function $\theta _i y_i^2+\eta _iy_i$ is decreasing of $y_i$ over $[\alpha _i,\beta _i]$ for $i=1,\ldots ,r$. Note that $\alpha _i\le u_i\le \beta _i$ for $i=1,\ldots ,r$. Therefore, by $g_{[l, u]}(y^*)\le 0$ and (A3), we follow that

$$\begin{aligned} 0\ge & {} g_{[l, u]}(y^*)= \sum ^m_{i=r+1}\left( \theta _i\beta _i^2+\eta _i\beta _i\right) + \sum _{i=1}^r \left( \theta _iu_i^2+\eta _iu_i\right) +\sigma \\\ge & {} \sum ^m_{i=r+1}\left( \theta _i \beta _i^2+\eta _i\beta _i\right) + \sum _{i=1}^r \left( \theta _i \beta _i^2+\eta _i\beta _i\right) +\sigma =g(\beta )>0. \end{aligned}$$

This gives a contradiction. $\square$