# Tagged Questions

22 views

### LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
38 views

26 views

### how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
28 views

### The convexity of the range of concave function

Given a concave function $f: X \rightarrow \mathbb{R}^n$ with a convex domain $X \in \mathbb{R}^n$, is the range of $f$ a convex set also?
33 views

### Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
28 views

### what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
30 views

### Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
131 views

### Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$\min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y)$$ $$\text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i$$ ...
20 views

57 views

### $F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
17 views

### What is a $0$-sublevel set?

I read the notes of S. Boyd, and am confused about the following: $f_0(x)$ is quasiconvex. I am confused about the latter one particularly. What does it mean? Thanks!
36 views

### Strong convexity of a function with cases

Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function \begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align} ...
21 views

65 views

34 views

### Linear constraint in convex optimization

Is it true that the solution to a linearly constrained convex minimization problem can only be placed on the boundary of the constraint set, for any nonlinear convex objective, e.g. $$\min_x f(x)$$ ...
31 views

### Is it possible to convexify this cone constraint?

General question An SOCP constraint is given by: $$\| A_i \mathbf{x} + b_i\| \leq \mathbf{c}_i^T \mathbf{x} + d_i.$$ I have the following constraint: $$\| A_i \mathbf{x} \| \geq d_i.$$ Is it ...
39 views

23 views

### Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
20 views

### Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
61 views

### Composition of non-monotonic convex function

Given the following composition of functions: $h:\Bbb R^k\rightarrow\Bbb R$ $g:\Bbb R^n\rightarrow\Bbb R$ $f(x)=h(g_1(x),g_2(x),...,g_k(x))$ There are known rules which guarantee ...
Consider $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$, defined as $f(x) := a x + b$, where $a<0$ and $b \in \mathbb{R}_{\leq 0}^{n}$. Note that $f$ is decreasing: $$x \geq y \Longrightarrow f(x) ... 2answers 56 views ### Minimization of log-sum-exponential function subject to constraints. I would like to minimize the following function: f(x)=log(e^{-x_1}+..+e^{-x_n}) Subject to: \sum_{i=1}^{n}{x_i}=1 0 \leq x_i \leq 1 So far I have discovered the following: If all the ... 1answer 63 views ### Showing a function is concave Given F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2)) on S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\} with A,B,a\in\mathbb{R}, show that F is concave on S. Since we have ... 0answers 29 views ### Convex set of polynomial coefficients Assume we have an infinite order polynomial f(L)=1-L\theta_1-L^2\theta_2-L^3\theta_3-.... and we know all roots of this polynomial cite outside the unite circle. It is obvious that latter condition ... 0answers 15 views ### Effect of proximal projection using a divergence measure, on the maximizer of the function Suppose we have a probability distribution p(\mathbf{x}) and we know :$$ \mathbf{x}^* = \arg\max_{\mathbf{x}} p(\mathbf{x}) $$Suppose we do a projection of this distribution onto another family ... 1answer 29 views ### Equality constrained Quadratic Program Consider the QP$$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b,  where $P \succ 0$. Without the non-negativity ...
Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...