convex-concave problems

Heuristic method for solving a specific type of non-convex problem. Solves a small sequence of convex problems.

difference-of-convex function

For:

\begin{equation} h\qty(x) = f\qty(x) - g\qty(x) \end{equation}

for convex \(f\qty(x)\) and \(g\qty(x)\).

some examples

• a convex quadratic, except the \(P\) in \(\qty(\frac{1}{2}) x^{T}Px\) is not PSD; we express this in terms of \(P = P_{\text{psd}} - P_{\text{nsd}}\). And thus we can get: \(\qty(\frac{1}{2})x^{T}P_{\text{psd}} x - \qty(\frac{1}{2})x^{T}P_{\text{nsd}}x\)

majorization

Taylor approximation:

\(\hat{g}\qty(z) + \nabla g\qty(z)^{T}\qty(x-z) \leq g\qty(x)\)

Consider:

\begin{equation} h\qty(x,z) = f\qty(x)- \hat{g}\qty(x; z) \end{equation}

This is a convex majorizer (convex function above og, tight at ponit \(z\)).

convex-concave procedure

Iterative method

\begin{equation} x^{k+1} = \arg\min_{x} \hat{h}\qty(x; x^{k}) = \arg\min_{x}\qty(f_{x}- \hat{g}\qty(x\chi^{k})) \end{equation}

we do it in sequence: minimize the majorizer, and remajorize.

dicipline concvex programming

For:

\begin{align} \min_{x}\quad & f_{0}\qty(x) - g_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) - g_{i}\qty(x) \leq 0, i = 1 … m \end{align

we can solve for $x^{k+1}$ the next iteration via:

\begin{align} \min &f_{0}\qty(x) - \hat{g}^{0}\qty(x; x^{k}) \\ \textrm{s.t.} \quad & f_{i}\qty(x) - \hat{g}_{i}\qty(x; x^{k}) \leq 0 \end{align}

which is a linearized the concave parts.