# Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

7,529 questions
Filter by
Sorted by
Tagged with
28 views

### Hessian matrix negative definite except in a finite number of points

I'm dealing with optimization problems and I have found myself wondering on this statement: If $f$ is twice differenciable on $\mathcal{D}$ and its hessian matrix $\mathbf{H}_f$ is negative definite ...
• 31
21 views

### Convexity of zero of partial derivative of a convex fonction. [closed]

Is there an integer d, an integer $1 \le i \le d$ and a convex function $f : \mathbb{R}^d \rightarrow \mathbb{R}$. Such that the set $\{x \in \mathbb{R}^d / \frac{\partial f}{\partial x_i}(x) =0 \}$ ...
36 views

### Finding the optimal distribution that maximises

Consider two discrete random variables $X$ and $Y$. Let $Q$ be a distribution over $X, W$ be a conditional distribution $Y$ given $X, U$ be a conditional distribution $X$ given $Y$, and $s$ and $r$ be ...
• 97
33 views

### Gradient and intermediate value theorem

I'm having trouble with an optimization problem. I have a continuous and concave objective function $\mathcal{O} : \mathbb{R}^n \longrightarrow \mathbb{R}$. I have strong evidence (numerical ...
• 31
43 views

### Is a quadratic program convex with respect to its parameters? [closed]

Consider a quadratic program $$\min_z \quad \frac{1}{2} z^T A z + b^T z$$ $$s.t. \quad Cz \leq d$$ with $A$ positive definite. For any choice of $A$ and $b$ we get a solution $z^*$. Is the ...
1 vote
19 views

### Quadratic Optimization with positivity, equality constraints - Literature Review?

I'm trying to solve a problem of the form $\min x^T Q x$ such that $Ax = b$ and $x_i \ge 0$ for all components $i$; $x, b$ are vectors; and $Q, A$ are matrices. In this case $Q$ is square and positive ...
• 1,290
27 views

### Minimizing a Function with Nonlinear Constraints

I am trying to minimize the function $f(x, y) = \frac{1}{x} + \frac{1}{y}$ subject to the constraints: $$x^3 + \frac{x}{x + y} y^3 - c \leq 0,$$ $$x \geq 0,$$ $$y \geq 0.$$ I have attempted to ...
49 views

• 51
1 vote
64 views

Suppose we want to find the minimum of a a strictly increasing function $f: [-a, a] \to \mathbb{R}$, for some $a > 0$, which is also concave in $[-a, 0]$ and convex in $[0, a]$ (exactly like the $... 0 votes 0 answers 28 views ### Proximal point operator of maximum of functions I want to know whether the proximal point operator of a function with a special structure can be expressed in terms of simpler proximal point operators. Setup: For a proper, convex and lower ... 0 votes 0 answers 25 views ### How to express fractional programming problem with DCP Let$f(\theta) \triangleq \mathbf{a}^T(\theta) \mathbf{x} + b(\theta)$, where$\mathbf{a}(\theta) \in \mathbb{C}^N$,$\mathbf{x} \in [0,1]^N$,$b(\theta) \in \mathbb{C}$, with$\theta \in [-\pi,\pi[$. ... 1 vote 1 answer 24 views ### Question on nestorovs theorem dealing with the oracle lower bound for the iteration complexity Right now I am studying the nesterov accelrated gradient where my objective is convex and has lipschitz continuous gradients. In my lecture notes it is mentioned that the NAG is special in the sense ... • 453 0 votes 1 answer 41 views ### Concavity of Distance-to-Boundary Function Let$B := \bar{B}_{R}(0) \subseteq \mathbb{R}^2$be the closed ball of radius$R$. The distance-to-boundary function$d: \mathbb{R} \rightarrow \mathbb{R}$gives the distance of any point$x_0$to the ... • 511 1 vote 1 answer 49 views ### Why does$\textbf{tr}(F_{i}(\nabla\,\text{log}\,\text{det}(F))) = \textbf{tr}(F_{i}F^{-1})$? In Example A.3 of Convex Optimization by Boyd and Vandenberghe, they write that $$\textbf{tr}(F_{i}(\nabla\,\text{log}\,\text{det}(F))) = \textbf{tr}(F_{i}F^{-1})$$ where$F \in R^{\,p,p}$is positive ... • 187 1 vote 1 answer 32 views ### Positive semi-definitiveness condition for multidimensional minimization case We study the nonlinear problem $$\underset{\mathbb{R}^2}{\text{min}}f(x)$$ where$f(x)=x_1^2+x_2e^{x_1}-x_1x_2+x_2^2$Evaluate whether the problem is convex. For a ... • 2,973 0 votes 0 answers 18 views ### Regarding convergence rates, is it important to distinguish between convergence rate of$(x^t)$and$(f(x^t))$? Right now I am dealing with iteration complexity of different gradient descent and stochastic gradient descent algorithms. Most of the time one assumes (strongly) convex objectives and smooth ... • 453 1 vote 1 answer 63 views ### Proving the two optimization are equivalent or not Here are two optimization problems: $$(P) : \inf_{x} [ f(x)|g(x) \leq 0 ] \text{ where } g(x) = \inf_{y} [ h(x,y)|y \in Y ]$$ $$(Q) : \inf_{x,y} [f(x)|h(x, y) \leq 0, y \in Y ]$$ Are they ... 0 votes 0 answers 24 views ### Minimize$\mathrm{tr}((FK + G)^TQ(FK + G) + K^TRK)$over block lower-triangular matrices$K$I want to solve the minimization problem $$\inf_{K\in\mathcal{K}}\mathrm{tr}\left(\left((FK + G)^TQ(FK + G) + K^TRK\right)\Sigma\right)$$ where$\mathcal{K}$is the set of block lower triangular ... -1 votes 1 answer 66 views ### Steepest descent direction Consider the unconstrained optimization problem $$\underset{\mathbb{R}^n}{\text{min}} f(x)$$ with $$f (x) = \frac12 x^T Qx - c^T x + \frac{1}{2\mu}(a^T x - \beta)^2 ,$$ in which$c$and$a$... • 2,973 0 votes 0 answers 54 views ###$||Ax|| \leq ||x||_{*} \leq \sqrt{n} ||Ax||_2$Show that exists a norm$||.||_{*}$such that for each matrix satisfying $$||Ax||_2 \leq ||x||_{*} \leq \sqrt{n} ||Ax||_2$$ exists a vector$x$such that$||x||_{*} = \sqrt{n}||Ax||_2$. This is ... • 5,164 2 votes 0 answers 57 views ### Covariances not below$\Sigma\Sigma_0,\Sigma_1,\dots,\Sigma_K$are real covariance matrices. I’m interested in the set of matrices $$\bigcap_{k=1}^K \left\{x: 0 \preceq x \preceq \Sigma_0, \ x\not\prec\Sigma_k\right\}.$$ I’m ... • 4,886 3 votes 0 answers 135 views ### Improving Ellipsoid Theorem$t+\mathcal{E} \subseteq K \subset t + c\cdot n \mathcal{E}$Setting: Definition (ellipsoid): An ellipsoid is$\mathcal{E} := \{y \in \mathbb{R}^n : ||A^{-1}(y-t)|| \leq 1\}$, i.e images under a given$A$of full rank of the unit closed ball of$\mathbb{R}^n$. ... • 5,164 2 votes 1 answer 98 views ### How to deal with ill conditioned optimization problem (Sinkhorn barycenter) Problematic (Debiased Sinkhorn barycenter, proposed by H.Janti et al.): Let$\alpha_1, \ldots, \alpha_K \in \Delta_n$and$\mathbf{K}=e^{-\frac{\mathrm{C}}{\varepsilon}}$. Let$\pi$denote a sequence ... • 1,238 0 votes 0 answers 44 views ### Least Squares Function Approximation and Convexity of Functions I have been reading about Least Squares function approximation and am dealing with the following definition: Let$f$be continuous on$[a,b]$and let$W$be a finite dimensional subspace of$C[a,b]$. ... • 197 0 votes 0 answers 20 views ### Concave maximization over$d$-dimensional simplex. Can either an analytic solution or the dual be characterized for the following concave maximization:$v:= \underset{w \in \Delta_d}{\max} \sum^{d}_{i=1}\frac{1}{\sqrt{1+b_i/w_i}}$where$\Delta_d$... 1 vote 0 answers 60 views ### Prove$f(x)=\log\left(\frac{1-x^a}{1-x}\right)$is convex Prove that$f(x)=\log\left(\frac{1-x^a}{1-x}\right)$,$x\in (0,1)$is convex for$a\geq 5. I've tried with the classical characterization of convex functions: $$f(\theta x + (1-\theta)y) \leq \theta ... 0 votes 0 answers 15 views ### SOCP and polynomial time constraints Given a multi-variable function f to minimize subject to some constraints, I am confused after reading few papers and the Wikipedia entry about SOCP(second order cone programming). I already know ... -1 votes 2 answers 38 views ### Suspicious function for calculating cardinality via \ell_0 norm [duplicate] I'm confused about a function for calculating a vector's cardinality via the \ell_0 norm as described in an "Optimization Models" textbook (ISBN: 9781107050877). Here's a photo of that ... 0 votes 1 answer 24 views ### Orthogonal Projection onto a Polyhedron (Matrix Inequality) How to efficiently solve:$$\begin{align*} \arg \min_{\boldsymbol{X}} \quad & \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} \\ \text{subject to} \quad & \begin{aligned}... • 8,984 0 votes 0 answers 17 views ### Counter-example request: set such that bilinear optimisation against ellipsoid is hard I'm reviewing a paper that has a pretty obvious false claim, but I'm really blanking on a simple counterexample. The claim is that for anyX$subset of the closed Euclidean$n$-dimensional unit ball ... • 266 0 votes 0 answers 18 views ### PCA with two subspace Given$N$data points$[a_1,\dots,a_N]$, mathematically the PCA is to find a rank-r subspace$S$such that the distances between these points and the subspace are minimized, i.e., S = ... • 145 1 vote 2 answers 48 views ### Orthogonal Projection onto the Convex Hull of Permutation Matrix Given a matrix$\boldsymbol{Y} \in \mathbb{R}^{m \times n}$where$n \leq m$. I want to find its projection onto the Convex Hull of Permutation Matrices: $$\mathcal{P} = \left\{ \boldsymbol{P} \mid \... • 8,984 1 vote 2 answers 57 views ### Is X \mapsto \operatorname{tr}( DXAX^TD^T - DXCD - DC^TX^TD) a convex function? I know that g \left( X \right) = \operatorname{tr}( XAX^T - XC - C^TX^T ) is a convex function. Is h \left( X \right) = \operatorname{tr}( DXAX^TD^T - DXCD - DC^TX^TD ) still a convex function？ ... • 365 1 vote 0 answers 58 views ### How to set up a convex concave procedure for the minimization of abc? From this post, it seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure. Out of curiosity, suppose that I have a simple problem that is \begin{... 0 votes 2 answers 63 views ### How to show that the set M = \{ (x,y) \mid x + 4y^2 \leq 4 \} is convex? I need to show that the following set is convex using the definition: M = \{ (x,y) \mid x + 4y^2 \leq 4 \} . I have considered 2 points: (x_1, y_1) \in M , (x_2, y_2) \in M . Then, we have ... • 15 0 votes 1 answer 21 views ### How to bound scalarized gradient difference norm in terms of smoothness in convex optimization? We know if a convex function is \mu-smooth, the following inequality is true: \| \nabla g (u) - \nabla g(v) \| \leq \mu \|u-v\| I want to derive an bound for the following slightly different term ... • 145 0 votes 1 answer 30 views ### Sundaram Theorem 8.5 I have one question about this theorem. I do not understand the part after "In particular," in the picture. I assume that any monotone transformation'' means that this includes ... • 36 0 votes 0 answers 30 views ### Incremental algorithm for 2D Linear Programming question for feasible points I have the following problem that I want to solve using linear programming: \max\{-3x+12y\} (objective function) and 4 contraints: -x+2y\leq-1, 2x-3y \leq 6, x-3y \leq 0, x+y\leq12 I start ... 1 vote 1 answer 145 views ### A hard optimization problem Consider the following function, for 1\leq j \leq N$$\tag{1} y_j=\sum_{k=0}^{M} \frac{e^{-\sum_{|i|\leq k}(k-|i|)x_{j+i}/v}-e^{-\sum_{|i|\leq k}(k+1-|i|)x_{j+i}/v}}{\sum_{|i|\leq k} x_{j+i}} $$for ... • 3,435 0 votes 0 answers 25 views ### Questions relating to the definition of the Frechet derivative My knowledge in multivarible calculas or real analysis is very limited. Please excuse the possibly ill-posed question and the use of intuivive explanation. Thanks for your understanding. As I ... • 187 1 vote 1 answer 45 views ### Lattice width of conv(0,ne_1,\cdots,n e_n) Given a subset K \subseteq \mathbb{R}^n we define the lattice width of K :$$\omega(K) = \min_{d\in \mathbb{Z}^n - \{0\}} \max_{x,y \in K} d^t(x-y)$$With$K = conv(0,ne_1,\cdots,n e_n)$how to ... • 5,164 4 votes 1 answer 112 views ### Conceptual difference between regularized and constrained optimization. In the literature of compressed sensing, one encounters optimization problems as shown in equation (1) and (2). focusing on the conceptual differences between regularized optimization and constrained ... • 297 3 votes 1 answer 107 views ### Efficient algorithm to solve a sparse recovery problem I come across with a problem of the form$y=Hx + z \in \mathbb{R}^m$, where$z\in \mathbb{R}^m$is the noise vector, and$x \in \mathbb{R}^N$is partially known.$H\in \mathbb{R}^{m \times N}$can be ... • 657 2 votes 3 answers 102 views ### Is$C = \{ x \in \mathbb{R}^n \:|\: \textbf{1}^T(x)_- \leq \frac{1}{2}\textbf{1}^T(x)_+ \}$a convex set? We define$(x)_+ = \textbf{max}\{0, x\}$and$(x)_- = \textbf{max}\{0, -x\}$, so$x = (x)_+ - (x)_-$. Let$\textbf{1} \in \mathbb{R}^n$be a column vector whose entries are$1$. The$\textbf{max}$... • 23 1 vote 1 answer 67 views ### Convexity of$\ln(a^\top x) - \sum_{i=1}^n \ln(x_i) $Given$f:\mathbb{R}^n_{>0}\rightarrow \mathbb{R}$, defined as$f(x)=ln(a^\top x) - \sum_{i=1}^n \ln(x_i)$, for all$x \in \mathbb{R}^n_{>0}$, where also$a\in \mathbb{R}^n_{>0}$. Is the ... • 126 1 vote 0 answers 18 views ### Expectation value given a convex order I want to know if the following proof is correct. Let$M,N$and$X$be random variables. If the following inequality holds for any concave non-decreasing function$u$\mathbb{E}[u(N)]\... • 366 4 votes 0 answers 33 views ### Existence and Uniqueness of Equilibrium points for Concave N-Person Games I am reading a paper. I have a problems with understanding their lemma Lemma: The nonzero elements of every vector$u \in U(x)$are given by a vector$\bar{u} \in E^k, \bar{k} \leqslant k$, where$\...
• 431
1 vote
In context of convex optimization the slack variable $\vec{s} \ge 0$ can be used to convert inequality $A \vec{x} \le \vec{b}$ to the equality $A \vec{x} + \vec{s}= \vec{b}$. Now in wikipedia is ...