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)

2
votes
0answers
7 views

About the interior of a polytope

Let us consider a polytope 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
0answers
15 views

Compact set in the interior of a cone

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
28 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 ...
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 ...
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" ...
1
vote
1answer
34 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
34 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 ...
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$ ...
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 ...
3
votes
2answers
39 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 ...
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: ...
1
vote
1answer
41 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. ...
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, ...
2
votes
0answers
24 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 $ ...
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 ...
0
votes
0answers
10 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
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$ ...
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 ...
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
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 ...
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
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 ...
1
vote
2answers
34 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
21 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
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 ...
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 ...
3
votes
2answers
61 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) $$ ...
1
vote
0answers
35 views

sum of fractional functions optimization problem

Consider the following sum of fractional functions optimization problem $$ \begin{array}{l} \mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1}{{{\bf{a}}_i^T{\bf{x}} + {b_i}}}} \\ ...
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 ...
1
vote
1answer
24 views

Why is this transformation convex?

Let $f:\mathbb{R}^n \to \mathbb{R}\cup\{ \infty \}$ be convex. It's claimed that this implies $g:\mathbb{R}^n \times (0,\infty) \to \mathbb{R}\cup\{ \infty \},(x,y)\mapsto yf(\frac{x}{y})$ is convex. ...
0
votes
0answers
19 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 ...
0
votes
1answer
17 views

Polyhedral cone as conic hull of a finite set

I am reading notes on optimization and it was claimed that all polyhedral cones in $K\subseteq \mathbb{R}^n$ can be written Cone(R) where $R\subseteq \mathbb{R}^n$ is a finite set. That is, if K is a ...
0
votes
0answers
6 views

Inner construction of polyhedral set: cone part uniquely determined

The "inner construction" of a polyhedral set is: given $V,R\subseteq \mathbb{R}^n$, $|V|,|R|\in \mathbb{Z}^+$ (nonempty, finite), put $S:=Co(V)+Cone(R)$. It was claimed that Cone(R) is uniquely ...
3
votes
3answers
83 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
1answer
28 views

Biconjugate of a nonconvex function

Is biconjugate of a non-convex function, the tightest lower bound on that function? If yes why?
7
votes
1answer
52 views

Partitioning $\mathbb{R}^d$ with two convex sets

The problem/puzzle is: Find two convex sets in Euclidean space, $A, B\subseteq\mathbb{R}^d$, such that the number of connected components of $\mathbb{R}^d\setminus (A\cup B)$ is the maximum ...
-1
votes
2answers
42 views

Joint Convexity Proof

Let $x$ be $n \times 1$ vector and $Y$ be $n \times n$ matrix. Prove that $f(x,Y) = x'Y^{-1}x$ is jointly convex in $x$ and $Y$ when $Y \succ 0$.
0
votes
0answers
13 views

Prove that $f(x,y,z)=\ln x-\alpha\ln y-(1-\alpha)\ln z$ is quasiconvex

I am trying to show that $f(x,y,z)=\ln x-\alpha\ln y-(1-\alpha)\ln z$ defined for $x,y,z\in\mathbb{R}^+$ and $\alpha\in(0,1)$ is quasiconvex. This is equivalent to showing that the set ...
1
vote
1answer
30 views

How to define a “line” and “symmetry w.r.t. a line” in $L_2(\lambda)$ space

For any $x,y\in L_2([0,1],\lambda)$, define the inner product $\langle. , . \rangle$ by \begin{equation} \langle x, y \rangle=\int_{[0,1]} x(t) y(t) \lambda (dt) \end{equation} Is it proper to ...
0
votes
1answer
23 views

Is mutual information convex in the joint distribution?

Assume some joint distribution $P(X,Y) = P(Y|X)P(X)$. It is well know that, for fixed $P(Y|X)$, mutual information is a concave function of $P(X)$ and, for fixed $P(X)$, a convex function of $P(Y|X)$ ...
0
votes
1answer
11 views

Continuity of convex functions that have continuous restrictions to closed subspaces

Let $X$ be an infinite-dimensional normed vector space , let $U\subset X$ be an infinite-dimensional closed subspace, and let $f:X\to[0,\infty)$ be convex. Question: If the restriction $f|_U$ is ...
2
votes
0answers
49 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
1
vote
0answers
47 views

Practical application of Gauss-Lucas theorem

Let $z_1,z_2,z_3 \in \mathbb C$ pairwise distinct be the affix of points $A, B$ and $C$. Let $P(x)=(x-z_1)(x-z_2)(x-z_3)$. Let $z_4$ and $z_5$ be the roots of $P'$ (with the possibilty that ...
1
vote
2answers
46 views

Is the function $\ln(ax + b)$ increasing/decreasing, concave/convex?

$h(x) = \ln(ax + b)$ NB. Examine your results acccording to values of $(a,b)$ I've differentiated twice in order to get the following: $$ h''(x) = -\frac{a^2}{(ax+b)^2} $$ I think this proves ...
0
votes
1answer
35 views

Complex analysis question regarding Cauchy's integral formula and holomorphic functions

Let $U \subseteq \Bbb{C} $ be an open convex subset of $\Bbb{C}$ We also assume that $\partial U$ is smooth. We fix a point $z_0 \in U.$ Using Cauchy's integral formula, show that $$\lvert ...
0
votes
0answers
4 views

Convexity of Log Determinant of Function

Given a function $g(x): \mathbb{R} \to \mathbb{R}^{N x N}$, under what circumstances is $f(x) = - \log \det g(x)$ a convex function? Assume that each of the $N^2$ entries in $g(x)$ is convex over ...
4
votes
1answer
36 views

Area of the lattice generated from $(n, n\sqrt{2} \mod 1)$

I plotted $\Big\{ (n, n \sqrt{2} \, \mathrm{mod} \,1) \;\Big| -50 \leq n \leq 50 \Big\}$ and even though the $n \sqrt{2}$ is a line, the pattern that emerges is a lattice. What is the basis of this ...
0
votes
1answer
30 views

Finding KKT conditions for nonlinear optimization problem.

I have an optimization like below: $\text{ minimize } \sum_k - \log_2 x_k $ $\text{subject to: } x_k \leq q , k =1,2, \cdots, N .$ I can form the Lagrange of the problem as below: $L(x, ...
1
vote
1answer
18 views

Convex hull of $3$ dimensional set reduced to $2$ dimensional set

Let $S = \{(f_1(t), f_2(t), f_3(t)) : t \in \mathbb{R}\}$ and suppose $f_3(t) \geq 1$ for all $t \in \mathbb{R}$. Is finding the convex hull of $S$ in some way equivalent to find the convex hull of $T ...