DCP analysis

DCP analysis#

In this exercise, you will fix optimization problems that break the DCP rules by identifying the DCP error and then rewriting the problem.

import cvxpy as cp
import numpy as np

Problem 1.#

\(\min\{ \sqrt{x^2 + 1 } : x \in \mathbb{R} \}\)

x = cp.Variable()
cost = (x**2 + 1) ** 0.5
prob = cp.Problem(cp.Minimize(cost))
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Problem 2.#

\(\min\{x + 2 \,:\, 5 = 2 / x,~~ x > 0 \}\)

x = cp.Variable()
prob = cp.Problem(cp.Minimize(x + 2), [5 == 2 * cp.inv_pos(x)])
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Problem 3.#

\(\min\{ x + 2 \,:\, 5 \leq 2 / x^2,~~ x \in \mathbb{R} \}\)

x = cp.Variable()
prob = cp.Problem(cp.Minimize(x + 2), [5 <= 2 * x**-2])
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Problem 4.#

\(\min\{ 1/ x \,:\, 0 \leq x^2 / y, ~~ y \geq 1, ~~ x > 0 \}\)

x = cp.Variable()
y = cp.Variable()
prob = cp.Problem(cp.Minimize(cp.pos(x)), [0 <= cp.quad_over_lin(x, y), y >= 1])
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Problem 5.#

\(\min\{ x + 2 \,:\, \exp(2x) + \exp(3x) \leq \exp(5x) \}\)

x = cp.Variable()
prob = cp.Problem(cp.Minimize(x + 2), [cp.exp(2 * x) + cp.exp(3 * x) <= cp.exp(5 * x)])
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Bonus Problem 1.#

\(\min\{ -(\max\{x, 4\} - 3)^2 \,:\, x \geq 1 \}\)

x = cp.Variable()
prob = cp.Problem(cp.Maximize(-((cp.maximum(x, 4) - 3) ** 2)), [x >= 1])
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.

Bonus Problem 2.#

\(\min\left\{ \sum_{i=1}^m c_i \frac{x_i}{u_i - x_i} \,:\, ~ u > x,~~ x \in \mathbb{R}^m \right\}\)

where \(c\) and \(u\) are nonnegative vectors.

# This is a real problem from the CVXPY forum.

m = 10
np.random.seed(1)
c = np.random.randn(m)
c = np.abs(c)  # Important: This is nonnegative.
u = np.random.randn(m)
u = np.abs(u)  # Important: This is nonnegative.

x = cp.Variable(m)
cost = sum([c[i] * x[i] * cp.inv_pos(u[i] - x[i]) for i in range(m)])
prob = cp.Problem(cp.Minimize(cost))
prob.solve()

# TODO explain why the problem isn't DCP and rewrite it to satisfy DCP.