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)

2
votes
2answers
26 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
1
vote
3answers
46 views

How to check the function is convex or not?

How one can check the function whether it is convex or not. I know one method by using Hessian Matrix but I think it did not fit for the following example. I think Hessian matrix method cannot be ...
5
votes
0answers
137 views
+50

Convexity of Matrix Exponential

Consider the function $A: \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ defined as $$ A( x ) := \left[ \begin{matrix} x_1 & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & x_2 & ...
0
votes
0answers
19 views

Cyclical monotonicity

I am deeply troubled by a question for the homework. Either prove or a give a conter-example to the following claim: A continuously differentiable function $f:\mathbb{R}^l\to\mathbb{R}^l$ is ...
1
vote
1answer
43 views

Onion-peeling in O(n^2) time

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels. At a high level pseudo-code, it is ...
3
votes
1answer
69 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
1
vote
0answers
19 views

ellpsoids have large spherical sections

i want to prove that "For any (2k-1)-dimensional ellipsoid E ,there is a k-flat L passing through the center of E such that $ E \cap L$ is a euclidean ball i see a proof for it in book "lectures on ...
0
votes
0answers
6 views

Convex hypograph implies convex level sets. Is this proof complete and correct?

I want to show that when the hypograph of a function is convex, then the upper level sets are convex too. By definition, a pair $(x, a)$ belongs to the hypograph $H$ if $f(x)\geq a$. Let's suppose ...
0
votes
1answer
604 views

generalized inequalities defined by proper cones

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ? ...
0
votes
0answers
14 views

Hyperplane optimization for Support Vector Machines

I am trying to learn about the theory behind the Support Vector Machines, by reading the tutorial at: http://research.microsoft.com/pubs/67119/svmtutorial.pdf In its most basic form, SVMs is a binary ...
5
votes
2answers
222 views

What is the smallest possible angle of this polygon?

A convex polygon contains a square with side-length 1 and is contained in a parallel square with side-length 2 (which is its smallest containing square). What is the smallest possible angle of the ...
0
votes
0answers
26 views

$C^2$ approximation of a convex set with a “flat part”

Suppose we have a closed, bounded, convex set $K \subset \mathbb{R}^n$ with non-empty interior. It's well-known that we can approximate $K$ either from the inside or from the outside in the Hausdorff ...
3
votes
1answer
356 views

Differentiability of Moreau-Yosida approximation.

I want to show that if $X$ is a reflexive Banach space with norm of class $\mathcal{C}^1$ and $f\colon X\to\mathbb{R}\cup \{+\infty\}$ is convex and lower semicontinuous, then $f_{\lambda}$ is ...
0
votes
1answer
21 views

Sufficient condition for global maximum of strictly quasi-concave functions (unconstrained)?

Suppose $f(x)$ is a function from $\mathbb{R}$ to $\mathbb{R}$ and $f$ is strictly quasi-concave. If $x^*$ is a point such that $f'(x^*)=0$, then can we say that $x^*$ is a global maximum of this ...
2
votes
1answer
20 views

A convex function is differentiable at all but countably many points

Let $f:\Bbb R\to\Bbb R$ be a convex function. Then $f$ is differentiable at all but countably many points. It is clear that a convex function can be non-differentiable at countably many points, ...
0
votes
0answers
18 views

Differentiability of Moreau-Yosida Regularization? [duplicate]

I'm looking for a proof of the differentiability of the Moreau-Yosida regularization of a proper closed convex function $f(y)$ defined on an n-dimensional Banach space $Y$. namely the function is ...
0
votes
1answer
24 views

Is the closure of a geodesically convex set convex?

My question is Is the closure of a geodesically convex set convex? If so, is there a simple proof for it? In $ R^n $ there is a simple proof for it through convergent sequences. How should I apply ...
0
votes
1answer
457 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
0
votes
1answer
36 views

What are the formulas for the number of vertices, edges, faces, cells, 4-faces, …, $n$-faces, of convex regular polytopes in $n \geq 5$ dimensions?

I know that in dimension $n \geq 5$ there are only 3 kind of convex regular polytopes in each dimension: the $n$-simplex, the $n$-cube and the $n$-orthoplex. I would like to know if there are ...
2
votes
2answers
48 views

Quasiconcavity of incomplete gaussian integral

From visual experiments , it appears that the set $$ S_r = \left\{ (x,y) \text{ s.t. } \int_x^y e^{-t^2} dt \geq r \right\} $$ is convex for $r \geq 0$. Or equivalently, the function $$ f(x,y) = ...
0
votes
1answer
22 views

Convexity of an exponential function

I failed the following question in a quiz: For which values of $a$ the function $e^{-a\sqrt(x)}$ with $dom = \mathbb{R}^+$ is convex? Check all that apply: $a\leq0$ $a\geq0$ $-1 \leq a\leq1$ ...
0
votes
1answer
22 views

Convex Sets Pre-image

I am struggling with the following question: Let $a \in \mathbb{R}^n $ and $ b \in \mathbb{R}$ and define $ f: \mathbb{R}^n \rightarrow$ $\mathbb{R} $ by $f(x) = \langle x,a \rangle + b, x \in ...
0
votes
1answer
13 views

what does full- dimensional means when speaking about covex cones

I want to know the exact definition of full-dimensional. And what does "dimension" refer to, is that in the sense of algebraic variety? I have read several writing announcing that the cone of ...
0
votes
1answer
30 views

Proofing set to be convex

I am struggling solving the following exercise: Let $a \in \mathbb{R}^n$ and $ b \in \mathbb{R}$ and define $f : \mathbb{R}^n \rightarrow \mathbb{R}$ by $f (x)=\langle x,a \rangle + b, x\in ...
1
vote
1answer
37 views

Example of a convex set whose closure is not convex?

An enumeration $ν\colon ℕ → A$ of the rationals $A$ in $(0..1)$ yields an open set $U_ν = \bigcup_{k ∈ ℕ} B_{1/4^k}(ν(k))$, containing all of $A$. You can choose $ν$ such that $U_ν ⊂ (0..1)$ (by using ...
1
vote
1answer
26 views

Compactness, Convexity, Convex Hull of Sets including sequences

Is the following set compact, is it convex and what is the convex hull? $V = \{(x_1, x_2,...,x_n) \in \mathbb{R}^n :\frac{1}{1 + i} \leq x_i \leq \frac{1}{i}, i=1,2,...,n\}$ My thoughts: I was ...
1
vote
1answer
43 views

Consider the problem minimize $f(x_1,x_2) = (x_2 −x_1^2)(x_2 −2x_1^2)$

(i) Show that the first- and second-order necessary conditions for optimality are satisfied at $(0,0)^T$. (ii) Show that the origin is a local minimizer of f along any line passing through the origin ...
-1
votes
1answer
29 views

Showing $\ln(1+e^x)$ is convex [closed]

I'd like to show that $\ln(1+e^x)$ is convex. Any help would be greatly appreciated!
0
votes
0answers
11 views

Expressing a convex set as an intersection of halfspaces

The question is as follows: Express the closed convex set {x $\epsilon$ $R^2_+$ | $x_1x_2$ >= 1} as an intersection of halfspaces. Here is what I have: $\bigcap$ {x $\epsilon$ $R^2_+$| $x^2$ >= 1} ...
1
vote
2answers
73 views

Is every convex function on an open interval continuous?

Let $f:(a,b)\rightarrow \mathbb{R}$. $f$ satisfied the following property: If $\forall x_{1},x_{0},x_{2}\in(a,b)$ and $x_{1}<x_{0}<x_{2};$then$\frac{f(x_{0})-f(x_{1})}{x_{0}-x_{1}}\geq ...
2
votes
3answers
165 views

Why doesn't the definition of the interior of a set depend on the dimension of the set

I have just started with a course on convex optimization and have been introduced to the concept of the interior of a set. I have a fairly basic question. I am still trying to understand this topic, ...
1
vote
1answer
41 views

Dual of concave function is convex

If $U(x)$ is strictly increasing and strictly concave and $lim_{x \rightarrow \infty}$ U'(x) = 0, prove that its dual: $$U^{*}(y) = max_x \{U(x) - xy\}$$ is convex. Does anyone know how to prove ...
0
votes
1answer
315 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
0
votes
1answer
226 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
1
vote
0answers
12 views

On Convex Interpolation and distances

Let $C$ denote the class of all real-valued convex functions on $[0, 1]^2$. Fix $n \geq 2$ and points $x_1, \dots, x_n$ in $[0, 1]^2$. Let $S \subset R^n$ be defined by \begin{equation*} S := ...
0
votes
0answers
21 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
52 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
0
votes
0answers
14 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
2
votes
1answer
16 views

Showing the multivariate normal is log-concave?

I'm trying to show that $\log p(x) = -\frac{1}{2}(x-\mu)^{T} \Sigma^{-1}(x-\mu)$ is concave. How would I go about this in $\mathbb{R}^n$? I've tried taking derivatives but I'm getting stuck once I get ...
0
votes
1answer
54 views

Show that this function is convex?

So I'm supposed to show that this function is convex, but I have no idea how to go about it...I've been told to use Cauchy Schwarz in order to show that the Hessian is non-negative definite, but I'm ...
0
votes
0answers
6 views

Verification of the Approach to a given non-convex integer programming problem

I need to verify my approach to a non-convex integer programming problem. It would be interesting to see other approaches as well. Let $\mathbf{C}_1,\dots,\mathbf{C}_R$ be $N\times N$ hermitian ...
0
votes
0answers
10 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
6
votes
0answers
197 views

Closest fixed point to a convex set

Consider the compact convex sets $Y \subset X \subset \mathbb{R}^n$, and a Lipschitz continuous function $f : X \rightarrow X$. Assume that $f$ has multiple fixed points. (From Brouwer's theorem, $f$ ...
1
vote
2answers
38 views

How to prove that $H(S_1\cap S_2)\subset H(S_1) \cap H(S_2)$ and $H(S_1 \cup S_2) \supset H(S_1) \cup H(S_2)$

I'm studying convex analysis and my task is to prove the following inclusions: $S_1, S_2$ are non-empty sets in $\mathbb{R}^n$, and $H(S) $ defined as the convex hull of set $S$. Show that ...
0
votes
1answer
25 views

LP with a linear cost function $c^Tx$: Prove optimal value is $-\infty$ or there exist some $v \in P$ such that $c^Tv \le c^Tx$ for all $x \in P$

Suppose I have a LP with a linear cost function $c^Tx$, where $P=\{x \in \mathbb R^n : Ax \ge b\}$ is the polyhedron I want to minimize over. How do I see that either the problem is unbounded, that ...
0
votes
0answers
12 views

extension of semilinear functional in cone.

I'm studying Nigel Kalton's work in extrapolation Banach space theory (paper: Differentials of complex interpolation processes for Kothe function spaces). My question is: Let $T$ be a cone contained ...
2
votes
1answer
39 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
0
votes
1answer
21 views

A question Kolmogrov's generalized inequality for projection onto convex sets

Kolmogrov's inequality says that, if $C$ is a convex set, and $P_C(x)$ is an operator for projecting point $x$ into the convex set $C$, if $z = P_C(x)$, then for any $y \in C$ we have $$ (z - y).(x - ...
0
votes
0answers
18 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
2
votes
2answers
24 views

Under what conditions does local concavity imply global concavity?

I have the following result: Assume $U:\mathbb{R}^+\to\mathbb{R}^+$ is continuous and strictly increasing. Further, for every $a>0$ there exists a neighborhood (interval) $S$ of $a$ such that $U$ ...