How to solve this convex optimization problem (with absolute and linear objective function)? I have the following problem:  
\begin{align*}
\sup_y&\quad \big | \langle u,y \rangle\big |\\
\mbox{s.t.}&\quad \frac{1}{2}\langle y,y \rangle\ + \langle b,y \rangle\ \geq \gamma.
\end{align*}
where $u$ is a constant vector.
I am confused about the following:  


*

*$\big | \langle u,y \rangle\big |$ is a convex function, then it seems that this problem is infeasible.   


To solve it, I try to find its dual. So the Lagrangian. The first step is to rewrite it in a familiar form:  
\begin{align*}
-\inf_y&\quad -\big |  \langle u,y \rangle\ \big |\\
\mbox{s.t.}&\quad \gamma - \frac{1}{2}\langle y,y \rangle\ - \langle b,y \rangle\ \leq 0.
\end{align*} 
$$L(x,y) = -\big |  \langle u,y \rangle\ \big| +x\big(\ \gamma - \frac{1}{2}\langle y,y \rangle\ - \langle b,y \rangle\big)$$
Then how to solve it?  How to deal with the absolute value? 
 A: Here is one approach that involves modifying the original program.
I claim that your problem
\begin{equation*}
\begin{array}{rcl}
\sup_y &&|\langle u,y\rangle|\hspace{1.5 in}(1)\\
s.t. &&\frac{1}{2}\langle y,y\rangle+\langle b,y\rangle \geq \gamma
\end{array}
\end{equation*}
is equivalent to 
\begin{equation*}
\begin{array}{rcl}
\sup_{y,w} &&w\hspace{1.75 in}(2)\\
s.t. &&\frac{1}{2}\langle y,y\rangle+\langle b,y\rangle \geq \gamma\\
&& w^2\leq \langle u,y\rangle^2\\
&&w \geq 0.
\end{array}
\end{equation*}
In order to see the equivalence of (1) and (2), let $y^*$ be an optimal solution to (1) and $(\bar{y}, \bar{w})$ be an optimal solution to (2). The constraints $w^2\leq \langle u,y\rangle^2$ and $w \geq 0$ in (2) imply that \begin{equation}
0\leq \bar{w}\leq |\langle u,\bar{y}\rangle|\leq |\langle u,y^*\rangle|. \hspace{.5 in}(*)
\end{equation}
Note that $(y^*, w^*)$ for $w^* = |\langle u, y^*\rangle|$ is a feasible solution for (2) and so 
$$|\langle u, y^*\rangle| = w^* \leq\bar{w} \leq |\langle u,\bar{y}\rangle|.\hspace{.5 in} (**)$$
From $(*)$ and $(**)$, we get the desired inclusion. 
Now (2) does not have any absolute values, but it does have some quadratic terms. However, your initial problem (1) also had quadratic terms. 
A: Given $\mathrm c, \mathrm y \in \mathbb R^n$ and $\rho > 0$,
$$\begin{array}{ll} \text{supremize} & | \mathrm c^{\top} \mathrm x |\\ \text{subject to} & \| \mathrm x - \mathrm y \|_2 \geq \rho\end{array}$$
Since $-\| \mathrm c \|_2 \| \mathrm x \|_2 \leq \mathrm c^{\top} \mathrm x \leq \| \mathrm c \|_2 \| \mathrm x \|_2$, we drop the absolute value. Hence, we have the following non-convex quadratically constrained linear program (QCLP)
$$\begin{array}{ll} \text{supremize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \| \mathrm x - \mathrm y \|_2 \geq \rho\end{array}$$
The feasible region is $\mathbb R^n \setminus \mathbb B_{\rho} (\mathrm y)$, where $\mathbb B_{\rho} (\mathrm y)$ is the open Euclidean ball of radius $\rho$ centered at $\mathrm y$.


*

*If $\mathrm c = 0_n$, then the maximum is zero and every feasible point is a maximizer.

*If $\mathrm c \neq 0_n$, then we can make $\mathrm c^{\top} \mathrm x$ arbitrarily large because the feasible region is isotropically unbounded. In this case, the supremum is $\infty$.
