SU-EE364A MAR102026 — Jemoka Knowledge Base

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\left(x\right) = f\left(x\right) - g\left(x\right) \end{equation}

for convex f\left(x\right) and g\left(x\right). some examples a convex quadratic, except the P in \left(\frac{1}{2}\right) x^{T}Px is not PSD; we express this in terms of P = P_{\text{psd}} - P_{\text{nsd}}. And thus we can get: \left(\frac{1}{2}\right)x^{T}P_{\text{psd}} x - \left(\frac{1}{2}\right)x^{T}P_{\text{nsd}}x majorization Taylor approximation: \hat{g}\left(z\right) + \nabla g\left(z\right)^{T}\left(x-z\right) \leq g\left(x\right) Consider:

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

(setq debug-on-error t) 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}\left(x; x^{k}\right) = \arg\min_{x}\left(f_{x}- \hat{g}\left(x\chi^{k}\right)\right) \end{equation}

we do it in sequence: minimize the majorizer, and remajorize. dicipline concvex programming For:

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

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

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

which is a linearized the concave parts.