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
0answers
9 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
12 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 ...
2
votes
1answer
20 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
0answers
20 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
0answers
27 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
23 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
21 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
45 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 ...
1
vote
0answers
7 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$ ...
0
votes
1answer
34 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
48 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
31 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
23 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
33 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
23 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
18 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
2answers
78 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
27 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
51 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
38 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
12 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
27 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
48 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
46 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
44 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
0answers
33 views

is $\ell^1$-norm a strongly convex function? [closed]

Is $\ell^1$-norm defined by $|x|_1:=\sum |x_i|$ where $x \in \Bbb R^N$ a strongly (or strictly) convex function? I think, as "strong convexity" is defined, the $L^1$-norm has $f''=0$ (second ...
0
votes
1answer
34 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
35 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
28 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
17 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 ...
1
vote
2answers
64 views

Prove that function is convex

Let $f\colon [a,b] \rightarrow \mathbb R$ be continuous and convex. Let $m \colon [a,b] \rightarrow \mathbb R$ and $m(x) = \max \left\{f(y): y \in [a,x] \right\}$. Prove that $m$ is convex I ...
1
vote
1answer
24 views

Prove that all terms of a sequence of functions are convex.

Let $\ f_{n}: [0,1] \rightarrow \mathbb R, \quad f_{n}(x) = \left(e^{x}\right)^{1/n}.$ Is there a natural $n$ such that $f_{n}$ is concave on $[0,1]$? So second derivative is ...
2
votes
1answer
22 views

Dual Cone Construction $\{z \; | \;z \perp v \text{ for some } v \in \Lambda \}$

In a linear algebra computation, in order to estimate the second eigenvalue we consider a collection of vectors. Let $\Lambda$ be a cone in $\mathbb{R}^d$ then $$ \Lambda' = \Big\{z \;\Big| \;z ...
0
votes
0answers
20 views

Describing set of points where a convex function is differentiable

I've been told that the set of points at which a convex function $f: \mathbb R^n\rightarrow \mathbb R$ is differentiable is an $F_{\sigma}$ set, and I was hoping someone could help me see this. ...
1
vote
0answers
18 views

Condition for product of increasing and decreasing functions to be quasiconcave?

Is there any condition for product of increasing and decreasing functions to be quasiconcave? More specifically, I am having in mind a condition for $F(x)\cdot(1-G(x))$ to be quasi concave where $F$ ...
0
votes
1answer
43 views

Line segment in the unit sphere

I want to prove the following statement Let $X$ be a normed linear space, with linearly independent vectors $x,y$, such that $\|x\|=1=\|y\|$, with $\|x\|+\|y\|=\|x+y\|$, then there is a line ...
2
votes
1answer
35 views

Application of convex functions in economy [closed]

I have read in some texts that convex functions has application in economy. I want to see some clear examples of such applications.