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

Separating convex sets in a tvs $X$.

I got doubt with the proof of this theorem. Let $X$ be a tvs, $A,B \subset X$ with $A$ an open convex set and $B$ convex such that $A \cap B = \emptyset$. Then there exists $f \in X^*$ (where ...
0
votes
0answers
31 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
1
vote
1answer
60 views

Convexity of a region on probability simplex

Exercise 2.15 g of Boyd et al Convex Optimization book : On the probability simplex in $\mathbb{R}^n$ where each point $p = (p_1,p_2,p_3,\ldots,p_n)$ corresponds to a distribution for random variable ...
0
votes
0answers
19 views

Proving function defined by algorithm is convex

I'm working on my bachelor thesis and I'm trying to prove a conjecture, but I seem to miss the hint that helps me. I have an algorithm that defines a function $f:\mathbb{R}_{\geq ...
0
votes
0answers
29 views

Prove the existing and uniqueness of a solution [duplicate]

Let function $f$ be differentiable and convex in $R^n$ . How can it be proved that $∀λ>0$ solution of system equations $f ′ (x)=−λx$ exists exclusively (∃and! ).
3
votes
0answers
50 views

Is it always possible to partition a fat shape to fat shapes?

The slimness factor of a geometric 2-dimensional shape is defined (for this question) as the ratio of the side-length of its smallest enclosing square to the side-length of its largest enclosed ...
4
votes
0answers
83 views

Characterization of Convex Polygons

John Lee's Axiomatic Geometry has an interesting characterization of convex and non-convex vertices for polygons. Let $P$ be a polygon. Consider a ray emanating from a vertex of $P$ which does not ...
1
vote
1answer
25 views

Concavity of a function

While I am reading a book I couldn't follow the following step. " By concavity of the function $x \sqrt{\log\frac{1}{x}}$ for $x \in (0,1)$ we have that " $O(x \sqrt{\log\frac{k}{x}})$ = ...
0
votes
1answer
33 views

What is the shape of all convex combinations of $\geq$ five vectors in $\mathbb{R}^3$?

The convex combinations of two linearly independent vectors in $\mathbb{R}^3$ span a line. The convex combinations of three linearly independent vectors in $\mathbb{R}^3$ span a solid triangle. The ...
0
votes
0answers
35 views

Sufficient conditions for convexity using the right derivative

We have a function $f:[0,1] \rightarrow \mathbb{R}$ that is continuous on $[0,1]$ with a non-decreasing right derivative everywhere in $(0,1)$. Is this definitely sufficient to show that $f$ is convex ...
1
vote
0answers
14 views

Begin study of convex algebraic sets in complex projective space

Where should I begin the study of convexity of (semi-)algebraic sets? In other words, projective varieties defined by polynomials of complex variables. The long-term goal is to study optimization in ...
3
votes
1answer
83 views

Proof that a set is convex

$$k\in \mathbb{R}_{+}$$ $$M=\left \{ (x_1,x_2)\in \mathbb{R}_{++}^2 \mid x_1 x_2\geq k\right \}$$ Prove that the set $M$ is convex. A hint is given (quoted from the text): We could choose to ...
0
votes
0answers
24 views

Dual convex pairs

I am currently trying to understand a certain proof. The author uses the term dual convex pair for a pair $(\phi,\psi)$ of convex functions defined on subsets $X,Y$ of $\mathbb R^n$ satisfying: $$ ...
2
votes
1answer
44 views

A question about norm for bounded linear transformations

Let $H$, $K$ be Banach spaces, and let $A: H \rightarrow K$ be a bounded linear transformation. Its norm is defined by: \begin{equation} \|A\| = sup\{\|Ah\|_K: \|h\|_H \le 1\} \end{equation} How to ...
0
votes
1answer
21 views

Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
5
votes
1answer
81 views

What functions are support functions of convex sets

Given a closed, convex, non-empty set $K\subseteq\mathbb{R}^n$ the support function $h_K:\mathbb{R}^n\to (-\infty,\infty]$ is defined as $$h_K(y) := \sup_{x\in K} \langle x,y\rangle$$ It is easy to ...
0
votes
0answers
18 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
1
vote
1answer
32 views

Proving upperbound using convexity

The original question is to prove $$\frac{1}{n}\sum_{i=1}^n x_i \leq \log{(\frac{1}{n}\sum_{i=1}^n e^{x_i})} \leq \max_{1 \leq i \leq} x_i$$ I show that $$x_{max} = \max_{1 \leq i \leq} x_i$$ ...
1
vote
0answers
24 views

Prove that a given function is convex

Consider the following convex set: $$S = \{m \in \mathbb{R}^N : m_i \geq 0 \text{ }\forall i=1, \ldots, N \wedge \sum_{i=1}^Nm_i = 1\}$$ and following function $f : S \rightarrow \mathbb{R}$: ...
8
votes
1answer
226 views

Proof that the set of doubly-stochastic matrices forms a convex polytope?

Does the set of all doubly-stochastic matrices form a convex polytope? In general, I wonder how the proofs of convexity and geometry can be established for sets of matrices of this kind? Anything to ...
0
votes
0answers
15 views

Gaussian measure of a convex hull with respect to scaling.

consider the following problem: Let $m\geq 1$ and consider $a_1,\ldots,a_{m+1}\in \mathbb{R}^m$. Let $A=(a_1,\ldots,a_{m+1})$ be the matrix having the $a_i$ as columns. Let ...
0
votes
1answer
35 views

The key step to prove log-convexity is preserved under sums

In S. Boyd textbook p.105 (button): (cvx = convex) Let F = log f & G = log g are convex (i.e. Let f & g are log-cvx) (This guarantees f & g are cvx, since log-cvx is included in ...
10
votes
2answers
184 views

n-simplex in an intersection of n balls

Consider a $n$-simplex, $n \geq 2$ with vertices $x_i,i=1,...,n+1$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ ...
0
votes
1answer
22 views

Increasing convex-like function in Hilbert space

I am intersted with the differential equation $$x'(t)=f(t,x(t)),\ t\in \mathbb{R}.$$ Can we find an example of a Hilbert space $H$ and a function $f:\mathbb{R}\times H \to H$ which satisfy the two ...
0
votes
1answer
27 views

Simplex - Help with a proof

I am trying to prove the following (basic) claim about simplex. If you check my proof and help me with the part where I stuck, I would appreciate it very much. Let $X$ be a finite set and define ...
11
votes
1answer
96 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
0
votes
0answers
32 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
67 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
37 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
400 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
20 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
20 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
57 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
52 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
180 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
63 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
831 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
156 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
28 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
38 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
37 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
227 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
29 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 ...