7
$\begingroup$

Motivation

Suppose that $u \in \mathbb{R}^d$ is a unit-norm vector, $\|u\| = 1$, $a, b, c$ are some positive constants and $\xi \in [0,1]$ is another constant (usually chosen close to 1). I am interested in solving the following problem

$$ \sup_{v \in \mathbb{R}^d}\ (\xi + (1-\xi)\|v\|_1^2)\left(\sqrt{ \frac{a \langle u, v \rangle^2 + b}{\xi + (1-\xi)\|v\|_1^2}} - c \right) $$

subject to $\|v\| = 1$.

Question

While any suggestions on how to find an optimal $v$ are welcome, I am specifically interested in the following question.

How to find a vector $v$ that maximizes $\langle v, u \rangle$ and satisfies $\|v\|_2 = 1$ and $\|v\|_1 = x$?

A related question (that may be an easier one): given a vector $v_1$ that maximizes $\langle v_1, u \rangle$ and satisfies $\|v_1\|_2 = 1$ and $\|v_1\|_1 = x$ and another vector $v_2$ that maximizes $\langle v_2, u \rangle$ and satisfies $\|v_2\|_2 = 1$ and $\|v_2\|_1 = x + \delta$, how to find the change $\langle v_1, u \rangle - \langle v_2, u \rangle$ as a function of $\delta$?

  • 0
    Kuhn-Tucker would work.2010-11-22
  • 3
    As a side remark about your first sentence: it is generally not a good idea to start a clause with a *comma separated* list of variables. Especially if the clause itself is preceded by a comma. I mentally stumbled a bit when I tried to parse that.2010-11-22
  • 0
    Geometrically it is quite easy to see that for the maximizer $v$, we can get it by: WLOG assuming $u$ is in the first orthant. Assume $u$ is not proportional to $w = (1,1,\ldots,1)$ (else all solutions to $\|v\|_2 = 1$ and $\|v\|_1 = x$ in that orthant are maximizers). Then $v$ is the unique intersection of the hypersurface $\|v\|_2 = 1$ with the hyperplane $\|v\|_1 = x$ and the 2-plane spanned by $u$ and $w$.2010-11-22
  • 0
    @Willie: It's not so simple. The intersection you describe may lie outside the positive orthant.2010-11-22

1 Answers 1

1

Your question doesn't say what $x$ is. Also is $u$ given and fixed? Assuming it is, your first problem can be written $$ \min_{v_1, v_2}\; \langle v_1 - v_2, u\rangle \;\; \text{s.t.} \;\; \lVert v_1 - v_2\rVert^2_2 = 1, \quad \sum_i v_{1,i} + \sum_i v_{2,i} = 1, \ (v_1, v_2) \geq 0, $$ where $v_{1,i}$ and $v_{2,i}$ are the individual components of $v_1$ and $v_2$. Th e idea is to split $v = v_1 - v_2$ with $v_1 \geq 0$ and $v_2 \geq 0$. This problem is smooth and can be solved using any method for smooth optimization (SQP, augmented lagrangian, interior-point method, etc.). On paper, you can write the KKT conditions and go from there.