0

everyone. Just bump into one nonconvex optimization problem. Looks simple, but I dont know how to solve it. The problem is

$\max_{a,b,\tau} \tau$

$\text{s.t.} \tau\leq \tau_{1}(a,b),$

$\tau\leq \tau_{2}(a,b),$

$a_{\text{min}}\leq a \leq a_{\text{max}},$

$b_{\text{min}}\leq b \leq b_{\text{max}},$

where $\tau_{1}(a,b)$ and $\tau_{2}(a,b)$ are not convex functions in terms of either $a$ or $b$.

Initially, I think maybe I can make use of duality and get its Lagrangian dual problem. Since the dual problem is always convex, I can use some off-the-shelf algorithms to solve dual problem. But I realize that what I can find is still a local optimal solution, not the global one. I know I can work on something on $\tau_{1}$ and $\tau_{2}$ (e.g., whether they are monotonically increasing functions of $a$ or $b$), but I am wondering is there any general way to solve such nonconvex problem? Thank you.

Holt Zerng
  • 15

1 Answers1

0

First of all, it is hard to understand your main question. 'Simple but not simple' is not reflecting your wish to solve a nonconvex problem. I assume your variables are continuous, e.g. $\tau \in \mathbb{R}$, so that the last two constraints will not be combinatorial constraints. I conclude they are just continuous simple constraints.

You have non-convex constraints, $\tau \leq \tau_i(a,b) $ which are the main problems. You can end up at a local minimum, be careful about it. And you are planning to use Lagrangian duality in a non-convex problem. That's another issue. You can just get a bound on the optimal value, where strong duality will most probably not hold.

What I suggest is you to write more details about the functions $\tau_i$ and try to analytically derive something. Search for convex hulls, SDP relaxations or whatever is relevant to your functions.

If you want to solve a specific problem, instead of analytically deriving a solution, you can always try to solve in Artelys Knitro solver. It is doing pretty well in dirty non-linear models.

independentvariable
  • 861
  • 1
    First of all, thank you for the feedback and sorry about the ambiguity of the question. I have dug more details about function $\tau_{i}$ and find out that I can find a convex optimization equivalent to the original nonconvex problem. By using some numerical methods, such as subgradient algorithm and interior point method, I can find the solution. – Holt Zerng Aug 26 '18 at 15:47
  • 1
    The initial purpose of asking such question is to find some common methods or numerical algorithms to solve nonconvex optimization problem. You have pointed out that Artelys Knitro solver can be helpful, and I will try to use such solver to verify the results obtained form the equivalent convex problem. Thank you. – Holt Zerng Aug 26 '18 at 15:52