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)

0
votes
2answers
12 views

is function $f$ with given property convex?

Let $C$ be a convex set and $f: C\to R$ be function with following property: $$\forall x,y \in C \Rightarrow f(\frac12 x+\frac12 y) \leq \frac12 f(x)+\frac12 f(y)$$ Is function $f$ convex on ...
0
votes
0answers
5 views

Only one system of equation has solution

Let $A$ be a $m\times n$ real matrix. Show that only one of the following systems has solution: (I): $Ax > 0$ (II): $Ay = 0, y \geq 0, y \neq \theta$, where $\theta$ is zero vector. ...
3
votes
0answers
8 views

Show that system $Ax\geq 0,$ and $A^Ty=0, y\geq 0$ has solution satisfies $Ax+y>0$.

Let $A$ be a $m\times n$ real matrix. Show that system (I): $Ax\geq 0,$ (II): $A^Ty=0, y\geq 0$ has solution satisfies $Ax+y>0$. I have no idea to prove above claim. Can you give me ...
1
vote
0answers
5 views

Find two $\epsilon$ splitting sets in convex analysis

Let $\epsilon >0$. The hyperplane $<a,x>=\alpha$ is said to be $\epsilon$-splitting two sets $C$ and $D$ if $$\sup_{x\in C}<a,x>-\epsilon \leq \alpha \leq \inf_{x\in ...
1
vote
4answers
61 views

Prove that in triangle $ABC$,$\cos^2A+\cos^2B+\cos^2C\geq\frac{3}{4}$

I have two similar looking questions. $(1)$Prove that in triangle $ABC$,$\cos^2A+\cos^2B+\cos^2C\geq\frac{3}{4}$ $(2)$If $\Delta ABC$ is an acute angled,then prove that ...
2
votes
1answer
23 views

About the interior of a polyhedron

Let us consider a polyhedron in $\mathbb{R}^n$ (in this context it must NOT be bounded) $\mathcal{P} = \{ x: A \cdot x \leq c\}$ for some matrix $A$. Let $\mathcal{I} = \{ x: A \cdot x < c\}$ be a ...
0
votes
1answer
24 views

Is the closure of a bounded open set in $\mathbb{R}^n$ locally convex about the boundary?

The question is basically in the title. I think it is true, but I'm not sure. Can someone verify whether this is in fact true. Thanks.
0
votes
0answers
34 views

Does a compact set in the interior of a cone also belong to the intersection of all slightly perturbed cones?

Suppose compact set $S \subseteq R^n$ is in the interior of $x_0+C$, where $C$ denotes a solid convex cone in $R^n$ with the vertex at $0$. I am trying to prove that $\exists r>0$ such that $$S ...
0
votes
1answer
14 views

Primal and dual feasible = optimal?

Is any primal feasible and dual feasible point of a convex function, a global min of that function? If yes, why? If no, do we need any more conditions?
0
votes
0answers
9 views

Almost surely strictly convex

Can anybody explain for me what almost surely strictly convex means? For example our function is $f(u)=u^TQu$ where u is a n-dimensional vector and Q is a n×n matrix. Thanks
3
votes
3answers
103 views

Is this an instance of any existing convex pentagonal tilings?

Inspired by Wikipedia's article on pentagonal tiling, I made my own attempt. I believe this belongs to the 4-tile lattice category, because it's composed of pentagons pointing towards 4 different ...
0
votes
0answers
32 views

Prove a complex function to be convex

I have a function and want to prove that it is convex when $0 \leq x \leq 1$: \begin{equation} f(x)=\frac{b1g'(x) f_1(x)^{n-2}+g'(1) \gamma}{g'(1) ( \gamma+b1) } \end{equation} and \begin{equation} ...
3
votes
1answer
44 views

Is this function Strictly convex or not?

We have a function $f(u)= u^{T}N^TNu$ where $u$ is a $n$-dimensional vector and $N$ is a $n\times n$ matrix. Is this a strictly convex function in $u$? I know that if the hessian of $f(u)$ with ...
18
votes
1answer
329 views

Does there exist regular planar pentagon?

How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ (treated as a surface) includes 5 points which form a regular planar pentagon?
0
votes
1answer
42 views

Legendre transform is everywhere finite iff $ f$ grows faster than $ 2$-norm

Let $f:\mathbb{R}^n \to \mathbb{R}\cup \{ \infty \}$ be convex. Its Legendre transform is $f^* (d):=\sup_{x\in \mathbb{R}^n}(d^Tx-f(x))$ Show $f^*(d)<\infty$ $\forall d\in \mathbb{R}^n$ iff ...
4
votes
1answer
317 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
0
votes
1answer
25 views

Strong convexity of Entropic regularization

Can somebody help me to prove that entropic regularizer $R(\mathbf{w})= \frac{1}{\eta}\mathbf{w}^T\log \mathbf{w}$ is strongly convex with respect to $l_1$ norm. My attempt: To show if a function ...
0
votes
1answer
35 views

Suppose $f(\beta)$ is strictly convex. Show that $f(\hat{\beta}_k^*) < f(\hat{\beta}_k)$

Suppose $f(\beta)$ is strictly convex. Show that $f(\hat{\beta}_k^*) < f(\hat{\beta}_k)$, where $\hat{\beta}, \hat{\beta}^* \in \mathbb{R}^n$ and $\hat{\beta}_k^* = \begin{cases} \hfill ...
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 ...
2
votes
2answers
1k views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull
1
vote
1answer
35 views

Negativity of Convex Combinations

Consider the functions $f(x)$, $g_1(x)$ and $g_2(x)$ with following properties: $\int f(x) dx =\int g_1(x)dx =\int g_2(x)dx =1$. Define the following measure of negativity for the functions: ...
0
votes
1answer
14 views

Classify the growth of functions and find a more general growth function

The following function $f(t,x):[0,T]\times R\mapsto R$ such that $\int^T_0|f(t,0)|^2 d t<\infty$, where $0<T<\infty$. If $f(t,x)$ satisfies $|f(t,x)|\leq Ax+B$ for each $x\in R$ and $A, B$ ...
2
votes
1answer
28 views

Multiplicative version of convex hull

The convex hull of a finite set of points, $(x_i,y_i) \in \mathbb{R_+}^2$ ($i=1,...,n$), is defined as: $$\left\{(\sum_{i=1}^{n} \alpha_i x_i,\sum_{i=1}^{n} \alpha_i y_i) \mathrel{\Bigg|} (\forall i: ...
3
votes
0answers
48 views

Subdifferential of integral

I am currently trying to extend my knowledge about subdifferentials. Now I am stuck at a particular property of the subdifferential. In this "paper" ...
3
votes
2answers
42 views

Faster Algorithms for Convex Hulls

I was interested in the following: Given two polyhedra $P_1, P_2$ specified in the form: $$ P_1 = {x : A_1x \le b_1 } $$ $$ P_2 = {x : A_2x \le b_2 } $$ Whereas $ x \in R^n$ and $b_1, b_2$ are ...
1
vote
1answer
43 views

Concavity of function implies convex upper contour

Today I saw a theorem in class that stated the following: $f$ is concave $ \Rightarrow\{z \in \mathbb R^n : f(z) \ge c\}$ is convex. The proof is relatively straight forward and I understand. ...
0
votes
1answer
26 views

How to show that $f(x,y,z) = (1-x^{2})^{2}+z^{2}+y^{2}+yz$ is a convex function on $S =\{(x,y,z) \in \mathbb{R}^3|\frac{1}{\sqrt 3} < x\}$?

Information: In the previous problem I had to find stationary points and the Hessian matrix and I found out that in the stationary points $(-1,0,0) $ and $ (1,0,0)$ were local minimums, and in the ...
0
votes
0answers
16 views

decomposition of Non-convex polygon

Is it possible to decompose a non-convex polygon, with more than one of its interior angles greater than 180, into a number of convex polygons ? If so, how is it possible ? Is there any algorithm for ...
1
vote
1answer
13 views

Are binomial coefficients with fixed “denominator” log-concave?

I'm working on a problem and began suspecting that the following inequality holds. Let $k\in\mathbb{N}$ be fixed, and define $f(n)={n\choose k}$. Then $f(n)$ is log-concave in $n$, in particular if ...
1
vote
1answer
26 views

Barrier cone of a convex set. Why it is a cone?

Barier cone $L$ of a convex set C is defined as $\{x^*|<x, x^*> \le \beta, x\in C\}$ for some $\beta \in \mathbb{R}$. However, consider an scenario when $x_1\in L$, $\beta>0$ and $<x, ...
0
votes
1answer
46 views

Where does this definition of convex set come from?

My textbook says the following. We call a set $E\subset R^k$ convex if $$\lambda x+(1-\lambda ) y\in E$$ whenever $x\in E, y\in E, 0<\lambda <1.$ I'm totally at a loss as to what this ...
2
votes
0answers
25 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
2
votes
1answer
26 views

Find projection of a point to a ball and box?

Find the projection of a point $y$ on a closed ball (center $x_0$, radius $r$) and hyperbox $H=\{x| a\leq x \leq b\}, a,b \in R^n$. I have no idea on how to proceed the proof. Please show me some ...
0
votes
0answers
11 views

Find the distance and projection convex analysis

Let $$C:= \{(x_1,x_2,x_3)| x_1^2+x_2^2+x_3^2 \leq 1, x_1^2-x_2\leq 0\},$$ and $y = (1,2,3)$. Find the distance $d_C(y)$ from $y$ to $C$ and projection $\pi(y)$ of $y$ on $C$. I have no idea ...
1
vote
1answer
39 views

Upper bound for a convex fractional function

Consider the following convex fractional function $$f\left( {\bf{x}} \right) = \frac{1}{{a - {{\bf{b}}^T}{\bf{x}}}}$$ where ${a - {{\bf{b}}^T}{\bf{x}}} \ge 0$. Is it possible to obtain a linear or ...
1
vote
1answer
37 views

Minimum of a convex function w.r.t. a subset of its domain

Let $X$ be a convex set and $f:X\mapsto \mathbb R$ be a continously differentiable convex function and $x_0$ be an element of $X$ such that $$\forall x\in X:f(x_0)\le f(x).$$ Let $y_0\in Y\subset X$ ...
0
votes
0answers
23 views

How to prove $\int_{\Omega} \sum_{i=1}^{N} f_i(x)dx$ is equivilant with $\sum_{i=1}^{N} \int_{\Omega} f_i(x)u_i(x)dx$

I have a 2D image in $\Omega$ space. Assume that the space can be separated into $N$ sub-regions $\Omega_i$ such that $\Omega_i \cap\Omega_j=\emptyset$; $\Omega_i \cup \Omega_j=\Omega, \forall ...
0
votes
1answer
18 views

Partitioning in convex problem (variables in two subsets)

Consider the following problem from textbook Convex Optimization Algorithm p.10: \begin{equation} \begin{aligned} &{\text{min}} & & F(x)+G(y)\\ ...
6
votes
4answers
50 views

If points in a convex set $C$ escape to infinity roughly in direction $v$ then an infinite ray in that direction exists

Let $C\subseteq \mathbb R^n$ a convex set. Assume there is a sequence $\{c_k\}_{k\in\mathbb N}$ with $c_k\in C$, $|c_k|\to\infty$ such that $v:=\lim \frac 1{|c_k|}c_k$ exists. Does this imply that ...
1
vote
3answers
768 views

How can it be proved that the geometric mean function is concave?

A function $f: \mathbb R ^n \rightarrow \mathbb R $ is said to be concave if $\forall x,y \in \mathbb{R}^n, \forall \lambda \in [0,1]$ we have $ \lambda f(x) + (1-\lambda)f(y) \le f( \lambda x + ...
1
vote
2answers
50 views

Proof that Right hand and Left hand derivatives always exist for convex functions.

Definition A function $f$ is convex on an interval if for $a,x, \text{and} \;b$ in the interval with $a\lt x\lt b$, we have $$\frac{f(x)-f(a)}{x-a}\lt \frac{f(b)-f(a)}{b-a}.$$ While reading the ...
3
votes
2answers
62 views

Is the minimum of a parametric convex function convex again?

Let $I$ and $J$ be compact intervals. Let $f:I\times J\to\mathbb R$ be differentiable and strictly convex. Is the function $g:I\to\mathbb R$ defined by $$ g(x) = \min_{y\in J} f(x,y) $$ ...
0
votes
2answers
84 views

How to prove the convexity of $f$ if the strict epigraph of $f$ is convex

I have trouble to prove the equivalence of the following two definitions of convex function. For convenience, I list them as follows: Def-A. Let $f : I\to \mathbb{R}$ be a function, where $I$ is (and ...
2
votes
1answer
29 views

Compact set has supporting hyperplane parallel to any hyperplane $H$?

Let $E$ be a non-empty compact set and $H$ is any hyperplane. Show that $E$ has a supporting hyperplane parallel to $H$. I have no idea to proceed the proof. Can anyone give me some hints? Thanks ...
0
votes
1answer
78 views

Example of sum of log-concave is not always log-concave

I know that sum of log-concave is not always log-concave. Could anyone provides me with an example to prove this? Like probability distribution fn (pdf) of normal distribution is log-concave; on ...
1
vote
2answers
35 views

Convexity of space of integrals of homotopic paths

Let $B$ be a Banach space. Consider a set $Q \subset B$, a path $\gamma_0:[0,1] \to Q$ and the set of paths $\Gamma_0$ of paths $[0,1] \to Q$ homotopic (with ends fixed) to the path $\gamma_0$. Let ...
0
votes
0answers
23 views

Interpolating a convex conjugates

Let $\|\cdot\|_2$ denote the 2 norm on $\mathbb R^N$. i.e. $\|x\|_2=\sqrt{x_1^2+x_2^2+\cdots+x_N^2}$. Then for any $\gamma \in (0,+\infty)$, we define $$ |x|_\gamma:= \begin{cases} ...
2
votes
3answers
28 views

strictly convex functions and limits

Suppose I have a strictly convex function $f(x)$ for $x\geq 0$, with $f(0) = 0$, $f'(0) =0$ and $f''(0) >0$. Is it obvious that $f$ must be superlinear as $x\to +\infty$? Alternatively, how can I ...
0
votes
0answers
20 views

Show that the set $\{y_1a_1+y_2a_2: -1\le y_1,y_2\le 1\}$ is a polyhedron

Show that the set is a polyhedron and express it in the form: $S = \{Ax\leq b, Fx = g\}$, $S=\{y_1a_1+y_2a_2 | -1\leq y_1\leq 1, -1\leq y_2\leq 1\}$ where $a_1,a_2\in\mathbb{R}^n$ My attempt: A ...
1
vote
0answers
251 views

Subsets of $\mathbb{R}^2$ that are convex, closed, and have non-empty interiors?

Can someone give me some guidance with this problem? Thanks. Suppose that $A, B \subset \mathbb{R}$ are convex, closed, and have non-empty interiors. Prove that $A, B$ are the closure of their ...