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 (3)

1
vote
1answer
243 views

Convexity of Binomial Term

I am reading a book on the probabilistic method, and the following claim was made: $\dbinom{y}{n}$ is convex. Why is this the case?
1
vote
1answer
41 views

Proof that the image of an Itō integral is convex if the driving Wiener process is in a metric ball

Let $(\Omega, \mathcal{F}, P)$ be a probability space and $A := \int_0^1 f(t)\,d W_t$ be the Itō integral of an $L_2([0,1])$ deterministic function $f$ with respect to the Wiener process $W$. ...
0
votes
1answer
58 views

Prove that $x \rightarrow \int_0^\infty \frac{e^{-tx}}{1+e^{-t}}dt$ is convex

To put it bluntly I'm stuck proving proving the subsequent inequality $$ \forall x>0, \int_0^\infty \frac{e^{-tx}}{1+e^{-t}}dt \int_0^\infty \frac{t^2 e^{-tx}}{1+e^{-t}}dt \geq {\left ( ...
1
vote
0answers
33 views

Litterature: Convex Geometry using differential forms

I've been looking for papers or books that discuss/use differential forms in convex geometry. I have been very unsuccessful in my search and was wondering if anybody here had come across such ...
2
votes
1answer
565 views

Finding the dual cone

Looking at the example here, I'm trying to understand how the author finds the dual cone $K^*$. The question asks to find the dual cone of $\{Ax | x \succeq 0\}$ where $A \in \mathbb R^{m\ ...
0
votes
2answers
34 views

Proof that the set $\{ x \in \mathbb{R}^n: \max\{w_1^Tx, \ldots, w_N^Tx\} \geq \gamma\}$ is not convex in general

Let $w_1, \ldots, w_m$ and $x$ be vectors in $\mathbb{R}^n$, and $\gamma$ be some constant in $\mathbb{R}$. How can I prove that the set $\{ x \in \mathbb{R}^n: \max\{w_1^Tx, \ldots, w_N^Tx\} \geq ...
0
votes
2answers
225 views

Stronger than strict convexity, bounded hessian?

I've encountered a condition similar, but slightly stronger, to that of a function being strictly convex. The condition is $\phi(\lambda x+(1-\lambda)y)\leq \lambda \phi(x)+(1-\lambda)\phi(y) - ...
1
vote
1answer
1k views

Proving that a Hessian Matrix is positive definite

I'm currently stuck on a problem for my Artificial Intelligence class. The assignment is provided at the following link: http://courses.engr.illinois.edu/cs440/HW1.pdf The problems that I'm stuck on ...
1
vote
0answers
71 views

Legendre transform for HJB PDE

I am trying to understand section 2.3 of the following article: http://www.princeton.edu/~sircar/Public/ARTICLES/montreal.pdf . I think I understand that $H_v(t,g(t,z)) =z$, because by definition of ...
0
votes
1answer
72 views

Intersection of half planes vs union?

Can someone explain to be why we are taking intersection instead of union? Because taking the union means we are also taking the union of ALL the $y$s in $S$ no?
1
vote
0answers
94 views

Properties of matrix functions

Can I say that a certain matrix function is absolutely continuous or monotonically increasing in $\lambda$(assuming that the matrix is a function of $\lambda$)? In other words, are these ...
3
votes
1answer
61 views

Conjugate of a function

Yes this is homework. Given $f(x) = 1^{T}(x)_+$ where $(x)_+ = \max\{0,x\}$, what is $f^*$? I know that the conjugate of a function $f$ is $f^*(y) = \sup (y^Tx - f(x))$ but I do not know how to show ...
2
votes
1answer
100 views

Determining if a function is convex

Yes this is homework. For which values of $a$ is the function $f(x)=e^{-a \sqrt x}$ with $\mathbf dom f = \mathbf R_+$ convex? The possible answers are: $a \le 0$ $a \ge 0$ $-1 \le a \le 1 $ ...
11
votes
2answers
291 views

Convexity of a complicated function

Let $\mathbb{S}$ be a 2-D convex set in the positive quadrant. Let us define \begin{align} y_L=\min_{(x,y)\in\mathbb{S} }y \\ y_R=\max_{(x,y)\in\mathbb{S} }y \end{align} For any positive number ...
0
votes
2answers
67 views

Convexity of product of two given functions

Let $f(x)$ be a convex function of $x$ in a given positive interval. Also assume $f(x)\geq 0$ everywhere in that interval. Is the function $g(x)=xf(x)$ convex in that interval?. Is it possible that ...
0
votes
1answer
719 views

Composition of convex function and affine function

Let $g: E^{m} \rightarrow E^{1}$ be a convex function, and let $h: E^{n} \rightarrow E^{m} $ be an affine function of the form $h(x)=Ax+b$, where $A$ is an $m \times n$ matrix and $b$ is an $m \times ...
2
votes
0answers
67 views

Why is the feasible set of utility values (in bargaining problem) convex?

Let $S := \{x \in \Bbb{R}^n \mid x \ge 0, \sum_{i=1}^n x_i = 1\}$ be the set of mixed strategies. For a bimatrix game with pay-off matrices $A$, $B$ we denote $C := \{ (u, v) \mid \exists (x,y)\in ...
1
vote
3answers
124 views

Convex functions - two questions

I have two questions regarding convex functions: First question: Let f be convex function on closed interval [a,b]. Prove that f has maximum in x=a or x=b. I understand that $\forall ...
2
votes
2answers
80 views

Convexity of $\frac{1}{f}$ over the set where the concave function $f$ is positive

$S \subset R^n,~~f : S \rightarrow R $ is a concave function. $S^{'}= \{ x \in S: f(x)>0 \}. $ Prove that $\frac{1}{f}$ is a convex function on $S^{'}.$
-1
votes
1answer
110 views

Prove or disprove the concavity of the function [closed]

Prove or disprove the concavity of $f$ over the following two domains. $$f(x_1,x_2)=10-2(x_2-x^{2}_{1})^{2}$$ defined either over $$S_1=\{(x_1,x_2) : -1\leq x_1 \leq 1, -1 \leq x_2 \leq ...
0
votes
1answer
40 views

Finding the determinant of a $ k \times k$ matrix (Hessian matrix)

Given $H(x_{1}, x_{2}, x_{3}) = \begin{bmatrix} -2 & \frac{1}{2} & 0 \newline \frac{1}{2} & -2 & 0 \newline 0 & 0 & -4 \end{bmatrix}$, I want to find (I think) the leading ...
1
vote
1answer
88 views

Lower semi-continuity of a convex functional on $L^1(\Omega,[0,1])$

Let $\Omega$ be a bounded domain and $f:\Omega\times[0,1]\to[0,\infty]$ be such that $x\mapsto f(x,u)$ is measurable for every $u$, $u\mapsto f(x,u)$ is continuous and convex for a.e. $x$. Furthermore ...
2
votes
1answer
621 views

convexity of matrix “soft-max” (log trace of matrix exponential)

In convex optimization it is often convenient to use the following smooth approximation to $\max\{x_1, \ldots, x_n\}$: $$ f_\lambda(x_1, \ldots, x_n) = \frac{1}{\lambda}\log \sum_{i = 1}^n{e^{\lambda ...
4
votes
1answer
62 views

Relation between convex functions

I formed the following conjecture and, since I can't find counterexamples, am trying to prove it. Let $f, g :[0,x_{max}]\rightarrow {\mathbb R}^{+}$ such that $f',g'>0$ $f'',g''>0$ ...
3
votes
1answer
96 views

Calculate Dq(x)

Let A be a symmetric $m \times m$ matrix, and $q(x)=x\cdot Ax$ a quadratic form on $\mathbb{R}^m$. Question: Calculate $Dq(x)$; write your answer in vector notation. Does anyone knows the answer on ...
0
votes
1answer
81 views

convexity of a Hessian matrix.

Suppose I have $f(x_{1},x_{2}) = x_{1}^2 + x_{2}^2, S = \mathbb{R}^2$. How do I determine whether the function is concave or convex based off of the Hessian of what is above? I know the Hessian is ...
1
vote
0answers
22 views

Uniqueness of the solution to a quadratic opt problem

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
2
votes
0answers
73 views

On the convexity of a particular discontinuous function.

Let $f:D\to\mathbb{R}$ be defined as follows: $$ f(\mathbf{x})=\frac{a-(\mathbf{x}_N\cdot\mathbf{x}_0+x_{n+1})}{\sqrt{\mathbf{x}_N^T\mathbf{A}\mathbf{x}_N}}, $$ where ...
10
votes
1answer
400 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
1
vote
0answers
31 views

Intersection of affine subspace of $\mathbb{R}^n$ with $[0, 1]^n$

Suppose I have an affine subspace $V \subseteq \mathbb{R}^n$, say given by a rank-$r$ system of $m$ equations in $n$ variables. I'm interested in two questions: Is there a straightforward way to ...
0
votes
2answers
54 views

Show that the set of points that are nearer $a$ than $b$ with respect to $\lVert \cdot \rVert_2$ is convex

I am trying to show the above statement: Show that the set of points that are nearer $a$ than $b$ in the sense of Euclidean $\lVert\cdot\rVert_2$ are convex. My attempt This follows from the ...
1
vote
1answer
60 views

Convex Hull of cyclic Permutations

It is known that the convex hull of permutation matrices yields exactly the stochastic matrices. I am interested in the convex hull of cyclic permutation matrices. Trivially this is a subset of the ...
2
votes
1answer
50 views

On Convexity of product of a convex and a bounded function.

Let $f:\mathbb{R}^n\to\mathbb{R}$ be a real-valued, $n$-dimensional function defined as follows: $$ f(\mathbf{x}) = g(\mathbf{x})h(\mathbf{x}), $$ where $g:\mathbb{R}^n\to\mathbb{R}$ is convex, and ...
0
votes
1answer
491 views

convex/concave problem.

I want to show that if $y = f(x) > 0$ is a concave function on $\mathbb{R}$, then $z = \frac{1}{f(x)}$ is a convex function. Since $f(x) > 0$ then if we applied the second derivative test, ...
0
votes
1answer
203 views

There is a closed hyperplane.

$\textbf{Question: }$ If $M$ is an open convex set in normed linear space $R$ and $x_{0}\not\in M$, then there exists a closed hyperplane which passes through the point $x_{0}$ and does not intersect ...
2
votes
0answers
216 views

Voronoi-Diagram - split concave polygon

I have a concave polygon c and a set of points p[]. What I need is to have a set of polygons splitted by the voronoi-diagram. My problem is the following: I already found a library to calculate the ...
2
votes
1answer
265 views

The convex conjugate of a quadratic form with positive semi definite matrix

I want to find the convex conjugate (Legendre transform) of a quadratic for $1/2x^{t}Qx$ when $Q$ is positive semi-definite. If Q is non-singular, the solution is easy - the gradient is $y-Qx=0$ so ...
0
votes
1answer
87 views

Cyclic monotonicity of sub-differential domain and convex property

I am looking for hints/proof's overview/reference about this proposition : Let $S\subset \mathbb{R}^d\times\mathbb{R}^d$. There exist a convex function $\phi$ such that $S\subset \partial\phi$ ...
1
vote
1answer
48 views

showing $y\to |y|^{p}$ is convex $p\geq 1$

$y\to |y|^{p}$ is convex only for $p\geq 1$ and $y\in \mathbb{R}$. This function is nondifferentiable but we can see that the second derivative is nonnegative in each interval $(-\infty,0)$ and ...
2
votes
3answers
169 views

Is this set convex ?2

Is this set convex for every arbitrary $\alpha\in \mathbb R$? $$\Big\{(x_1,x_2)\in \mathbb R^2_{++} \,\Big|\, x_1x_2\geq \alpha\Big\}$$ Where $\mathbb R^2_{++}=[0,+\infty)\times [0,+\infty)$.
0
votes
1answer
70 views

strictly convex function when plotted but second derivative not unambiguously positve

I have a function $$ z(x) = (Kx)^{x/(1-x)}, x \in (0,1)\text{ and }K>1 $$ When I plot the function it has a U-shape. However when I take the second derivative wrt $x$ I have the following ...
0
votes
1answer
36 views

Space where the separation theorem doesn't hold

I have read the proof of the next separation theorem: Let X b a normed space in R and A a convex and open set that contains 0. Let b be a point wich is not in A then there exists f in X* such that ...
2
votes
2answers
137 views

Verifying the convexity of some function

Convex function: We will say that $f:X\rightarrow R$ is convex function if for every $\lambda\in [0,1]$ and for every $x,y\in X$ ($X$ is convex space) $f(\lambda x+(1-\lambda)y)\leq\lambda ...
6
votes
1answer
351 views

Dual of a rational convex polyhedral cone

A rational convex polyehedral cone $\sigma\subseteq\mathbb R^n$ is a set of the form $$ \sigma=\operatorname{Cone}(u_1,\dots,u_k) := \left\{ \sum_{i=1}^k r_i u_i \,\Bigg|\, r_i\ge ...
2
votes
1answer
173 views

Convex Function to Given (Three) Data Points

Assume that a function $h(x)$ is decreasing and convex given interval $[l,u]$. I'd like to get a function which connects three points, say $(a,h(a)), (b,h(b)), (c,h(c))$, where $l\leq a<b<c\leq ...
5
votes
1answer
204 views

Find the Polar of a set.

Let $A \subset \mathbb{R}^{n}$ be non-empty. The set $$ A^{\circ} = \lbrace c \in \mathbb{R}^{n} |\; \langle c,x \rangle \leq 1 \quad \forall x \in A \rbrace $$ is called the polar of $A$. I'm ...
0
votes
1answer
380 views

Linear combination of convex set is convex

A set $U$ is a convex set if whenever $\mathbf{x},\mathbf{y}$ are points in $U$, the line segment joining $\mathbf{x}$ to $\mathbf{y}$,$$\mathcal l(\mathbf{x},\mathbf{y})=\left\{t\mathbf ...
0
votes
1answer
178 views

infimum of a convex function over an open domain

Let $f: \cal D_0 \to [0, \infty]$ be a convex function on a compact set $\cal{D}_0$ and let $\cal D \subseteq \cal D_0$. I think the following holds: $$ \inf_{x \in \cal{D}}\ f(x) = \inf_{x \in ...
0
votes
1answer
39 views

Geometry question with convexity

Assume that a function $h(\lambda)$ is decreasing and convex given interval $[l,u]$ and has an unique root $\lambda^*\in (l,u)$. Also, assume $|l-\lambda^*| > |\lambda^*-u|$. Consider any $z\in ...
1
vote
1answer
76 views

Dual of a convex function $f:\mathbb{R} \to \mathbb{R}$: existence, solution to ODE

Let $f(x)$ be a smooth strictly convex (i.e. $f''(x)>0 \,\,\,\,\,\forall x)$ funtion of $x\in \mathbb{R}$. Define the dual function $F(p)$ as $$F(p)=\max_x [px-f(x)].$$ Make a sketch ...