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
22 views

Proving the concavity of a function

I want to prove that the function $x \mapsto \Phi(\Phi^{-1}(x) + \lambda)$ defined for $x \in [0,1]$ is concave for any $\lambda \geq 0$. $\Phi$ is the cumulative distribution function of a standard ...
0
votes
1answer
18 views

Inequality involving the Hessian matrix of a convex function

Let $f \in C^2(\mathbb{R}^d)$ be a convex function with Hessian $H$. Is it true that $$ (x^T H(x) - y^T H(y)) (x-y) \ge 0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(1) $$ for all $x,y \in \mathbb{R}^d$? ...
0
votes
0answers
11 views

Medial axis of non-convex polygon

I used CGAL 4.8 - 2D Straight Skeleton and Polygon Offsetting, which covers the convex case. Now the polygon can be non-convex and simple. How to compute the medial axis in this case? This ...
2
votes
1answer
978 views

How to see that K-means objective is convex?

I'm trying to proof that the objective of the K-means clustering algorithm is non-convex. The objective is given as $J(U,Z) = \|X-UZ\|_F^2$, with $X \in\mathbb{R}^{m\times n}, U\in ...
1
vote
1answer
25 views

How to prove coercivity

I have a problem in understanding how to prove if a function is positive or negative coercive. I understood the definition of coercivity, which is: $$\lim_{||x|| \to +\infty}f(x) = +\infty$$ However, ...
0
votes
1answer
16 views

Convex set in a vector space gives a norm

Given an $\mathbb{R}$ or $\mathbb{C}$ vector space $X$ and a function $p:X\rightarrow[0,\infty)$ with $p(x)=0$ iff $x=0$ and $p(\alpha x)=|\alpha|p(x)$ for all $x,\alpha$, I want to show that $p$ is a ...
1
vote
1answer
21 views

Show that $f$ is convex if and only if $f\left( \sum_{i=1}^m\lambda_ix_i \right) \leq \sum_{i=1}^m\lambda_if(x_i)$

I need to prove the following statement Let $S \subset \mathbb{R}^n$ a nonempty convex set and $f: S \to \mathbb{R}$. Then $f$ is convex in $S$ if and only if $f\left( \sum_{i=1}^m\lambda_ix_i ...
1
vote
0answers
11 views

Can Extragradient method be expressed with proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method ...
0
votes
0answers
14 views

Proof of Convexity Using Quasiconvexity

Suppose $f_{1}, \ldots, f_{n}$ are continuously differentiable functions defined on $\mathbb{R}$ such that for each $i\in \{1,\ldots,n\}$, we have: (i) $f_{i}(v_{i}^{0})=0$ and ...
1
vote
2answers
22 views

Log-concave function changes when scalar is added

A function $f$ is log-concave if $\log(f)$ is concave. Intuitively, one might guess that adding a scalar to a function would not affect properties like concavity, log-concavity, quasi-concavity etc., ...
0
votes
0answers
42 views

Dual of a maximization problem

We have a positive, smooth, increasing concave function $f:\mathbf{R}^n\to \mathbf{R}^+$ and $k$ smooth, increasing constraint functions $f_i:\mathbf{R}^n\to\mathbf{R}$. I've recently encountered two ...
5
votes
0answers
42 views

When is a mapping the proximity operator of some convex function?

Sorry for cross-posting from MO. It's been a few days and the question hasn't received any attention there. So, is there a characterization of mappings $p : \mathbb R^n \rightarrow \mathbb R^n$ which ...
1
vote
1answer
36 views

Solution of a sublinear elliptic problem.

In a lecture notes, the author showed the problem $\tag{$P$}$ $\begin{cases} -\Delta u = |u|^{q-2}u \textrm{ in } \Omega, \\ u(x)= 0 \textrm{ in } \partial\Omega, \end{cases}$ where $\Omega ...
0
votes
0answers
35 views

Conditions for all positive $x$ solved by $\min \bf{x}^T\bf{x}$ $s.t. Ax=b$

I want to find a condition for having all nonnegative $x_i$ in $\min \bf{x}^T\bf{x}$ $s.t. \bf{Ax}=\bf{b}$ where $\bf{x}\in \mathbb{R}^{n\times 1}$, $\bf{A}\in \mathbb{R}^{m\times n}$, $\bf{b}\in ...
0
votes
1answer
17 views

Closure of intersection of convex sets

Let $C_i$ be a convex set in $R^n$ for $i\in I$, suppose sets $ri \, C_i$ have at least one point in common, then how to prove this: $cl\bigcap\{C_i\mid i\in I\} = \bigcap\{cl \, C_i \mid i\in I\}$
0
votes
0answers
15 views

Monotony and convexity of $U(t) = w(t) - t. w'(t)$

Let $\mathcal{D} = (\mathbb{R}^{+*})^2$. $c \in ]0,1[$. Moreover we have $\theta < 1$ and $\theta \ne 0$. We consider the following function (which is called CES or constant elasticity of ...
2
votes
1answer
25 views

Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
1
vote
1answer
288 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 ...
0
votes
1answer
22 views

Concavity condition for function of more than one variable

We know for single variable function $f(t)$, the necessary and sufficient condition for concavity is $$ f((1-\lambda)x+\lambda y) \ge (1-\lambda)f(x)-\lambda f(y) $$ for every $x$ and $y$ and $0 ...
1
vote
0answers
43 views

The subset of $\mathbb R$ with $x\geq 0$ is closed and convex

Let $C=\{x\in \mathbb R|x\geq 0\}$. Prove that $C$ is a closed convex subset of $\mathbb R$ and show that for $x_0 \in \mathbb R$, the closest element in $C$ to $x_0$ is $max\{x_0,0\}$. I have looked ...
1
vote
0answers
33 views

How to Compute or Find an Upper Bound for the Diameter of a Convex Set?

Let $\mathcal{R}$ be an $n$-dimensional bounded hyperrectangle, and consider a $n\times n$ matrix $A$ with real entries. Given set $\mathcal{R}$ and matrix $A$, I want to compute or find an ...
2
votes
2answers
28 views

How can I prove the concavity of $f(p_1,p_2,\ldots,p_n) = \sum_{i = 1}^n p_i(1-p_i)$?

Assume $p_n$ is the probability of being in class $n$ which mean that $f(0) = 0$ , $f(1) =0$ , and $p_1+p_2 = 1$ I need to come up with a concave function that show the relation between $p_1$ and ...
4
votes
3answers
147 views

Can a figure inside a circle be seen at right angle from any point on the circle?

A convex, closed figure lies inside a given circle. The figure is seen from every point of the circumference at a right angle (that is, the two rays drawn from the point and supporting the convex ...
0
votes
1answer
45 views

Is the set of probability density functions convex?

Given is the set of probability density functions defined as $P:=\left \{ p(x)\mid p(x)\, is\ a\ probability \ density \ function \right \}$ Is $P$ a convex set? I am not sure that here i have to ...
0
votes
0answers
5 views

An inequality involving expectation and a concave function

I have a real-valued random variable $X$ and a function defined on the real line $x \mapsto U(x)$ which is concave and strictly increasing. What I am wondering is whether the following is true. For ...
1
vote
1answer
39 views

How to get explicit solution of the fractional minimization problem?

I need to minimize $f(x) = \frac{x^tQx}{a^tx-b}$, $Q$ is positive definite, $a,b$ are constant vector. But when I take gradient and set it equal to $0$, it's hard to get an explicit expression for ...
0
votes
1answer
24 views

Minima of two convex functions that are “close” to each other

Consider two convex functions $f_1 : \mathbb{R}^n \to \mathbb{R}$ and $f_2 : \mathbb{R}^n \to \mathbb{R}$ such that $\hspace{2cm} |f_1(x) - f_2(x)| \leq \epsilon \hspace{2cm} \forall x \in ...
2
votes
1answer
23 views

Concave up theorem for $f:A \to\mathbb R, A \subseteq \mathbb R $ - True or false?

I am a 1st year-2nd semester student of the department of Applied Mathematics @ NTUA. Some days ago, I had a really interesting conversation with one of my old school mathematics teacher about a ...
1
vote
1answer
47 views

Is function $f(x) = \left( ( {\bf w} -x {\bf v})^T ( {\bf w} -x {\bf v}) \right)^k$ convex for $k \ge 1/2$

Let ${\bf v}$ and ${\bf w}$ be column vector of dimension $n$. Is function $f(x) = \left( ( {\bf w} -x {\bf v})^T ( {\bf w} -x {\bf v}) \right)^k$ convex for $k \ge 1/2$ ? I want to show this via ...
1
vote
1answer
14 views

Is $h(x,y) = g(x)f(y)$ convex, if $g(x)$ and $f(y)$ are convex in $x$ and $y$, respectively?

I want to check if $h(x,y) = g(x).f(y)$ is convex, given that g(x) is convex and decreasing in $x$ on its and $f(y)$ is increasing and convex in $y$. Is there any way to check/prove the convexity of ...
1
vote
0answers
37 views

Good text book recomendation

I would like to do some reading about a technique called sequential convex programming. There is a lot of material about sequential quadratic programming out there, including books (Nocedal & ...
14
votes
3answers
863 views

If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?

If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
0
votes
1answer
25 views

Alaoglu & Krein-Milman to show bounded convex weak-$*$ closed subset has extreme point

Let $X$ be a normed linear space and $K$ a bounded convex weak-$*$ closed subset of $X^{*}$. I need to show that $K$ possesses an extreme point; however, I am not entirely sure how to do this. I ...
0
votes
1answer
26 views

Are odd functions that are concave and increasing everywhere necessarily linear?

The title gives away pretty much the entire question except for the fact that the class of functions I am interested in is a subset of twice continuously differentiable functions. I think that if an ...
0
votes
0answers
22 views

What value of 'a' will be the function is convex, concave or not either?

$$f(x,y) = -6x^2 + (2a+4)xy - y^2 + 4ay$$ The solution has to be : $$-2-\text{gyök}(6) \leq a \leq -2 + \text{gyök}(6)$$ I tried to define the derivation of the function accordance with $x$ , and ...
1
vote
1answer
22 views

Property of Conical Hull

Let $H$ be a real Hilbert space and $C$ be a nonempty convex subset of $H$. The conical hull of $C$ is defined by $$ \operatorname{cone}{C} := \bigcup_{\lambda >0}{\lambda C}. $$ (it is a cone in ...
0
votes
1answer
102 views

Find a positive convex function $f$ defined on $[a,b]$, s.t. $f(a)\times f(b)=1$ and $\int_a^b{f'^2dt}=12$

Find a function $f:[a,b]\to \mathbb{R}$ which is convex on $[a,b]$ such that $\int_a^b{f(t)dt}=0$, $\int_a^b{f'^2(t)dt}=\frac{12}{b-a}$, and $f(a)f(b)=1$? Another similar question which states: Find ...
0
votes
1answer
15 views

Caratheodory's theorem for a point in boundary

I am wondering whether the following holds: if $x$ in $\mathbb{R}^d$ lies in the boundary of the convex hull of a set $P$, then $x$ can be expressed as a convex combination of $d$ points in $P$. We ...
2
votes
0answers
449 views

Convex hull of bounded set is bounded

I want to show that in a locally convex topological vector space $X$, the convex hull of a bounded set is bounded. Apparantly this does not hold if $X$ is not locally convex. So the fact that that ...
0
votes
0answers
31 views

How can show the following function is log-concave?

Suppose that $g(x)$ is an increasing function and $0\leq g(x)\leq1$. I was working on a problem and it reduced to show that if $1-g(x)$ is log-concave then $$f(x)=(1-g^a(x))^b, a\geq 1, b,x>0$$ is ...
6
votes
1answer
42 views

How to prove this inequality about the arc-lenght of convex functions?

Let be $f,F:[0,1] \to \mathbb{R}$ with $f,F \in C^2([0,1])$ two convex functions such that $f \le F$ in all points and $f(0)=F(0)$, $f(1)=F(1)$. Considering the plane-curves $\gamma(t)=(t,f(t))$ and ...
1
vote
0answers
36 views

maximum of a concave function in a minkowski sum

Let: $f(x,y)$ - a strictly-concave function, monotonically increasing in $x$ and $y$; $A,B$ - two compact and convex sets in the positive quadrant; $C$ - their Minkowski sum, $A+B$; $(x_A,y_A)$ - ...
0
votes
0answers
15 views

convex function on open interval

I have a quick question. If a continuous function $f$ is convex on $(a,b)$, then the following is true? Could you explain why or why not it is true? $for \,\,x\in(a,b)$, $t=\frac{x}{b}<1$ Thus, ...
2
votes
0answers
7 views

How to get inequality representation of cone give by generators

To be as specific as possible, I have a subspace $I \subset R^{14}$ of dimension $3$ and an $11\times14$ matrix $A$ with linearly independent rows spanning the orthogonal complement of $I$. I have an ...
0
votes
0answers
26 views

If $1^TR K Y diag(f) l=m$, how to upper bound $f^T l$

In the following $K$ is a kernel matrix, ( and so is positive semidefinite), $Y$,$R$ are diagonal matrices with elements $R_{ii}=+1$ or $R_{ii}=-1$, $Y_{ii}=+1$ or $Y_{ii}=-1$. $f$ is a diagonal ...
1
vote
0answers
16 views

Dual of a point which is in the convex cone of a set, contains the dual cone of that set

Let $\Lambda\subseteq R^n$ contains $m$ elements, where $\lambda_i$ is the $ith$ element, and $co(\Lambda)$ is the smallest convex cone contains $\Lambda$. Also, consider any point $u\in R^n$. Now, I ...
0
votes
0answers
15 views

Correctness of use induction in the proof

"Let $S$ be a subset of vector space $V$. Let $P_1, ... , P_n$ be elements of vector space $V$. Let $S$ be the set of all linear combinations $t_1 P_1 + ... t_n P_n$, with $0 \le t_i$ and $t_1 + ... ...
1
vote
0answers
35 views

Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}argmin_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}argmin_{t}\{t+5\mathbf{E}[Z-t]_{+}\}$$ I ...
1
vote
0answers
6 views

Closed-form solution for a simple system of concave equations

I am trying to solve what looks like a simple system of equations: $$x_j = A_j\left(\sum_{i=1}^n B_{ij} x_i\right)^\alpha $$ for all $j\in\{1,\dots,n\}$, where $n$ is a positive integer, ...
1
vote
2answers
104 views

Non-subdifferentiable convex function on a normed space

Is there any convex function $f$ on a normed space $X$ such that $\partial f(x)=\emptyset$ at every $x\in X$?