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)

4
votes
2answers
134 views

Equality in definition of midconvex function

Let $f:I \rightarrow \mathbb{R}$, where $I\subset \mathbb{R}$ is an interval, be midconvex, that is $$f\left(\frac{x+y}{2}\right) \leq \frac{f(x)+f(y)}{2}$$ for all $x,y \in I$. Assume that for some ...
4
votes
2answers
2k views

Is $g(x)=\log x$ convex function?

The graph of convex function is : In a book it is written that $g(x)=\log x$ is strictly convex function. So i searched for graph of $g(x)=\log x$ and found that Though it has been said that ...
4
votes
3answers
227 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 $$ ...
4
votes
3answers
268 views

Proving the Obvious

Is it normal that I have the hardest time when I'm trying to prove statements that are blatantly obvious on a visual and/or intuitive level? For instance, how does one go about formally proving the ...
4
votes
1answer
120 views

$ \text{cl}(\text{int}(A)) = \text{cl}(A)$ when A is convex

How can one prove that $ \text{cl}(\text{int}(A)) = \text{cl}(A)$, where $ A \subseteq \mathbb{R}$ is convex? I know that if $A$ is convex, $\text{int(A)}$ and $\text{cl(A)}$ are convex too. I need ...
4
votes
2answers
151 views

proving this inequality related to conjugate functions

For $x \in \mathbb{R}^n$ let us denote $x_{[i]}$ the $i$th largest component of $x$ s.t $$ x_{[1]} \geq x_{[2]} \geq x_{[3]}\ge\cdots $$ The function $$ f(x)= \sum_{i=1}^r x_{[i]} $$ is the sum of ...
4
votes
2answers
127 views

How should I prove a set is convex?

Given a set $$ \mathbf{S} = \{ \mathbf{x}\:|\: \mathbf{x}^T\mathbf{V}\mathbf{x}=1 \} $$ where $\mathbf{V}$ is a positive semidefinite matrix. How to prove this set is convex? I tried in the ...
4
votes
1answer
496 views

Limit of derivatives of convex functions

Let $(f_n)_ {n\in\mathbb{N}}$ be a sequence of convex differentiable functions on $\mathbb{R}$. Suppose that $f_n(x)\xrightarrow[n\to\infty]{}f(x)$ for all $x\in\mathbb{R}$. Let ...
4
votes
1answer
352 views

Convex combination

Assume that $I$ is a countable set, and we have $u_i\in \mathbb{R}^n$ for $i\in I$. Suppose that $v=\sum_{i\in I} a_i u_i$ and $\sum_{i\in I}a_i=1$ and $a_i\geq 0$. Can one show that there exists a ...
4
votes
1answer
129 views

Can we prove $\operatorname{tr}(M X X^T)$ is convex?

Define $f(X) = \operatorname{tr}(MXX^T)$. If $M$ is a positive semi-definite matrix, can we prove that $f$ is convex?
4
votes
1answer
29 views

What class of functions is characterized by the property $f[\operatorname{conv} A] \subseteq \operatorname{conv} f[A]$

It is well-known that the inclusion $f[\overline A] \subseteq \overline{f[A]}$ (for every subset $A$) characterizes continuous functions.1 Asking similar questions for other closure operators seems ...
4
votes
2answers
99 views

Describing convex hulls in purely metrical terms

Let $X$ denote a Euclidean space; take $X = \mathbb{R}^n$ for concreteness. Now consider $x,y \in X$. Then the line segment joining $x$ and $y,$ hereafter denoted $[x,y]$, can be described in ...
4
votes
1answer
45 views

If $\Omega$ is convex, then $K_{\Omega}$ is convex?

Let $\Omega\subset\mathbb{R}^n$ and $$K_{\Omega}=\{\lambda x|\lambda\ge0,x\in\Omega\}$$ Is it true that if $\Omega$ is convex, then $K_{\Omega}$ is also convex. Let $\gamma\in(0,1)$ and $z,t\in ...
4
votes
1answer
50 views

Is $f(x)x$ convex for increasing function $f$?

Suppose that $f:(0,\infty)\to[0,1]$ is strictly increasing and infinitely differentiable. I have an intuition that $$ g(x)=f(x)x $$ should be convex in $x$ (i.e. increasing at accelerating rate) ...
4
votes
1answer
104 views

How to prove Godunova's inequality?

Let $\phi$ be a positive and convex function on $(0,\infty)$. Then $$\int_0^\infty \phi\left(\frac{1}{x}\int_0^x g(t)\,dt\right)\frac{dx}{x} \leq \int_0^\infty \phi(g(x))\frac{dx}{x}$$ The ...
4
votes
3answers
2k views

convexity of inverse function

I have a question on the reverse of a convex function. Let $f(x)$ be a convex function. Is the reverse function, say $g(x)=f(x)^{-1}$, is necessarily a concave function ? Considering that such ...
4
votes
2answers
4k views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
4
votes
1answer
1k views

maximum and minimum singular values

I was studying the Stephen Boyd's textbook on convex optimization and have a question. The book says the following: The singular values of $A$, $\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_n$ are ...
4
votes
1answer
128 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
4
votes
1answer
946 views

Why does positive semi-definiteness in this inequality imply a convex set?

I was reading a proof that rewrote an inequality in the form: $$b^Tx +x^T A x \le \alpha$$ for $b,x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$, and with $A$ positive semidefinite. It then ...
4
votes
1answer
151 views

Is it possible to 'approximate' compact, convex sets in $\ell^2$ by the Hilbert cube

Define $H=\{(x_n)_n\in\ell^2:|x_n|\le \frac1n, n\in\mathbf N\}\subset\ell^2$. This set is known as the Hilbert cube and it is well-known that $H$ is compact, convex and non-empty. Let ...
4
votes
1answer
184 views

Convex hull approximated from inside by only finite number of elements?

In approximating the convex hull "from inside", i.e. $$ \text{conv}S = \{ x \in \mathbb{R}^n \mid x= \sum_{i=1}^k \lambda_i x^i, x^i \in S, \lambda_i \geq 0, \sum_{i=1}^k \lambda_i= 1 \} ...
4
votes
2answers
366 views

How to verify the following function is convex or not?

Consider function $$f(x)=\frac{x^{n_{1}}}{1-x}+\frac{(1-x)^{n_{2}}}{x},x\in(0,1)$$ where $n_{1}$ and $n_2$ are some fixed positive integers. My question: Is $f(x)$ convex for any fixed $n_1$ and ...
4
votes
1answer
700 views

Both convex and concave functions

Let $f$ be a function from $\mathbb{R}^n$ to $\mathbb{R}$, which is convex & concave and continuous with $f(0)=0$. How to prove that $f(x)=q\cdot x$ for all $x$ in $\mathbb{R}^n$, for a scalar ...
4
votes
1answer
1k views

How to prove this function is concave?

This is the function: $\displaystyle f(\vec x) = \log \frac{\exp(x_1)}{\sum_{i=1}^n \exp(x_i)} $
4
votes
1answer
3k views

Positive definite Hessians from strictly convex functions

Let $f: D \to \mathbb{R}\ $ be a function on non-singular, convex domain $D \subseteq \mathbb{R}^d$ and let us assume the second-order derivatives of $f$ exist. It is well known that $f$ is convex if ...
4
votes
2answers
68 views

Supporting hyperplane of a convex set

Let $\Omega$ be a bounded convex set in $\mathbb{R}^n$, and let $\partial \Omega$ denote its boundary. Fix a point $p$ in $\Omega$, and let $c$ denote the point on $\partial \Omega$ that is closest ...
4
votes
1answer
50 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
4
votes
2answers
66 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
4
votes
2answers
69 views

$\{x_n\} \to x$ iff $\bigcap_{n=1}^\infty K_n = \{x\}$

Let $\{x_n\}$ be a sequence in $\mathbb{R}^k$ and let $K_n$ be the intersection of all closed convex sets that contain $x_m$ for all $m \ge n$. How do I show that $\{x_n\}$ converges to $x$ if and ...
4
votes
3answers
136 views

Is every such function convex or concave?

I was pondering convex functions today, and the following questions naturally posed themselves. Call a function $f : \mathbb{R} \rightarrow \mathbb{R}$ $2$-limited iff for all $m,c \in \mathbb{R},$ ...
4
votes
2answers
56 views

about an interesting affirmation involving convex sets

Consider the following definition Definition: Let $\Omega \subset R^n$ a bounded convex set. A point $x \in \partial \Omega$ is called an extremal point if $x$ cannot be written as linear ...
4
votes
1answer
51 views

Is the set of convex bodies include in a closed ball compact?

I consider the set $\mathcal{K}_B$ of convex bodies (convex and compact) which are include inside the unit closed ball of $\mathbb{R}^d$. I endow this set with the Hausdorff distance. Is it compact?
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$ ...
4
votes
2answers
290 views

Is projection of a convex polyhedron on a plane a convex polygon?

If we have a convex polyhedron with vertices $\mathbf{V}$ and project it on a plane $\mathbf{P}$, is this procedure equivalent to projecting points in $\mathbf{V}$ on the plane $\mathbf{P}$ and then ...
4
votes
2answers
123 views

Convex sets: a hint on how to solve a problem

Could anyone give me a hint on how to solve the following problem? Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, ...
4
votes
1answer
151 views

Is this matrix function convex or non-convex?

Given, $g(Z)=Tr(Z^Tf(Z)Z)$ , where $f(Z)=h(Z)-ZZ^T$ is a p.s.d matrix formed using entries in $Z$, where again $h(Z)$ is a diagonal matrix with its $i$'th diagonal entry being ...
4
votes
1answer
310 views

Anderson's Inequality for Gaussian measures

Let $C\subset \mathbb R^n$ be convex and symmetric about the origin. I am trying to prove that $\gamma(C) \geq \gamma(C+x)$ for any $x\in \mathbb R^n$, where $\gamma$ is the standard Gaussian measure. ...
4
votes
1answer
85 views

convex relaxations

Is there a notion of "best" convex relaxation of a particular function in a normed vector space? For example, the $\ell^0$ pseudo-norm can be relaxed into the $\ell^1$ norm, and that allows us to ...
4
votes
1answer
2k views

Relation between Positive definite matrix and strictly convex function

I have a problem. From wikipedia http://en.wikipedia.org/wiki/Positive-definite_matrix any function can be written as $$z^TMz$$ where z is a column vector and M is a symmetric real matrix. However ...
4
votes
1answer
407 views

Is the variance concave?

Let $X$ be a discrete random variables with values in the set $\{x_1,\ldots, x_n\}\subset\mathbb{R}$. Denote by $p_i$ the probability that $X=x_i$. We can then regard the variance $Var(X)$ as a ...
4
votes
1answer
317 views

Cancellation law for Minkowski sums

Let $(X,\|\cdot\|)$ be a Banach space and $A,B,C\subset X$ closed bounded non-empty convex subsets. Let $+$ denote the Minkowski symbol for addition. Does the $+$ satisfy: $$A+C\subset B+C\implies ...
4
votes
2answers
337 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone.

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
4
votes
3answers
353 views

Average degree of convex hull vertices in a Delaunay triangulation

Let $P \subset \mathbb{R}^2$. The boundary of $DT(P)$, the Delaunay triangulation of the point set $P$, is $conv(P)$. It is also known that the average degree of the vertices of $DT(P)$ is $\lt 6$. ...
4
votes
1answer
167 views

Is the boundary of a compact convex set given by the union of its proper faces?

Let $C$ be a compact convex subset of a finite-dimensional real vector space $V$ with non-empty interior (where $V$ is equipped with the unique Hausdorff linear topology, i.e. with the standard ...
4
votes
1answer
1k views

Prove that the convex hull of a set is the smallest convex set containing that set

How do you prove that the convex hull of A is the smallest convex set containing A? edit: definition of a convex hull: Given a set A ⊆ ℝn the set of all convex combinations of points from A is called ...
4
votes
3answers
3k views

how to decide if set is convex?

I have two variables, $x$ and $y$, and a few inequalities of the form $f(x,y) \le g(x,y)$. I want to know if the intersection of all $(x,y)$ that satisfy each inequality is convex. Is there some ...
4
votes
1answer
24 views

Which functions are the composition of convex functions?

The composition of convex functions is not necessarily convex or concave: For example, composing $f_1(x) = x^2-1$ and $f_2(y) = y^2$ gives $f_2(f_1(x)) = (x^2-1)^2$. Or consider $f_1(x) = x^2$ and ...
4
votes
1answer
56 views

Number of ways to separate $n$ points in the plane

Say you are given $n$ points such that no three are colinear. Show the number of ways to separate them into two subsets by drawing a straight line depends on $n$ but not the position of the points.
4
votes
1answer
132 views

Obtaining an estimate for the Lagrangian $L=H^*$ from the Hamiltonian $H$

This is from C. Evans' PDE book, page 130. The convex function $H:\mathbb{R}^n\to\mathbb{R}$ is $C^2$ and satisfies $$ H\big(\frac{p_1+p_2}{2}\big) \leq \frac{1}{2}H(p_1) + \frac{1}{2}H(p_2) - ...