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 (1)

0
votes
1answer
16 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
0
votes
0answers
17 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
1
vote
1answer
36 views

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
2
votes
0answers
20 views

Convex interpolation between two points with given derivatives

Let's say I have two real values $x_1$ and $x_2$, to each of which I associate $y_i$ and $y'_i$ satisfying $$ (y_2-y_1)(y'_2 - y'_1) \geq 0. \tag{1} $$ I would like to find a polynomial ...
0
votes
0answers
15 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
12 views

What is the nature of this one dimensional function?

Let $\mathcal{S}$ be a 2-D convex set whose elements can be represented as $(x,y)\in\mathcal{S}$. Let $p_L$ and $p_U$ be two real constants such that $p_L\leq p_U$. For $p\in[p_L,p_U]$, I define the ...
1
vote
1answer
27 views

Convex Combination of 3 point in R2 and Triangle

I am new to convex combination, and I am quite amazed by some easy result. I know that convex combination of 2 points($P_1P_2$) in $R^2$ is all points in the line segment $P_1P_2$. And then I see a ...
0
votes
1answer
32 views

Interesting and intuitive affirmation involving convex sets

Let $\Omega_1$ and $\Omega_2$ two open, bounded and convex domains in $R^n$ with $\Omega_1 \supset \overline{\Omega_2}$ and $0 \in \Omega_2.$ Suppose that for each $x_0 \in \partial (\Omega_1 ...
0
votes
1answer
30 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all ...
1
vote
0answers
37 views

Dual norm of the matrix L1 norm is infinity norm (and vice versa)

Recall that for a given norm $\|\cdot\|$ on $\mathbb{R}^n$, the dual norm is defined as a function $\|\cdot\|_*: \mathbb{R}^n \rightarrow \mathbb{R}$ with: $\|y\|_* = \max \limits_x \{x^Ty: \|x\|\le1 ...
1
vote
2answers
25 views

Suitable composition of concave and convex functions is convex?

Let $f:[0,1]\to[0,1]$ be a strictly increasing continuous concave function with $f(0)=0$ and $f(1)=1$. Let $g$ be the inverse of $f$. Then $g$ is strictly increasing and convex. It seems that the ...
0
votes
2answers
31 views

Basic question about tangent cone

The following is from Prof. Jahn's book " Intro. to the theory of nonlinear optimization" about tangent cone: After definition, he gave an example: My question is: Does the tangent cone include ...
5
votes
1answer
80 views

Continuous linear image of closed, bounded, and convex set of a Hilbert Space is compact

Is my proof of this proposition correct ? And is this proposition well known? Proposition: Let $C$ be a closed, bounded, and convex set in a separable Hilbert space $H$. Let $L : H \to \mathbb{R}^n$ ...
1
vote
1answer
21 views

Convolution of Strictly Convex Function

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be a $C^2$, strictly convex function, and $\theta_\epsilon$ the standard approximation to identity ...
0
votes
0answers
29 views

No element in the convex hull of other elements [closed]

Consider a set $A$. If there is no element $a_i \in A$ lies in the convex hull of the other elements $\text{conv}(A\backslash \{a_i\})$.... Could anyone give me an simple example for this ...
2
votes
2answers
38 views

Is the distance between disjoint closed convex subsets of a Hilbert space positive? Is it attained?

Let $H$ be an infinite dimensional and separable Hilbert space. Let $A,B$ be infinite, closed and convex subsets of $H$. If $A$ and $B$ are disjoint and if at least one of them is bounded, is the ...
0
votes
1answer
26 views

Subtracting a constant from log-concave function preserves log-concavity, if the difference is positive

I am trying to work out a question from 'Convex Optimization - Boyd' . Specifically, exercise 3.48: Show that if $f : \mathbb R^n \to \mathbb R$ is log-concave and $a > 0$, then the function $g ...
2
votes
1answer
35 views

Affine to linear like conversion of a concave function

Is the following true: $$\log \left( \frac{1}{f(x)+K}\right)\mathrm{is\;concave}\Longleftrightarrow \log \left( \frac{1}{f(x)}\right)\mathrm{is\;concave},$$ where $K\in\mathbb{R} $ and ...
0
votes
1answer
19 views

Do full-rank linear transformations preserve strong convexity?

Consider a strongly convex function $g$, that is, for all $x,y$ in the domain and $t\in[0,1]$ we have $$ g(t x + (1-t)y) \le tg(x)+(1-t)g(y) - \frac{1}{2}mt(1-t)||x-y||_2^2 $$ for some $m>0$. Also, ...
6
votes
3answers
234 views

Dual norm intuition

The dual of a norm $\|\cdot \|$ is defined as: $$\|z\|_* = \sup \{ z^Tx \text{ } | \text{ } \|x\| \le 1\}$$ Could anybody give me an intuition of this concept? I know the definition, I am using it ...
0
votes
0answers
18 views

Convex Inequality describing Functions inside specific area

Let us assume that we have two functions $f_1$, $f_2:[0,1] \rightarrow \mathbb{R}^{2}$, which describe each a point trajectory on the plane. Let us further assume that we parametrize those functions ...
0
votes
0answers
19 views

Intuitive affirmation on convex sets

Let $D_1, D_2$ two open, bounded and convex domain in $R^n$. Suppose that $D_2 \supset \overline{D_1}$, and the boundaries of these sets are of class $C^1$. Fix $x \in \partial D_1$ and suppose that ...
1
vote
1answer
40 views

Prove that $f(x) > g(x)$ where both functions are convex and have the same value and slope at $0$

Let $f: [-a,a] \to \mathbb{R}$ and $g: [-a,a] \to \mathbb{R}$ be two non-negative, convex and smooth functions. We further know $f(0) = g(0)=0$ and $f'(0) = g'(0)=0$. I'd like to show $$f(x) \ge ...
0
votes
0answers
27 views

Proving concavity for complicated function

I have a rather complicated function, $f$, that I am trying to demonstrate is log-log-concave, i.e., $$\frac{d^2\log f}{(d\log x)^2}\leq 0.$$ The reason I think it is concave is purely heuristic. ...
0
votes
1answer
22 views

Is strict convexity necessary and sufficient for non-degeneracy of the Hessian?

A function $f$ is called strictly convex if for $\lambda\in(0,1)$, $x\neq y,$ $$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda)f(y)$$ If $f:\mathbb{R}^n\to\mathbb{R}$ is a twice ...
0
votes
1answer
10 views

How to derive the support function for this set?

I want to ask how to derive the support function of the convex set (in $\mathbb{R}^2$) that is described as the intersection of $x_1\leq \frac{3}{4}$, $x_2\leq \frac{3}{4}$, $x_1+x_2\leq 1$, and ...
2
votes
1answer
61 views

Point-wise converging convex functions on $[0,1]$

Suppose we have a sequence of continuous convex functions $\{f_n\}$ defined on $[0,1]$ which converge point-wise to a limit $f$ on $[0,1]$, i.e. for all $x \in [0,1]$ $$\lim_n f_n(x) = f(x).$$ Let $G ...
3
votes
1answer
38 views

Generalization of log-convexity (log-concavity): log-log-convexity (log-log-concavity)?

$\underline{\mathrm{Background\; on\; function\; Convexity}}$ A function, $f$, is convex if: $$f( x\theta+y(1-\theta) ) \leq \theta f(x) + (1-\theta)f(y).$$ $f$ is concave if $-f$ is convex, [1]. If ...
1
vote
1answer
25 views

Difference quotients are increasing for $f$ convex

Problem 11A.9(c) in Spivak's Calculus (4th edition) asks the following (I'm paraphrasing): Suppose $f$ is convex. Show that $f'(a)$ exists iff $f_+'(x)$ is continuous at $a$. ($f_+'(x)$ is the ...
1
vote
1answer
32 views

On a Banach space $X$, is the functional $x \mapsto \frac{1}{p}\|x\|^p$ convex?

Let $X$ be a Banach space. Let $p > 1$ and, consider the functional $X \to \mathbb{C}$ given by: $$x \mapsto \frac{1}{p}\|x\|^p$$ I would like the know if the above functional is convex. That ...
1
vote
1answer
36 views

Prove that a Hilbert space is convex of power type $2$

Let $X$ be a Banach space. For $\epsilon \in (0,2]$, define: $$\delta_X(\epsilon) = \inf_{x,y \in X}\{1 - \|\frac{1}{2}(x + y)\| : \|x\| = \|y\| = 1, \|x-y\| \ge \epsilon\}.$$ Then we say that $X$ ...
1
vote
1answer
48 views

On Stochastic Matrices

Let "stochastic" matrix be the matrix whose rows sum to one and deterministic matrix be a stochastic matrix whose all rows consist of a one and zero. For example $\left [ \begin{array}{ccc} 1 & ...
1
vote
0answers
33 views

A proof for Jensen’s inequality

I’m trying to prove a version of Jensen’s inequality, but I end up with the wrong result. I’d appreciate any help or comments. The theorem states: let $\varphi :{{R}^{k}}\to R$ be convex. Then for ...
1
vote
0answers
16 views

How to convexify (relax) this L0 eigenvalue optimization problem?

Let $C_1,\dots,C_L$ be $N\times N$ hermitian matrices. Let $d<0$ be a given negative constant. Then consider the optimization problem \begin{align} \max_{r\in \mathcal{R}^{L\times 1}} &\mid\mid ...
0
votes
0answers
42 views

Strictly Convex Functions

I am trying to show the equivalence of two definitions of strictly convex functions. Let $f:\mathbb{R}^n\to \mathbb{R}$ be a smooth function. The function $f$ is strictly convex if for each ...
2
votes
1answer
44 views

Are strictly convex functions with positive second derivatives on compact domains strongly convex?

Claim: Let $\chi$ be a compact set. If $f''(x)>0$ for all $x\in\chi$, then $f$ is strongly convex. This seems to be true, intuitively, as I can't think of a counterexample. All of the examples ...
1
vote
1answer
103 views

Knuth's Sandwich Theorem: requesting proof clarification

The question is about F6 of Section 8 ("Elementary facts about cones") in Donald Knuth's Sandwich Theorem (http://arxiv.org/pdf/math/9312214.pdf). He claims to prove $(A \cap B)^* = A^* + B^*$ when ...
4
votes
3answers
102 views

Is every such function convex or concave?

I was pondering convex functions today, and the following questions naturally posed themselves. Call a function $f : \mathbb{R} \rightarrow \mathbb{R}$ $2$-limited iff for all $m,c \in \mathbb{R},$ ...
0
votes
2answers
32 views

Convexity of functions

I'm trying to read up on convex/concave functions (is that the same as concave up, concave down?) If I were asked to prove a convexity of a function, what are the general steps to follow? (So far I ...
17
votes
2answers
306 views

Convex surface on which any two points $a,b$ can be joined by a curve of length $(\pi/2-\epsilon)|a-b|$

I am trying to solve an exercise on page 13 of the book Metric structures on Riemannian and non-Riemannian spaces by Gromov. Construct a closed, convex surface $X$ in $\mathbb R^3$ such that any ...
0
votes
1answer
12 views

Quasi-Concavity and Quasi-Convexity

My book states that: $f$ is a quasiconcave function on $U$ if for all $x,y \in U $ and $t \in [0,1]$: $f(x) \geq f(y) \implies f(tx + (1 - t)y) \geq f(y)$ $f$ is a quasiconvex function on $U$ ...
0
votes
1answer
38 views

Two Strictly Convex Functions with Contact of Order 1

Let $f,g: \mathbb{R}\rightarrow \mathbb{R}$ be two strictly convex functions, where $f$ is differentiable, $g$ is smooth, and $f\geq g$. Suppose that for some $x_0\in \mathbb{R}$: ...
1
vote
1answer
17 views

Differentiable Strictly Convex Function on Interval

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be a differentiable, strictly convex function. Let $I\subset \mathbb{R}$ be a closed, bounded interval such that $f'(x) \neq 0$ on $I$. Is $f$ strongly ...
0
votes
1answer
30 views

Strictly Convex and Differentiable Implies

Let $f:\mathbb{R} \rightarrow \mathbb{R}$ be strictly convex and differentiable. Is $f$ strongly convex when restricted to a closed and bounded interval $[a,b]$? This is true if $f$ is smooth but am ...
0
votes
1answer
99 views

Gradient descent (with line search) for convex functions viewed as alternation

I have fundamental confusion about gradient descent (with line search) and the reason it works. I try to explain my view here, and please tell me where it goes wrong. Let $f: \mathbb{R}^n \to ...
0
votes
0answers
19 views

convex set but not convex cone

Let S be a subset of R^n. If we say S is convex cone, it means S is convex and it is a cone. Obviously, a convex set contains convex cone. So can we take an example to say that it is a convex set ...
0
votes
0answers
17 views

separating hyperplane theorem proof

I need help understanding the last part of this proof, the lemma they are refering too is just a lemma about convex sets that shows us that p is unique: I do not see how H* separates C and z. The ...
0
votes
1answer
55 views

$F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
0
votes
2answers
32 views

Prove that the set $C = \{x \in\Bbb R : ax\le b\}$ is convex

Prove that if a and b are real numbers, then the set $C = \{x \in\Bbb R : ax\le b\}$ is a convex set. My solution so far: To show that a set $C$ is convex it needs to be shown that for for every ...
-4
votes
0answers
35 views

Prove $T(e) = \int_{e}^{\infty} (y-e) \mathrm{d}F(y)$ is convex

Prove that $T(e) = \int_{e}^{\infty} (y-e) \mathrm{d}F(y)$ is a convex function, where $F(y)$ is cumulative distribution function of some real random variable $Y$. This is an exercise from ...