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)

3
votes
3answers
523 views

Show by example that the Minkowski sum of two sets $X+Y$ may be convex even if neither $X$ nor $Y$ are convex

There were two parts to this question. I proved that the Minkowski sum of two sets $X+Y$ is convex whenever $X$ and $Y$ are convex, but how do I prove this second part? "Show by example that the ...
3
votes
1answer
1k views

How to prove convexity?

Let us consider the function $$I(p):= \frac {\Gamma(2-p)\Gamma(3p)}{(p\Gamma(p))^2} $$ on the interval $(0,1),$ where $\Gamma(x)$ denotes the gamma function. How to prove its convexity there?
3
votes
4answers
270 views

Is second derivative of a convex function convex?

If $f$ is twice differentiable and convex, is it true that $f''$ is a convex function ?
3
votes
3answers
96 views

Prove that $0 < x < y$ implies $\|x\| < \|y\|$ for any norm.

All vectors are real. Prove that $0 < x < y$ (element-wise) implies $\|x\| < \|y\|$ for any norm. This is probably very basic, but I don't seem to get the hang of it. Edit: it turns out this ...
3
votes
2answers
185 views

How can I prove that a function $f(x,y)= \frac{x^2}{y}$ is convex for $y \gt 0$?

How can I prove that a function $f(x,y)= \frac{x^2}{y}$ is convex for $ y \gt 0$? I take the Hessian matrix of $\displaystyle \frac{x^2}{y}$, and I got: $$H = \displaystyle\pmatrix{\frac{2}{y} & ...
3
votes
4answers
169 views

Sufficient condition for a function to be affine

If for a function $f:\mathbb{R}\to\mathbb{R}$, I can prove for any real $x,y$, that $f(\frac{x+y}{2})=\frac{f(x)}{2}+\frac{f(y)}{2}$, can I say for sure that it is affine, as in of the form ...
3
votes
3answers
138 views

Convexity of intersection

I have been asked to prove that, given a convex set $C$, its intersection with a line is also convex. From convexity definition, I have that $\forall x_1,x_2\in C, \alpha x_1+\beta x_2 \in C$ with ...
3
votes
3answers
158 views

Euclidean Metric and Convexity

Question: Consider the Euclidean metric space $(\mathbb{R}^n , \Vert\cdot \Vert)$. Let $X\subset \mathbb{R}^n$ and $f\colon X \to \mathbb{R}$. $X$ is said to be a convex set if for every $x,y \in X$ ...
3
votes
2answers
184 views

Show that $(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z)$.

If $x>0,y>0,z>0$ and $x+y+z=1$, prove that $$(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z)$$ Trial: Here $$(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z) \\ \implies (1+x)(1+y)(1+z)\ge 8(y+z)(x+z)(x+y)$$ I ...
3
votes
2answers
146 views

Property of convex functions

I am trying to show that if a function $f$ defined in $\mathbb R^n$ is differentiable and convex then $f(y)-f(x)\ge \nabla f(x)(y-x).$ for each $x,y\in\mathbb R^n$ Using differentiability of $f$ I ...
3
votes
3answers
1k views

Using the definition of a concave function prove that $f(x)=4-x^2$ is concave (do not use derivative).

Let $D=[-2,2]$ and $f:D\rightarrow \mathbb{R}$ be $f(x)=4-x^2$. Sketch this function.Using the definition of a concave function prove that it is concave (do not use derivative). Attempt: ...
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 $$ ...
3
votes
6answers
252 views

Convex Sets in Functional Analysis?

Why did Bourbaki choose to study convex sets, convex functions and locally convex sets as part of the theory of topological vector spaces, and what is so important about these concepts? I'd like to ...
3
votes
1answer
352 views

Two questions regarding the ergodic decomposition theorem

In Walters' An Introduction to Ergodic Theory, page 153, Remark (2), he writes If $E(X,T)$ denotes the set of extreme points of $M(X,T)$ then for each $\mu \in M(X,T)$ there is a unique measure ...
3
votes
1answer
69 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 ...
3
votes
2answers
72 views

Conjugate convex functions property

$E$ is normed vector space.Let $f\in E^*$ in a bounded linear functional from $E$ to $C$ and fix $x\in E$. We have $$\forall y\in E;\ \ \ \ f(y-x)\leq \frac{1}{2}\|y\|^2-\frac{1}{2}\|x\|^2$$ And I ...
3
votes
1answer
48 views

How to prove the compactness of the set of Hermitian positive semidefinite matrices

I am dealing with convex optimization problems. There are some useful theories for optimization problems where real-valued vector parameter, e.g., $x \in \mathbb{R}^n$, is considered. I manage to ...
3
votes
1answer
262 views

The unit ball in a Hilbert space

I have a request for any ideas to prove: If $H$ is a Hilbert space, then any unit vector is an extreme point of the unit ball of $H$. Every isometry is an extreme point of the unit ball of the ...
3
votes
2answers
89 views

Lipschitz functions in $\mathbb{R}^n, \ \ \mathbb{R}^m$, extension

I've found the following lemma : Let $\{x_1, . . . , x_k\}$ be a finite collection of points in $\mathbb{R}^n$ , and let $\{y_1, . . . , y_k\}$ be a collection of points in $\mathbb{R}^m$, such that ...
3
votes
2answers
493 views

When finding root, does Newton's method fail if the function is non-differentiable?

According to wikipedia's description, the Newton's method finding a root presumes a differentiable function. Then, will it fail when encountering non-differentiable function? For example, can it find ...
3
votes
1answer
159 views

Interior point and Minkowski functional

I want to prove for a convex set that contains zero a point $x$ is interior iff the value of Minkowski functional in that point is strictly less than $1$. is there anyone to help me.
3
votes
1answer
47 views

If a vector in a convex set can be extended infinitely to a certain direction, can any vector in that set be extended infinitely to that direction

Assume we have a convex set $U$. Given $x \in U$, assume there exists a vector $y$ such that $\forall t>0, \ \ x+ty \in U$. I wish to prove that $\forall z \in U,\ \ \forall t>0,\ \ z+t y \in U$ ...
3
votes
3answers
238 views

About convex function

The exercise is about convex functions: How to prove that $f(t)=\int_0^t g(s)ds$ is convex in $(a,b)$ whenever $0\in (a,b)$ and $g$ is increasing in $[a,b]$? I proved that $$f(x)\leq ...
3
votes
1answer
323 views

Concave functions on discrete domain

We are given a positive, non-decreasing function $f$ defined on natural numbers with $f(0) = 0$. $f$ has a submodularity-like property: $f(x+y) \leq f(x) + f(y) $ for all natural numbers $x$ and ...
3
votes
3answers
202 views

Quantifying convexity

What methods exist to quantify convexity. Yes, a set is convex if the the line between two points in the set is contained in the set, but is there a measure of how convex a set is? If so, what is ...
3
votes
1answer
147 views

Convexity of a set in Hilbert space

Let $H$ be a Hilbert space and $\left\{ e_{i}\right\} _{i=1}^{\infty}$ an orthonormal system. I need to prove that the following set is a convex set: $$C=\left\{ x\in ...
3
votes
2answers
30 views

Showing convexity, having trouble showing positive definiteness

I am interested in showing the convexity of $$-\log(-f(\pmb{x}))$$ for $f: \mathbb{R}^{n}\rightarrow \mathbb{R}^{-}$ and $f$ convex. If we let $\nabla f$ denote the column vector where the $i$th ...
3
votes
2answers
208 views

Gradient-descent algorithm always converges to the closest local optima?

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 ...
3
votes
2answers
1k 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 ...
3
votes
1answer
95 views

Showing existence of solution by positive definiteness/convexity

For a physics problem, I am considering the following problem: I have a certain function, $S: \mathbb{R}^M \rightarrow \mathbb{R}$, of which the critical points, given by $$ \frac{\partial ...
3
votes
1answer
209 views

Find the maximum convex area

My question is very similar to Plow's Question; but with this difference: How can I find the maximum convex area that can fit inside a non-convex region? For an example, consider this non-convex ...
3
votes
1answer
135 views

Equivalent definitions of uniform convexity.

I think I'm dumb, but I can't follow a simple proof from "Functional analysis and infinite dimensional geometry". They show that two different definitions of modulus of convexity of a norm are the ...
3
votes
1answer
301 views

Jensen's inequality and $L^p$ norms

Let $(X,\Sigma,\mu)$ be a probability space; in particular, $\mu(X)=1$. The integral form of Jensen's inequality can be phrased in terms of permuting a convex function $\varphi$ (say, with the ...
3
votes
2answers
1k views

KKT and Slater's condition

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following: "For any convex optimization problem with differentiable objective and constraint function, any ...
3
votes
1answer
98 views

Is this function convex

Is function $$f(x, y) = \left(\frac{x}{y} - a\right)^2 \left(\frac{y}{x} - \frac{1}{a}\right)^2$$ convex on the domain $$\{(x,y): x, y \in \mathbb{R}, x >0, y >0 \}\quad?$$ Now I think that it ...
3
votes
1answer
185 views

$(d-1)$-rectifiability of a boundary of compact convex set

Let us have a compact convex set $A\in \mathbb{R}^d$. Then $\delta A$ should be a $(d-1)$-dimensional rectifiable set. I don't seem to be able to show that it can be covered by a countable union of ...
3
votes
1answer
80 views

Showing that the set of polynomials is convex

How to show that the set of polynomials of $x^2+bx+c$ having at least one real root, is convex? Let $x^2+b_1x+c_1$ and $x^2+b_2x+c_2$ have at least one real root. Need to show that ...
3
votes
1answer
95 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 ...
3
votes
2answers
358 views

A standard quadratic minimization problem

Consider the "Complex" Quadratic minimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1 \end{align} ...
3
votes
1answer
203 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. ...
3
votes
1answer
515 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 ...
3
votes
1answer
487 views

Intersection of two (specific) convex functions

Given are the following two functions: $$g(z) = \left(z-2\right)\left(2+z\left(z-2\right)\right)$$ and $$h(z) = 2\left(z-1\right)^{2}\ln\left(z-1\right),$$ where $z>2$. I would like to show ...
3
votes
3answers
434 views

Representing a point inside a polyhedron as a convex combination of extreme points

Is there some standard way of representing any point in a polyhedron as a convex combination of some of the extreme points ? More precisely, by n poly(n) n extreme points where n is the number of ...
3
votes
1answer
49 views

Local convexity of the topology of weak convergence of probability measures

Let $X$ be a Polish or standard Borel space, and $\mathcal P(X)$ be the space of all Borel probability measures on $X$ endowed with the topology of weak convergence. I am thinking of using ...
3
votes
2answers
46 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 ...
3
votes
1answer
123 views

Proof that a set is convex

$$k\in \mathbb{R}_{+}$$ $$M=\left \{ (x_1,x_2)\in \mathbb{R}_{++}^2 \mid x_1 x_2\geq k\right \}$$ Prove that the set $M$ is convex. A hint is given (quoted from the text): We could choose to ...
3
votes
1answer
73 views

Hyperplane which can separate two closed convex set

Define: $$E=:\ell^1(R)=\{x=(x_n)_n: \|x\|_1=\sum_{n=1}^{\infty}|x_n|<\infty\}$$ We have two closed convex sets $X,Y$ as subsets of normed vector space $\ell^1(R)$ with $X\cap Y=\emptyset$ and $Y$ ...
3
votes
1answer
85 views

Does $\phi\circ g$ convex imply $\phi\circ f\circ g$ convex?

Assume that $\phi$ is an increasing function and $g$ is a decreasing function with $\phi\circ g$ convex. If $f$ is an increasing convex function does this imply $\phi\circ f\circ g$ is a convex ...
3
votes
1answer
122 views

Every face of compact convex set is closed?

Well, this is my doubt: Let $\vec{E}$ be a n.v.s. and $K\subset \vec{E}$ a compact convex set. Then every face of $K$ is closed. Any hint in order to prove it is welcome. Thanks in advance!
3
votes
1answer
108 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$