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
7 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 ...
1
vote
1answer
10 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
12 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$, ...
2
votes
1answer
23 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 ...
0
votes
0answers
8 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 ...
0
votes
0answers
22 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 ...
3
votes
1answer
29 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
32 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
48 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
14 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
0answers
14 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
16 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 ) ...
1
vote
1answer
32 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 ...
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?
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 ...
0
votes
1answer
28 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
23 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 ...
0
votes
0answers
60 views

Open set in $C(X,Y)$

I am looking for a formal proof of (seemingly easy) result that that for $C(X,Y)$ where $X$ is arbitrary metric and $Y$ is finite dimensional (dimension $K$), compact and convex, there exists an open ...
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
17 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 ...
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 ...
0
votes
1answer
63 views

Brouwer fixed-point theorem infinite dimension [closed]

Brouwer fixed-point-theorem holds for compact convex set. Do you have example(s) where the theorem doesn't hold in infinite dimensional Banach spaces?
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
2answers
114 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
6 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
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$ ...
1
vote
0answers
10 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
5 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
23 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
44 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, ...
1
vote
0answers
12 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 $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$ and the ...
0
votes
1answer
14 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
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$ ...
0
votes
1answer
96 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
86 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
41 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
30 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
26 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
36 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), ...
0
votes
1answer
38 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
104 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
20 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
0answers
12 views

Signs and value of higher order terms in the Taylor expansion of a strongly convex function

Say that I have a function $f: S \rightarrow \mathbb{R}^+$ such that: $S \subset \mathbb{R}^n$ is a closed convex set such as $S=[-10,10]^n$ $f$ is continuous and infinitely differentiable at all ...
0
votes
2answers
32 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
26 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 ...