# Questions tagged [convex-optimization]

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

756 questions
Filter by
Sorted by
Tagged with
1 vote
76 views

### Submodularity of a particular function derived from a convex function?

Consider a convex function $f : \mathbb{R}^d \to \mathbb{R}$. Define now the set-input function $g_f : 2^{[d]} \to \mathbb{R}$ as follows, \begin{align} g_f(S) = \min \left\{ f(x) : x \in \mathbb{R}^d ...
1 vote
43 views

### Characterization of the behavior of the residuals in conjugate gradient

In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...
47 views

### problem：Conditions for including cones [duplicate]

I have considered a very interesting question myself, and I think it is very difficult to answer it. Consider N n-dimensional vectors, where the angle between any two vectors is acute and their ...
97 views

77 views

### Given optimality of L1 norm, prove that absolute value of sum of a vector with proper sign is less than 1?

Problem: Given a domain $\mathcal{D}\subset\mathbb{R}^{l}$, we can find $l$ points $\boldsymbol{v}_{i}\in\mathcal{D}$, $i=1,\cdots,l$. Each point is a column vector with dimension $l\times1$. They ...
115 views

### An upper bound of gradient norm for convex functions near minimizer

Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function. Denote $X^*$ as the set of minimizers of $f$ and assume $X^*$ is unbounded. Is it possible that $\|g_x\|$ is unbounded when $d(x,X^*)$ ...
28 views

### Trying to transform a minimization problem to a saddle point problem for the primal–dual algorithm

I’m reading about a problem, and the author goes from a classical minimization problem to a saddle point problem in order to perform a primal–dual algorithm on it . However, It’s my first problem ...
1 vote
46 views

### Estimate of minimum of the Poisson integrals corresponding to a convergent Hausdorff sequence of smooth bounded domains from below

Let $\{\Omega_{j}\}_{j\in\mathbb{N}}$ be a sequence of smooth bounded domains in $\mathbb{C}^{n}$ such that $\Omega_{j}$ converges to a smooth bounded domain $\Omega$ in the sense that the defining ...
1 vote
101 views

### How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem $$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$. ...
1 vote
80 views

### Establishing quasiconcavity

Let $f:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be twice differentiable quasi-concave function satisfying $f(x)>0,\forall x \in \mathbb{R}_+$. Let $g:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be a positive, ...
68 views

### Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?

Crossposted at Computational Science SE Consider a quadratic programming problem with the following format: $$\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\$$ $$\text{s.t.} Ax\leq b, \\ x\geq 0$$ ...
1 vote
29 views

### Fitting a convex polytope with 𝑛 facets between two nested spheres

This is related to a research problem that is interested in approximation of spheres by convex polytopes. Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
62 views

64 views

### Sensitivity of the solution of QP with respect to parameters

Given a quadratic program, $$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$ Suppose $A \succ 0$, so the program strongly ...
40 views

### Identify maxima for 2-Dimensional Function without knowing cross-derivative

I am trying to proof the uniqueness of a maximum for a two-dimensional function (well behaved, twice differentiable, domain $R^2$, etc.), yet cannot compute the exact derivatives or the Hessian. I ...
35 views

1 vote
170 views

95 views

### Is there a redundant constraint in linear programming? [closed]

From wikipedia: But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice). (In order to do that, ...
42 views

### On the convex inequality $x^2\leq u$

Suppose $x$ is in $[0,M]$ where $M^2$ is known and treated as constant in a convex program. Consider the convex inequality $x^2\leq u$. The reverse inequality $u\leq x^2$ is non-convex. On the other ...
1 vote
118 views

### Optimal transport: the existence of an optimal pair of $c$-conjugate functions

$\newcommand{\diff}{ \, \mathrm d}$ Let $X,Y$ be Polish spaces, $\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$, $\mathcal P(X)$ the space of Borel probability ...
1 vote
47 views

### Comparison of solutions of Hamilton-Jacobi equations with different initial conditions

Consider a Hamilton-Jacobi equation: $$u_{t} + f(u_{x}) = 0 \quad (x,t) \in \mathbb{R}\times [0,+\infty)$$ with two possible initial conditions $u(x,0) = g_{i}(x)$ for $x \in \mathbb{R}$ and $i=1,2$. ...
1 vote
55 views

### John and Lowner ellipsoid

I am looking at a proof to show that Lowner ellipsoids are unique for centrally symmetric convex body $K$. I want to show basically that $$Low(K)=John(K^{\circ})^{\circ},$$ where the $\circ$ means ...
201 views

59 views

### A little question about the derivation of the generalized alternating projection (GAP) algorithm

This question is actually just a question about Euclidean projection. I've been studying some articles on the generalized alternate projection (GAP) algorithm recently, but have a little question ...
57 views

### Strict inclusion for recession cone of closure of a convex set

Let $C$ be a nonempty closed convex subset of $\mathbb{R}^n$. The recession cone of $C$ is given by $$R_C=\left\lbrace d\in\mathbb{R}^n:x+td\in C, \forall t>0, \forall x\in C\right\rbrace.$$ It is ...
1 vote
25 views

### Finding variance-minimizing weights [closed]

I'm trying to solve the following matrix calculus problem: $\text{argmin}_{v \in R_+^K}(v'\Sigma v) \hspace{0.5pc} \text{subject to} \hspace{0.5pc} 1'v=1$ where $\Sigma$ is a well-behaved (symmetric, ...
Let $A$ be a linear transformation, let $\mathcal{S}^n_+$ be the cone of positive semidefinite matrices. Suppose $P$ is a polyhedral cone. We consider the image of the intersection of the two cones, i....