Mathematics Stack Exchange
Mathematics Stack Exchange

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.

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
0
votes
1 answer

Second order condition for convexity

In Pr. Boyd's optimisation book, it is stated that for twice differentiable function $f$ with convex domain, $f$ is convex if and only if $\nabla^2f(x) \succcurlyeq 0$ for all $x \in dom f$. The point here is that the Hessian matrix should be…
Green Falcon
  • 109
0
votes
1 answer

Why this problem is not convex?

My problem looks like this: $$\min x^TAx$$ subject to: $$\|x\|_1 = 1$$ matrix $A$ is $n \times n $ positive semi-definite, $x$ is $n$ dimensional vector. Constraint is convex because every norm is. Function should also be convex because it is…
Kate
  • 191
0
votes
1 answer

proof that $\log(\det(XX^H))$ is not concave

Is there an elegant way to proof that $\log(\det(XX^H))$ is not concave, with respect to the complex-valued matrix elements of $X$?
user211673
  • 43
0
votes
1 answer

converting quadratic format

I have a mathematical model that looks like follows: minimize, $$J(x) = \sum_{i=1}^{n}(c_i.x)^2$$ where, $x \in \mathbb{R}^m$ and $c_i \in \mathbb{R}^m$ are constants. But the software I'm using (Gurobi) seem to be demanding the objective function…
PPGoodMan
  • 297
0
votes
1 answer

Prove support function $f$ is convex and show subgradient

Let S be a nonempty, bounded convex set in $\mathbb{R}^n$, and let $f: \mathbb{R}^n \to \mathbb{R} $ be defined as follows: $$ f(y) = \sup \{y^T x: x\in S\}. $$ The function $f$ is called the support function of S. Prove that $f$ is convex. Also,…
751495642
  • 1
0
votes
0 answers

sub differential calculation

I would like to use the sub gradient method on the rotated second order cone function: $f(x) = \partial\|Q^Tx\|_2^2$. So, I would like to find out what the sub differential $\partial f(x)$ is:
P. Khoza
  • 41
0
votes
0 answers

Find a finite set $S$ that a point in $S$ can be represented as convex combination of $n+1$ points in $S$

What kind of finite set that belongs to $\mathbb{R}^n$, with $P$ points $(P\geq n+1)$ satisfy both of the following conditions: There exist a set of $n+1$ points in $S$ such that every point in $\operatorname{Conv}(S)$ can be represented as a…
Alex
  • 1
0
votes
1 answer

Prove that $f(x+y) \ge f(x+ty)$, if $f(x+y)$ is concave function and $t>1$.

Let $f(x)$ be a concave function of many variables that we want to maximize $x=(x_1,x_2,\cdots,x_n)$ a point in its domain. Prove that if for some vector $y=(y_1,y_2,\cdots,y_n)$ we have that $f(x)\ge f(x+y)$ then for every number $t>1$, it holds…
Bill123
  • 3
0
votes
1 answer

Prove that strong convex $f(x) < \max \{f(a), f(b)\} \forall x \in (a, b)$

Given strongly convex $f(x)$ definded on $[a, b]$. I'm trying to prove that $\forall x \in (a, b)$ correct this strong inequality: $$f(x) < \max \{f(a), f(b) \}. $$ I can understand this fact on intuition level - from geometric side of convexity -…
taciturno
  • 480
0
votes
0 answers

cutting-plane method with equality constraint

I'm trying to use a cutting plane algorithm to minimize a convex objective and constraint. The constraint is an equality constraint, however, and the algorithm only specifies how to work with inequality constraints. Imagine the constraint to be…
Frank
  • 880
0
votes
1 answer

condition for nonexpansivity of a square matrix?

suppose $X=R^{n}$ and let $N \in R^{n \times n}$ be a matrix. Show that N is nonexpansive if and only if $\lambda_{max}(N^T N)\leq 1$. For showing nonexpansiveness we must show that $(\forall x \in X) (\forall y \in X) \hspace{5mm} ||Nx-Ny|| \leq…
Maria_Buffay
  • 25
0
votes
1 answer

Conjugate function

Q. Consider $f := \mathbb{R}^n → R$ defined by $$f(x) = 1/p |x_i|^p$$ for $1 < p < ∞$. Find $f^∗$ I came across other questions such as that of finding the conjugate of $f(x) = \frac{1}{2}||x||^2$. However, I am not really sure of whether it is…
eun ji
  • 51
0
votes
1 answer

Is the following formula convex or concave?

I have the formula using Frobenius norm as follows: $1 - \frac{\bigg\|\mathbf{a} - \frac{\sum_{m=1}^M m(x_{m} - x_{m-1})}{\gamma} \mathbf{b}\bigg\|_F}{\|\mathbf{a}\|_F}$, where $\mathbf{a}, \mathbf{b}, \gamma$ are constants, $x_0 = 0$, and $x_m,…
bnbfreak
  • 219
0
votes
1 answer

How to check the concavity of the following formula

I have a formula containing two squared root components as follows: $1 - \frac{\sqrt{\sum_{\forall i \in \mathcal{I}}\sum_{\forall j \in \mathcal{J}}(a_{ij} - b_{ij})^2}}{\sqrt{\sum_{\forall i \in \mathcal{I}}\sum_{\forall j \in…
bnbfreak
  • 219
0
votes
0 answers

How can I prove this equation to be concave?

$$ \sqrt[w]{x_{1}^{w_{1}} x_{2}^{w_{2}} \cdots x_{n}^{w_{n}}} $$ I am new in convex optimization, so I am confused to prove the equation. Given nonnegative parameters $w_i > 0$, $i=1, \ldots, n$ and $w = w_1 + \ldots + w_n$. Prove that the following…
jacksons
  • 1
1 2 3
…
24 25