Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Kuhn-Tucker would work. –  Jonas Teuwen Nov 22 '10 at 11:14
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. –  Willie Wong Nov 22 '10 at 11:52
    
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$. –  Willie Wong Nov 22 '10 at 12:05
    
@Willie: It's not so simple. The intersection you describe may lie outside the positive orthant. –  Rahul Nov 22 '10 at 16:47

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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