non-convex quadratic with only one quadratic constraint?

Question

I have a non-convex optimization problem in the form: \begin{align} \min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr \text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq \frac{1}{n-n_m}, \xi \geq 0 , \xi_i \geq 1-a_i^\mathsf{T} \eta\cr \end{align} In Boyd and Vandenberghe's Convex Optimization, Appendix B (p. 653), it is said that non-convex quadratic with only one quadratic constraint has strong duality, i.e. you can find it's dual and then find the optimal of the dual and it is equal to non-convex quadratic global optimal.

My question is : Can I do this procedure for the above problem and how? Is it the best method for solving the above problem with respect to $b,\xi$?

Answer 1

Following the derivation in Section B.1 of Boyd and Vandenberghe, it seems plausible that you could solve the SDP dual of your primal to obtain the optimal objective function value. You could also solve the dual of the dual, which is an SDP relaxation of your primal problem.

Following Boyd's notation, suppose the primal variables of your problem are denoted by the vector $x$, and the decision variables of the SDP relaxation (i.e., the dual of the dual) are denoted $X$. There are two cases:

1. An optimal value of $X$ has the form $vv^{T}$; then $v$ is an optimal solution of the nonconvex primal.
2. All optimal values of $X$ cannot be expressed in the form $vv^{T}$ for any $v$, in which case it is not possible to recover a primal optimal solution from the SDP relaxation.

In the second case, all is not lost: by strong duality, the optimal objective function value of the SDP relaxation equals the optimal objective function value of the primal. This observation is useful in the following strategy:

• Solve the SDP relaxation, which gives you an optimal objective function value. This operation can be done using an SDP solver, which is theoretically efficient, and practical with current solvers if your instances are not too large.
• Supply this optimal objective function value to a global optimization solver (e.g., GLOMIQO, BARON, Couenne, Bonmin, etc.). These solvers operate on the principle of generating sequences of subproblems that generate lower and upper bounds on the optimal objective function value; in the process, they also yield feasible solutions (which are used for upper bounds).
• Since you already know the optimal objective function value from the SDP relaxation, you can calculate the optimality gap of any upper bound exactly. This calculation is a significant improvement over the estimates of the optimality gap given by these solvers, which are usually calculated by taking the difference of the best upper and lower bounds.
• Also, since you already know the optimal objective function value from the SDP relaxation, you could potentially save some work in the lower bounding problems, because you do not need lower bounds.

The situation you describe, where you can determine efficiently the optimal solution value, but not necessarily where it is attained, isn't a case I normally see treated explicitly in a solver, because it's rare. Normally, the optimal objective function value isn't known in advance, and can't be determined easily. However, one way to incorporate this information in a formulation would be to include it in the constraints as a lower bound.

Finally, regarding linearization techniques, you could look at work by Misener and Floudas in the context of global optimization, which would potentially reduce your problem to solving a bunch of mixed-integer linear programs.

Answer 2

$b$ is bang-bang, ie $b$ puts 1 on where $\xi$ is smallest. So for any fixed $\eta$, the $b, \xi$ part is known

$$b^\top\xi=\min(\max(1-a_i^\top\eta,0))$$

The problem reduces to an unconstrained problem on $\eta$