Tagged Questions

Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (1)

0
votes
0answers
16 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 ...
0
votes
0answers
78 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 ...
2
votes
1answer
24 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 ...
0
votes
0answers
7 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 ...
0
votes
1answer
62 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 ...
0
votes
1answer
278 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
1
vote
2answers
40 views

How to prove that $H(S_1\cap S_2)\subset H(S_1) \cap H(S_2)$ and $H(S_1 \cup S_2) \supset H(S_1) \cup H(S_2)$

I'm studying convex analysis and my task is to prove the following inclusions: $S_1, S_2$ are non-empty sets in $\mathbb{R}^n$, and $H(S) $ defined as the convex hull of set $S$. Show that ...
0
votes
0answers
15 views

extension of semilinear functional in cone.

I'm studying Nigel Kalton's work in extrapolation Banach space theory (paper: Differentials of complex interpolation processes for Kothe function spaces). My question is: Let $T$ be a cone contained ...
0
votes
1answer
31 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 ...
2
votes
1answer
43 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
0
votes
0answers
34 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
2
votes
2answers
28 views

Under what conditions does local concavity imply global concavity?

I have the following result: Assume $U:\mathbb{R}^+\to\mathbb{R}^+$ is continuous and strictly increasing. Further, for every $a>0$ there exists a neighborhood (interval) $S$ of $a$ such that $U$ ...
7
votes
1answer
167 views

Characterization convex function.

Let be $f:[0,1]\rightarrow\mathbb{R}$ a continuous function such that far all $a,b\in [0,1]$ with $a<b$ $$f\left(\frac{a+b}{2}\right)\leq\frac{1}{b-a}\int_a^b f(x)\,dx.$$ How to prove that $f$ is ...
0
votes
1answer
23 views

Proving that $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, for convex cone $C$

I'm doing convex analysis studies and I have the following problem to prove: Show that, if $C$ is a convex cone, then $\lambda_1\textbf{x}_1+\lambda_2\textbf{x}_2\in C$, with ...
0
votes
0answers
16 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
45 views

Convex function and its epigraph PROOF

Can someone help prove this statement. Consider a function $f:R^{n} \to R$ and epi $f$ = {$(x,t) \in R^{n+1}$: $x \in R^{n}$, $t \geq f(x)$} A function is convex if and only if its epigraph is a ...
0
votes
1answer
17 views

Questions on conditions for convexity of a real function

We have a function $f:[0,1] \rightarrow \mathbb{R}$. We know it is continuous on $[0,1]$. Aside from a set $S$ of measure $0$, we can compute its right derivative, and can show that this right ...
0
votes
2answers
39 views

Identity regarding convexity of the logistic loss function

I found the following identity regarding the logistic loss function in these lecture notes (slide 16) from Berkeley university: $$\log(1 + e^{-z}) = \max_{0 \leq v \leq 1} -zv + v\log(v) + ...
5
votes
1answer
110 views

Non-empty intersection of convex sets

Assume that $X_1,\ldots,X_n$ are open, convex subsets of $\Bbb R^d$ such that for any $i,j,k$ with $1\le i,j,k\le n$, we have $X_i\cap X_j\cap X_k\neq\emptyset$. Is it possible for $\bigcap_{i=1}^n ...
1
vote
1answer
69 views

Maximal intersection of slabs in $\mathbb{R}^n$ with a compact convex centrally symmetric set

Let $K \in \mathbb{R}^n$ be a compact convex set containing the origin and symmetric with respect to the origin. Let $S_i(t_i)$ be a finite set of slabs of various widths and orientations, translated ...
6
votes
0answers
209 views

Closest fixed point to a convex set

Consider the compact convex sets $Y \subset X \subset \mathbb{R}^n$, and a Lipschitz continuous function $f : X \rightarrow X$. Assume that $f$ has multiple fixed points. (From Brouwer's theorem, $f$ ...
0
votes
1answer
34 views

Minimizing a non-convex rational function of two variables

I need to minimize the following function $$f(x,y)= \frac{a}{x}+\frac{bx}{y}+\frac{cy}{x}+dy+\frac{e}{y}$$ where $a,b,c,d$, and $e$ are positive constants, and $x$ and $y$ are both strictly positive. ...
0
votes
1answer
26 views

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities. The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined ...
3
votes
1answer
69 views

Strictly increasing and strictly convex function that does not go to negative infinity

Let $f : \mathbb{R} \to \mathbb{R}$ be continuous, strictly increasing, and strictly convex for all $x$. What are necessary and sufficient conditions for $f$ to be bounded below? Strong convexity is ...
0
votes
0answers
21 views

Some good reference on convex functions

I want some good reference on convex functions i.e. all of their properties along with their proofs.
0
votes
1answer
39 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 ...
0
votes
0answers
20 views

Does $\mu\coth(\mu)=A\mu^{2}+B$ have at most two positive solutions $\mu$?

Is it true that $$ \frac{\mu\cosh(\mu)}{\sinh(\mu)} = A\mu^{2} + B $$ has at most two solutions $\mu > 0$ for any choice of $A$, $B$? I believe this is true; it looks true when I ...
2
votes
0answers
26 views

Convexity of sigmoid-based squared error loss

Assume $w, a_1,a_2 \in \mathbb{R}^d$ and $\sigma = \dfrac{1}{1+e^{-x}}$ the sigmoid function. Is the following squared difference a convex function? $$J(w)= (\sigma(w^Ta_1)\times \sigma(w^T ...
1
vote
1answer
32 views

Directions of sublevel sets ofa convex function

Let $f:\mathbb R^n \rightarrow \mathbb R$ be a convex (continuous ) function. Let's assume that some sublevel set $L_a:=\{x\in \mathbb R^n : f(x) \leq a\}$, where $a \in \mathbb R$, contains a ...
1
vote
0answers
17 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
0
votes
0answers
42 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 ...
0
votes
1answer
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 ...
0
votes
0answers
48 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 ...
3
votes
3answers
136 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 $$ ...
2
votes
0answers
28 views

Convex interpolation between two points with given derivatives

Let's say I have two real values $x_1$ and $x_2$, to each of which I associate $y_i$ and $y'_i$ satisfying $$ (y_2-y_1)(y'_2 - y'_1) \geq 0. \tag{1} $$ I would like to find a polynomial ...
0
votes
0answers
37 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
15 views

What is the nature of this one dimensional function?

Let $\mathcal{S}$ be a 2-D convex set whose elements can be represented as $(x,y)\in\mathcal{S}$. Let $p_L$ and $p_U$ be two real constants such that $p_L\leq p_U$. For $p\in[p_L,p_U]$, I define the ...
1
vote
1answer
56 views

Convex Combination of 3 point in R2 and Triangle

I am new to convex combination, and I am quite amazed by some easy result. I know that convex combination of 2 points($P_1P_2$) in $R^2$ is all points in the line segment $P_1P_2$. And then I see a ...
0
votes
1answer
37 views

Interesting and intuitive affirmation involving convex sets

Let $\Omega_1$ and $\Omega_2$ two open, bounded and convex domains in $R^n$ with $\Omega_1 \supset \overline{\Omega_2}$ and $0 \in \Omega_2.$ Suppose that for each $x_0 \in \partial (\Omega_1 ...
0
votes
1answer
45 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all ...
1
vote
0answers
75 views

Dual norm of the matrix L1 norm is infinity norm (and vice versa)

Recall that for a given norm $\|\cdot\|$ on $\mathbb{R}^n$, the dual norm is defined as a function $\|\cdot\|_*: \mathbb{R}^n \rightarrow \mathbb{R}$ with: $\|y\|_* = \max \limits_x \{x^Ty: \|x\|\le1 ...
1
vote
2answers
37 views

Suitable composition of concave and convex functions is convex?

Let $f:[0,1]\to[0,1]$ be a strictly increasing continuous concave function with $f(0)=0$ and $f(1)=1$. Let $g$ be the inverse of $f$. Then $g$ is strictly increasing and convex. It seems that the ...
0
votes
2answers
42 views

Basic question about tangent cone

The following is from Prof. Jahn's book " Intro. to the theory of nonlinear optimization" about tangent cone: After definition, he gave an example: My question is: Does the tangent cone include ...
5
votes
1answer
106 views

Continuous linear image of closed, bounded, and convex set of a Hilbert Space is compact

Is my proof of this proposition correct ? And is this proposition well known? Proposition: Let $C$ be a closed, bounded, and convex set in a separable Hilbert space $H$. Let $L : H \to \mathbb{R}^n$ ...
1
vote
1answer
38 views

Convolution of Strictly Convex Function

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be a $C^2$, strictly convex function, and $\theta_\epsilon$ the standard approximation to identity ...
2
votes
2answers
43 views

Is the distance between disjoint closed convex subsets of a Hilbert space positive? Is it attained?

Let $H$ be an infinite dimensional and separable Hilbert space. Let $A,B$ be infinite, closed and convex subsets of $H$. If $A$ and $B$ are disjoint and if at least one of them is bounded, is the ...
0
votes
1answer
29 views

Subtracting a constant from log-concave function preserves log-concavity, if the difference is positive

I am trying to work out a question from 'Convex Optimization - Boyd' . Specifically, exercise 3.48: Show that if $f : \mathbb R^n \to \mathbb R$ is log-concave and $a > 0$, then the function $g ...
2
votes
1answer
36 views

Affine to linear like conversion of a concave function

Is the following true: $$\log \left( \frac{1}{f(x)+K}\right)\mathrm{is\;concave}\Longleftrightarrow \log \left( \frac{1}{f(x)}\right)\mathrm{is\;concave},$$ where $K\in\mathbb{R} $ and ...
0
votes
1answer
36 views

Do full-rank linear transformations preserve strong convexity?

Consider a strongly convex function $g$, that is, for all $x,y$ in the domain and $t\in[0,1]$ we have $$ g(t x + (1-t)y) \le tg(x)+(1-t)g(y) - \frac{1}{2}mt(1-t)||x-y||_2^2 $$ for some $m>0$. Also, ...
7
votes
3answers
550 views

Dual norm intuition

The dual of a norm $\|\cdot \|$ is defined as: $$\|z\|_* = \sup \{ z^Tx \text{ } | \text{ } \|x\| \le 1\}$$ Could anybody give me an intuition of this concept? I know the definition, I am using it ...