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
3answers
213 views

About convex function

The exercise is about convex functions: How to prove that $f(t)=\int_0^t g(s)ds$ is convex in $(a,b)$ whenever $0\in (a,b)$ and $g$ is increasing in $[a,b]$? I proved that $$f(x)\leq ...
3
votes
1answer
307 views

Concave functions on discrete domain

We are given a positive, non-decreasing function $f$ defined on natural numbers with $f(0) = 0$. $f$ has a submodularity-like property: $f(x+y) \leq f(x) + f(y) $ for all natural numbers $x$ and ...
3
votes
3answers
198 views

Quantifying convexity

What methods exist to quantify convexity. Yes, a set is convex if the the line between two points in the set is contained in the set, but is there a measure of how convex a set is? If so, what is ...
3
votes
1answer
144 views

Convexity of a set in Hilbert space

Let $H$ be a Hilbert space and $\left\{ e_{i}\right\} _{i=1}^{\infty}$ an orthonormal system. I need to prove that the following set is a convex set: $$C=\left\{ x\in ...
3
votes
2answers
164 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
3
votes
2answers
801 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
1answer
89 views

Showing existence of solution by positive definiteness/convexity

For a physics problem, I am considering the following problem: I have a certain function, $S: \mathbb{R}^M \rightarrow \mathbb{R}$, of which the critical points, given by $$ \frac{\partial ...
3
votes
1answer
179 views

The unit ball in a Hilbert space

I have a request for any ideas to prove: If $H$ is a Hilbert space, then any unit vector is an extreme point of the unit ball of $H$. Every isometry is an extreme point of the unit ball of the ...
3
votes
1answer
185 views

Find the maximum convex area

My question is very similar to Plow's Question; but with this difference: How can I find the maximum convex area that can fit inside a non-convex region? For an example, consider this non-convex ...
3
votes
1answer
113 views

Equivalent definitions of uniform convexity.

I think I'm dumb, but I can't follow a simple proof from "Functional analysis and infinite dimensional geometry". They show that two different definitions of modulus of convexity of a norm are the ...
3
votes
1answer
255 views

Jensen's inequality and $L^p$ norms

Let $(X,\Sigma,\mu)$ be a probability space; in particular, $\mu(X)=1$. The integral form of Jensen's inequality can be phrased in terms of permuting a convex function $\varphi$ (say, with the ...
3
votes
2answers
1k 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
1answer
93 views

Is this function convex

Is function $$f(x, y) = \left(\frac{x}{y} - a\right)^2 \left(\frac{y}{x} - \frac{1}{a}\right)^2$$ convex on the domain $$\{(x,y): x, y \in \mathbb{R}, x >0, y >0 \}\quad?$$ Now I think that it ...
3
votes
2answers
150 views

$(d-1)$-rectifiability of a boundary of compact convex set

Let us have a compact convex set $A\in \mathbb{R}^d$. Then $\delta A$ should be a $(d-1)$-dimensional rectifiable set. I don't seem to be able to show that it can be covered by a countable union of ...
3
votes
1answer
78 views

Showing that the set of polynomials is convex

How to show that the set of polynomials of $x^2+bx+c$ having at least one real root, is convex? Let $x^2+b_1x+c_1$ and $x^2+b_2x+c_2$ have at least one real root. Need to show that ...
3
votes
1answer
93 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
3
votes
2answers
312 views

A standard quadratic minimization problem

Consider the "Complex" Quadratic minimization problem \begin{align} \min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1 \end{align} ...
3
votes
1answer
178 views

Anderson's Inequality for Gaussian measures

Let $C\subset \mathbb R^n$ be convex and symmetric about the origin. I am trying to prove that $\gamma(C) \geq \gamma(C+x)$ for any $x\in \mathbb R^n$, where $\gamma$ is the standard Gaussian measure. ...
3
votes
1answer
260 views

Limit of derivatives of convex functions

Let $(f_n)_ {n\in\mathbb{N}}$ be a sequence of convex differentiable functions on $\mathbb{R}$. Suppose that $f_n(x)\xrightarrow[n\to\infty]{}f(x)$ for all $x\in\mathbb{R}$. Let ...
3
votes
1answer
433 views

Why does positive semi-definiteness in this inequality imply a convex set?

I was reading a proof that rewrote an inequality in the form: $$b^Tx +x^T A x \le \alpha$$ for $b,x \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$, and with $A$ positive semidefinite. It then ...
3
votes
1answer
419 views

Intersection of two (specific) convex functions

Given are the following two functions: $$g(z) = \left(z-2\right)\left(2+z\left(z-2\right)\right)$$ and $$h(z) = 2\left(z-1\right)^{2}\ln\left(z-1\right),$$ where $z>2$. I would like to show ...
3
votes
3answers
404 views

Representing a point inside a polyhedron as a convex combination of extreme points

Is there some standard way of representing any point in a polyhedron as a convex combination of some of the extreme points ? More precisely, by n poly(n) n extreme points where n is the number of ...
3
votes
1answer
34 views

Local convexity of the topology of weak convergence of probability measures

Let $X$ be a Polish or standard Borel space, and $\mathcal P(X)$ be the space of all Borel probability measures on $X$ endowed with the topology of weak convergence. I am thinking of using ...
3
votes
2answers
40 views

about an interesting affirmation involving convex sets

Consider the following definition Definition: Let $\Omega \subset R^n$ a bounded convex set. A point $x \in \partial \Omega$ is called an extremal point if $x$ cannot be written as linear ...
3
votes
1answer
83 views

Proof that a set is convex

$$k\in \mathbb{R}_{+}$$ $$M=\left \{ (x_1,x_2)\in \mathbb{R}_{++}^2 \mid x_1 x_2\geq k\right \}$$ Prove that the set $M$ is convex. A hint is given (quoted from the text): We could choose to ...
3
votes
1answer
68 views

Hyperplane which can separate two closed convex set

Define: $$E=:\ell^1(R)=\{x=(x_n)_n: \|x\|_1=\sum_{n=1}^{\infty}|x_n|<\infty\}$$ We have two closed convex sets $X,Y$ as subsets of normed vector space $\ell^1(R)$ with $X\cap Y=\emptyset$ and $Y$ ...
3
votes
1answer
83 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
99 views

Every face of compact convex set is closed?

Well, this is my doubt: Let $\vec{E}$ be a n.v.s. and $K\subset \vec{E}$ a compact convex set. Then every face of $K$ is closed. Any hint in order to prove it is welcome. Thanks in advance!
3
votes
1answer
216 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
1answer
104 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
3
votes
2answers
65 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
418 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
2answers
82 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
132 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
62 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
473 views

Proof of an obvious fact about convex polygons.

Consider a closed simple polygon in the plane. It is intuitively obvious that the polygon is convex if and only if all the interior angles measure less than or equal to $\pi$ radians. I have never ...
3
votes
2answers
631 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
212 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
123 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
276 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
361 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
321 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
506 views

Prove that the convex hull of a set is the smallest convex set containing that set

How do you prove that the convex hull of A is the smallest convex set containing A? edit: definition of a convex hull: Given a set A ⊆ ℝn the set of all convex combinations of points from A is called ...
3
votes
1answer
385 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
38 views

Generalization of log-convexity (log-concavity): log-log-convexity (log-log-concavity)?

$\underline{\mathrm{Background\; on\; function\; Convexity}}$ A function, $f$, is convex if: $$f( x\theta+y(1-\theta) ) \leq \theta f(x) + (1-\theta)f(y).$$ $f$ is concave if $-f$ is convex, [1]. If ...
3
votes
2answers
24 views

Composition of convex and power function

Let $g$ be a convex nonegative function, and $p\ge1$. To show: $f(x)=g(x)^p$ is convex. Let $h(x)=x^p$. Then clearly $f=h \circ g$. Denote $\tilde{h}$ as the extended-value extension of $h$, which ...
3
votes
1answer
68 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
215 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
1answer
31 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
71 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 := ...