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
1answer
69 views

Showing a function is concave

Given $F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2))$ on $S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\}$ with $A,B,a\in\mathbb{R}$, show that $F$ is concave on $S$. Since we have ...
0
votes
1answer
68 views

How to prove that $f$ is convex function

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
2answers
142 views

Notion of a concave function and proving ln is concave

I've just checked that the definition is right, a function is convex if: $(1-t)f(x_1)+tf(x_2)\ge f((1-t)x_1+tx_2)$ which is odd because this is ... well I was taught (very young age) that concave ...
0
votes
0answers
49 views

Minimization of product function subject to constraints

I want to minimize the following function: $\prod_{i=1}^{n}{x_i}$ Subject to the following constraints: $\sum_{i=1}^{n}{x_i}=1.1+(n-1)(0.1)$ and $0.1 \leq x_i \leq 1.1$ How should I go about it? ...
1
vote
1answer
53 views

Show that for $f,g: [0, + \infty) \to \mathbb{R}$ convex functions of Class $C^2$ their product $fg$ is convex

Problem: Let $f,g: [0, + \infty[ \to \mathbb{R}$ be two convex functions of Class $C^2$. Assume that $$ f(0) \geq 0, g(0) \geq 0 \text{ and } f'(0) \geq 0, g'(0) \geq 0 \tag{!}$$ Show that $fg$ ...
1
vote
1answer
40 views

$\mathrm{Prox}_{f}(x)$ and $\mathrm{Prox}_{af}(x)$

Let $a\in \mathbb{R}$, and $f$ is a convex function $f: \mathbb{R}^n\rightarrow \mathbb{R}$. $\mathrm{Prox}_{f}(x)=y_1$ and $\mathrm{Prox}_{af}(x')=y_2$. Because I know $\mathrm{Prox}_{f}(x)$. And ...
0
votes
1answer
46 views

Dual of dual cone of nonconvex closed cone

let $K$ be a nonconvex closed cone, then $K^{**}=conv(K)$ should this hold? I am not quite sure about it. Thanks.
1
vote
1answer
122 views

convex closed and unclosed functions and (lower semi)continuity

I'm grappling a bit with lower semicontinuity and convex functions. Let me consider convex functions as functions to $\mathbb{R}$ and not to $\mathbb{R}\cup \{\pm\infty\}$. By Rockafellar's book ...
0
votes
1answer
71 views

The conjugate relation between two functions.

Suppose $K\in \mathbb{R}^{m\times n}$, $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$. Let a function $F: \mathbb{R}^m \rightarrow \mathbb{R}$, $F(y)$. Let $y=Kx$, $G(x)=F(Kx)$. Suppose $G(x)=F(Kx)$, ...
1
vote
0answers
44 views

How to show this converges in probability

$A_n(s)$ is a sequence of convex random functions defined on an open set $S\in \mathbb{R}^p$ which converges in probability to some $A(s)$ for each $s$. I'm trying to show that $\sup_{s\in K} \big| ...
1
vote
1answer
34 views

Equality constrained Quadratic Program

Consider the QP $$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$ where $P \succ 0$. Without the non-negativity ...
0
votes
1answer
50 views

Are there necessary and sufficient conditions for Krein-Milman type conclusions?

This, the third of three self-answered questions, contains a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The second question is here. ...
0
votes
1answer
22 views

Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The third ...
0
votes
1answer
78 views

Convexity of LASSO

I would like to know if some variables in design matrix are correlated then LASSO is convex or not. If you give me a proof for convexity of LASSO and ADAPTIVE lasso, I will be thankful. LASSO is ...
1
vote
0answers
78 views

When do partial subgradients give a subgradient?

I'm looking for sufficient conditions that guarantee that partial subgradients of a convex, lower-semicontinuous functional $f:X_1\times X_2\rightarrow\overline{\mathbb{R}}$ form a subgradient of $f$. ...
0
votes
1answer
47 views

Are there necessary and sufficient conditions so that every element in a partially ordered set is either the least element or in the upset of an atom?

This is the first of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The second question is here. The third ...
1
vote
1answer
107 views

Strictly convex unit balls in $L^p$

I need to show that if $1<p<\infty$, then the unit ball is strictly convex in $L^p$, that is, $||\lambda x+(1-\lambda)y|| < 1$ whenever $||f|| = ||g||=1$ and $\lambda \in (0,1)$. I tried ...
3
votes
2answers
359 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
0
votes
1answer
22 views

On the Composition of simple Projections

Consider the compact convex set $X = \{ x \in \mathbb{R}^n \mid x \geq 0, \ \underline{1}^\top x = 1 \}$. I am wondering if the projection onto $X$ is the composition of the projection on $[0,1]^n$ ...
1
vote
1answer
46 views

Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$ x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b $$ where $X \subset \mathbb{R}^n $ is a non-empty, convex, bounded polyhedron. ...
0
votes
1answer
31 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
19 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 ...
2
votes
1answer
25 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$ ...
1
vote
1answer
42 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
75 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
50 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
89 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
586 views

convex hull function in matlab

Is there any way 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
138 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
37 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
44 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\}$$
2
votes
0answers
151 views

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
39 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
2answers
41 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$?
1
vote
0answers
77 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
72 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
30 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 ...
0
votes
1answer
52 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
22 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
29 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 ...
1
vote
1answer
102 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
105 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
48 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
102 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
177 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!
8
votes
3answers
436 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
128 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 ...
2
votes
1answer
132 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
41 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
156 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) = ...