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)

3
votes
1answer
59 views

Uniform Sampling on Intersection of Simplices

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
3
votes
1answer
55 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
3answers
62 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
88 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 ...
1
vote
1answer
26 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$?
1
vote
1answer
51 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 ...
0
votes
1answer
26 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 ) ...
2
votes
1answer
119 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 $g(x,...
3
votes
2answers
53 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?
0
votes
0answers
23 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 ...
0
votes
1answer
86 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 ...
0
votes
0answers
54 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 ...
1
vote
1answer
110 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, ...
1
vote
1answer
60 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
68 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
18 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 \{e_1,e_2,e_3,(1,1/2,1/2)...
1
vote
1answer
66 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 ...
1
vote
1answer
48 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
2answers
151 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
47 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?
0
votes
1answer
49 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
30 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$ ...
1
vote
0answers
75 views

Iterative algorithms to approximate unknown multivariate convex real-valued functions by a set of linear upper/lower bounds

I am looking for iterative algorithms that can approximate a multivariate convex real-valued function $f(\vec{x})=y,\, \Bbb{R}^n\rightarrow \Bbb{R}$. The function is not known beforehand, but it is ...
0
votes
0answers
9 views

Suppose $P = \text{conv}(\text{ext}(P))$. Is it possible to find $S \subset P$ of cardinality $< \text{ext}(P)$ s.t $\text{conv}(S) =P$?

Suppose that $P$ is a polyhedron and that $P = \text{conv}(\text{ext}(P))$. Suppose further that $ \text{ext}(P)$ has cardinality $r$. How do I see that I cannot find a set $S \subset P$ of ...
1
vote
2answers
34 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 ...
3
votes
2answers
49 views

Can $\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$ be reduced to a convex hull of a subset of these?

How do I see whether $$\text{conv} \{ e_1,e_2,e_3, (1/2, 1/2, 1) , (1/2, 1, 1/2) , (1, 1/2, 1/2) \}$$ can be reduced to a convex hull of a subset of these vectors? That is, if $D = \{ e_1,e_2,e_3, (...
3
votes
0answers
65 views

Estimate the volume of a convex body given a uniform random sample of points inside it?

Let $K$ be a convex, full-dimensional, bounded region of $\mathbb{R}^n$. More precisely, there exist two balls of radiuses $0<r<R$ such that the ball of radius $r$ is fully contained inside $K$ ...
0
votes
1answer
135 views

Is the ratio of a decreasing function and an increasing function, a quasi-concave function?

$f(x)$ is a strictly decreasing function and $g(x)$ is a strictly increasing function and positive. Is $h(x) = f(x)/g(x)$ quasi-concave?
0
votes
1answer
28 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$ ...
0
votes
1answer
118 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
5answers
96 views

Let $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Prove existence of a unique point $v_0 \in B$ that is closest to $v \notin B$?

Suppose $B=\{ (x,y,z) \in \mathbb R^3 : x^2 + y^2 + z^2 \le 1\}$. Consider a point $v \notin B$. How do I prove that there exist a unique point $v_0 \in B$ that is closest to $v$. Also, how do I ...
1
vote
2answers
54 views

Prove that a functional is convex

Let $T$ be a self-adjoint bounded operator on a Hilbert space $H$. We define the functional $\Phi$ as: \begin{equation} \Phi(x)=\frac{1}{2}(Tx,x) \end{equation} My exercise says that $\Phi$ is ...
2
votes
2answers
48 views

Prove the existence of minimal height of a convex polygon

Suppose we have a polygon in $\mathbb{R}^n$. Obviously, we can always trap the polygon into two parallel hyperplanes perpendicular to any given direction. Now the question is, how to prove the ...
2
votes
1answer
48 views

$U$ bisected by all hyperplanes $\implies$ $U$ symmetric?

Let $U \subset \mathbb{R}^n$ be a bounded open convex set, such that every hyperplane passing through the origin divides $U$ into two sets of equal volume ($n$-dimensional Lebesgue measure?). ...
1
vote
1answer
43 views

Simple question on maximizing a family of concave functions

Given $x \in [0,1]$, let $f_k(x)$ be concave function in $x$ for all $k= 0,1,...,N$. Is the following two maximization formulations equivalent? $$ \max_{0 \le k \le N} f_k(x) =?= \max \{f_0(x), f_1(...
0
votes
1answer
47 views

Is a maximum function concave?

A function such as $$\max (X, Y)$$ given $X\geq 0$, $Y \geq 0$. Because It would form an inverse L shape on the graph, and that looks like a concave function. However my teacher said that the function ...
5
votes
2answers
274 views

The convex hull of every open set is open

Let $X$ be a topological vector space. Prove that the convex hull of every open subset of $X$ is open. I tried using definition of Convex Hull and Open Set, but I couldn't prove the statement.
0
votes
1answer
24 views

Convexity of $f(x) = \sum_i x_i^p$ for $x_i \ge 0, p \ge 1$

Let $x = (x_1,\ldots, x_n)$ be nonnegative real numbers and $p \ge 1$, then the function $f(x) = \sum_{i=1}^n x_i^p$ is convex, the following proof is wrong, or not? I have it from here, but then ...
1
vote
2answers
50 views

Maximal eigenvalue is convex function

Let $A$ be a symmetric real matrix. let $f(A)=\lambda_{max}(A)$ be it's largest eigenvalue. Why is $f(A)$ convex?
1
vote
1answer
48 views

Orthogonal projection of an $n-$vector onto the subspace ($m\leq n$)of $\mathbb{R}^n$ containing a convex polytope

Lets say we have an $n \times m$ matrix $A$, whose column vectors are $(\vec{\mathbf{0}},a_1,a_2,...a_j)$ are points in $\mathbb{R}^n$ and the non-zero vectors have unit length. Let $S:=\mathrm{span}\{...
1
vote
1answer
76 views

Multivariate convex function / increasing differences

$\newcommand\Rr{\mathbb{R}}$I am trying to show the following statement. It feels true to me, but I haven't found any reference in the literature so far: Let $\Rr^n$ be ordered component-wise, i.e., $...
0
votes
1answer
33 views

Differentiability of support function (even for non-convex)

I am reading an economics book (for those who are interested, MWG Microeconomic Theory) and there's a theorem that was just given without proof, but I am interested in the proof - also because I ...
0
votes
1answer
37 views

Boundary of convex set is piecewise $C^1$

Let $K$ be a convex and compact subset of $\mathbb{R}^2$. Is it true that the boundary of $K$ can be parameterized by a piecewise $C^{1}$ application $\gamma :I\to\mathbb{R}^2$?
1
vote
1answer
133 views

Quasi concavity and Quasi Convexity-intuitive understanding

I'm having trouble grasping the concept of quasi concavity and quasi convexity. My textbook states that if f is quasi-concave, then f (λx + (1 − λ) y) ≥ min {f(x), f(y)} . Also that is f is quasi ...
0
votes
0answers
46 views

Is an lsc sublinear function $X^* \rightarrow (-\infty, \infty]$ always a support function for some closed non-empty $C \subset X$?

I can't seem to find any resources on this, even though it seems like an obvious question to ask. The separation theorem implies that, if we have an lsc sublinear function $\phi : X^* \rightarrow (-\...
0
votes
1answer
58 views

Isn't every increasing continuous convex function strictly increasing (disregarding $f(x) \equiv 0$)?

Isn't every increasing continuous convex function $f$ strictly increasing (disregarding the trivial case $f(x) \equiv 0$)? I don't see any counterexample!
-1
votes
2answers
100 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
0answers
36 views

Properties of a proper cone

Let $K$ be a proper cone. I need to prove following properties: if $x \preceq_K y$ and $u \preceq_K v$, then $x+u \preceq_K y+v$ if $x \preceq_K y$ and $y \preceq_K z$, then $x \preceq_K z$ if $x \...
1
vote
0answers
63 views

Taylor Expansion of Power of Cumulative Log Normal Distribution Function - Show Lagrange Remainder tends to Zero

QUESTION I am looking to find a simplification of the expression below. I have attempted this using the Taylor series. The question then remains if we can show the Lagrange remainder goes to zero. I ...
2
votes
2answers
75 views

Proof that Convex Function with alternate variable is convex

Given that say, $f(x)$ is convex for $x>0$. Would the proof that $f(a-x)$ where $a>x$ is convex proceed as shown below. Please verify the correctness and/or alternative approaches that can ...