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
0answers
15 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
18 views

Redefine a discrete compact and convex 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
21 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
17 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
39 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
66 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
28 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
29 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
2answers
100 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
29 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
44 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
35 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
39 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
39 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
33 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
17 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
22 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
20 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
29 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 - ...
0
votes
0answers
14 views

Show that the graph of a convex function is above any tangent plane

In proving jensen inequality one use that the graph of a convex function is above any tangent plane. I've been reading Property of convex functions and Tangent line of a convex function. But what ...
0
votes
1answer
13 views

Volume of Minkowski sum of a point and a hypercube

Let $A$ be a single point and $B$ a unit cube in $\mathbb{R}^n$, what is then the volume $\lambda \mapsto \mathrm{Vol}\big((1-\lambda)A + \lambda B\big)$? I am not exactly sure, what the set ...
0
votes
1answer
35 views

Volume of unit n-dimensional ball, definite integal

As a part of an assignment to calculate the volume of unit n-dimensional ball I got to the following expression, which I believe is true: ...
0
votes
0answers
13 views

Linear transformation preserving strict convexity

Consider the functions $f:\mathbb{R}^n\to\mathbb{R}$, $g:\mathbb{R}^m\to\mathbb{R}$ and the non-square matrix $A \in \mathbb{R}^{m\times n}$ with $m>n$. Let $x\in\mathbb{R}^n$ and consider the ...
0
votes
1answer
18 views

Computing subgradients, a basic example.

A vector $v \in \mathbb{R}^n$ is a subgradient of a convex function at $x$ if $$f(y) \geq f(x) + <v, y - x>$$ for all $y \in dom(f).$ The set of all sub gradients is known as the sub ...
2
votes
1answer
27 views

Sums of convex functions strictly convex in one variable

Let $f_i:\mathbb{R}^n\to\mathbb{R}$, $i=1,2,\ldots,n$ be twice continuously differentiable, convex functions in $x = (x_1,x_2,\ldots,x_n)$. Let each $f_i$ be strictly convex in $x_i$. Is the function ...
0
votes
1answer
17 views

Convexity definition confusion

When one writes $$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$$ for $x,y\in \mathbb{R}^n$, $\lambda\in(0,1)$ what does this mean? 1) Does it mean that the function is jointly ...
0
votes
0answers
31 views

Creating a $C^2$ smooth convex curve which joins circular arcs

Suppose that I have many points $p_1$,..., $p_n$, all very close to origin 0. For R very, very large, I have circular arcs of radius R, $\alpha_i$, about $p_i$. I do not speak about their ...
0
votes
1answer
14 views

L1 ball contained in convex hull of L0 ball

Consider the set $S$: the set of vectors whose $L^0$ pseudo-norm is upper bounded by $s$. Also, consider the $L^1$ ball of radius $\sqrt{s}$. It is apparently a well known fact that the $L^1$ ball is ...
1
vote
1answer
16 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
0
votes
2answers
28 views

Question on convexity

If I have a function $f:\mathbb{R}^n\to\mathbb{R}$ that is convex in ${\bf x} = (x_1,x_2,\ldots,x_n)$ and strictly convex in one of the variables, say $x_1$, then is $f({\bf x})$ strictly convex in ...
4
votes
0answers
135 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
0
votes
0answers
24 views

Gradient of the optimal point

Hope to ask a Q on S. Boyd's cvx book: (p.139) A point x is optimal iff x in X and My Q is: If x is optimal, the 1st order differentiation at this point should be zero. Gradient is like ...
0
votes
1answer
14 views

Continuity of convex functions at point out of domain

I have been studying the continuity of a convex function and having a trouble below: In some books, the authors defined the the continuity of a convex function $f$ even $f$ is not in $\mbox{dom }f$, ...
0
votes
1answer
37 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
1
vote
1answer
10 views

Properties that guarantee quasiconvexity in $\mathbb{R}^n$

I have an open bounded connected domain $\Omega \subseteq \mathbb{R}^n$ and I would like to say that for every two $x,y \in \Omega$ there is a path $\gamma$ from $x$ to $y$ of length at most $C|x-y|$ ...
2
votes
1answer
30 views

Distance of convex combination of pairs of points in $\mathbb{R}^n$

Given 4 points $w,x,y,z \in \mathbb{R}^n$ define for $t\in [0,1]$ $f(t)=d(wt + (1-t)x, yt + (1-t)z)$. Is this function convex? I have found a proof by differentiating twice and calculating a lot but ...
0
votes
1answer
14 views

A Q about convex optimality criterion

Hope to ask about p. 139 of S. Boyd's cvx book: x is optimal iff x is in X (feasible set) and And the book use the following pic to illustrate: My Q is: why there is a negative sign '-' in ...
0
votes
1answer
21 views

Integral of increasing continuous function is convex

Suppose $g$ is increasing and continuous. Does it follow that $G(x) = \int_0^xg(y)dy$ is convex? Clearly $G'$ is increasing and continuous, and $G''\geq 0$ exists a.e., but I don't see how this ...
0
votes
1answer
19 views

Partial Ordering of proper cone K

$K$ in $\mathbb{R}^n$, and $K$ is a proper cone. Partial Ordering of $K$ : $x \leq_K y$ iff $y-x\in K$ (S. Boyd p. 43) My questions are: Does it require $x,y\in K$? If $x,y\in K$, it seems ...