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
240 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
91 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
146 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
75 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
91 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
307 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
173 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
251 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
416 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
407 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
1answer
380 views

Both convex and concave functions

Let $f$ be a function from $\mathbb{R}^n$ to $\mathbb{R}$, which is convex & concave and continuous with $f(0)=0$. How to prove that $f(x)=q\cdot x$ for all $x$ in $\mathbb{R}^n$, for a scalar ...
3
votes
1answer
2k views

Is the sum of convex functions on different domains convex?

On the same domain, the sum of convex functions is convex (e.g. $f(x) + g(x)$ is convex if $f(x)$ and $g(x)$ are convex). However, I don't know that this is true for the sum of convex functions on ...
3
votes
3answers
397 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
27 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
38 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
79 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
66 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
82 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
94 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
200 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
64 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
398 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
79 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
129 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
620 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
206 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
122 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
273 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
353 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
316 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
491 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
372 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
2answers
23 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
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
70 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
134 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
36 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
127 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
542 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
192 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
166 views

Hessian of a function that takes matrix arguments

I have a function that that takes a matrix and returns a scalar, $f : \mathbb{R}^{m\times n} \rightarrow \mathbb{R}$. I know how to calculate the derivative of this function with respect to the matrix ...
3
votes
1answer
136 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
92 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
580 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
126 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
119 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 ...