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
0answers
34 views

how to find the maximum area of a two rectangle under a parabola

Starting from a very basic concept, what is the largest triangle to be drawn under the function $f(x)$ as shown in the figure. Picking an arbitrary point on the x-axis $(x, 0)$ and its mirror $(-x, ...
1
vote
1answer
9 views

Separition arguments and support functions

Show that if $F,G \subseteq E$ are compact convex sets such that $\sigma_F=\sigma_G$ then $F=G$ (this requires a separation argument) where$$\sigma _F (x) := \max\{\langle x, u\rangle : u ∈ F\}.$$ ...
5
votes
1answer
37 views

How to show that $y^T x - \frac{1}{2}x^T Q x$ is bounded above?

Strictly convex quadric function. Consider $f(x)=\frac{1}{2}x^TQx$, With $Q\in S_{++}^n$. The function $y^T x - \frac{1}{2}x^T Q x$ is bounded above as a function of $x$ for all $y$. It attaints its ...
2
votes
1answer
19 views

When is a functional a convex combination of other functionals?

Suppose that $f, g_1,...,g_n$ are functionals defined on a normed vector space $E$ and that for each $x \in E$ we have that $f(x)$ is in the convex hull of $\{g_1(x),...,g_n(x)\}$. Does this imply ...
1
vote
1answer
19 views

Support function and convexity

Let $A, B, C$ be compact convex sets in $\Bbb R^n$ such that $A + C = B + C$. The purpose of this problem is to prove that $A = B$. Define the support function $$\sigma _A (x) := \max\{\langle x, ...
2
votes
1answer
46 views

boundedness of convex functions

Let $X$ be a vector space, $\Omega$ a convex subset thereof and $f:\Omega \to \mathbb R$ a convex function. Then $f$ need not be bounded from below - not even if it is strictly convex, as the example ...
0
votes
2answers
15 views

Show that the following is a convex set

I've been banging my head against the wall trying to handle these proofs for two hours now, it seems very simple but I guess I need a hand starting out. I hope I at least know what to show: Show that ...
1
vote
0answers
26 views

How to use Farkas' lemma?

How can I prove, that the set $$P = \{(x, y) \in \mathbb{R}^{n+m} : Ax + By \geq c, \: x \geq 0^n, \: y\geq 0^m \}, $$ where $B \in \mathbb{R}^{m \times m} \;$ is positive semidefinite matrix, $A ...
0
votes
1answer
18 views

Equivalent characterization of quasi-concavity [duplicate]

For $f: \mathbb R^n \to \mathbb R$ prove that the two statements are equal: For all $x,y \in \mathbb R^n$ and for all $t \in [0,1]$, $f(tx+(1−t)y)\geq \min (f(x),f(y))$ For all $k \in \mathbb R$, ...
0
votes
0answers
26 views

Chek the convexity of a set via affine functions

The set: $\{x| x^TPx \leq (c^Tx)^2, c^Tx \geq 0 \}$ where $P \in S^n_+$(SPD matrices) and $c\in R^n$, is convex, since it is the inverse image of the second-order cone, $\{ (z,t) | z^Tz \leq t^2, ...
3
votes
0answers
76 views

Permutation and Combinatorics Problem

A function $G$ is defined on a set $S$ with size $k$ : $G(a_1,a_2,a_3,\ldots,a_k)$. $G(a_1,a_2,a_3,\ldots,a_k) = 1$ if and only if a convex polygon can be created by taking these $k$ elements as the ...
0
votes
0answers
20 views

Differentiability of convex functions except at countably many points

There is this result in Notions of Convexity, Hormander. The relevant part of it reads: let $f$ be convex in an interval $I$ and $x$ be an interior point. Let $f_l'$ and $f_r'$ denote left derivative ...
2
votes
1answer
31 views

Convex function?

I have a positive function $f(x,y)$, where $x\in{\mathbb R}^n$ and $y\in{\mathbb R}$. I know that for $y$ fixed, $g(x)=f(x,y)$ is convex, and that for $x$ fixed, $h(y)=f(x,y)$ has positive second ...
11
votes
3answers
4k views

Midpoint-Convex and Continuous Implies Convex

Given that $$f\left(\frac{x+y}{2}\right)\leqslant \frac{f(x)+f(y)}{2}~,$$ how can I show that $f$ is convex. Thanks. Edit: I'm sorry for all the confusion. $f$ is assumed to be continuous on an ...
0
votes
1answer
25 views

What would be a description of this set in $\mathbb R^3$?

Suppose that $K=\{(x,y,z)\in \mathbb R^3|x\geq 0,y\geq 0, xy\geq z^2\}$. Let $K_0=\{x\in\mathbb R^3|\langle x,k\rangle\leq 0\forall k\in K\}$. What would be a description of the set $K_0$? I don't ...
1
vote
1answer
31 views

If $y\in C$ then $||x-y||>||y-z||$.

I'm trying to prove the Separating Hyperplane Theorem. Let $C\subset \mathbb{R}^n$ be a closed and convex set, and $x\not \in C$. Then there exists $d\in \mathbb{R}^n$ and $\delta\in \mathbb{R}$ ...
2
votes
1answer
87 views

Proof involving Ramsey numbers

$S$ is a set of R(m,m;3) points in the plane in which no 3 points are collinear. I am trying to prove that $S$ contains $m$ points that form a convex $m$-gon. I have tried using similar logic to the ...
1
vote
1answer
50 views

Write a function as sum of convex and concave functions

I'm trying to tackle a question for some time. The question is: Let $f\in\mathcal{C}^2$ (i.e, $f$ is differentiable twice and $f',f''$ are continuous. Show that $f$ can be written as ...
2
votes
1answer
117 views

How to prove that $f$ is convex function if $f(\frac{x+y}2)\leq \frac12f(x) + \frac12f(y)$ and $f$ is continuous? [duplicate]

Let $f:(a,b) \mapsto \mathbb{R}$ be continuous function such that $f(\frac{x+y}{2})\leq \frac{1}{2}f(x) + \frac{1}{2}f(y) \;\; \forall x,y \in (a,b)$ Show that $f$ is convex function. Please give ...
0
votes
1answer
29 views

Supremum over ellipsoid set

In Boyd's Convex Optimization Textbook, page 157, it is stated: $ \mathrm{sup}\{a_i^T x\; |\; a_i\in\mathcal{E}_i \} = \bar a_i^T x + \mathrm{sup}\{u^T P_i^T x\; |\; \lVert u \rVert_2 \leq 1 \} = ...
5
votes
2answers
59 views

Is $f(x) = x^T A x$ a convex function?

Is $f(x) = x^T A x$ a convex function, where $x \in \mathbb{R}^n$, and $A$ is a $ n\times n$ matrix? If not, my question can be reformed to: when is $f(x)$ convex, any restriction for $A$? For ...
1
vote
1answer
21 views

the boundary normal vectors

Suppose $X, Y$ are convex compact sets in $\mathbb R^n$ and $z \in \mathbb R^n$. Would it be the case that $$\max_{x\in X} [ \langle x, z \rangle-\max_{y\in Y} \langle x ,y \rangle ]=\max_{x\in ...
2
votes
1answer
17 views

Concave functions

Given $(X,\mathcal{F},m)$ a measure space with $m(X)=1$ and $||f||_p<\infty$ for some $p>0$. Need to show that $\forall q \in (0,p)$ $$\int \log |f| dm\leq \log(||f||_q),$$ $$ \log ||f||_q ...
0
votes
1answer
97 views

How to compute the hessian of the log barrier function

According to note, the log barrier function is given by (page 10): $f(x) = - \sum\limits_{i = 1}^m \log(b_i - a_i^Tx)$ where $b_i$ is a scalar, $a_i, x$ are $n$ dimensional vectors I have ...
0
votes
0answers
54 views

A maximal monotone operator (and not a subdifferential) with a non-convex domain

I am looking for a maximal monotone operator $T:X\to 2^{X^*}$ that has a non-convex domain $D(T)=\{x\in X\mid T(x)\neq\emptyset\}$ and $T$ is not cyclically monotone, that is, $T$ is not a convex ...
0
votes
5answers
75 views

Is $S = \{(x,y) : y = e^x\}$ is convex or not?

If $S = \{(x,y) : y = e^x\}$ was convex, the following relation holds \begin{align} &t y_1 + (1-t) y_2 = e^{t x_1 + (1-t) x_2} \tag{1}\\[2mm] \Longleftrightarrow \quad & t e^{x_1} + (1-t) ...
3
votes
0answers
295 views

mid-point convex but not a.e. equal to a convex function

I recently stumbled upon Wikipedia's page on convexity (http://en.wikipedia.org/wiki/Convex_function#Properties) and there's reference to Sierpinski's theorem from which we can deduce that for ...
18
votes
3answers
1k views

Example of a function such that $\varphi\left(\frac{x+y}{2}\right)\leq \frac{\varphi(x)+\varphi(y)}{2}$ but $\varphi$ is not convex

Rudin's Real and Complex Analysis Chapter 3 Exercise 4 is: Assume that $\varphi$ is a continuous real function on $(a,b)$ s.t. $$\varphi\left(\frac{x+y}{2}\right)\leq ...
4
votes
1answer
179 views

Example of function satisfying for fixed $t\in (0,1)$ inequality $f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)$

I would like to know an example of function $f: \mathbb{R} \rightarrow \mathbb{R}$ which is not convex but satisfies for fixed $t\in (0,1)$ the following inequality: $$f(tx+(1-t)y) \leq t ...
0
votes
1answer
20 views

A problem about $-\max$ and $\min$

Suppose $X$ and $Y$ are convex compact subsets in $\mathbb R^n$. Let $\langle.,.\rangle$ be the standard inner product. Does the following equality $$\max_{y\in Y} [\langle y, z\rangle- \max_{x\in ...
4
votes
1answer
262 views

Mid-point convexity does not imply convexity [duplicate]

A function $f: X \rightarrow \mathbb{R}$ is said to be mid-point convex if for all $x, y \in X$, we have $$f(\frac{x + y}{2}) \leq \frac{f(x) + f(y)}{2}. $$ Can you please give an example of a ...
1
vote
1answer
36 views

Characterization of a projection operator in $\mathbb R^n$

Let $X$ be a closed convex set in $\mathbb R^n$ and $y\in \mathbb R^n$. Suppose a projection $T_X: \mathbb R^n \to \mathbb R^n$ satisfies $$T_X( \alpha y+ (1-\alpha) T_X(y))=T_X(y)$$ for all ...
1
vote
0answers
16 views

Tangential surface of an extreme point of a convex subset of a simplex

Suppose that there is a convex set (polyhedra) $H$ which is a convex subset of a simplex $G = \{x\in R^d ~|~ \sum_{i=1}^d x_i=1, x_i \ge 0, i=1,2, ..., d \}$. Clearly, $H$ has extremal points $x^*$ ...
0
votes
1answer
125 views

Given the sides of a polygon, determine if it is convex or concave

We are given the lengths of all sides of a polygon. We need to determine if the given polygon is convex or concave. How can this be done? What is the propery applied to determine this?
1
vote
2answers
70 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 ...
0
votes
1answer
30 views

Implicit function for a convex gradient.

Let $Q \colon \mathbb{R}^n \to \mathbb{R}$ denote a convex function with $g(x) = \nabla Q(x)$ well-defined. I am interested in defining the following variables \begin{eqnarray} c & = & x - ...
4
votes
3answers
253 views

Maximizing a ratio of convex matrix functions by minimizing a difference?

Given that $g(.),h(.)$ are twice-differentiable convex quadratic real functions whose domain is the set of all real matrices while the range is the set of positive real numbers, then: Is maximizing ...
0
votes
2answers
15 views

Hessian at a non-stationary point

I have a function $G(Q) : \mathbb{R}^n \rightarrow \mathbb{R}$ that is known to be convex. I also know that $Q^*$ is a minimum of $G(D)$. If I apply Taylor's theorem to $G(Q)$ at $Q^*$, I get: $$ ...
0
votes
2answers
77 views

Prove $\frac{1}{2} \|y-x\|^2$ is a strongly convex function

Get stuck in proving $f(y)=\frac{1}{2} {||y-x||}^2$ is strongly convex function (Assume $x$ is fixed). My Proof: $y_1$, $y_2$ are two variables. \begin{align} & f(\lambda y_1+(1-\lambda) ...
-2
votes
2answers
27 views

differentiable functions, concave or convex?

Suppose U and g are two twice differentiable functions of x, both of them increasing and concave, with U’ ≥ 0, U” ≤ 0, g’ ≥ 0, and g” ≤ 0. Prove that the composite function f(x) = g(U(x)) is also ...
0
votes
0answers
7 views

conditions on a pdf such that a ratio is unimodal

Consider a pdf $f(\cdot)$ of a positive continous random variable with support $[0,1]$. And let $G(\theta) = \frac{\int_0^{\theta} x f(x)dx}{\theta}$. What conditions can be found for $f(\cdot)$ ...
0
votes
2answers
55 views

What is the mathematical notation for Convex Hull?

I've been scanning through scientific papers, this site and just googling for it, but I can't find a commonly accepted notation for the convex hull. So my question is; if there is, what is the ...
2
votes
1answer
45 views

How to show that $f(x) = \frac{\sqrt{\cos x}}{1-x^2}$ is convex and has a minimum value

I want to show that $f(x) = \frac{\sqrt{\cos x}}{1-x^2}$ is convex on the interval $]-1,1[$. How do I have to proceed? I did take the derivative of the function which is $f'(x) = \frac{2x\sqrt{\cos ...
0
votes
1answer
52 views

Convex function and local extrema problem

Let $f$ be twice differentiable and strictly convex on $[a,b]$. Assume also that at a point $x_0 \in (a,b)$ the derivative $f'(x_0) = 0$. Show that $x_0$ must be a strict local minimum. I find that ...
-1
votes
2answers
58 views

Prove that if $f(x)$ is convex and nonnegative, then $g(x)=(f(x))^2$ is convex too

Let $$f: \mathbb{R}^d \longrightarrow \mathbb{R}\\ g: \mathbb{R}^d \longrightarrow \mathbb{R}$$ such that $$f(x)\geq 0 \quad \forall x \in \mathbb{R}^d.$$ Prove that if $f(x)$ is convex, then ...
0
votes
1answer
31 views

Hypograph of a quasiconcave function

If $f$ is a quasiconcave function, is its hypograph necessarily a convex set? My intuition says yes, but somehow I feel that this is not true, does anybody has a conterexample if the statement is not ...
1
vote
2answers
37 views

Prove a linear combination of a convex set is convex

Suppose $S$ is a convex subset of $\mathbb R^n$ , and suppose $T: \mathbb R^n \rightarrow \mathbb R^m $ is any linear transformation. Prove that the set $\,\{T(x)\,|\,x \in S \}$ is also convex. ...
1
vote
0answers
24 views

Differentiable iff unique subgradient

Let $f:\mathbb{R}^n\to\mathbb{R}\cup \{ \infty \}$ be convex, $D:=Dom(f)$, $x\in D^o$. Then f is differentiable at x iff $\partial f(x)=\{ d \}$ (a singleton), in which case $\nabla f(x)=d$. ...
0
votes
0answers
30 views

Show that $f$(sum of log terms) is convex with Jensen's inequality..

We have the equation \begin{equation} f(\mathbf{x})=\mathbf{c}^T\mathbf{x}-\sum_{i=1}^m\log{(b_i-\mathbf{a}_i^T\mathbf{x})} ,\;\;\; \mathbf{x} \in \mathbb{R}^n \text{ and } m>n \end{equation} ...
0
votes
0answers
11 views

Determining Euler-Lagrange equations for a nonsmooth functional

Is there any good resource for understanding how to derive the EL equations for non-smooth problems? In particular, I would like to get them for: $\mathcal{J}(u,v)=\iint_{\Omega} \sqrt{u_x^2 + u_y^2 ...