4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Just to make sure I understand your constraints, they're all linear, correct? $\endgroup$ – Geoff Oxberry Jun 3 '15 at 0:02
  • $\begingroup$ Yes. They are all linear. Do you think it is incorrect? $\endgroup$ – user85361 Jun 3 '15 at 6:36
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. we can define a new variable by appending $\xi$ and $b$ and then define a nonconvex quadratic SDP. What do you mean by a Gram matrix? $\endgroup$ – user85361 Jun 3 '15 at 6:45
  • $\begingroup$ If I cannot use this method, what do you think of linearization technique. i.e. make concave part of the function linear? $\endgroup$ – user85361 Jun 3 '15 at 6:51
  • $\begingroup$ Boyd concatenates the primal variables into a single vector $x$, and denotes the SDP relaxation decision variables by $X$. His condition is that it must be possible to find an $x$ such that the solution of the SDP can be expressed as $X=xx^T$. $\endgroup$ – Geoff Oxberry Jun 3 '15 at 7:15
  • $\begingroup$ I mean, I suppose you could try some sort of piecewise linear envelope representation with a branch-and-bound routine, like Misener, Floudas, and Gounaris. The utility of Boyd's work when paired with solvers like GLOMIQO, BARON, Couenne, Bonmin, etc., is that you could use an SDP solver to get the optimal objective function value, which gives you a certificate for your optimality gap that will probably be better than the default choices in those algorithms (feasible points, IIRC). $\endgroup$ – Geoff Oxberry Jun 3 '15 at 7:26
  • $\begingroup$ Your second comment is so complicated for me!. "The utility of Boyd's work... ". Could you explain a little more. Thank you very much. $\endgroup$ – user85361 Jun 3 '15 at 8:22
1
$\begingroup$

$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$

$\endgroup$
  • $\begingroup$ Thank you very much for your answer and sorry for forgetting to mention constraint on b. I edited the question. I just wanted the reader concentrate on non-convex part and not br bothered with details of constraints. I really appreciate if you kindly answer the edited question. $\endgroup$ – user85361 Jun 2 '15 at 16:01
  • $\begingroup$ That extra $b$ constraint doesn't involve $\xi$, so $b$ is still bang-bang, albeit a bit more involved. Basically the $b,\xi$ part is out of your optimisation $\endgroup$ – jf328 Jun 3 '15 at 8:16
  • $\begingroup$ Do you mean the same answer is correct for the edited constraints?. It seems true that $b_i$ becames large whenever $\xi_i$ is small. But constraints limit $b_i$. Do you mean this by bang-bang? How can I change it not to be bang-bang?. I like your term, "bang-bang" :). Thanks $\endgroup$ – user85361 Jun 3 '15 at 8:34
  • $\begingroup$ Think simply to minimise $x_1k_1+x_2k_2+\cdots$ where $L_i\leq x_i\leq M_i, \sum x = 1$. Then you sort $k$ ascending and allocate the maximum to $x_i$ corresponding to smallest $k_i$. $\endgroup$ – jf328 Jun 3 '15 at 9:39
  • $\begingroup$ Thank you very much. It's correct for this version of the problem. Your discussion helped me a lot. $\endgroup$ – user85361 Jun 4 '15 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.