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

something about convex set

Let $M$ be a convex subset in $\mathbb R^n$ and $\partial M=\emptyset$. Then $M=\emptyset$ or $\mathbb R^n$. This can be deduced by Theorem Let $M\subset X$ with $\partial M=\emptyset$ and $X$ is ...
0
votes
1answer
13 views

Establishing convexity of a function

Let $\theta \in \Theta \subset \mathbb{R}^k$. I have the following objective function $$ F(\theta):=||\max(0,f_1(\theta)),...,\max(0,f_n(\theta))||^2 $$ where $||\cdot||$ is the Euclidean Norm and ...
1
vote
0answers
12 views

Proving that $0 \in A \implies h_A = j_{A^\circ}$

Where $h_A$ is the support function of $A$ and $j_{A^\circ}$ the Minkowski functional of the polar set of $A$ There is a "proof" in my course which I don't understand: " Let $x \in A$ and $t>0$ ...
0
votes
0answers
9 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
2
votes
1answer
33 views

Existence of global minimum

Could someone help me with this problem? Let $C$, $D$ convex and closed sets such that the intersection is empty. I want to show that the function $f: \mathbb{R^n} \to \mathbb{R}$ defined by $f(x) = ...
4
votes
1answer
34 views

Is the set of convex bodies include in a closed ball compact?

I consider the set $\mathcal{K}_B$ of convex bodies (convex and compact) which are include inside the unit closed ball of $\mathbb{R}^d$. I endow this set with the Hausdorff distance. Is it compact?
0
votes
3answers
47 views

A convex function has a lower bound?

Suppose that $f=f(x)$ is strictly convex for $x\in\mathbb{R}$, i.e. there exists $\epsilon>0$ such that $f''(x)\geq\epsilon>0$ for $x\in\mathbb{R}$. Does there exist $\delta>0$ such that ...
0
votes
1answer
38 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
2
votes
0answers
22 views

Mid-point convexity does not imply convexity

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 function ...
1
vote
1answer
20 views

Is a constrained optimization problem equalivant to its Lagrangian form?

For the following problem: $\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$ Is the above problem equalivant to the following problem? $\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$ where $t$ and ...
0
votes
1answer
42 views

What's the solution for $\max_{x\in(0,1]}: \{-1-x\}$

What's the solution for the following optimization problem? Is the constraint set convex? $$\max_{x\in(0,1]}:\{-1-x\}$$
0
votes
0answers
59 views
+50

Projection and Pseudocontraction on Hilbert space

Let $H$ be a real Hilbert space with inner product $\langle\cdot, \cdot \rangle: H \times H \rightarrow \mathbb{R}$, and induced norm $\left\| \cdot \right\|: H \rightarrow \mathbb{R}_{\geq 0}$. Let ...
0
votes
1answer
19 views

Confusions of Convex Set

I am interested in the properties of convex set in $\mathbb R^n$ and want to clarify the three statements below $A$ is an open convex set. Can we get the conclusion that $\bar{A}$ is convex? ...
0
votes
0answers
7 views

Sum of quasi-concave function and linear function

Let $F(k)$ have the following properties: $$ F(k) \in C^1 \\ F'(k) > 0 \\ F(0)=0 \\ \lim_{k \to \infty} F'(k) = 0, \lim_{k \to 0} F'(k) = \infty \\ F ~\text{strictly quasi-concave}. $$ Then, let ...
0
votes
2answers
30 views

Critical points and Convexity?

Function $f(x)$ has no critical points in $M$, can we say $f(x)$ is either convex or concave over $M$?
0
votes
0answers
14 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
0
votes
1answer
21 views

Analog of Birkhoff's theorem for doubly stochastic matrices

Birkhoff's theorem states that extreme point of the set of doubly stochastic matrices are permutation matrices. An $n \times n$ matrix $A$ is doubly stochastic if each row and column sums to 1. What ...
0
votes
1answer
20 views

Certain property of convex functions…

I come to you with yet another qualifying problem we can't seem to solve... Let $f:$ $(0,\infty) \to \Bbb R$ be convex, and let $\lim_{x \to 0}f(x)=0$. Show that $g(x)$ = $f(x) \over x$ is increasing ...
1
vote
0answers
64 views

Proving an inequality for convex and increasing functions [closed]

Can anyone show or disprove the following? Let $f:R^+ \rightarrow [1,+\infty]$ be a strictly increasing, convex nonasymptotic and differentiable function and $f'(0)>1$, then for $\forall \ ...
0
votes
0answers
20 views

No critical points means convex or conave? [closed]

If we don't know whether $f(x)=0$ is convex or concave or not, but we know under certain constraint sets there is no critical points of $f(x)$ inside meaning the solution of $df(x)=0$ is outside the ...
0
votes
1answer
29 views

Compact and convex discrete set

I am working with discrete sets but I have a doubt: is the set $\{ 0,1\}$ compact and convex? And the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$?
0
votes
1answer
20 views

Redefine a discrete compact set

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,\ldots,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as ...
0
votes
1answer
23 views

Define a compact and convex set through inequality constraints

I need to find twice continuously differentiable functions $g_i: \mathbb{R}^2 \rightarrow \mathbb{R}$ $i=1,...,I$ such that the set $\{ 0,1\}^2=\{(0,0), (1,0), (0,1), (1,1) \}$ can be written as $\{x ...
0
votes
0answers
22 views

Convex cones and positively homogenous and subadditive functional

Let $V$ be a linear topological space, $K \subsetneq V$ a convex, closed cone with $0 \in K$ and $k \in K \setminus (-K)$. Show that the functional $\varphi : V \to \mathbb R \cup \{ \pm \infty \}$ ...
1
vote
1answer
45 views

How to use Markov-Kakutani fixed point theorem to show that abelian groups are amenable?

Recall that a group $\Gamma$ is amenable if there exists a state $\mu$ on $l^{\infty}(\Gamma)$ which is invariant under the left translation action: for all $s\in \Gamma$ and $f\in ...
4
votes
2answers
78 views

On the convexity of a particular form of integrals

EDIT: I made some critical corrections below. Let $\mathcal{H}\colon\mathbf{w}\cdot\mathbf{x}+c=0$ be a hypeplane in $\mathbb{R}^n$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$, be a non-negative, ...
0
votes
1answer
34 views

Motivating convex sets.

I am kind of TAing for a class of real analysis, and I would like to speak a little about convex sets tomorrow, and explain why they are important. What kind of examples could I give? I was thinking ...
0
votes
2answers
34 views

The Fundamental Theorem of Matrix Games, and the “indifference” method of solving games

In the following we will consider two-person zero-sum games. Let $A = (a_{ij})$ be the payoff-matrix of such a game. In this book the fundamental theorem of such games is states as: Theorem: Given ...
1
vote
3answers
63 views

Is convex hull of a finite set of points in $\mathbb R^2$ closed?

Is the convex hull of a finite set of points in $\mathbb R^2$ closed? Intuitively, yes. But not sure how to show that. Thanks!
5
votes
3answers
168 views

Isoperimetric inequality, isodiametric inequality, hyperplane conjecture… what are the inequalities of this kind known or conjectured?

Question: Which inequalities similar to the famous isoperimetric inequality is known? conjectured? I recently learned about some inequalities which are all similar to the famous isoperimetric ...
0
votes
1answer
31 views

Min of concave symmetric function on a convex set

Consider the convex set $$C=\left\{ \mathbf{x}\in \mathbb{R}^N :0\le x_1\le x_2\le\dots\le x_i\le x_{i+1}\le \ldots\le x_N\le \frac 1{N-1}\text{ and } \sum_{k=1}^{N}x_k=1\right\}$$ I need to minimize ...
0
votes
0answers
8 views

Pseudoconcavity of a fractional function q(x)=f(x)/g(x) if f(x) is nonnegative concave and g(x) is positive convex?

I know from Chandra that $q(x)=\frac{f(x)}{g(x)}$ is strong pseudoconcave if $f(x)$ is nonnegative concave and $g(x)$ is strictly positive convex. Is there a theorem that states $q(x)$ is ...
2
votes
1answer
52 views

Relation between mean width and diameter

Question: Let $A$ be a compact set in $\mathbb R^n$. Is it always true that $\text{mean-width}(A) \ge C \cdot \text{diam}(A)$ for some constant $C$ depending only on the dimension? If not, is it ...
1
vote
0answers
29 views

Quickly checking if an inequality holds on a convex region

Let $C$ be a given convex polygon in $\mathbb{R}^2$ containing the origin and let $a$, $\mathbf{b}$, and $Q\succeq0$ be a given scalar, vector, and matrix respectively. Is there a fast way to verify ...
0
votes
0answers
36 views

Why is pointwise maximum a convex function?

It seems like if you have a family of function $$g = \{a(x), \: b(x), \: c(x), \:d(x)\}$$ $$\text{given} \:\: f(x):= max(g),$$ $$\text{if} \: f(1) = a(1), \: f(2) = b(2), \: f(3) = c(3), \: f(4) = ...
2
votes
2answers
40 views

Prove: $f: (a,b) \rightarrow \mathbb{R}$ is convex iff for every triple $x_1,x,x_2 \in (a,b)$…

Assignment: Prove that a function $f : (a,b) \rightarrow \mathbb{R}$ is convex if and only if for every triple $x_1,x,x_2 \in (a,b)$ with $x_1 < x < x_2$ following inequality is satisfied: ...
0
votes
1answer
24 views

Why does convexity of a function required the following

What is the significance of the following condition $$\forall x_1, x_2 \in dom(f) , \forall \theta \in [0, 1], f(\theta x - (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$ and why isn't the ...
2
votes
1answer
44 views

Let $f: [a,b] \rightarrow R$ be convex. If f is not constant, then the supremum of $f$ is not inside of [a,b].

I could use some help with this proof. Let $a,b \in \mathbb{R}, \ a<b \ \ f: [a,b] \rightarrow \mathbb{R}$ be convex. Prove: If f is not constant, then the point, where the supremum of ...
0
votes
2answers
44 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
2
votes
2answers
36 views

Convexity / Concavity --> Formal Definition

How do I show that $f(x, y)=(x + y)^2$ is convex/concave using the formal definition of convexity/concavity?
0
votes
1answer
17 views

How do I justify that a second order cone is an intersection of half space

I am studying convex optimization right now, and the text book claims that a second order cone is a collection of intersections of half space $$K_n = \bigcap_{ u:\|u\|_2 \leq 1} \{(x,y) \in R^{n+1 } ...
1
vote
0answers
25 views

Is continuity preserved under Max operator and Euclidean norm?

Suppose that the functions $f_i: \mathbb{R}^k \rightarrow \mathbb{R}$ are all continuous over $\mathbb{R}^k$ for $i=1,...,k$. Is the function $$ g(x)=\|\max\{0,f_1(x)\},...,\max\{0,f_k(x)\}\|^2 $$ ...
0
votes
0answers
19 views

Hyperplane - soft and hard questions

This would be a rather long question. Apologies for that. Instead of asking three separate questions I've consolidated them in one. I am trying to learn hyperplanes, convex hulls, separations theorems ...
2
votes
0answers
18 views

Complexity of finding extremal rays

Suppose that $\{L_i\}$ is a collection of $k$ linear forms on $\mathbf R^n$. Let $$C=\{x \in \mathbf R^n : L_i \cdot x \geq 0 \text { for all } i \}$$ be the closed convex cone defined by the ...
0
votes
0answers
19 views

Non-subdifferentiable convex function

Is there any convex function $f$ on a norm space $X$ such that $\partial f(x)=\emptyset$ at every $x\in X$? Thanks in advance.
0
votes
0answers
26 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
0
votes
2answers
27 views

Relation between sum of a max and max of a sum?

Consider $\frac{1}{T}\sum_{t=1}^{T}\max\{ 0,a_t\}$. Can we say whether this is greater or equal then $\max\{ 0,\frac{1}{T}\sum_{t=1}^{T}a_t\}$?
1
vote
1answer
22 views

Tangent cone of graph and epigraph sets.

Let us first recall the definition of tangent cone $\; T(\bar x; \Omega)$ of a subset $\Omega$ at $\bar x \in \Omega$, where $X$ is a Banach space: $$T(\bar x; \Omega)=\{v\in X:\; \; \exists ...
1
vote
1answer
30 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
35 views

The closednees in Moreau - Rockafellar Theorem.

One says that $x\mapsto \langle x^*,x\rangle +\alpha\;$ is an affine minorant of $f: \; X\to \overline{\mathbb R}\;$ if $\;\langle x^*,x\rangle +\alpha \leq f(x)\;$ for all $x\in X$. The Moreau - ...