0
votes
1answer
22 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 concave. Does anyone know how to prove ...
0
votes
0answers
14 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
12 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 ...
0
votes
0answers
15 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 ...
2
votes
1answer
14 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
0answers
5 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
1answer
47 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
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 ...
0
votes
1answer
24 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 ...
2
votes
1answer
38 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
0answers
16 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 ...
0
votes
0answers
12 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
27 views

how to check an optimization function is convex or not

This is the sparse coding optimization function: $\operatorname*{argmin}_{B, \alpha} \sum_j \| \bf{x}_j - B\bf{\alpha}_j \|_2^2 + \lambda\sum_j |\bf{\alpha}_j|_1$ I read in the literature that this ...
0
votes
0answers
28 views

The convexity of the range of concave function

Given a concave function $f: X \rightarrow \mathbb{R}^n $ with a convex domain $X \in \mathbb{R}^n$, is the range of $f$ a convex set also?
0
votes
0answers
33 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
1answer
32 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
30 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 ...
3
votes
3answers
133 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 $$ ...
0
votes
0answers
20 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
19 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 ...
3
votes
1answer
40 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
0answers
18 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 ...
1
vote
1answer
107 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 ...
0
votes
1answer
112 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
1answer
57 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
1answer
17 views

What is a $0$-sublevel set?

I read the notes of S. Boyd, and am confused about the following: $f_0(x)$ is quasiconvex. I am confused about the latter one particularly. What does it mean? Thanks!
0
votes
1answer
36 views

Strong convexity of a function with cases

Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function \begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align} ...
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 - ...
1
vote
1answer
57 views

New variable in a convex optimization problem

Consider the convex optimization program $$ \min_{x \in X } x^\top P x + p^\top x \quad \text{ sub. to: } Ax = b $$ where $X \subset \mathbb{R}^n$ is compact, $P \succ 0$, $A \in \mathbb{R}^{m \times ...
0
votes
1answer
27 views

Optimality conditions in convex programming

I'm reading about Zero-order conditions in Nonlinear Programming and the following confuses me (my questions are below the theory): Consider the set $\Gamma \subset E^{n+1} = \{(r,\textbf{x}): ...
0
votes
0answers
21 views

closed form solution of a particular convex program

I wish to know if there is a closed form solution of a program of the following form $\max_w x^Tw \text{ such that } \tau_2\| w \|_2 + \tau_1 \| w \|_1 \leq 1, ~\ \tau_1, \tau_2 > 0$ When either ...
0
votes
0answers
30 views

Proof of sufficient condition of existence of Lagrange multipliers

Consider the optimization problem $$ (P) \quad \inf\{ f(x) : g_i(x) \le 0, i = 1,\ldots, m, x \in \mathbb R^m \} $$ where $f, g_i : \mathbb R^n \to (-\infty, \infty]$ are convex and $0 \ne ...
0
votes
1answer
37 views

Sufficient condition on convex function such that $f(x) > -\infty$ for all $x$.

Let $f : \mathbb R^n \to [-\infty, \infty]$ convex and let $f(\overline x) > -\infty$ for $\overline x \in \mbox{int}(\mbox{dom}(f)$. Show that $f(x) > -\infty$ for all $x \in \mathbb R$. ...
2
votes
1answer
58 views

Solving $ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$

Let $\phi \in \mathcal ( [0,1]^2)$ symetric , can we find a solution to the following minimisation problem? $$ \inf \left\{ F[\nu] : \nu \in L^2 , \nu \geq 0, \int _0 ^1 \nu=1\right\}$$ with $$ ...
1
vote
1answer
67 views

Proximal Mapping for maximum of linear and quadratic function

I was wondering if there is an efficient way of calculating the proximal mapping of the following function $f : \mathbb{R}^3 \rightarrow \mathbb{R}$, $b_i \in \mathbb{R}^3$, $c_i \in \mathbb{R}$ : $$ ...
0
votes
1answer
31 views

Dual norm equivalence?

$\|\|$ is a norm in $R^n$, its dual norm is defined as $\|s\|^*=max_{\|x\|=1}s^Tx$. We denote $s^\#$ as any vector in the following set: [Arg $max_x: \ \ s^Tx-\frac{1}{2}\|x\|^2$] How to verify ...
1
vote
1answer
24 views

The Dual problem of a non constraints problem?

The primal problem is $min_{w\in R^d}: P(w)$ where $P(w)=\frac{1}{n}\sum_{i=1}^n\phi_i(w^Tx_i)+\frac{\lambda}{2}||w||^2$. The dual problem is $max_{\alpha\in R^n}: D(\alpha)$ where ...
0
votes
0answers
21 views

Detecting faces of polytopes

I am working in convex geometry for the summer with little experience beforehand. It's a lot of fun but it does mean I don't know some of the basic things. I'm interested in the orbits of finite ...
0
votes
2answers
56 views

Regularization vs. Inequality Constraint

For what values of a regularization parameter $\alpha$, there is an equivalent inequality constraint in convex optimization? In particular, in the convex optimization problems below $$ \text{ Problem ...
1
vote
1answer
34 views

Linear constraint in convex optimization

Is it true that the solution to a linearly constrained convex minimization problem can only be placed on the boundary of the constraint set, for any nonlinear convex objective, e.g. $$ \min_x f(x)$$ ...
0
votes
1answer
31 views

Is it possible to convexify this cone constraint?

General question An SOCP constraint is given by: $$ \| A_i \mathbf{x} + b_i\| \leq \mathbf{c}_i^T \mathbf{x} + d_i.$$ I have the following constraint: $$ \| A_i \mathbf{x} \| \geq d_i.$$ Is it ...
0
votes
1answer
39 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
0
votes
1answer
35 views

regarding the concept of dual cone

When studying the covex analysis, I am not clear about the concept of dual cone. In the following graph, $\mathcal{K}*$ was the dual cone. I marked two points, the ...
0
votes
1answer
83 views

Convex optimization: affine equality constraints into inequality constraints

I have the following problem: \begin{equation} \begin{array}{cll} \displaystyle \min_{ \mathbf{x} } & & \displaystyle f(\mathbf{x}) \\ \mathrm{s.t.} & & \mathbf{x} \in \mathcal{C} \\ ...
0
votes
0answers
33 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
0
votes
2answers
48 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
0
votes
0answers
24 views

Dual convex pairs

I am currently trying to understand a certain proof. The author uses the term dual convex pair for a pair $(\phi,\psi)$ of convex functions defined on subsets $X,Y$ of $\mathbb R^n$ satisfying: $$ ...
0
votes
1answer
24 views

Deriving projection operator for an affine set

Given an affine set $Ax=b$, the Projection operator to this set is $$P(z) = z - A^{T}(AA^{T})^{-1}(Az-b)$$ which is also affine. How is this derived?
0
votes
0answers
20 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
1
vote
2answers
61 views

Composition of non-monotonic convex function

Given the following composition of functions: $h:\Bbb R^k\rightarrow\Bbb R$ $g:\Bbb R^n\rightarrow\Bbb R$ $f(x)=h(g_1(x),g_2(x),...,g_k(x))$ There are known rules which guarantee ...