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
16 views

How do I prove this simple result for the face structure of convex sets?

I have a convex set $P$ with faces $f_1, f_2$ such that all extremal points of the convex set belong to either $f_1$ or $f_2$ (the faces are disjoint and cover $P$). How can I prove that if every ...
1
vote
1answer
24 views

Convexity of multi variate functions

Let $f:\mathbb{R}^m\rightarrow \mathbb{R}$ be a smooth function. I know $f(x)$ is convex if its Hessian ($\frac{\partial^2 f(x)}{\partial x\partial x^T}$) is positive semi-definite. Now, let $g(...
2
votes
0answers
23 views

Is $(\sum_{i=1}^n a_i{x_i}^2)(\sum_{i=1}^n b_i{x_i}^2)$ convex?

I was trying to solve a problem and at a point I needed that $$(\sum_{i=1}^n a_i{x_i}^2)(\sum_{i=1}^n b_i{x_i}^2),$$ $a_i,b_i >0$ is convex. So, I tried instead to prove that $x^2y^2$ is convex( ...
2
votes
2answers
30 views

How can I prove the concavity of $f(p_1,p_2,\ldots,p_n) = \sum_{i = 1}^n p_i(1-p_i)$?

Assume $p_n$ is the probability of being in class $n$ which mean that $f(0) = 0$ , $f(1) =0$ , and $p_1+p_2 = 1$ I need to come up with a concave function that show the relation between $p_1$ and $...
3
votes
2answers
84 views

Can you prove that this function is convex? $\sqrt{2x_1^2+3x_2^2+x_3^2+4x_1x_2+7} + (x_1^2+x_2^2+x_3^2+1)^2$.

My analysis: The second term can be proven to be convex as follows. It is basically a composition of norm with an affine transformation to the power of four: $(x_1^2+x_2^2+x_3^2+1)^2 = \|(x_1^2, x_2^2,...
0
votes
0answers
5 views

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x$?

Is $f(x)=-3x_1+x_2-x_3^2$ pseudoconvex at $\bar x=[-115/588, -95/588, 5/14]^T$? Pseudoconvexity: If $\nabla f(\bar x)^T(x-\bar x)\ge0$, then $f(x)\ge f(\bar x)$ for any $x\in \mathbb{R^3}$ (in this ...
1
vote
1answer
38 views

$xy \leq \frac{x^p}{p}+\frac{y^q}{q}$

I struggled to show that this is true when $x,y >0$, $p>1$ and $q=\frac{p}{p-1}$. But, I managed to show that if we assume that $x \geq 1$ the assertion is possibly false only for a finite ...
0
votes
0answers
18 views

Convexity and composition of functions

A function $g(f(x))$ is convex if $g$ and $f$ are convex and $g$ is non-decreasing, what happens if $g(f_1(x),f_2(x),...,f_m(x))$ where $x = (x_1,...,x_n)$. Is $g$ convex if each $f_i$ is convex in $x$...
0
votes
1answer
30 views

Is every convex cone a manifold?

Let $C \subseteq \mathbb{R}^n\setminus \{0 \}$ be a connected convex cone*. Question: Is $C$ always a topological manifold (perhaps with boundary)? A smooth one? Does anything change if we do not ...
1
vote
0answers
42 views

Log-convexity of completely montone sequences

Let $s_0, s_1, \ldots$ be a completely monotone sequence. This means that, defining \begin{align*} (\nabla s)_n &= s_{n}-s_{n+1}\quad\text{and}\\ (\nabla^{r+1}s)_n &= (\nabla^{r}s)_n - (\...
0
votes
0answers
11 views

Proof of $A\ne \mathrm{conv}~ \mathrm{relbd} A\Rightarrow A$ is a flat or a half-space

Picture below is from the 16 page of Schneider R. "Convex Bodies--The Brunn-Minkowski Theory". I am fuzzy with the red line, what is the translate of $H^-$ ? And what is the effects of convexity ...
0
votes
2answers
62 views

$\big\langle\nabla f(x)-\nabla f(y),\,(x-y)\big\rangle\ge m\,\left\| x-y\right\|^2,\;m>0\;$ for strictly and strong convex function [closed]

Prove that $\,\big\langle\nabla f(x) - \nabla f(y),\, (x-y)\big\rangle \geq m\,\left\lVert x-y\right\rVert^2, \;\,m > 0\,$ for strong convex function $f: \mathbb R^n \to\mathbb R$. Is it true for ...
0
votes
1answer
31 views

Lipschitz implies bounded gradient

Assume $f:\mathbb{R}^n \to \mathbb{R}$ is convex, and $L$-Lipschitz, so $|f(x)-f(y)|\leq L\|x-y\|$. I would like to show that $\|\nabla f(x)\|\leq L$. In one dimension this is a straightforward ...
1
vote
0answers
25 views

Is there a way to determine if the Convex Hull of two polyhedra is going to be huge?

So in this post: Faster Algorithms for Convex Hulls I was interested in determining if a convex hull of two $n$ dimensional polyhedra can be computed quickly, and the answer was in general: no, ...
1
vote
1answer
60 views

A consequence of the convexity of $ f(x) = x \log x $

I verified that $f:\mathbb{R_{+}^{*}} \rightarrow \mathbb{R}, f(x) = x \log x $ is convex, since it is twice differentiable and $f''(x) = \frac{1}{x}$ is positive for the domain. But my teacher asked ...
3
votes
1answer
41 views

Is $\Gamma(\alpha, 0, x)$ log-concave as a function of $x$ (for fixed $\alpha$)?

The incomplete Gamma function is defined as: $$\Gamma(\alpha, 0, x) = \int_0^x t^{\alpha - 1} e^{-t} dt$$ Let $\alpha \ge 1$ be a fixed number. Is $\Gamma(\alpha, 0, x)$ log-concave, as a function ...
1
vote
0answers
86 views

Some intuition on the support function of a convex set

I have some doubts on the interpretation and properties of the support function of a convex subset of $\mathbb{R}^d$. (1)Let $K$ be a convex set in $\mathbb{R}^d$. (2) The support function of $K$ is ...
1
vote
2answers
31 views

Is a convex cone a convex polyhedron?

Say that I have a convex cone $C=\{t|Ax = t, x\geq 0\}$. where $x\in R^n$, and $t\in R^m$, $A\in R^m\times R^n$. Can I say that this is a convex polyhedron? and why? EDIT: Just in order to avoid ...
1
vote
1answer
43 views

Lagrange's theorem and convex functions

Let f:U⊂ $\mathbb{R}^n$--->$\mathbb{R}$ a $C^1$ function with U being convex and an open set. Let g: U ⊂ $\mathbb{R}^n$ ---> $\mathbb{R}^m$ (with m smaller than n) an affine application. Let M={x $ ...
0
votes
0answers
38 views

convex hull of a lower hemicontinuous correspondence is lower hemicontinuous

Let $(X, \mathcal{T})$ and $(Y, \mathcal{T}')$ be two topological spaces. We call a correspondence (set-valued function) $F: X \rightarrow 2^Y$ lower semicontinuous if for every $G \in \mathcal{T}'$ ...
0
votes
1answer
20 views

Locally convex spaces - is any space that contains a locally convex space as a subspace, also locally convex?

Given $E$, a locally convex space (l.c.s.) and $E\subseteq F$ where $F$ is another subspace of a larger vector space. The inclusion is strict since I know there exists a $y\in F\backslash E$. I have ...
0
votes
0answers
16 views

Characterization of projective convexity

Let $K$ be a closed set in projective space $\mathbb P^n$. Is it true that $K$ is "projectively convex", i.e., its intersection with every line is connected, if and only if it is the projectivization ...
0
votes
1answer
23 views

Proof of property of unique nearest point equal to convex.

In the picture below, I really don't know how to use the compactness to get there will be a ball $C$ with maximal radius. I report this book for my classmate and teacher. I tell they the $r$ has a ...
0
votes
0answers
21 views

If $f,g:\mathbb{R} \rightarrow \mathbb{R}$ are positive, non-increasing and convex functions, then $F(x,y) = f(x)g(y)$ is quasiconvex.

Hypothesis: $\forall x_{1},x_{2}\in \mathbb{R}, \forall \lambda \in [0,1], f(\lambda x_{1} + (1- \lambda) x_{2}) \leq \lambda f(x_{1}) + (1- \lambda) f(x_{2})$ $\forall x_{1},x_{2}\in \mathbb{R}, \...
0
votes
1answer
26 views

Extreme points of unit ball of $l_1(\mathbb{N})$

Let $K$ be the closed unit ball of $l_1(\mathbb{N})$ over real numbers. Show that $$ Ext(K)= \{\pm e_n: e_n=(0,\ldots,1,0,\ldots)\}. $$ My attempt: I could prove that $\{\pm e_n: e_n=(0,\ldots,1,0,\...
0
votes
0answers
14 views

Solve convex optimization problem with objective function having power \alpha >1

I am not able to figure out how to get the explicit solution of the following minimization problem: $$\min_{\mathbf{w}\in \mathbb{R}^n} = \sum_{i = 1}^{k}b_i\left(\mathbf{w}^T\mathbf{Z_i}\right)^{\...
1
vote
0answers
38 views

Need to prove that convex property is the intersection of an increasing and decreasing property for graph

I need to prove that any convex property for graphs can always be expressed as the intersection of an increasing property and decreasing property for graph, specifically that: $\forall A\subset B\...
0
votes
0answers
20 views

general framework for proof of convexity in least square problem

Let $f(x_i,\theta) : X \times \Theta \rightarrow Z$ be a parametric function with parameter $\theta$ that we wish to fit to set of samples $S =\{(x_i,z_i)\}_{i=1}^N$, where $(x_i, z_i) \in X \times Z$....
3
votes
1answer
50 views

Convex set: extreme points and distance to the origin

I'm fairly sure the following is true, although I wouldn't mind being proven wrong. If true, I would like to see an elegant proof, as my attempts are kind of messy. Let $K\subset\mathbb R^2$ be a ...
0
votes
0answers
27 views

convexity of composite function

There is a composite function F(x)=f(g(x)): R -> R where f(v): R^2 -> R and g(x): R -> R^2. It is given that f(v) is convex on v and v = g(x) gives a map R -> R^2. If x is in a convex set, is F(x) ...
0
votes
1answer
68 views

Convex set without zero

Let $\emptyset \neq A \subset \mathbb{R}^n$ be a convex set with $0 \notin A$. Then there exist a $v \in \mathbb{R}^n$ such that $v \cdot a \geq 0$ for all $a \in A$ and there exists $a_0 \in A$ with $...
0
votes
0answers
18 views

An inequality of a multivariate function: $f(x_1,…,x_n) \geq \frac{1}{n}\sum_i^n f(x_i,x_i,…,x_i) $

Let us assume we have a non linear function $f : \Bbb R^{n+} \to \Bbb R ^+$, and let $x = \{x_1, x_2 , ..., x_n\}$, $x_i \in \Bbb{R}^+$, further define $\bar{x} = \frac{1}{n}\sum_i^n x_i$. My ...
0
votes
0answers
27 views

A necessary and sufficient condition for $f(x,y) = \phi(x²+y²)$ be a convex function

Let $f(x,y) = \phi(x²+y²) , \phi \in C^2$ and $\phi$ non-decreasing. Proof that $f$ is convex in the disk $x²+y² \leq a² \iff 2u \phi''(u) + \phi'(u) \geq 0 $ $\forall u \in [0,a]$ Here is my ...
0
votes
1answer
36 views

Show non-convexity of a function with vector input

How does one go about proving non-convexity of the function d? $$ d(v) = 1/2*||F(v)- p||^2 $$ $$ F(v)=\sum_{i=1}^n l_i*\begin{pmatrix} cos(\sum_{j=1}^i v_j) \\ sin(\sum_{j=1}^i v_j \end{pmatrix} $$ ...
0
votes
0answers
25 views

Subdifferential optimality conditions

I need help with subdifferential optimality. Let $f(x_1, x_2)=x_1^2 + x_2^2 + |x_1 -x_2 - y|$. Find: \begin{align} \min_{x_1, x_2} f(x_1, x_2) \end{align} This is convex, so must have unique ...
0
votes
0answers
25 views

minimal representation of convex hull

Here is a question about the convex hull. Let $S$ be a set and $\bar{S}$ be the closed convex hull of $S$, i.e., $\bar{S}$ is the smallest convex set that contains $S$. Then is the following claim ...
2
votes
1answer
109 views

Solution for $\min_{x^Tx=1} x^TAx-c^Tx$

$\min_{x^Tx=1} x^TAx-c^Tx$ looks like a simple QPQC problem. If $A$ is positive semi-definite, can I get the solution by first getting $x=A^{-1}c$ and then projecting $x:=\dfrac{x}{||x||}$ to make ...
0
votes
0answers
23 views

Sum of convex and concave functions when one is greater than the other

Given two $C^\infty$ functions $f,g:\mathbb{R}\to\mathbb{R}$ such that $f(x)>g(x)\text{ }\forall x\in\mathbb{R}$. Moreover, we know that $f(x)$ is convex while $g(x)$ is concave. Now, let's define $...
0
votes
0answers
17 views

Comparison between secant and derivative in a convex function

Imagine that we have a function $f:\mathbb{R}\to\mathbb{R}$ which is convex, that is $f''>0$. We also know that $f'''<0$, that is its first derivative function is concave. Now, we can define its ...
1
vote
0answers
34 views

Is this function really not concave or convex in any range?

Consider the function $f(x,y)=\frac{y}{1+e^x}$ where $0<y<1$ and $x \in \mathbb{R}$. If you plot this function, it looks like this: Also note that for a given value of $y$ the function $f$ ...
1
vote
1answer
36 views

Properties of convex function with Lipshitz continuous gradient (Prof. Nesterov's textbook)

I am reading the Prof. Nesterov's textbook: Introductory lectures on convex optimization - a basic course p.57 I have problem in the following: My ...
3
votes
1answer
68 views

interior of convex hull relatively open

Consider $k+1$ affinely independent vectors $\left\{p_0,p_1, \dots, p_k \right \}$ in $n$-dimensional euclidean vector space $n>k$ and consider their convex hull. It is known that each point $x$ of ...
0
votes
0answers
30 views

If $f$ is log-convex then $f$ is convex

Here's my attempt: $f$ is log-convex. Then: $\log f(\lambda x + (1-\lambda)y )\leq \lambda \log f(x) + (1-\lambda) \log f(y)$ As $e^x$ is increasing, we can apply it to the inequation without ...
0
votes
0answers
25 views

A function is convex if and only if its gradient is monotonous.

Let a convex $ U \subset_{op} \mathbb{R^n} , n \geq 2$, with the usual inner product. A function $F: U \rightarrow \mathbb{R^n} $ is monotonous if $ \langle F(x) - F(y), x-y \rangle \geq 0, \forall x,...
0
votes
1answer
17 views

Quasiconvexity (in the sense of Morrey) implies Rank-One convexity

I am trying to understand why Quasiconvexity implies Rank-One convexity. In a standard proof of this fact a sequence of functions is constructed, which converges weakly to zero in $W^{1,p}.$ in ...
0
votes
0answers
24 views

Composition of convex and concave functions

I had a homework question: "Show that the function f(x,u,v) = -log(uv-xTx) is convex on domain {(x,u,v)| uv-xTx,u,v > 0}". EDIT: x,u,v are Real No.s One pdf I found online says: "We can express f as ...
0
votes
1answer
36 views

Minkowski sum and Polygons

The problem:.. Given two convex polygons $A$ and $B$, we can define Minkowski sum as A + B = {a + b: a $\in$ A, b $\in$ B}, where $a + b$ vector sum. Prove that: every vertex $p \in A + B$ is a ...
0
votes
1answer
18 views

How to prove a two variable set is convex

$X=\{(x,y)\in R^2\ :\ 3\le 2x+3y\le 8\}$ i tried to solve it as: Let set $X$ is convex for $x_2,y_2\in X$ such that $\alpha x_1+(1-\alpha)x_2$,$\alpha y_1+(1-\alpha)y_2\in X$ Now, $3\le 2x+3y\le 8$ ...
1
vote
1answer
28 views

Proximal-type support function properties - nonnegative & strongly convex (proof)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The following part confuses me: $\\$ $\\$ ${\color{red}{E}}\...
2
votes
0answers
75 views

LASSO constrained and penalised forms: first - order conditions?

The LASSO problem can be formulated in two ways: 1) Constrained formulation: $$ \|Xw-y\|^2\to\min_{w}\\ \text{s.t. } \sum_{i}|w_i|\leq{t}. $$ 2)Penalised formulation: $$ \|Xw-y\|^2+\lambda\left(\...