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)

1
vote
0answers
13 views

Looking for an entry level discussion on convex analysis

I have been studying for a qualifier and every so often I come across questions such as: Let $f_n:[a,b] \to \mathbb{R}$ be convex functions and suppose that $f(x) = \lim_{n \to \infty} f_n(x)$ exists ...
0
votes
1answer
55 views

Can we say a convex cone is a closed set without further proof?

There are some related problems: 1. dual cone is closed 2. Why is any subspace a convex cone? Consider a cone $\mathcal{C}(A)$: $$\mathcal{C}(A) = \{Ax: x\geq 0\}$$ This is a cone generated ...
0
votes
0answers
15 views

Proof of the Line Segment Principle for Convex Sets

I'm self studying a chapter on convex sets in preparation for a course on optimisation for economists however I'm having trouble understanding the proof of the line segment principle. I would ...
1
vote
1answer
44 views

Show that exactly one of the following two systems has a solution.

Let A be a $m \times n$ matrix, $\mathbf{c}$ an $n$-dimensional ector and $\mathbf{b} \ge \mathbf{0}$ an $m$-dimensional vector. Show that exactly one of the following two systems has a solution: $\...
0
votes
2answers
69 views

Support function of an ellipse

I defined the support function $h_A:R^n→R$ of a non-empty closed convex set $A\subseteq \mathbb{R}^n$ as $$h_A(x)= \sup\left\{x⋅a |\ a \in A\right\}$$ Everything I know about this topic I found it. I ...
1
vote
2answers
98 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where $D(\alpha)=\frac{...
1
vote
1answer
32 views

Convexity and Proof of one sided Derivative

Working on some real analysis work, I've been able to show that for a function $f$, which is convex on $[a,b]$, for $a\leq x_1< x_2< x_3\leq b$: $$\frac{f(x_2)-f(x_1)}{x_2-x_1} \leq \frac{f(x_3)...
0
votes
2answers
17 views

Dual cone and sum of closed cones

Picture below is from the 35 page of Schneider R.-Convex Bodies_ The Brunn-Minkowski Theory-Cambridge University Press (2013) , I think $C^o$ is always closed no matter $C$ is closed or not. Because ...
3
votes
0answers
63 views

Convexity in oriented matroid theory: proof on closure operator?

I would like to try to solve the following problems. Problem from the Oriented Matroids book by Bjorner, Las Vergnas, Sturmfels, White, and Ziegler. It is problem 3.9 on page 152. Attempt ...
0
votes
1answer
38 views

Minimal Ellipsoid in $R^{2}$; why is it the Ellipsoid 2 in the figure?

It is stated in the book Convex Optimization, Boyd in page 47 that the ellipsoid 2 is the minimal because no other ellipsoid (centered at the origin) contains the point (top point) and is contained in ...
1
vote
1answer
21 views

Is it possible to move vertices of a regular polygon to shape a given convex polygon?

can vertices of a regular polygon (n-gon) in the plane be moved (slide) one at a time to form a given convex polygon so that the polygons in between remain convex?
0
votes
1answer
36 views

convex conjugate

$X$ is a Banach space and $X^{*}$ denotes its dual. Let $f:X\rightarrow\mathbb{R}$ be an arbitrary convex function. The Fenchel conjugate of $f$ is the function $f^{*}:X^{*}\rightarrow\mathbb{R}$, ...
0
votes
1answer
50 views

$f:\mathbf{R}^n \to \mathbf{R}$'s derivative in each argument has the same sign everywhere. What is $f$'s shape?

We have a differentiable $f:\mathbf{R}^n \to \mathbf{R}$ with the property that each partial derivative has the same sign everywhere in its domain. Does this mean that the sublevel sets of $f$ (sets ...
0
votes
0answers
8 views

A question of the proof of the duality mapping for convex bodies.

In picture below ,why the set $A$ is convex ? Below picture is from the A characterization of the duality mapping for convex bodies ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
0
votes
0answers
6 views

A question of the duality mapping for convex bodies

In picture below ,why the define of $\varphi$ is independent of the choice of sequence $(K_i)_{i\in N}$ ? Below picture is from the A characterization of the duality mapping for convex bodies ~~~...
5
votes
1answer
156 views

Chebyshev sets in finite dimension are closed and convex

Prove a finite-dimensional converse to the “best approximation theorem”: Let $K$ be a subset of a finite-dimensional Hilbert space $H$ which satisfies the following property: for each $x \in H$ there ...
0
votes
1answer
17 views

discrete convexity arising in a simple discrete optimization problem

Let $S$ be a fixed integer satisfying $S \ge 1$, let $a$ range over the integers between $1$ and $S$ inclusive, and for $i = 1, \dotsc, a$, let each $x_i$ range over the nonnegative integers, such ...
1
vote
1answer
45 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 ...
1
vote
1answer
33 views

How to Calculate the normal cone of a covex set at a point?

Let $C$ be a convex set of $\mathbb{R}^d$ and $\overline{x}\in C$ we define the normal cone of $C$ at $\overline{x}$ by \begin{equation} N_C(\overline{x}) = \{ y \in \mathbb{R}^d \ <y ,c-\...
0
votes
1answer
39 views

Proving an inequality involving a strictly convex function

Given, $f$ is a strictly convex function. Based on what assumptions on '$x$' and '$y$', can I say that the following inequality stands true : $$f(x) \; + f(y) \; > \; f(x + y) \; \; ?$$
12
votes
2answers
203 views

Is $\frac{1}{2}\|x\|^2$ the only function that is equal to its convex conjugate?

Is $\frac{1}{2}\|x\|^2$ the only function that is equal to its convex conjugate? The convex conjugate is defined as $$ f^{*}(x) = \sup_y\{\langle x, y\rangle - f(y)\}. $$
0
votes
1answer
58 views

A term for a function $f$ such that $x f'(x)$ is decreasing

Consider a differentiable, monotonically increasing function $f$. If $f'(x)$ is increasing, then $f$ is convex. If $f'(x)$ is decreasing, then $f$ is concave. Is there a term that describes $f$ when ...
0
votes
1answer
23 views

Set of marginals is convex [closed]

Let $[n] = \{1,2,\cdot,n\}$ and $[m] = \{1,2,\cdot,m\}$. Let $Z_{1,2}$ denote the set of all probability distribution on the Cartesian product $[m]\times [n]$. Let $S_{1,2}$ denote a convex closed ...
0
votes
1answer
33 views

The standard n-simplex is compact set

$ " Let \ K\subseteq \mathbb R^n \ be \ a \ compact \ set,\ then\ the\ convex \ hull \ of\ K\ is\ also\ compact \ set\ " $ In order to prove this we use that the standard n-simpex as defined ...
0
votes
1answer
16 views

Shape of polar set

Let $K$ be a subset of $R^n$, which contains the origin $\theta$ , maybe , it is needed that it is not very strange . The polar set of $K$ is $$ K^0=\{x\in R^n : \langle x,y \rangle \le 1 ~~~\forall ...
1
vote
1answer
31 views

Convexity of a set generated by $A^TA$

Problem: Let $X_k = \lbrace A^T A \mid \operatorname{rank} A \ge k, A \textrm{ is an $n \times n$ matrix} \rbrace $. Show that $X_k$ is convex. I know from the classes that $\operatorname{rank} ...
0
votes
1answer
30 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
21 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$? ...
2
votes
1answer
1k 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 \mathbb{R}^{m\...
1
vote
1answer
41 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
22 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
25 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
2answers
24 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., ...
5
votes
0answers
53 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
41 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
36 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
20 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
16 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
29 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
295 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
32 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
37 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
30 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
150 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
47 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
8 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 $x$....
0
votes
1answer
27 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 \mathbb{R}^...
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
120 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 ...