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
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
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), ...
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?
1
vote
2answers
105 views

Convexity of the ratio of the standard normal PDF by its CDF

Is there some way to show that the following function $\psi$ is concave or convex? Here, $\phi$ and $\mathbf{\Phi}$ are the standard normal PDF and CDF, respectively. ...
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
31 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 ...
1
vote
1answer
83 views

Convex Function

$f: U\subset\mathbb{R}^m \to \mathbb{R}$ is a convex function if $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$, for all $x,y \in U$ and all $t \in [0,1]$. If $f$ is convex and continuous function, and $f$ has ...
1
vote
0answers
13 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 ...
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.
2
votes
1answer
27 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?). ...
8
votes
3answers
3k views

Showing that $f$ is convex given that $f(\frac{x+y}2)\le\frac{f(x)+f(y)}2$

Given that $$f\left(\frac{x+y}{2}\right)\leqslant \frac{f(x)+f(y)}{2}~,$$ how can I show that $f$ is convex. Thanks. Edit: I'm sorry for all the confusion. $f$ is assumed to be continuous on an ...
1
vote
1answer
30 views

Proof that f is convex

Consider $D\subset\mathbb{R}^n$ a convex set and $f_i:D\rightarrow\mathbb{R}$ convex functions in $D$, $i \in I$ is a any set of indexes. Suppose there is $\beta \in \mathbb{R}$ such that ...
1
vote
1answer
19 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
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 ...
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?
0
votes
1answer
15 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$?
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
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 ...
0
votes
1answer
14 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
197 views

Proof of $Ax = b, x \ge 0$ is a closed subset

I'm trying to follow the The Farkas-Minkowski Theorem (Internet Archive) but I'm having a little bit of difficulty. On the second page the author states, Then we consider a set of the form $R_k ...
0
votes
0answers
14 views

how can we check convex or nonconvex feasible?

example if i have 20 constraints functions.These functions cut the objective function and create the feasible region. Their intersections can become edges and create a nonconvex feasible region even ...
0
votes
0answers
25 views

Optimising a piecewise convex function

I have a function $f(x)$ defined for $x\in \mathbb{R}^+$ that is decreasing, piecewise convex and continuous. The 'pieces' of $f$ are exponential and the rate of decrease for each piece reduces as we ...
1
vote
1answer
17 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
1answer
21 views

Given Convex Function, Conditions when Variable times Convex Function is convex

Given that say, $f(x)$ is convex for $x>0$. We can arrive at the following conditions for when $xf(x)$ would be convex. Please add anything that I might have overlooked and further simplifications ...
0
votes
0answers
24 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
44 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
vote
2answers
58 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 ...
0
votes
0answers
17 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
1answer
25 views

Is a twice differentiable function whose only extrema is a minimum automatically convex?

I have a twice differentiable function $H(x)$ for which I have already proven that: $\exists !x^*:H'(x^*)=0$ and furthermore that $H''(x^*)>0$ (the only extremal is a minima). $H''(x)$ is ...
0
votes
1answer
452 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
1
vote
1answer
21 views

Convex Hull = Boundary+Segments

If $A\subseteq\mathbb{R}^n$ is an non empty set and $H$ is the convex hull of $A$, how can I prove that the boundary of $H$ consists only of points that lie in the boundary of $A$ and segments that ...
-3
votes
1answer
31 views

Prove a convex function

I have to prove that if $f:A \to \mathbb{R}$ is convex and $c \ge 0$ then $c \cdot f:A \to \mathbb{R}$ is convex. I know that function $f:A \to \mathbb{R}$ is convex if for $\forall x,y \in A$ and ...
0
votes
1answer
20 views

Is the following function concave? (or log of it)

I have a function $f(x_1, x_2, ..., x_M) = \displaystyle \prod_{i = 1}^N \frac{(\sum_{j = 1}^{M} a_jx_jI_{ij})^2}{\sum_{j = 1}^{M} a_jx_j}$ in domain $\{{\bf x} \in {\bf R}^m \setminus {\bf 0} \ ...
0
votes
1answer
25 views

A convex hull of a union of convex sets [closed]

Let ${A_1},{A_2},....{A_n}$ be convex sets in a vector space and suppose $x \in \operatorname{co}({A_1} \cup {A_2} \cup \dotsb \cup {A_n})$. Is it true that $x = {t_1}{a_1} + \dotsb + {t_n}{a_n}$ such ...
0
votes
1answer
40 views

Proving a convex function [closed]

I'm given a function $f:A \to \mathbb{R}$ which is twice continuously differentiable on $A \subseteq \mathbb{R}^n$. $A$ is a convex set. Show that $f$ is convex. Any ideas on how to prove this?
0
votes
1answer
35 views

What are the extreme points of the closed unit ball of $C$? .

What are the extreme points of the closed unit ball of C(the space of all continuous functions on the unit interval), with the supremum norm?
0
votes
0answers
37 views

how to prove convexity of the function below?

For a graph $G$ consider the following function, $$f=\sum_{(i,j) \in G ,(i,k) \notin G } \max(0,c+ \left\|e_i-e_j\right\|_2^2-\left\|e_i-e_k\right\|_2^2)$$ where $e_i \in\mathbb R^n$ ($n$ dimension ...
3
votes
3answers
2k views

Using the definition of a concave function prove that $f(x)=4-x^2$ is concave (do not use derivative).

Let $D=[-2,2]$ and $f:D\rightarrow \mathbb{R}$ be $f(x)=4-x^2$. Sketch this function.Using the definition of a concave function prove that it is concave (do not use derivative). Attempt: ...
0
votes
1answer
24 views

Rectificable curve as a boundary of a convex set

Let $K\subseteq\mathbb{R}^2$ be a convex compact set. Is it true that $\partial K$ (the boundary of $K$) is a rectificable curve (i.e. it has length)?
0
votes
2answers
15 views

Sequence of convex non increasing sets convergence

I have a question for you. I was wondering whether a non increasing sequence of convex set converges to a convex set. Here my question made more precise: Let $\{S_k\}_{k=1}^\infty$ be a sequence of ...
1
vote
0answers
20 views

Why there is nonconstant linear funectional $\Gamma $ on $X$ such that $\Gamma (A) \cap \Gamma (B)$ contains at most one point?

Let $X$ is a real vector space(without topology). call a point $x \in A \subset X$ an internal point of $A$ if $A-x$ is an absorbing set.Suppose $A$ and $B$ are disjoint convex set in $X$ and $A$ has ...
0
votes
3answers
28 views

How to show the optimal condition of $f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$

Consider the following function: ($\alpha>0$) $$f(\alpha) = \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$$ It is a quadratic (in $\alpha$) over linear (in $\alpha$); therefore, ...
0
votes
1answer
30 views

KKT conditions for a convex optimization problem with a L1-penalty and box constraints

I am having some trouble deriving / understanding optimality conditions for a convex optimization problem of the form: $$\begin{align} \min_{x\in\mathbb{R}^d}~ & f(x) + C.\|x\|_1 &\\ &x_i ...
0
votes
0answers
18 views

Classify extreme points of multivariate implicit functions when cross derivative is not available

I have the following problem: Let $f(x,y)$ be a function defined on $[0,1]^2$ I want to prove that $f(x,y)$ has no local minimum for $x>y$. I have no idea about the sign of the cross derivatives ...
1
vote
2answers
46 views

Proof that a log-of-sum-of-exponentials is a convex function

It's well known in statistical mechanics that the following is a convex function of the vector $\theta$: $$ A(\theta) = \log \left( \sum_{i=1}^\infty e^{\theta \cdot f(i)} \right) $$ where $f(i)$ is ...
0
votes
1answer
19 views

Compact convex subset and hyperplanes

Suppose $K$ is a compact and convex subset and $x^*$ a point in $\mathbb{R}^n$. Suppose there exists $y\in \mathbb{R}^n$ such that $$\langle x^*, y\rangle> \sup_{x\in K} \langle x, y\rangle$$ ...
-2
votes
0answers
13 views

Subhessians for maximum eigenvalue of a matrix

I am trying to solve a non-linear, non-smooth convex optimization problem using a generic convex optimization solver. This solver requires and (sub)gradients of the objective and the constraints, as ...
1
vote
1answer
69 views

Intersection of a convex polygon and a moving circle

I have a straight line which intersects a convex polygon in 2D plane. There exists a circle with constant radius. The center of circle is moving on this line. So at first the polygon and circle don't ...