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
1answer
632 views

convex hull function in matlab

Is there any way 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 ...
0
votes
1answer
8 views

What modification is this of the notion of Renyi divergence?

Given two probability distributions $P$ and $Q$ over the same outcome and event space (assume finite if needed) one defines their Renyi divergence as $D_\alpha (P \vert \vert Q) = \frac{1}{\alpha -1} ...
0
votes
0answers
29 views

Why is the affine hull of the unit circle $\mathbb{R}^2$?

My question is addressed in Why is the affine hull of the unit circle $\mathbb R^2$? However, I am still confused. I thought that the affine of C in this case would be the interior of the circle. I ...
0
votes
1answer
27 views

Dot product - geometrical interpretation in convex analysis

I am studying a theorem on the characterization of solutions in nondifferentiable convex problems. Say that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and $f: \mathbb{R}^n \to ...
0
votes
0answers
20 views

How to find the domain of the support function

First the definition of the support function of set $S$: Let $S$ be a nonempty convex set. The support function $h$ of $S$ is the real-valued function defined by $$h(x)=\sup_{s\in S}\langle ...
17
votes
1answer
296 views

Does there exist regular planar pentagon?

How to prove or disprove that the boundary of any convex body in $\mathbb{R}^3$ (treated as a surface) includes 5 points which form a regular planar pentagon?
0
votes
0answers
39 views

Concave optimization and corner solution

I have a optimization problem as follows: Assumptions: $f$ is an increasing and convex function on $R^+$ such that: $f(x): R^+\rightarrow R^+, \quad f(0)=0, \quad f'(x)\ge1,\quad f''(x)\ge 0 ...
6
votes
1answer
352 views

Cones of positive semidefinite matrices generated by matrices of rank $1$

Let $S_n$ be the space of real $n \times n$ symmetric matrices and let $S_n^+$ be the convex cone of positive semidefinite matrices in $S_n$. The extremal rays of this cone correspond to the positive ...
1
vote
1answer
32 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
1
vote
1answer
31 views

How to resolve total variation $F(u)=f(u)+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$

Given $u(x)=[u_1(x)..u_N(x)]$, $0 \le u_i(x) \le 1, \sum_i^N u_i(x)=1$ and the cost function is: $$F(u)=f(u(x))+\lambda\sum_i^N\int_{\Omega}|\nabla u_i(x)|dx$$ where $u_i(x)$ is a value that indicate ...
2
votes
1answer
26 views

What is the convex hull of $ \{t \to e^{-\lambda t} : \lambda >0\}? $

What is the convex hull of $$ \{t \to e^{-\lambda t} : \lambda >0\}? $$ (Interpreted as the set of all functions on the above form.) Reference or argument is great.
0
votes
1answer
15 views

Is it covex function?$J_{new}(u)=\int_{\Omega} \sum_{i=1}^{N} \lambda_if(x)u_i(x)dx$

I have a function such as $$J(u)=\int_{\Omega} \sum_{i=1}^{N} f(x)u_i(x)dx$$ where $f(x):\Omega \to R$, $0 \le u_i(x) \le 1,\sum_i u_i(x)=1$ Given that $J(u)$ is a convex function w.r.t $u$. Now I ...
1
vote
1answer
35 views

Minimizing the function with a log determinant and trace function?

I am trying to minimize the following argument, which is unbounded in case one of the eigenvalues of $A$ is equal to zero. $\arg min_{S} \log|S^H A S| - tr\{ \Sigma^{-1}S^HAS\}$ Let $A > 0$, ...
1
vote
2answers
35 views

A question on convex hull

Let $a_1, a_2,\ldots, a_n$ be $n$ points in the $d$-dimensional Euclidean space. Suppose that $x$ is a point which does not belong to the convex hull of $a_1, a_2,\ldots, a_n$. My question is, does ...
-1
votes
0answers
27 views

Prove an upper bound [on hold]

Let $O$ be the origin, and $K$ be a convex polygon in $\mathbb{R}^2$ with edges $K_1, \dots K_n$. Let $\nu_i$ be the unit outer normal of each $K_i$. Suppose $O \notin K$. Prove that there exists a ...
3
votes
1answer
36 views

Uniform Sampling on Intersection of Simplices

I'm trying to sample uniformly on the intersections of several simplicies, with all coordinates being non-negative. That is, given $$A\vec{x}=\vec{b} \ \ and \ \ \vec{x} \geq \vec{0},$$ I want to ...
0
votes
0answers
13 views

Homeomorphic images of convex sets

Let $K$ be a convex set of a topological vector space $X$. Is there anything we can say about the image $f(K)$ under a continous or homeomorphic map $f \colon X \to X$ ?
1
vote
0answers
44 views

How to give a rigorous proof of a fact about convex polygon?

I claim that there exists universal constants $0<\delta_1(m), \delta_2(m)<1$ such that for any convex polygon $P$ in $\mathbb{R}^n$ with $m$ faces, \begin{equation} \frac{\mathcal{H}^{n-1}(\{x ...
1
vote
1answer
28 views

Matrix norm in the objective of an optimization problem

I am stuck with the following optimization problem from research. The optimization problem have the following objective function: $\|Q-H\|_\infty$. Here $Q$ is a PSD matrix and $H$ is a symmetric ...
0
votes
0answers
10 views

how to show a concave function on discrete domain increases in x?

Define $g(x)=\frac{f(x)/x}{f(x)-f(x-1)}$ where x$\in$ $\mathbb{Z}$. Known that $f(x)$ has the concave extension in every consecutive $x$, i.e: $f(x+1)+f(x-1)-2f(x)<0$ holds $\forall x$. My question ...
2
votes
1answer
25 views

Is convex hull linear subspace of linear hull?

We have some convex and compact supset $G$ of banach space $B$ and finitely many points ${x_1,...,x_N}$ . The question is : does the convex hull $C$ of ${x_1,...,x_N}$ a linear subspace of space ...
1
vote
0answers
17 views

Question about sub differentiability of convex function

I am reading this book to study sub differentiability. On page 20 it says, as $V$ is a normed linear space for simplification, "a continuous affine function $l(v)$: $V\to \mathbb R$ everywhere less ...
1
vote
3answers
38 views

How to compute the projection of a polyhedron

Suppose that we have a polyhedron in $(x,y)$: $P=\{ (x,y) \mid A_1 x +A_2 y \leq b \}$ How can I find the polyhedron $P_x=\{ x \mid (x,y)\in P \}$? In other words, I would like to write $P_x=\{x ...
3
votes
2answers
57 views

In linear programming, how to check whether a convex polyhedron is contained in another

Suppose we have two convex polyhedra $P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$ and $P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$ Is there a way to check whether $P_1 \subseteq P_2$? I was ...
3
votes
1answer
31 views

A question about Caratheodory's Theorem of Convex Sets

As I understand it, Caratheodory's Theorem of Convex sets essentially states If $Q$ is a set in a vector space of dimension $n$ and x lies in the convex hull of $Q$, then x can be written as a ...
1
vote
1answer
18 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
0
votes
1answer
18 views

Question on relation between convex sets

The book I am referring regarding bell inequalites has the following two things it mentions about two convex sets which I am unable to understand. There are two convex sets $C$ ($C$ is a polytope ) ...
0
votes
0answers
26 views

Convex envelopes of bivariate functions

In order to convexify my nonlinear non-convex program I need convex envelopes for the function $(x/y)^2$, both x,y are positive. I am only aware of the convex envelopes of the type $xy$ from here ...
2
votes
2answers
37 views

Are differentiable and strictly decreasing functions always concave?

If a demand function is continuously differentiable and strictly decreasing in price, does that mean it will be always concave?
1
vote
1answer
33 views

Is the expectation of log-concave function still log-concave?

I know the expectation preserves the concavity (or convexity), but I was wondering is it still true that the expectation of log-concave function still log-concave; to be more precise, Let ...
0
votes
1answer
31 views

The Legendre-Fenchel transform of $BV$ semi-norm

I am reading a numerical paper in which it calls some "easy" facts from convex analysis but I can't justify it... Let $\Omega\subset \mathbb R^2$ be open. Define for a function $u\in L^1(\Omega)$ and ...
1
vote
1answer
32 views

Prove the concavity of the transformation from a concave function to another

Let's say we have $f_1$ and $f_2$, both strictly increasing and strictly concave on $[0,+\infty)$. $f_1(0)=f_2(0)=0$ and the difference $f_1-f_2$ is strictly positive and strictly increasing. That is, ...
0
votes
0answers
13 views

Convex signal reconstruction for convex generator function?

Let $f : \mathbb{R} \mapsto \mathbb{R}$ be a convex (not affine) function and suppose that $y = f(x)$. We want to reconstruct the input $x$ for a given $y$, and the standard approach would be to ...
1
vote
2answers
73 views

proving that $\text{aff}C-\text{aff}C\subset\text{aff}\,(C-C)$

In proof of Theorem 6.4.1 of Auslender's book about asymptotic cones, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that ...
-2
votes
2answers
47 views

Is this Function of Product of variable and Ratio of CDF and PDF of Standard Normal Distribution Convex?

Let $G\left(x\right)=x\frac{\phi\left(x\right)}{\Phi\left(x\right)}$. Here, $\phi$ and $\mathbf{\Phi}$ are the standard normal PDF and CDF, respectively. Is $G\left(x\right)$ convex? It has been shown ...
0
votes
1answer
51 views

Jensen inequality for convex functions - infinite countable number of weights

Does Jensen inequality for convex functions hold if there is countable infinite number of weights? For example weights are given by sequence $(\frac{1}{2^n})_{n\in\mathbb{N}_1}$ ? If not, where is ...
0
votes
0answers
18 views

Convex functionals, min-max of linear functionals, etc

I was reading in this book on the well-known Courant-Fischer min-max Theorem, which states that if $\lambda_1(A)\geq \lambda_2(A)\geq \lambda_n(A)$ are the $n$ eigenvalues of a $n\times n$ Hermitian ...
0
votes
1answer
25 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
1
vote
1answer
17 views

An affine set $C$ contains every affine combinations of its points

Show that an affine set $C$ contains every affine combinations of its points. Proof by induction: From the definition of an affine set, we know that $\forall x_1,x_2\in C \text{ and } \theta_i\in ...
1
vote
0answers
46 views

Minimizing the max function

Suppose we have the single-variable function $$f(x) = \max_k \{f_k(x)\}$$ where each $f_k$ is convex and smooth (and known beforehand). We want to minimize it over some bounded interval. We can, in ...
0
votes
0answers
17 views

Find $U \subset D $ with $|U|$ minimal s.t $v = (1/2,1/2,1/2)$ belongs to the convex hull of $U$.

Consider the convex hull $\text {conv} \{e_1,e_2,e_3,(1,1/2,1/2),(1/2,1,1/2), (1/2,1/2,1)\}$ in $\mathbb R^3$ and the vector $v = (1/2,1/2,1/2)$. I want to compute $U \subset ...
1
vote
1answer
38 views

Function dominated by convex function is eventually convex

Suppose that we have a twice-differentiable function $f$ on $x\in [0,\infty)$ such that $f(x)>0$ on $x\in [0,\infty)$ (i.e. strictly positive) $f'(x)<0$ on $x\in [0,\infty)$ (i.e. strictly ...
0
votes
0answers
20 views

Invex function? How can I show?

Let $\mathbb{S}^m_+$ and $\mathbb{M}^{(m,n)}$, respectively, be the closed cone of positive semidefinite matrices and space of $m\times n$-dimensional matrices. Define function $F$ as ...
0
votes
1answer
20 views

Every convex function is locally Lipschitz ($\mathbb{R^n}$)

I know that if $f$ is convex function so $f$ is continuous. And I know too that partial derivatives exists. What can I do?
0
votes
1answer
98 views

How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$?

Let $B = \{ (x,y,z) \in \mathbb R^3 \mid x^2 + y^2 + z^2 \le 1\}$. How do I show that $B$ has an infinite number of extreme points, but no faces (sides) of dimension $1$ or $2$ ? I've been thinking ...
0
votes
2answers
115 views

Prove a closed ball in $\mathbb R^3$ has an infinite number of extreme points.

How do I show that a closed ball in $\mathbb R^3$ has an infinite number of extreme points ? (Closed ball is written as $S = \{(x,y,z) \in \mathbb R^3 | \sqrt {x^2 + y^2 + z^2} \le R \}$) I know ...
0
votes
1answer
7 views

Convex combination of quasiconvex functions.

Is a convex combination of two quasiconvex functions necessarily quasiconvex? If not, what can be said about the convex combination?
1
vote
2answers
25 views

Let a polyhedron $P = \text{conv}(S)$ where $S$ extreme points. Can $S' \subset S$ (proper) be a generator?

Let $P$ be a polyhedron and let $S=\{ v_1, \ldots, v_r\}$ its extreme points. Suppose further that $\text{rec}(P)={0}$ so $P=\text {conv}(S)$. How do I see that I cannot remove any points from $S$ and ...
0
votes
1answer
47 views

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove $(1-\lambda)x + \lambda y \in S$ for $x=\lambda'y$, $\lambda' < 0$.

Let $S = \{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. I've verified that $x,y \in S$ implies $(1-\lambda)x + \lambda y \in S$ when $x,y$ are linearly independent using Pythagoras and when ...
0
votes
1answer
18 views

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these. I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ ...