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
2
votes
1 answer

Is this necessarily true for a convex function?

$$\sum_{s \in V} \lambda_sf(s) \geq f(\sum_{s \in V} s\lambda_s)$$ $V$ is a set of points and corresponding to each point in $V$, there is a $\lambda_s$ which is a scalar so $\sum_{s \in V} s\lambda_s$ is basically another point in the space, which…
AnkurVijay
  • 647
2
votes
1 answer

Karush-Kuhn-Tucker (KKT) conditions

I am having difficulties understanding the graphical interpretation as well as why the two following KKT conditions is necessary for a point x* being a minimum. It is my understanding that the (d) conditions is also known as complementary slackness…
Morten
2
votes
0 answers

Tractability of a cardinality problem

I have this confusion related to the convexity and tractability of a problem. The given problem is maximize $u^TSu$ subject to $||u||_2 = 1$ and card(u) <= r This is a NP hard problem because of the combinatorial nature of the cardinality. Then…
user34790
  • 4,192
2
votes
1 answer

establish that a minimization problem is indeed a convex minimization problem and then solve it

I have a minimization problem of the following form : $$\underset{\lambda (x) \in [0,1]}{min} \int_\Omega (1- \lambda(x))C_s(x)dx + \int_\Omega \lambda(x)C_t(x)dx + \alpha\int_\Omega |\nabla\lambda(x)|dx$$ $ \Omega$ is a region in $\mathbb{R}^2$ (…
AnkurVijay
  • 647
2
votes
0 answers

How to prove logistic function $h(x) = \log(1 + e^x)$ as a function h : R → R, the minimizer of h is at infinity.

How to rigorously prove thar $h(x) = \log(1 + e^x)$ has minimum at $-\infty$? I have tried taking the derivative of which comes $\frac{e^x}{1+e^x}=0\implies e^x=0$. This can only happen if $x\rightarrow -\infty$ also since it is a monotonically…
james
  • 21
2
votes
2 answers

Why does Carathéodory's theorem for $C\subset\mathbb R^n$ hold for $k\le n+1$?

Carathéodory's theorem says "If $C\subset R^n$, then every point from ${\rm conv}\; C$ can be expressed as a convex combination at the most of $n+1$ elements from $C$" In every proof I found, it say that it holds for $k\leq n+1$ elements from C.…
user23709
  • 759
2
votes
1 answer

Is the following optimization problem convex?

I'm not an mathematician so sorry for the possibly trivial question. I have written the following integer programming model: \begin{align} \max z &= \sum_{i=1}^M \left(\sum_{j=1}^N b_j x_{ij}- c_i y_{i}\right)\\ \text{s.t.} & \sum_{j=1}^N…
seg.fault
  • 153
2
votes
1 answer

Convex hull of an open set is an open set

I have to prove this. Actually, I have the proof, but I don't understand one part. It says: "Since $\operatorname{co}A$ is intersect of all convex sets that contain set A, it follows that $\operatorname{co}A\subset (\operatorname{co}A)^\circ$".
user23709
  • 759
2
votes
4 answers

Convex set. Proof.

Prove that if A is convex set and $\alpha, \beta ≥ 0$ then $(\alpha + \beta)A = \alpha A + \beta A$ What came first on my mind is that I have to show that $(\alpha + \beta)A\subset \alpha A + \beta A$ and $\alpha A + \beta A\subset (\alpha +…
user23709
  • 759
2
votes
0 answers

Expressing Sinkhorn algorithm as a mirror descent on its dual function

The Question Sinkhorn algorithm solves the entropy regularized optimal transport problem. The primal problem is $$min\langle C,X\rangle-H(X), s.t. X1_{n}=r, X^{T}1_{n}=c$$ where $H(X)$ is the entropy of $X$. The dual problem of it is Sinkhorn…
Hanyang
  • 21
  • 1
2
votes
1 answer

Is the following problem convex?

I think the following problem is convex (due to the results of some simulations), but I am not sure: $min_x||e^{(Ax)}-b||^2_2$ s.t. x>0 where $A$ is m x n, $x$ is n x 1, and b is m x 1. $A,x,b$ are all real. The exponent of a vector means taking the…
Bitwise
  • 1,216
2
votes
2 answers

Why is the hessian of strictly convex quadratic functions positive definite?

Quadratic functions are of the form: $$f(x)=b^Tx+\frac{1}{2}x^TCx$$ where $C$ is assumed without loss of generality to be symmetric. Tried to prove it myself using contradiction but I didn't find a valid argument.
wostysums
  • 167
2
votes
1 answer

Lp Norm Conjugacy

$f(\mathbf{x}) = \frac{1}{p}\sum_{i=1}^n |x_i|^p$, for $1 < p < \infty$. Find the conjugate of $f$, $f^*$. My attempt: \begin{align} f^*(y) &= sup_{x \in \mathbb{R}^n} \{y^\intercal x - \frac{1}{p}\sum_{i=1}^n |x_i|^p\}\\ &= sup_{x \in \mathbb{R}^n}…
Marwin
  • 39
2
votes
0 answers

seeking explanation of given solution to this optimization problem

Trying to parse this solution $$ \text{minimize} \sum_{i = 1} ^ r (\sigma_i x_i - b_i)^2 + \sum_{i = r + 1}^m b_i^2\\ \text{subject to } \sum_{i = 1}^n x_i^2 = \gamma $$ Convex Optimization by Boyd offers this solution : "Although the problem is…
Frank
  • 880
2
votes
0 answers

Maximizing an inner-product over a convex set.

Let $x \in \mathbb{R}^N$ and let $K$ be a closed convex set in $\mathbb{R}^n$. Let $$ \widehat{y} = \textrm{arg} \, \textrm{max} _{\,\,y \in K} \langle x,y \rangle,$$ where $\langle \cdot, \cdot \rangle$ denotes the usual inner-product. A) Provide…
user67350
  • 21
1 2 3
…
24 25