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)

0
votes
0answers
30 views

Boundary points of probability simplex

I have a very simple question for which I know the answer but I can not prove it! What are the boundary points of a probability simplex? I know every probability vector with one zero component lies ...
1
vote
2answers
66 views

Integral of convex set

Let $D$ be a convex set and $X_1,\dots,X_d$ be integrable random variables. If $X= (X_1,\dots,X_d)$ is in $D$ almost surely, why is it true that the vector $a= (\mathbb{E}X_1,\dots,\mathbb{E}X_d)$ ...
3
votes
0answers
40 views

Random convex shapes containing a ball

I'm interested in the properties of randomly generated convex shapes in $n$-dimensional space. Suppose I were to generate $v$ uniformly distributed random points on the $n$-ball of radius $R$. What ...
1
vote
1answer
35 views

Difference of concave functions

Suppose that there are two concave functions $f_1(x)$ and $f_2(x)$ defined on $x\geq0$. In addition, the functions are positive, smooth, bounded ($|f_2|\leq b_2,|f_1|\leq b_1$ such that $b_2 = ...
0
votes
2answers
383 views

What Stopping Criteria to Use in Projected Gradient Descent

Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
1
vote
0answers
19 views

Is the volume of a convex polytope efficiently computable from the vertices

Is there an efficient method to compute the exact volume of a bounded full-dimensional convex polytope, given the coordinates of its vertices (V-representation)?
1
vote
1answer
19 views

Convexity and Jensen's Inequality for simple functions

Suppose $\varphi$ is convex on $(a,b)$. I want to show that for any $n$ points $x_1,\dots,x_n \in (a,b)$ and nonnegative numbers $\theta_1,\dots,\theta_n$ such that $\sum_{k=1}^n \theta_k = 1$ we are ...
1
vote
2answers
52 views

Composition of non-monotonic convex function

Given the following composition of functions: $h:\Bbb R^k\rightarrow\Bbb R$ $g:\Bbb R^n\rightarrow\Bbb R$ $f(x)=h(g_1(x),g_2(x),...,g_k(x))$ There are known rules which guarantee ...
0
votes
2answers
37 views

an elementary inequality about convex function

Given $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is convex, then we have $f(y)\geq f(z)+Df(z)\cdot(y-z)$ where we fix a point $z\in B(x,r/2)$ Integrate the above inequality directly with respect to $y$, ...
0
votes
1answer
24 views

Decreasing Function Projected onto Simplex

Consider $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$, defined as $f(x) := a x + b$, where $a<0$ and $b \in \mathbb{R}_{\leq 0}^{n}$. Note that $f$ is decreasing: $$ x \geq y \Longrightarrow f(x) ...
1
vote
2answers
50 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
5
votes
1answer
177 views

Subdifferential boundary conditions: Testing with $L^2$ or $H^{1/2}$ functions

My question was essentially this: Does it make a difference if I test subdifferential boundary conditions with functions from $L^2(\Gamma)$ or $H^{1/2}(\Gamma)$? In the following, I will phrase the ...
1
vote
1answer
62 views

Showing a function is concave

Given $F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2))$ on $S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\}$ with $A,B,a\in\mathbb{R}$, show that $F$ is concave on $S$. Since we have ...
23
votes
2answers
821 views

Does local convexity imply global convexity?

Question: Under what circumstances does local convexity imply global convexity? Motivation: Classically, a twice differentiable function $f:\mathbb{R} \rightarrow \mathbb{R}$ is convex if and only ...
9
votes
1answer
155 views

Subdifferential boundary conditions: Testing pointwise or with $L^2$ functions

Let $\phi \colon \mathbb R^n \to \mathbb R$ be convex, proper and lower semi-continuous (lsc). Let $M$ be a measurable subset of $\mathbb R^n$. We can define a functional $\Phi \colon L^2(M) \to ...
0
votes
2answers
26 views

Notion of a concave function and proving ln is concave

I've just checked that the definition is right, a function is convex if: $(1-t)f(x_1)+tf(x_2)\ge f((1-t)x_1+tx_2)$ which is odd because this is ... well I was taught (very young age) that concave ...
0
votes
1answer
30 views

How to prove that $f$ is convex function

Let $f:(a,b) \mapsto \mathbb{R}$ be continuous function such that $f(\frac{x+y}{2})\leq \frac{1}{2}f(x) + \frac{1}{2}f(y) \;\; \forall x,y \in (a,b)$ Show that $f$ is convex function. Please give ...
2
votes
1answer
22 views

Proving that $0 \in A \implies h_A = j_{A^\circ}$

Where $h_A$ is the support function of $A$ and $j_{A^\circ}$ the Minkowski functional of the polar set of $A$ There is a "proof" in my course which I don't understand: " Let $x \in A$ and $t>0$ ...
0
votes
0answers
36 views

Minimization of product function subject to constraints

I want to minimize the following function: $\prod_{i=1}^{n}{x_i}$ Subject to the following constraints: $\sum_{i=1}^{n}{x_i}=1.1+(n-1)(0.1)$ and $0.1 \leq x_i \leq 1.1$ How should I go about it? ...
1
vote
1answer
35 views

Show that for $f,g: [0, + \infty) \to \mathbb{R}$ convex functions of Class $C^2$ their product $fg$ is convex

Problem: Let $f,g: [0, + \infty[ \to \mathbb{R}$ be two convex functions of Class $C^2$. Assume that $$ f(0) \geq 0, g(0) \geq 0 \text{ and } f'(0) \geq 0, g'(0) \geq 0 \tag{!}$$ Show that $fg$ ...
6
votes
2answers
221 views

About the hyperplane conjecture.

I have recently heard about the hyperplane conjecture and I would like to understand better the problematic behind this conjecture. The hyperplane conjecture: There exists a universal constant ...
0
votes
0answers
26 views

Convex set of polynomial coefficients

Assume we have an infinite order polynomial $f(L)=1-L\theta_1-L^2\theta_2-L^3\theta_3-...$. and we know all roots of this polynomial cite outside the unite circle. It is obvious that latter condition ...
1
vote
1answer
36 views

$\mathrm{Prox}_{f}(x)$ and $\mathrm{Prox}_{af}(x)$

Let $a\in \mathbb{R}$, and $f$ is a convex function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. $\mathrm{Prox}_{f}(x)=y_1$ and $\mathrm{Prox}_{af}(x')=y_2$. Because I know $\mathrm{Prox}_{f}(x)$. And ...
0
votes
0answers
26 views

What Projections preserve Pseudocontractiveness?

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a pseudocontraction, i.e., $$ \left\| f(x) - f(y) \right\|^2 \leq \left\| x-y\right\|^2 + \left\| f(x) - f(y) - (x-y) \right\|^2 $$ for all $x,y \in ...
0
votes
0answers
28 views

Extreme points by intersection of extreme rays and hyperplane

I just met one question and have no idea about the proof, hope someone can give me some ideas on how to attack this question. Given a graph $G=(V,E)$ with $|E|=n$. Define a set $S$: ...
2
votes
0answers
128 views

Projection and Pseudocontraction on Hilbert space

Let $H$ be a real Hilbert space with inner product $\langle\cdot, \cdot \rangle: H \times H \rightarrow \mathbb{R}$, and induced norm $\left\| \cdot \right\|: H \rightarrow \mathbb{R}_{\geq 0}$. Let ...
0
votes
0answers
13 views

Effect of proximal projection using a divergence measure, on the maximizer of the function

Suppose we have a probability distribution $p(\mathbf{x})$ and we know : $$ \mathbf{x}^* = \arg\max_{\mathbf{x}} p(\mathbf{x}) $$ Suppose we do a projection of this distribution onto another family ...
0
votes
1answer
59 views

The conjugate relation between two functions.

Suppose $K\in \mathbb{R}^{m\times n}$, $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$. Let a function $F: \mathbb{R}^m \rightarrow \mathbb{R}$, $F(y)$. Let $y=Kx$, $G(x)=F(Kx)$. Suppose $G(x)=F(Kx)$, ...
1
vote
1answer
28 views

convex closed and unclosed functions and (lower semi)continuity

I'm grappling a bit with lower semicontinuity and convex functions. Let me consider convex functions as functions to $\mathbb{R}$ and not to $\mathbb{R}\cup \{\pm\infty\}$. By Rockafellar's book ...
1
vote
0answers
39 views

How to show this converges in probability

$A_n(s)$ is a sequence of convex random functions defined on an open set $S\in \mathbb{R}^p$ which converges in probability to some $A(s)$ for each $s$. I'm trying to show that $\sup_{s\in K} \big| ...
1
vote
1answer
27 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
0
votes
1answer
61 views

Convexity of LASSO

I would like to know if some variables in design matrix are correlated then LASSO is convex or not. If you give me a proof for convexity of LASSO and ADAPTIVE lasso, I will be thankful. LASSO is ...
0
votes
1answer
14 views

Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The third ...
0
votes
1answer
30 views

Are there necessary and sufficient conditions so that every element in a partially ordered set is either the least element or in the upset of an atom?

This is the first of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The second question is here. The third ...
0
votes
1answer
28 views

Are there necessary and sufficient conditions for Krein-Milman type conclusions?

This, the third of three self-answered questions, contains a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The second question is here. ...
1
vote
0answers
66 views

When do partial subgradients give a subgradient?

I'm looking for sufficient conditions that guarantee that partial subgradients of a convex, lower-semicontinuous functional $f:X_1\times X_2\rightarrow\overline{\mathbb{R}}$ form a subgradient of $f$. ...
1
vote
1answer
66 views

Strictly convex unit balls in $L^p$

I need to show that if $1<p<\infty$, then the unit ball is strictly convex in $L^p$, that is, $||\lambda x+(1-\lambda)y|| < 1$ whenever $||f|| = ||g||=1$ and $\lambda \in (0,1)$. I tried ...
0
votes
1answer
20 views

On the Composition of simple Projections

Consider the compact convex set $X = \{ x \in \mathbb{R}^n \mid x \geq 0, \ \underline{1}^\top x = 1 \}$. I am wondering if the projection onto $X$ is the composition of the projection on $[0,1]^n$ ...
0
votes
0answers
16 views

Show that E(g(T-p)) < E(g(S-P) for any convex function g if T and S are estimators of p

The more detailed question. I'm kinda having some trouble starting out with answering this question. My initial approach would be to g(x)= x^2 since that is a convex function and find the expected ...
2
votes
1answer
58 views

Existence of global minimum

Could someone help me with this problem? Let $C$, $D$ convex and closed sets such that the intersection is empty. I want to show that the function $f: \mathbb{R^n} \to \mathbb{R}$ defined by $f(x) = ...
1
vote
1answer
37 views

Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$ x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b $$ where $X \subset \mathbb{R}^n $ is a non-empty, convex, bounded polyhedron. ...
1
vote
1answer
34 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
0
votes
1answer
17 views

something about convex set

Let $M$ be a convex subset in $\mathbb R^n$ and $\partial M=\emptyset$. Then $M=\emptyset$ or $\mathbb R^n$. This can be deduced by Theorem Let $M\subset X$ with $\partial M=\emptyset$ and $X$ is ...
0
votes
1answer
16 views

Establishing convexity of a function

Let $\theta \in \Theta \subset \mathbb{R}^k$. I have the following objective function $$ F(\theta):=||\max(0,f_1(\theta)),...,\max(0,f_n(\theta))||^2 $$ where $||\cdot||$ is the Euclidean Norm and ...
0
votes
3answers
62 views

A convex function has a lower bound?

Suppose that $f=f(x)$ is strictly convex for $x\in\mathbb{R}$, i.e. there exists $\epsilon>0$ such that $f''(x)\geq\epsilon>0$ for $x\in\mathbb{R}$. Does there exist $\delta>0$ such that ...
1
vote
1answer
121 views

Does every convex-linear map have an affine extension?

There is one step in a proof which I don't manage to show, although it seems to be very easy. Let $A, B$ be real vector spaces, let $S \subset A$ be a convex set and let $\text{aff}(S)$ be its affine ...
5
votes
3answers
219 views

Isoperimetric inequality, isodiametric inequality, hyperplane conjecture… what are the inequalities of this kind known or conjectured?

Question: Which inequalities similar to the famous isoperimetric inequality is known? conjectured? I recently learned about some inequalities which are all similar to the famous isoperimetric ...
0
votes
1answer
142 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
4
votes
1answer
46 views

Is the set of convex bodies include in a closed ball compact?

I consider the set $\mathcal{K}_B$ of convex bodies (convex and compact) which are include inside the unit closed ball of $\mathbb{R}^d$. I endow this set with the Hausdorff distance. Is it compact?
2
votes
0answers
45 views

Mid-point convexity does not imply convexity

A function $f: X \rightarrow \mathbb{R}$ is said to be mid-point convex if for all $x, y \in X$, we have $f(\frac{x + y}{2}) \leq \frac{f(x) + f(y)}{2}$. Can you please give an example of a function ...