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

-
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 Narain Nov 22 '10 at 16:47

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 41, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9244539737701416, "perplexity_flag": "head"}