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
1answer
26 views

Let S ⊂ R 2 . Show that if cl(S) is convex, then S is convex.

Let $S ⊂ R^2$. Show that if $cl(S)$ is convex, then S is convex. This seems intuitive but, I am having trouble thinking of a proof or counter example.
2
votes
1answer
24 views

How to prove convexity of a given set

I have the set $$ C_c = \{(x,y,z) \epsilon \mathbb{R}^3 : (2x-x^2+y)(2y-3z)(5x-z) > 1, |x| < 1, y > 3, z < 2\} $$ and I need to prove whether it's convex or not. I know that the ...
1
vote
1answer
14 views

Set of points at which a function coincides with its convexification is compact?

Let $f:[0,1]\rightarrow\ \mathbb{\bar{R}}$, and let $\tilde{f}$ be the convexification of $f.$ (i.e., $\tilde{f}$ is the pointwise supremum of all affine functions that lie everywhere below $f$.) Let ...
0
votes
0answers
22 views

connections between polar set, polar cone?

Given a set $S$, its polar cone http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone and its polar set http://en.wikipedia.org/wiki/Polar_set are defined. Could some please tell me the ...
1
vote
0answers
28 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
1
vote
0answers
16 views

Hahn Banach theorem and supporting hyperplane theorem

The question is out of Rudin Functional analysis Chapter 3 problem 1. Call a set $H \subset \mathbb{R}$ a hyperplane if there exists real numbers $a_1,\ldots, a_n, c$ (with $a_i \neq 0$ for at least ...
0
votes
0answers
27 views

Krein Milman Property

If a closed bounded (not compact) set $X$ in a Banach space $B$ (like $L^1$) has extreme point(s), must the max of a linear functional defined on $X$ occur at one of them? I suppose it depends on $B$. ...
0
votes
0answers
20 views

Book recommendation for Choquet theory

Assuming a good background in basic functional analysis and operator algebras, what is an appropriate text for self-study in Choquet theory?
3
votes
3answers
131 views

Why are convex polyhedral cones closed?

Let $V = \mathbb{R}^n$, $v_1, \dots, v_s \in V$ and let $\sigma = \text{Cone}(v_1, \dots, v_s) = \{r_1v_1 + \dots + r_sv_s \mid r_i \geq 0\}$ be the associated convex polyhedral cone in $V$. Why is ...
0
votes
0answers
15 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
1
vote
1answer
19 views

Convex hull of set of sparse vectors?

I am trying to understand how one can define the convex hull of sparse vectors. I understand that for k sparse vectors can be described as a union of subspaces (such as in: ...
1
vote
3answers
51 views

Proving that the second derivative of a convex function is nonnegative

My task is as follows: Let $f:\mathbb{R}\to\mathbb{R}$ be a twice-differentiable function, and let $f$'s second derivative be continuous. Let $f$ be convex with the following definition of ...
0
votes
0answers
24 views

regularity of a bivariate function

Consider a bivariate function $f(x,y)$ which is concave in $y$. Moreover, for any given $y$, let $x^*(y)$ be the solution to $f_x(x,y)=0$, and there is $f_x(x,y)>0$ for $x<x^*(y)$ and ...
1
vote
0answers
26 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
5
votes
1answer
198 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. ...
1
vote
1answer
42 views

How to use convexity in this step?

I am trying to fill in the details of a proof about the following statement: If $f:\mathbb{R}^n\to \mathbb{R}$ be a convex function, if subdifferential of $f$ at $x$ is singleton, then $f$ is ...
1
vote
0answers
36 views

Expectation of an increasing, bounded concave function of a non-negative random variable

Let $h:[0,\infty)\to [0,1)$ be a strictly increasing and strictly concave function. Let the argument of this function be a random variable $C$ with probability density function (pdf) $f_{C}(c)$ with ...
0
votes
0answers
16 views

Continuity of convex function [duplicate]

Let $f$ be a proper convex lower semi-continuous function on $\mathbb R^n$, how can we prove $f$ is continuous in the interior of $Dom(f)=\{f<\infty\}$ ?
0
votes
1answer
12 views

Variation of linear matrix inequality

When reading "Convex optimization, S. Boyd" p.76, Example 3.4, it says The last condition is a linear matrix inequality (LMI) in $(x,Y,t)$. Therefore, epi($f$) is convex. I am confused about ...
1
vote
2answers
41 views

If $f$ is midpoint convex, continuous, and two times differentiable, then for any $a, b \in \mathbb{R}$, there exists $c$ such that $f''(c) \geq 0$

One of my analysis texts states this as an exercise If $f$ is midpoint convex, continuous, and two times differentiable, then for any $a, b \in \mathbb{R}$, there exists $c \in [a, b]$ such that ...
2
votes
0answers
163 views

An improvement of Jensen's inequality - help please!

It would nice if someone could help me with this problem. I am looking at an improvement to the classical Jensen's Inequality: $$\int_\limits{}^{} \phi(x) \mu \mathrm{d}x \geq ...
2
votes
1answer
38 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
3
votes
1answer
50 views

How can I prove the hypersurface $M$ is neither convex nor concave?

The question is so simple: how can I prove that $M$ (as defined below) is neither convex nor concave (in the real sense)? The point here is to define a new notion of convexity, the complex convexity, ...
0
votes
0answers
21 views

Notion of positive third derivative for nondifferentiable functions?

Are there any notions that generalize the idea of a positive third derivative of a univariatve function to those for which the function is not necessarily differentiable? For example, a function ...
1
vote
2answers
195 views

(Updated) Geometric Illustration of Monotone and Maximal Monotone Maps

I am writing a note about the Monotone and Maximal Monotone maps from the following book http://link.springer.com/book/10.1007%2Fb97594 In this book we read a map ...
7
votes
5answers
1k views

Is every monotone map the gradient of a convex function?

Recently in a seminar someone mentioned that monotone maps are equivalent to gradients of scalar convex functions, but it's not clear to me why this is true. One direction of the equivalence is ...
1
vote
0answers
17 views

Intersection numbers on blow ups of toric varieties

Suppose we have a smooth, complete toric varietiy $X_{\Sigma}$ of dimension $n$. Let $\sigma_k \in \Sigma(k)$ a smooth $k$-dimensional cone in $\Sigma$ and suppose we make the toric blow up at the ...
0
votes
1answer
420 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 ...
3
votes
1answer
171 views

Polytopes inside polytopes

I would like to share some facts about polytopes and how to check whether a polytope is a subset of some other polytope. I will provide some methods and I would like to know whether there exist other ...
1
vote
1answer
29 views

Quasiconvex functions

Let $\lambda$ be any real number and $f:[0,1]\times[0,1]\rightarrow\mathbb{R}$ given by $$ f(x,y) = \begin{cases} \lambda &\mbox{if } \quad0<x<1, y=1, \\ 1+\lambda y & \mbox{if } ...
2
votes
1answer
93 views

Minkowski sum of two polytopes via the halfspace representation

If i have two polytopes denoted by $P_1, P_2 \subset \mathbb{R}^d$, suppose their halfspace representations are respectively $H_1x \leq K_1$ and $H_2x \leq K_2$. Now, considering their Minkowski sum, ...
1
vote
1answer
52 views

Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region (X) of a Linear Program can be represented as a convex combination of the extreme points of X plus a non-negative combination of the extreme directions of ...
0
votes
0answers
22 views

convex region with 7 vertices

Let, $X$ be a convex region in the plane bounded by straight lines. Let, $X$ have $7$ vertices. Suppose $f(x,y)=ax+by+c$ has maximum value $M$ & minimum value $N$ on $X$ & $N<M$. Let, ...
1
vote
2answers
45 views

Is the optimum of this problem unique?

I have a convex optimisation problem: $$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$ The KKT conditions are: $$\lambda=\begin{cases} ...
2
votes
0answers
72 views

Question about Random Walks and An $O^*(n^5)$ Volume Algorithm for Convex Bodies - Kannan Lovasz Simonovits 97

I've been trying to understand this paper: "Random Walks and An $O^*(n^5)$ Volume Algorithm for Convex Bodies", Ravi Kannan, Laszlo Lovasz, Miklos Simonovits. Motivation: The paper is about ...
0
votes
0answers
20 views

Need to prove a property using super modularity and convexity

I have a function $f(x,y)$ that is convex on both x and y separately (but maybe not a joint convex function). It is also super modular. Assume that we have ordered sets of $x$ and $y$ as $(x1\gt x2,\ ...
1
vote
0answers
43 views

How to calculate Jensen's Inequality

How would one show that $\mathbb{E}\Big[f(X)\Big] \geq f\Big[\mathbb{E}(X)\Big]$ for the convex function f(x)=x$^{2}$ ?
1
vote
1answer
24 views

Nonlinear discontinuous convex function

Let $X$ be a normed vector space. Construct nonlinear discontinuous convex function $f:X \rightarrow \mathbb{R}$. I tried something with $\frac{-1}{\|x\|}$ but had no success.
2
votes
1answer
127 views

Existence of Hessian of convex conjugate

Define convex conjugate of $f, f^*(x):=\sup_{y\in\mathbb{R}^n}\langle x,y\rangle-f(y)$. Then I want to prove this statement: Let $f:\mathbb{R}^n\to\mathbb{R}$ be a convex function. Assume $f$ is ...
0
votes
2answers
1k views

generalized inequalities defined by proper cones [duplicate]

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ? ...
12
votes
1answer
419 views

Convexity of Matrix Exponential

Consider the function $A: \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ defined as $$ A( x ) := \left[ \begin{matrix} x_1 & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & x_2 & ...
1
vote
2answers
117 views

Triangle containing most points from a set

Given a point set in $\mathbb{R}^2$, I need to find a triangle connecting three points of the set that contains the most points of the set. Points that lie on the connecting lines don't count. The ...
0
votes
1answer
22 views

Is this function jointly convex in its variables?

I have a function which I suspect is jointly convex, but have a difficult time proving it, especially since the Hessian is messy. The function is $f(y_i,i=1.2,\ldots,N)=\sum_i l_i w_i + y_i$, where ...
4
votes
1answer
46 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
0
votes
0answers
33 views

Is there a unique saddle value for a convex/concave optimization?

Here is the question: Consider a function of two variables $f(x,y)$ on some compact domain. Let it be convex in $x$ and concave in $y$. Is it true that $f(x,y)$ has a uniqe saddle point ...
1
vote
1answer
29 views

Convexity definition when $\lambda \in \mathbb{R} \setminus (0,1)$

We are given the standard definition $$f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)$$ for $\lambda \in (0,1)$. I am trying to prove that the opposite inequality is true when ...
2
votes
1answer
37 views

How do I integrate the inequality $ \frac{f(\frac{1}{2}+h)+f(\frac{1}{2}-h)}{2} \leqslant f(\frac{1}{2})$ over the range $h\in[0,1/2]$?

I would like to know the formal steps and theory. I was told that, by integrating this inequality, I can achieve one of the definitions of a concave function in the interval [0,1]. Thanks for your ...
0
votes
0answers
27 views

Show that $f(\mathbf x)=e^{Q(\mathbf x)}$ is a convex function.

Here's the problem: Let $A$ be a positive definite symmetric matrix and let $Q(\mathbf x)$ denote the associated quadratic form on $\mathbb R^n$. Show that $f(\mathbf x)=e^{Q(\mathbf x)}$ is a convex ...
0
votes
2answers
26 views

Mean value for a concave function over $[0,1]$ VS $f(1/2)$

I am looking for a concave function $f(x)$ for which the integral over $[0,1]$ is bigger than $f(1/2)$. That is, a function which mean value between 0 and 1 is bigger than the middle value of the ...
0
votes
1answer
55 views

How do I prove function convexity? [duplicate]

I have the following task: Prove that if $ f : I \rightarrow \mathbb{R} $ is continuous ($ I $ is a range) and $$ \forall {x,y \in I} \qquad f\left(\frac{x+y}{2}\right) \leq \frac{f(x) + f(y)}{2} $$ ...