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)

3
votes
1answer
79 views

Does $\phi\circ g$ convex imply $\phi\circ f\circ g$ convex?

Assume that $\phi$ is an increasing function and $g$ is a decreasing function with $\phi\circ g$ convex. If $f$ is an increasing convex function does this imply $\phi\circ f\circ g$ is a convex ...
3
votes
1answer
148 views

Strictly convex function: how often can its second derivative be zero?

It's a basic fact that a twice-differentiable function from $\mathbb{R}$ to $\mathbb{R}$ is strictly convex if its derivative is positive everywhere. The converse is not true: consider, e.g., $f(x) = ...
3
votes
2answers
474 views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
3
votes
2answers
60 views

Need a way of computing the vertices of intersection of two simplices

I have two simplices $\Delta_1, \Delta_2$ defined as: The first simplex, $\Delta_1$, is the set of points defined as follows: $$\Delta_1 = \left\{\sum\theta_iu_i, \theta_i >= 0, ...
3
votes
1answer
293 views

maximum and minimum singular values

I was studying the Stephen Boyd's textbook on convex optimization and have a question. The book says the following: The singular values of $A$, $\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_n$ are ...
3
votes
1answer
868 views

KKT and Slater's condition

I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following: "For any convex optimization problem with differentiable objective and constraint function, any ...
3
votes
2answers
76 views

About the convexity of Ky Fan's norm

As we know, the Ky Fan norm is convex, and so is the Ky Fan k-norm. My question is, does this imply that the difference between them is a non-convex function, since it results from "difference between ...
3
votes
1answer
111 views

Is it possible to replace function by its concave envelope

Let $f(x) \in C[-1,2]$. Consider an optimization problem $$ J[\mu] = \int\limits_{-1}^{2}f(x) \, \mu(dx) \to \max\limits_{\mu - \text{Borel probability measure}} $$ with restriction $$ ...
3
votes
1answer
58 views

convex relaxations

Is there a notion of "best" convex relaxation of a particular function in a normed vector space? For example, the $\ell^0$ pseudo-norm can be relaxed into the $\ell^1$ norm, and that allows us to ...
3
votes
2answers
557 views

Projection onto closed convex set

Show that the function defined by $f(t)=|P_{D}(x+td)-x|$ is nondecreasing, where $D$ is closed convex, $x\in D$, $t\geq 0$, $d\in \mathbb{R}^{n}$ and $P_{D}$ is projection onto D. I tried to solve ...
3
votes
2answers
192 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone.

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
3
votes
1answer
117 views

Can all convex polytopes be realized with vertices on surface of convex body?

Each convex polytope $P$ has a combinatorial type, its so-called face lattice. This lattice is just the poset of all faces of $P$ ordered by inclusion. Given one realization of such a combinatorial ...
3
votes
1answer
264 views

lipschitz property of the derivative of a convex function

Let $f\in C^1(\mathbb R^n\to \mathbb R)$ be a convex function. Suppose the equation $$f(x+\Delta x)-f(x)-\bigr<f'(x),\Delta x\bigl>\leq A|\Delta x|^2$$ holds for some constant $A>0$, ...
3
votes
1answer
332 views

Basic properties of the point-to-set distance function

Let $X$ be a normed vector space, $x\in X$ and $Z\subseteq X$. Then we define the point-to-set distance function as: $$ \|x\|_Z = \inf_{z\in Z} \| x-z\| $$ I use the notation $\|\cdot\|_Z$ for ...
3
votes
1answer
261 views

Differentiability of Moreau-Yosida approximation.

I want to show that if $X$ is a reflexive Banach space with norm of class $\mathcal{C}^1$ and $f\colon X\to\mathbb{R}\cup \{+\infty\}$ is convex and lower semicontinuous, then $f_{\lambda}$ is ...
3
votes
1answer
333 views

Is a convex function defined on a convex open subset of $\mathbb R^n$ continuous?

Let $K$ be a convex open set in $\mathbb R^n$ and $f$ a convex function defined on $K$; how to show that $f$ is continuous?
3
votes
1answer
29 views

nonsurjectivity of Banach-Stone theorem

Currently I'm studying the extension of Banach-Stone theorem using this book. There is one section about the removal of surjectivity of the isometric isomorphism between the two function spaces $C(K)$ ...
3
votes
1answer
60 views

What type of convex constraint is defined by SQRT?

Let $A$ be an $n \times n$ positive semidefinite matrix and $\forall k, x_k \in \mathbb{R}^n$. The distance with respect to this matrix is defined as $ \|x_i -x_j\|_A := ...
3
votes
1answer
74 views

Lovasz Extension Intuition

I am confused by the definition of Lovasz extension. The problem is I don't get the intuition behind the definition. In addition, Lovasz extension can be defined in different ways I don't see that ...
3
votes
1answer
35 views

Does every convex subset of $\mathbb{R}^n$ have normal almost everywhere?

Does every convex subset of $\mathbb{R}^n$ have normal almost everywhere? I want to know if I have any convex subset $M$ of $\mathbb{R}^n$ is it meaningful to talk about integral of second kind ...
3
votes
1answer
119 views

optimizing a logdet function with respect to a scalar and the Hessian matrix

Given a logdet function $\mathcal{L}(\gamma)$, $$ \mathcal{L}(\gamma) = \log\vert \mathbf{I} + \gamma\mathbf{S} \vert - \mathbf{q}^T(\gamma^{-1}\mathbf{I} + \mathbf{S})^{-1} \mathbf{q}, $$ where ...
3
votes
1answer
446 views

Strictly convex sets

If $S\subseteq \mathbb{R} ^2$ is closed and convex, we say $S$ is strictly convex if for any $x,y\in Bd(S)$ we have that the segment $\overline{xy} \not\subseteq Bd(S)$. Show that if $S$ is compact, ...
3
votes
1answer
165 views

Show that any convex function is locally bounded

Show that a convex function $f:\mathbb{R}^n \rightarrow \overline{\mathbb{R}}$ is bounded in a neighborhood of $x\in \text{ri}(\text{dom}(f))$. Showing that it has an upper bound is not difficult ...
3
votes
1answer
130 views

Strictly Convex Function and Well-Separated Minimum

Suppose $\Theta \subset \mathbb{R}^d$ is a convex set, and $f:\Theta \rightarrow \mathbb{R}$ is a strictly convex function that has a minimum at $\theta_0\in\Theta$. Is it true then that $\forall ...
3
votes
1answer
82 views

Prove that there are no convex functions on compact manifolds

This one seems intuitively obvious to me but I don't know how to prove it. Suppose you have a compact manifold $M$ with a function $f$ defined on it. Given two points $x$ and $y$ on the manifold, ...
3
votes
1answer
488 views

Why is this composition of concave and convex functions concave?

Please forgive my ignorance. I have a quick silly question about a statement given without proof in Convex Optimization by Boyd and Vandenberghe (page 87). Suppose $\mathbb{R}_+^n$ is the set of ...
3
votes
1answer
121 views

Intersection of two $n$-dimensional quadratic inequalities?

I have two quadratic inequalities of the form $$ a_1x^TAx + b_1^Tx + c_1 \le 0\\ a_2x^TAx + b_2^Tx + c_2 \le 0 $$ where $A\in\mathbb{R}^{n\times n}$ is positive semidefinite, $x\in\mathbb{R}^n$, ...
3
votes
1answer
108 views

Edges of the convex hull of a finite point set

I'm looking for a formal proof of a statement that seems obvious (and yet may be wrong) to make sure one of my algorithms is correct. Given a set S of N points in $\mathbb{R}^3$, suppose we have a ...
3
votes
2answers
125 views

Codimension of the largest subspace of a closed convex cone in a normed vector space

Please, help to prove (or disprove) the following statement. Let $K \neq V$ be a closed convex cone ($K+K=K$, $\alpha K \subseteq K$ for any $\alpha \geq 0$) in a real normed vector space $V$. If $-K ...
3
votes
1answer
56 views

Show that $Z=T(2S−I)+I−S$ is firmly nonexpansive

Suppose $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Let $I$ be identity operator. I want to show that $Z=T(2S−I)+I−S$ is firmly nonexpansive. Definition. We say ...
3
votes
1answer
34 views

Strong Separation of Closures

Let $\bar D $ and $\bar E$ denote the closures of $D$ and $E$ respectively. If $ D\subset \mathbb R^n$, $E \subset \mathbb R^n$ and they are strongly separated. Show that $\bar D $ and $\bar E$ can ...
3
votes
1answer
119 views

Regularity Conditions for Constrained Optimization

Question: Let $G$ be a convex mapping from $\Omega \subseteq X$ into a normed space $Z$, and assume that $P \subseteq Z$ be a positive cone with nonempty interior. Show that the following two ...
3
votes
1answer
282 views

Going in the direction of the gradient

First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$. Now my ...
3
votes
1answer
208 views

Hausdorff distance via support function

Let $A$ and $B$ be convex compact sets in $\mathbb{R}^n$. Define $$ h_{+}(A,B) = \inf \left\{ \varepsilon > 0 \mid A \subseteq B+\mathbb{B}_{\varepsilon} \right\} $$ where ...
3
votes
2answers
278 views

Convexity of inverted sum of positive definite matrices

I am currently working with a class of functions, where every function looks like $f(x)=v^T(xA+(1-x)B)^{-1}v,$ where $v\in\mathbb{R}^n$ is an arbitrary vector, $A,B \in \mathbb{R}^{n\times n}$ are ...
3
votes
1answer
144 views

Dual of a polytope — intersection of infinitely many halfspaces?

Let $S \subseteq \mathbb{R}^d$ be a $d$-dimensional convex set (i.e. $\exists d+1$ affinely independent points in $S$). Let the origin of the coordinate system lie in the interior of $S$ and let: ...
3
votes
1answer
129 views

Properties of nearly concave functions

Is there any existing literature on the properties/applications of the following class of functions? $$\frac{f(E[x])}{E[f(x)]}\geq c$$ where $c< 1$ is a constant. Note that for $c=1$ these are ...
3
votes
1answer
62 views

Algebraic Proof that a Disk is Convex

After searching on Google for a while, I cannot seem to find an algebraic proof that a disk is a convex set. Intuitively, this seems obvious: if you take any two points $x, y$ in a disk, then the line ...
3
votes
2answers
37 views

convexity of inverse function

I have a question on the reverse of a convex function. Let $f(x)$ be a convex function. Is the reverse function, say $g(x)=f(x)^{-1}$, is necessarily a concave function ? Considering that such ...
3
votes
0answers
46 views

Convex Functions are Continuous

In W. Rudin's Principles of Mathematical Analysis, we read in Chapter 4 that real-valued functions defined on an open interval $(a,b)\subseteq\Bbb R$ are continuous (specifically, Exercise 23). I am ...
3
votes
0answers
63 views

What are the extreme points of the set of probability measures on $(\mathbb N, \mathcal{F})$?

Say, we have some $\sigma$-algebra on $\mathbb N$ and let $\mathbb P$ be the set of all probability measures on it. We know that $\mathbb P$ is convex, so I wonder how do the extreme points look like. ...
3
votes
1answer
28 views

Calculate Dq(x)

Let A be a symmetric $m \times m$ matrix, and $q(x)=x\cdot Ax$ a quadratic form on $\mathbb{R}^m$. Question: Calculate $Dq(x)$; write your answer in vector notation. Does anyone knows the answer on ...
3
votes
1answer
24 views

Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
3
votes
1answer
59 views

Converting to canonical Polyhedral Sets

In many places, results about Polyhedral sets (for example the Characterization Theorem of Polyhedral sets) are proved for the canonical polyhedral set $\{x \in \mathbb R^n: Ax = b\}$ with $b\in ...
3
votes
0answers
60 views

On convex functions being continuous

Every convex function is continuous. It usually says "draw this and it will become obvious that the epigraph is not convex. However, when I draw the epigraph of $f: [0,3] \to \mathbb{R}, f(x) = x^2$ ...
3
votes
0answers
51 views

Biggest ellipse included in a convex polygon

Considering a N edges convex 2D polygon called P. Let's name its vertices $\{p_1, p_2, ..., p_N\}$ described in a counter-clockwise order, with $p_i = (x_i, y_i)$ What would be, and how would one ...
3
votes
1answer
47 views

Conjecture about a property of concave functions

Trying to prove a proposition in my paper, which can potentially use a conjecture about convex (concave) functions. This is likely to be wrong. I appreciate any thoughts on how to prove/disprove this. ...
3
votes
0answers
74 views

Averages of a Function

Let $(X,M,\mu)$ a measure space and $f:X \rightarrow \mathbb{C}$ a function in $L^{\infty}(\mu)$. Define $A_f$ as the set of all averages \begin{equation} \frac{1}{\mu(E)} \int_{E} f d \mu ...
3
votes
1answer
63 views

Does convex and radially open imply open?

I want to show that a convex set $A$ is radially open iff $A\cap W$ is open in W, for every finite dimensional linear subspace. Here the 'openness' we are talking about is from any normed space. ...
3
votes
0answers
84 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...