I have an optimization problem in the form of:
$\min_x \quad u^Tx \\ s.t. \quad (x-\textbf{1/2})^2 - \vert x-\textbf{1/2}\vert \leq \textbf{-1/4}$.
Since the constrained of this problem is not convex, the standard convex programming methods cannot be applied. I learned that DC (difference of convex) programming and convex-concave programming (CCCP) can be used to solve this problem. However, I did understand their differences, or their capability to provide an algorithm (e.g., DCA) to converge to the global optimal solution.
Just to recap, I have two questions:
What are the differences of CCCP and DC programming, especially in terms of their convergence to the global optimal solution?
Are they convergent to the global optimal solution?!
Any help is appreciated!
Edit:
The shape of the constraint function is as below:
I am not sure whether I misunderstand OP's problem. To solve this problem, why not Dividing the constraint into two parts such that it becomes two convex optimization problems: \begin{equation} \begin{array}{cl} {\min} & {u^T x} \\ {\text{s.t.}} & {(x-\frac{1}{2})^2+(x-\frac{1}{2}) \leq -\frac{1}{4}} \\ {} & {x \leq \frac{1}{2}} \end{array} \end{equation} and \begin{equation} \begin{array}{cl} {\min} & {u^T x} \\ {\text{s.t.}} & {(x-\frac{1}{2})^2-(x-\frac{1}{2}) \leq -\frac{1}{4}} \\ {} & {x \ge \frac{1}{2}} \end{array} \end{equation} Then solve these two convex optimization problem at the same time, and the optimal solution of original problem is the lower objective value.
For DC programming and CCCP, in my humble opinion, I think these two method is the same method, although the first one analyze the problem in dual perspective and the second one describe the method in a more friendly way. In addition, the author of DC programming discusses some more DC decomposition methods.
And both DC programming and CCCP could not converge to global optimal solution. They are both convergent globally, that means they can converge for any initial point.