# Tagged Questions

22 views

### Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is concave. Does anyone know how to prove ...
14 views

### A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
12 views

### Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
15 views

### weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
14 views

### Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
5 views

### Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...
47 views

### Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
10 views

### Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
24 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

27 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 ...
32 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 ...
133 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

67 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

24 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?
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 ...
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 ...