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)

3
votes
1answer
52 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
22 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
207 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
18 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 ...
1
vote
1answer
31 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
100 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
58 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
23 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
47 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
73 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
24 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
50 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
26 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$ ? ...
13
votes
1answer
431 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
126 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
26 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
47 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
45 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
31 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
38 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
27 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
56 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} $$ ...
-2
votes
1answer
29 views

Determine if$ f(x) = -|x + 2| \,\,\,\forall x ∈ [-2, 0]$ is convex

Having trouble with this homework question, Determine if $f(x) = -|x + 2| \forall x ∈ [-2, 0]$ is convex using the below definition of convexity. A function $f: X -\to\mathbb{R}^n$ is convex for ...
1
vote
0answers
39 views

Two fundamental questions about convexity of a function (number2) [duplicate]

The second question is as follows (the first one is here): 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 ...
4
votes
3answers
140 views

If $(\nabla f(x)-\nabla f(y))\cdot(x-y)\geq m(x-y)\cdot(x-y)$, why is $f$ convex?

I was reading on wikipedia that a strongly convex function is also strictly convex. I say that a function $f\colon\mathbb{R}^n\to\mathbb{R}$ is convex if $$ f(\lambda x+(1-\lambda)y)\leq\lambda ...
8
votes
4answers
2k views

Convexity and Affineness

In reading about convex optimization, the author states that all convex sets are affine. Are affinity and convexity equivalent? If I understand, both definitions incorporate the notion that a set is ...
1
vote
2answers
51 views

Convex analysis of $h(x) = \log (f(x)) \ $ for $f \in C^2(\mathbb{R, \mathbb{R}_+})$

Problem: Let $f: \mathbb{R} \to \mathbb{R}_+$ be of Class $C^2$ such that $$g(x)= f(x)e^{cx} \text{ is convex } \forall c \in \mathbb{R} $$ Verify that $h(x)= \log(f(x))$ is convex My approach: ...
0
votes
1answer
92 views

finding the polar set

the question say find the polar-duals of the following sets in $\mathbb{R}^2$ 1) $\{(x,y):x\geq 2\}$ 2) $\{(x,y):x\leq 2\}$ 3) $\{(x,y):x=2\}$ the answers are $\{(x,0):x\leq 0\}$ , $\{(x,0):0\leq ...
1
vote
0answers
22 views

An inequality regarding convex functions

For a convex function $f(\cdot)$ for $x_4 \ge x_3 \ge x_2 \ge x_1 \ge 0$ and $t,t^{'}\ge 0$ we are given that \begin{equation} \frac{f(x_4)-f(x_3)}{f(x_2)-f(x_1)} \ge ...
0
votes
1answer
24 views

Proof regarding convex sets

A set of points is said to be convex provided that every pair of points in the set can be joined by a line segment that lies entirely within the set. Show that, if $ | ∇f(x)| ≤ M \space \space ...
3
votes
2answers
251 views

Is $g(x)=\log x$ convex function?

The graph of convex function is : In a book it is written that $g(x)=\log x$ is strictly convex function. So i searched for graph of $g(x)=\log x$ and found that Though it has been said that ...
1
vote
2answers
58 views

Two fundamental questions about convexity of a function (number1)

The first question is as follows (see the second one): If $f$ is a convex function it is know that there is at most a single minimum. However the argument of the minimum is not guaranteed to be ...
0
votes
1answer
68 views

Proof - extreme point of a convex set

everybody! I am wondering how to prove the following theorem: Let $S \subset \mathbf{R}^{n}$ be a non-empty closed convex set. Then $S$ has at least one extreme point iff $S$ does not contain any ...
0
votes
1answer
17 views

Convex downward function and its inverse function

How to prove that if function $f$ is convex downward and invertible then $f^{-1}$ is convex downward or convex upward? When is it downward and when upward?
2
votes
1answer
47 views

Lipschitz constant of the convex function $f(x) - \frac{a}{2} |x|^2$

I was going through this blog post https://blogs.princeton.edu/imabandit/2013/04/04/orf523-strong-convexity/ It has been mentioned without proof that for a function ...
0
votes
1answer
20 views

Polynomial and convex functions

Consider polynomials $\mathbb{R} \rightarrow \mathbb{R}$. I have to Give an example of polynomial that isn't convex downward nor convex upward. Give an example of polynomial that is convex downward ...
1
vote
1answer
54 views

Function going from $0$ to $1$ with minimal concavity

How small can I take $C>0$ such that there exists an $f\in C^2(\mathbb R;\mathbb R)$ satisfying the following properties: $f(x)=0$ for $x\leq 0$ and $f(x)=1$ for $x\geq 1$ $f'(x)\geq 0$ for ...
3
votes
1answer
89 views

Extensions of Carathéodory's theorem

We know about the Carathéodory's theorem which is on the convex bodies of $\mathbb{R}^d$. My question is, how far we can extend it? Is it true for say, any convex object of Banach space, or for convex ...
0
votes
0answers
37 views

Does every boundary segment of a convex polyhedron lies on one of its faces?

When I was reading this note, I found Theorem 3.1.5 said: Let $P\in\mathbb{R}^n$ be a polytope whose affine dimension is $d$. Then, every point on the boundary of $P$ lies in a facet of $P$. I have ...
1
vote
1answer
29 views

condition for uniform input to minimize convex function

Let $f:\mathbb{P}(X) \rightarrow \mathbb{R}$ be a convex function where $\mathbb{P}(X)$ is the set of probability distribution on (finite) set $X$. I am looking for condition on $f$ so I can said ...
2
votes
1answer
39 views

Convex hull of convex set boundary

A is a closed convex set with non-empty interior. Does A must equal to the convex hull of its boundary? I know this is false when A is half space. But what about other sets?
1
vote
3answers
181 views

Proof of convexity from definition ($x^Tx$)

I have to prove that function $f(x) = x^Tx, x \in R^n$ is convex from definition. Definition: Function $f: R^n \rightarrow R$ is convex over set $X \subseteq dom(f)$ if $X$ is convex and the ...
0
votes
0answers
24 views

convergence of infimal convolution

I am trying to show the following statement: Let $f:\mathbb{R}^n\to \mathbb{R}\cup\{\infty\}$ be a convex function. Let $f_\epsilon(x)=\frac{|x|^2}{2\epsilon}$. Show that $\lim_{\epsilon\to ...
1
vote
1answer
44 views

Are these inconsistent definitions of extreme subset of convex set?

I need some elementary knowledge of polyhedral and I am consulting several books. However, I found the definitions may not be consistent. I am not sure if I understand them right. The question is ...
0
votes
0answers
20 views

How can I solve $\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$ in a closed form depending on projection?

I'm trying to solve the minimization problem $$\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$$ where $b \in \mathbb{R}^n$, $X \subset \mathbb{R}^n$ is a convex set. And $A$ is a symmetric ...
1
vote
1answer
30 views

Can I assume $g$ is finite for proof involving infimal convolution

I am trying to show the following statement: Let $f,g:\mathbb{R}^n\to \mathbb{R}\cup \{\infty\}$ be two convex functions. Assume that there are constants $C_1,C_2>0,\alpha>1$ such that ...