0
$\begingroup$

I have the optimization problem

$$\underset{\mathbf{x} \in \Bbb C^N}{\max} \left| \frac{\mathbf{x}a-b}{\mathbf{x}c+b} \right|^2$$

where $a$, $b$ and $c$ are some scalars. I want to solve this optimization problem using semidefinite programming (SDP) but don't know how to handle this fraction in the objective function.

$\endgroup$
2
  • 2
    $\begingroup$ That looks non-convex. I don';t see how you colud use CVX, CVXPY, etc. for that. Read and solve some exercises fro at least the 1st 4 or 5 chapters of "Convex Optimization" by Boyd and Vandenberghe: web.stanford.edu/~boyd/cvxbook $\endgroup$ Nov 9, 2023 at 21:52
  • $\begingroup$ What is $\mathbf{x}a-b$? How can one subtract a scalar from a vector? $\endgroup$ Nov 10, 2023 at 11:55

1 Answer 1

2
$\begingroup$

I assume the given problem is $$ \max \frac{\|ax-b\|^2}{\|cx+b\|^2}, x \in \mathbb{C}^N $$

I may try the following relaxation. The given problem is equivalent to

$$ \begin{align} &\max &\|ax-by\|^2\\ &\textrm{subject to} &\|cx+by\|^2 = 1\\ &&x \in \mathbb{C}^N, y\in \mathbb{C} \end{align} $$

Any solution of this problem $(x^\star, y^\star)$ could be translated to a optimal solution of the given problem: $x = x^\star / y^\star$.

(If an optimal solution gives $y^\star = 0$, it means the optimal value of the original problem is bounded below $|a/c|$, and is not reachable if $b \neq 0$.)

Or

$$ \begin{align} &\max &\|Au\|^2\\ &\textrm{subject to} &\|Cu\|^2 = 1\\ &&u \in \mathbb{C}^{N+1} \end{align} $$ where $$ A = \begin{bmatrix}aI_N &-b\mathbf{1}_N \end{bmatrix} \in \mathbb{R}^{N \times (N+1)} $$ and $$ C = \begin{bmatrix}aI_N &b\mathbf{1}_N \end{bmatrix} \in \mathbb{R}^{N \times (N+1)} $$

The relation is $u^\star = [x^\star, y^\star]$.

Then it is equivalent to $$ \begin{align} &\max &\langle A^HA, U\rangle\\ &\textrm{subject to} &\langle C^HC, U\rangle = 1\\ &&U \in \mathbb{S}_{N+1}^+\\ &&\mathop{\mathrm{rank}}(U) = 1 \end{align} $$ where $\langle X, Y\rangle = \mathop{\mathrm{tr}}(X^H Y)$ is matrix inner product. The relation is $U^\star = (u^\star)(u^\star)^H$.

Drop the rank constraint to get the following SDP relaxation $$ \begin{align} &\max &\langle A^HA, U\rangle\\ &\textrm{subject to} &\langle C^HC, U\rangle = 1\\ &&U \in \mathbb{S}_{N+1}^+ \end{align} $$

You may use the eigenvector corresponding the largest eigenvalue of $U^\star$ or use some random sampling technique to find an approximate solution $\tilde u$, which may be further polished with first-order method (like gradient descent) on the original non-convex problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.