Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

2
votes
1answer
47 views

Given the following two assumptions, How to conclude $\lim_{k \rightarrow \infty}|\nabla g_r(y^{k})|=0 \ $?

Please refer attached 6-page short paper for details. Let $M(y)=y+2r\nabla g_r(y)$. Given $\ g_r(M(y^k))>g_r(y^k)+r|\nabla g_r(y^k)|^2, \forall k. \ $ (equation 36 in the paper) and $ \ \lim_{k ...
0
votes
0answers
18 views

Projecting a polyhedral cone onto its intersection with the infinity-norm ball

For a point in a convex polyhedral cone, $x\in \mathcal{C} = \{\sum_{i=1}^m \alpha_i r_i \vert \alpha_i \geq 0, r_i \in \mathbb{R}^n \}$, is there an efficient algorithm to project $x$ onto the ...
1
vote
0answers
53 views

Solve simple stochastic variational inequality

Let $Z$ be a random variable with finite mean $\mathbb E[Z]$ and let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a convex l.s.c function which is differentiable at $z=1$ with gradient $\...
0
votes
0answers
19 views

Dual representation of problems involving $f$-divergences

Studying some problems arising in decision-making under model uncertainty, I'm led to consider the following problems. Let $\mathbb E_P$ and $\mathbb V_P$ denote the expectation and variance ...
0
votes
0answers
67 views

How to understand the span of a matrix? [closed]

https://people.eecs.berkeley.edu/~brecht/cs294docs/week7/12.candes.recht.pdf In the section 3.3 of the paper above, the author explains the span of matrices: To apply our results to recovering low-...
1
vote
1answer
101 views

How to solve this optimization problem efficiently?

Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements $V\in\mathbb{C}^{3^M\times M}$ is a given matrix $T$ is a scalar (real and $>1$) $\textbf{The problem at hand is as follows:}$ ...
3
votes
1answer
59 views

Echange of Infimum Integral with Pointwise Infimum

Setup Suppose that $U$ is a subset of $L^{\infty}_{\mu}(\mathscr{F})\cap L^1_{\mu}(\mathscr{F})$ defined by $$ f\in U \Leftrightarrow g(f(x))\leq M \mbox{ and } f \in L^{\infty}_{\mu}(\mathscr{F})\...
2
votes
1answer
99 views

it's convex sequence inequality

Sequence of real numbers $a_0,a_1,\dots,a_{n}$ are called concave if for each $0<i<n$, $a_i\geq\dfrac{a_{i-1}+a_{i+1}}{2}$.$a_{0}=0$ Find the largest $c(n)$ such that for every concave sequence ...
2
votes
1answer
112 views

Advantages of hyperbolic programming over semidefinite programming?

What are the advantages of a hyperbolic program over a semi definite program? SDPs can be used to represent a wide variety of algebraic constraints. Are there constraints that can be represented in a ...
2
votes
0answers
59 views

convex approximation for a non convex function

Consider the function $f\left( {{x_1},...,{x_M},{y_1},...,{y_N}} \right) = \left( {\sum\limits_{j = 1}^M {{\alpha _j}{x_j}} } \right)\left( {{e^{ - \sum\limits_{i = 1}^N {{\beta _i}{y_i}} }}} \right)$...
2
votes
1answer
86 views

Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...
0
votes
1answer
52 views

maximization of a log norm function

Considering the following optimization program: $$ maximize \ \ \ \log \left( \|x\|_\infty \right) $$ $$ subject \ to \ \ Ax\leq b, \ x \geq 0 $$ can we rewrite this program as a convex ...
1
vote
1answer
67 views

LASSO problem but with a maximization instead of minimization

I have the following optimization problem (like the LASSO problem but with maximization instead of minimization): $\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...
0
votes
1answer
47 views

Quasiconvexity property of quasinorms

Schatten $p$ norm is convex when $p\geq1$ holds and if $p\in(0,1)$ it is quasinorm. If $p\in(0,1)$ then is Schatten $p$ norm quasi convex? I am interested in definition of quasi convexity here https:...
-1
votes
0answers
10 views

Convex Optimization - Derive Conjugate function [migrated]

I have been trying to solve this question and managed to prove subquestion (a). But I have no idea about proving the other two subquestions. Can anyone help? Note: The question is from Stephen Boyd'...
3
votes
0answers
24 views

Level sets of strongly convex and smooth functions

Let $f: \mathbb{R}^N \to \mathbb{R}$ be a $\alpha$-strongly convex and $\beta$-strongly smooth function, i.e., $$ f(x) + \langle\nabla f(x), y- x\rangle + \frac{\alpha}{2}\|y-x\|^2 \leq f(y) \leq f(x) ...
0
votes
0answers
38 views

optimizing convex piecewise linear function

What it the best way to optimize the following objective function? $$ \min_{x \ge 0} \; c^T x + \sum_{i=1}^n \max(0, a_i^T x + b_i, \eta_i a_i^T x + b_i) $$ with $\eta_i \le 0$. Since this function ...
4
votes
2answers
224 views

Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
1
vote
0answers
34 views

Minimum Preserving Transformations [closed]

If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then $$ \operatorname{argmin}_{x \in X} f(x) = \operatorname{argmin}_{x \in X} g\circ f(x) . $$ X and Y ...
2
votes
1answer
76 views

Why the convexity condition on the definition of a face of a convex set?

A face of a closed convex set $X\subseteq\mathbb{R}^n$ is defined to be a set $F\subseteq X$ such that: $F$ is convex. Every line segment from $X$ whose interior meets $F$ is contained in $F$. Is ...
1
vote
2answers
136 views

Maximizing a function that is sum of gaussians

Let $\mathbf{x}_1,\dots,\mathbf{x}_n$ be given $n$ vectors in $\mathbb{R}^d$. Define the function \begin{align} \mathcal{K}(\mathbf{x},\mathbf{y})= \alpha\exp(-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\...
4
votes
2answers
119 views

Is there any efficient solution of the matrix equation AXB + (AXB)' + cX = D

I am trying to find the symmetric solution $X\in \mathbb{R}^{p\times p}$ of following matrix equation: $AXB + (AXB)^T + cX = D$ where $A,B\in \mathbb{R}^{p\times p}$ are symmetric positive ...
9
votes
1answer
318 views

Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...
0
votes
0answers
62 views

Iterative methods for minimizing sequences

Let $\mathbb{X}$ be a Banach space equipped with some norm $||\cdot||_\mathbb{X}$ and $F:\mathbb{X}\to\mathbb{R}$ be some linear functional. Suppose we are given a set $A\subseteq\mathbb{X}$ which is ...
3
votes
0answers
75 views

Fenchel conjugate on a Hadamard manifold

Let $M$ be a Hadamard manifold and let $F:M\to\mathbb{R}$ be a real-valued convex function on $M$. What would be the Fenchel-Young conjugate of $F$? In general for a real locally convex vector space $...
3
votes
1answer
186 views

concavity of $\log [ (1+\frac{x_0}{1+x_0+x_1/2+x_2/4}) (1+\frac{x_1}{1+x_0/4+x_1+x_2/2}) (1+\frac{x_2}{1+x_0/2+x_1/4+x_2}) ]$

Let $f:~ [0,1]^3 \rightarrow \mathbb{R}$ be $$ f(x_0,x_1,x_2)= \log \left[ \left(1+\frac{x_0}{1+x_0+\frac{x_1}{2}+\frac{x_2}{4}}\right) \left(1+\frac{x_1}{1+x_1+\frac{x_2}{2}+\frac{x_0}{4}}\right) \...
4
votes
3answers
141 views

Quasi-concavity of $f(x)=\frac{1}{x+1} \int_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt$

I want to prove that function \begin{equation} f(x)=\frac{1}{x+1} \int\limits_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt \end{equation} is quasi-concave. One approach is to obtain the closed form ...
1
vote
0answers
36 views

Lower semicontinuity of proximal gradient descent sequence

I'm using an alternate optimization scheme to minimize a function $F(a,b,c) = G(a,b,c) + H(c)$ where $G$ is continuous and differentiable, $H$ is not differentiable but lower semi-continuous and ...
0
votes
1answer
88 views

Strict complementary slackness for semidefinite programs with strong duality

By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...
3
votes
1answer
102 views

Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
2
votes
1answer
110 views

Quasi-concavity of $f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$ on $[0~1000]$

I want to prove that function $f:[0~1000]\rightarrow R$, $$f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$$ is quasi-concave. Any idea how to do the proof? I already tried to prove that any super-level set is ...
3
votes
1answer
277 views

Minimize the variance of a Boltzmann distribution

N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here). ...
1
vote
0answers
38 views

Relative interior of a normal cone at a face of a convex polytope?

Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$. Consider the normal cone of $A$ at $F$: $C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
1
vote
1answer
156 views

Is this parametrized semidefinite program convex?

I am considering an optimization problem of the form: \begin{equation} \begin{split} f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\ &\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\ &\;\;\;\;\;\;\;\;\;\;\; \...
0
votes
0answers
44 views

Is this set of polynomial constraints convex? Can I optimise it?

Basically I want to optimise a problem with a constraint on the (variable dependant) roots of a polynomial, which I would like to be assigned depending on other constraints. I reduced the problem to ...
0
votes
1answer
46 views

Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb ...
1
vote
1answer
52 views

Convex integer programming on totally unimodular polytope?

If $$\min x'Qx + Rx$$ $$Ax\leq b$$ $$x\in\mathbb Z^n$$ is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular? In particular if we ask ...
0
votes
0answers
54 views

non-convex optimization with constraint

I have a special non-convex optimization problem: $\min / \max \ f(x) + g(x) + h(x)$, subject to $| g(x) - h(x)| < \varepsilon$, where $f(x)$ is non-convex, but both $g(x)$ and $h(x)$ are ...
1
vote
1answer
98 views

Maximizing mutual information between two linearly projected random variables

Consider continous random variable $X$ with bounded support $\mathcal{X} \subset \mathbb{R}$, discrete random variable $Y$ with finite support $\mathcal{Y}$ , and constants $c_1 ,c_2 \in \mathbb{R}$. ...
2
votes
1answer
46 views

Linear program with one quadratic condition convex in domain of interest polynomial time solvable?

$c\leq xy$ is not a convex condition. However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$. Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...
0
votes
0answers
45 views

Optimization of generalized Fisher information over space of probability measures

Assume we already have $p(\theta)$ apriori desnsity function about unknown parameter $\theta$, and we consider an optimization problem as follows: \begin{equation} \max_{P \in \mathcal{M}} \int_{\...
0
votes
2answers
146 views

Lagrange Multipliers for two constraints, degenerate case

To optimize $f(x,y,z)$ subject to $g(x,y,z)=h(x,y,z)=0$, we use the Lagrange Multiplier method and solve \begin{equation*} \nabla f=\lambda \nabla g+\mu\nabla h,\quad g=0,\quad h=0. \end{equation*} ...
2
votes
1answer
116 views

Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently? $$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
1
vote
0answers
41 views

Projecting two convex polyhedra onto their intersection

Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$. For the orthogonal ...
11
votes
2answers
310 views

Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold $$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$ where $I_k$ is the $k$-dimensional identity matrix. It is well known that $$\mathrm{conv} \left( ...
0
votes
0answers
51 views

Suggestions to solve an optimization problem that involves quadratic forms

I am in a crucial part of my research, I have arrived at an optimization problem that I can not solve, I need to solve it to be able to perform simulations and thus complete my research, due to this ...
2
votes
1answer
101 views

Constructive version of Hilbert Projection Theorem

I am looking at the Hilbert Projection Theorem, which states that every non-empty closed convex set in a Hilbert space admits a unique element that has the minimum norm in the set. The proof involves ...
0
votes
0answers
62 views

Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example. Let $...
4
votes
1answer
229 views

Inf of Jensen's inequality

I'm reading a monograph that considers the following problem: $$\inf_{z(t) \in C^1} \int_0^1 c\bigg(\frac{dz(t)}{dt}\bigg) dt\\ z(0) = x, z(1) = y$$ Here $c$ is a convex function, $z(t)$ are paths ...
4
votes
0answers
203 views

Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables

Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest: $1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed; $...