Convexify the Non-convex's

---

# 🔄 Convexify the Non-convex's

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: Transformations** 🔄
- Change of Curvature
- Logarithmic & Reciprocal

**Part 2: Advanced Methods** 🧪
- Exponential Transformation
- Perspective Transformation

]
.pull-right[

**Part 3: Matrix & DC** 📐
- Matrix Inequalities
- DC Programming
- SDR

]
---

### 📚 Example: Convexifying a Simple Non-Convex Function

Consider the non-convex function:
$${\color{red} f(x)} = x^4 - 4x^2 + 4$$

**Transformation:**
Let $y = x^2$. The problem becomes:
$${\color{green} f(y)} = y^2 - 4y + 4$$

**Post-proccessing:**
$${\color{darkmagenta} x_\text{opt}} = \pm\sqrt{y_\text{opt} }$$

---

### 🔄 Change of curvature: square

**Original Problem:**
$${\color{red} x^2 } + {\color{red} y^2 } \geq 0.16 \quad \text{(non-convex)}$$

**Transformation:**
Let $x' = x^2$, $y' = y^2$. The problem becomes:
$${\color{green} x'} + {\color{green} y'} \geq 0.16, \quad x', y' \geq 0$$

**Post-proccessing:**
$${\color{darkmagenta} x_\text{opt}} = \pm\sqrt{x'_\text{opt} }, \quad {\color{darkmagenta} y_\text{opt}} = \pm\sqrt{y'_\text{opt} }.$$

---

### 🧩 Convex Relaxation Overview

.mermaid[
<pre>
graph LR
    A["Non-convex\nProblem"] --> B["Convex\nRelaxation"]
    B --> C["Solve Convex\nRelaxed Problem"]
    C --> D["Round or\nProject Back"]
    D --> E["Feasible\nSolution"]

style A fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
    style B fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style C fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440
    style D fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
</pre>
]

Key idea: Replace non-convex constraints with convex approximations.

---

### 🔄 Change of curvature: sine

**Original Problem:**
$${\color{red} \sin{x} } \leq 0.4, \quad 0 \leq x \leq \pi/2$$

**Transformation:**
$${\color{green} y} \leq 0.4, \quad 0 \leq y \leq 1$$

**Post-proccessing:**
$${\color{darkmagenta} x_\text{opt}} = \sin^{-1}(y_\text{opt}).$$

👉 Note that $\sin(\cdot)$ are monotonic concave functions in $(0, \pi/2)$.

---

### 🔄 Change of curvature: square

**Original Problem:**
$$0.3 \leq {\color{red} \sqrt{x} } \leq 0.4$$

**Transformation:**
$$0.09 \leq {\color{green} x} \leq 0.16 \, .$$

👉 Note that $\sqrt{\cdot}$ are **monotonic** **concave** functions in $(0, +\infty)$.

**Generalization:**
- Consider $|H(\omega)|^2$ (power) instead of $|H(\omega)|$ (magnitude). 🎚️
- Square root → Spectral factorization 🧩

---

### 📐 Logarithmic Transformation

**Original Problem:**

$$\pi \leq {\color{red} x / y} \leq \phi, \; x > 0, y > 0$$

**Transformation:**
Let $z' = \log(z)$. The problem becomes:

$$\pi' \leq {\color{green} x' - y'} \leq \phi'$$

**Post-proccessing:**

$${\color{darkmagenta} z_\text{opt}} = \exp(z'_\text{opt}).$$

**Generalization:**

- Geometric programming 🔗

---

### 🔁 Reciprocal Transformation

**Original Problem:**
$${\color{red} \log(x)} + 0.4 \leq 0, \; x > 0$$

**Transformation:**
Let $y = 1 / x$. The problem becomes:
$${\color{green} -\log(y)} + 0.4 \leq 0, \; y > 0 \, .$$

**Post-proccessing:**
$${\color{darkmagenta} x_\text{opt}} = y^{-1}_\text{opt}.$$

👉 Note that $\sqrt{\cdot}$, $\log(\cdot)$, and $(\cdot)^{-1}$ are monotonic functions.

---

### 🧮 Generalize to Matrix Inequalities

**Original Problem:**

$${\color{red} \log(\det X)} + \text{Tr}(X^{-1} C) \leq 0.3, \; X \succ 0$$

**Transformation:**
Let $Y = X^{-1}$. The problem becomes:
$${\color{green} -\log(\det Y)} + \text{Tr}(Y \cdot C) \leq 0.3, \; Y \succ 0$$

**Post-proccessing:**
$${\color{darkmagenta} X_\text{opt}} = Y^{-1}_\text{opt}.$$

---

### 🔄 Change of Variables Flow

.mermaid[
<pre>
graph TD
    A["Original Variable\nx (non-convex)"] --> B["Transformation\ny = g(x)"]
    B --> C["New Variable\ny (convex)"]
    C --> D["Solve in\ny-space"]
    D --> E["Inverse\nx = g^{-1}(y)"]
    E --> F["Optimal\nSolution x*"]

---

### ⚡ Exponential Transformation

### 📚 Example: Exponential Utility Functions

For problems involving exponential utility functions, an exponential transformation can be useful.

**Original Problem:**
$$\text{minimize} \quad -{\color{red} \exp(f(x))}$$

**Transformation:**
Let ${\color{green} y} = \exp(f(x))$. The problem becomes:
$$\text{minimize} \quad -{\color{green} y} \quad \text{subject to} \quad y = \exp(f(x))$$

This can help in transforming the problem into a convex form.

---

### 🔄 Change of Variables

### 📚 Example: Power Transformation

For certain power functions, a change of variables can help.

**Original Problem:**
$$
\text{minimize} \quad {\color{red} f(x)} = x^p \quad \text{for} \quad p \lt 1
$$

**Transformation:**
Let ${\color{green} y} = x^p$. The problem becomes:
$$\text{minimize} \quad {\color{green} y} \quad \text{subject to} \quad y = x^p$$

This can help in transforming the problem into a convex form.

---

### 🎭 Perspective Transformation 🤔

### 📚 Example: Perspective Function

For certain functions, applying a perspective transformation can help.

**Original Problem:**
$$\text{minimize} \quad \frac{{\color{red} f(x)}}{t}$$

**Transformation:**
Let ${\color{green} y} = \frac{x}{t}$. The problem becomes:
$$\text{minimize} \quad {\color{green} f(y)} \quad \text{subject to} \quad t = 1$$

This can help in transforming the problem into a convex form.

---

### 🔄 Change of variables

**Original Problem:**
$$(a +  b \cdot {\color{red} y}) x \leq 0, \; x > 0$$

**Transformation:**
Let $z = y \cdot x$. The problem becomes:
$$a \cdot x + b \cdot {\color{green} z} \leq 0, \; x > 0$$

**Post-proccessing:**
$${\color{darkmagenta} y_\text{opt}} = z_\text{opt} x^{-1}_\text{opt}$$

---

### 🧮 Generalize to matrix inequalities

**Original Problem:**
$$(A + B \cdot {\color{red} Y}) X + X (A + B \cdot {\color{red} Y})^T  \prec 0, \; X \succ 0$$

**Transformation:**
Let $Z = Y \cdot X$. The problem becomes:
$$A \cdot X + X \cdot A^T + B \cdot {\color{green} Z} + {\color{green} Z}^T \cdot B^T \prec 0, \; X \succ 0$$

**Post-proccessing:**
$${\color{darkmagenta} Y_\text{opt}} = Z_\text{opt} X^{-1}_\text{opt}$$

---

### 🧩 DC Programming

.mermaid[
<pre>
graph LR
    A["Non-convex\nFunction f"] --> B["Decompose\nf = g - h"]
    B --> C["g is convex\nh is convex"]
    C --> D["Iteratively\nLinearize h"]
    D --> E["Solve Convex\nSubproblem"]
    E --> F["Update\nSolution"]
    F -.-> D

DC (Difference of Convex) programming decomposes a non-convex function into a difference of two convex functions, then solves iteratively.

---

### 💭 Other thoughts

- 🎯 Minimizing any quasi-convex function subject to convex constraints can easily be
  transformed into a convex programming.
- 🔄 Alternating minimization
- 🔒 Replace a non-convex constraint with a sufficient condition
  (such as its lower bound). Less optimal.
- 🎲 Relaxation + heuristic
- 🧩 Decomposition

---

### 🎲 Semi-definite Relaxation (SDR)

.mermaid[
<pre>
graph TD
    A["QCQP\nProblem"] --> B["Lift to\nMatrix Space"]
    B --> C["Drop Rank-1\nConstraint"]
    C --> D["SDP\nProblem"]
    D --> E["Extract\nSolution via SVD"]

style A fill:#ffcdd2,stroke:#c62828,stroke-width:3px,color:#2e3440
    style B fill:#fff3e0,stroke:#e65100,stroke-width:3px,color:#2e3440
    style C fill:#e3f2fd,stroke:#1565c0,stroke-width:3px,color:#2e3440
    style D fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px,color:#2e3440
    style E fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px,color:#2e3440
</pre>
]

SDR lifts a quadratically constrained quadratic program (QCQP) into a higher-dimensional space and drops the non-convex rank constraint.

---

### ✅ Conclusion

Convexifying a non-convex function through change of variables and transformations is a powerful technique in optimization. By applying appropriate transformations, many non-convex problems can be converted into convex problems, allowing the use of efficient convex optimization algorithms to find global optima. The choice of transformation depends on the specific structure of the original problem and requires careful analysis to ensure that the transformed problem retains the essential characteristics of the original problem.

---

## Q&A 🎤