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
1
vote
1 answer

Closed form solution of a convex optimization problem

Suppose we want to solve the following optimization problem: \begin{equation*} \begin{aligned} & \underset{x,y,z}{\text{minimize}} && x(a-y) \\ & \text{subject to} && (1-x)f(z)+xf(y)=b \end{aligned} \end{equation*} where $0 \leq x \leq 1$, $0 \leq z…
Richie
  • 891
1
vote
1 answer

Calculating the Fenchel Conjugate

I know this might seem as a simple question, but I just hope that I can learn how would people normally approach this question? Thanks in advance! Compute the Fenchel conjugate of the following function: $f(x) = e^x, x \in \Bbb R$ The Fenchel…
Kayla
  • 31
1
vote
1 answer

Function on interval

I am having trouble with a question, just hope that someone out there is kind enough to help me with it. Thanks in advance!! Suppose $f := \Bbb R^n \rightarrow \Bbb R$ is continuous, and $f$ has the following properties: (i) $f(x) \ge 1$ for all $x$…
Kayla
  • 31
1
vote
1 answer

What is the conjugate function of products?

Suppose I have following function $f(x) = \pi_{i=1}^nx_i$, that is the function is product of all $x_i$. For example, in 2d case, $f(x) = x_1x_2$. I am just wondering whether anyone can help me find the conjugate function of it. calculating…
user3086871
  • 287
1
vote
1 answer

How to prove this function is quasi-convex/concave?

this is the function: $$\displaystyle f(a,b) = \frac{b^2}{4(1+a)}$$
Amir Vahiti
  • 11
1
vote
0 answers

Proving that the maximizer of the product function in a convex set dominates the midpoint of that set

Let $S\in\mathbb{R}^n$ be a convex set containing the zero vector $(0,...,0)$, and assume that for all $i=1,...,n$ $$\max_{x\in S\cap\mathbb{R}^{n}_{+}}x_{i}=1.$$ To prove is then that $$\arg\max_{x\in…
Orosius
  • 33
1
vote
0 answers

Maximum volume inscribed ellipsoid of given aspect ratio

It is well know (see Boyd & Vandenberghe's Convex Optimization, Sec. 8.4.2) that the maximum volume ellipsoid inscribed in a given convex polytope in $\cal{H}$-form can be computed by solving the Semi-Definite-Program $\mbox{max} \qquad \log \det…
Arrigo Benedetti
  • 280
1
vote
2 answers

Affine dimension of a simplex

In Stephen Boyd's book on Convex optimization he points out that k+1 affinely independent points form a simplex with affine dimension k. My understanding of affinely independent points is that no 3 points are in a line. So if I take 4 points no 3 of…
Shirin
  • 465
1
vote
1 answer

Max Cut: Form of Graph Laplacian?

In my convex optimization notes, it defines the max cut problem as $$\max_{x\in\Bbb{R}^n} \hspace{.1 in} x^TL_Gx\hspace{.5 in} \text{subject to}\ \ x_i\in \{-1,1\},\ i=1,\cdots,n$$ where $L_G$ is a matrix called the Laplacian of the graph $G$. In…
Dan
  • 575
1
vote
2 answers

Positive Second derivative and convexity

Let $f:\mathbb R\to\mathbb R$, maps a point $x \in \mathbb R$. $f$ is twice differentiable. Show that if second derivative is positive for all $x$ then $f$ is convex Is there anyway to prove this without using MVT/definitions of…
Alex
  • 11
1
vote
1 answer

optimization through matching

I have two sets of events (a, b) taking place at times $a_i$ and $b_j$, |a|=N, |b|=M, $N \geq M$. I now wish to find a subset $ \mathbf{a}^*$ of a consisting of M elements, such that $||a^*-b||$ is minimized (the norm is whatever choice makes this…
Kaare
  • 113
1
vote
1 answer

Convex Optimization - Derive Conjugate function

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's Convex Optimization book - Additional Exercise…
Johnnylin
  • 135
1
vote
1 answer

Vector perpendicular to level set of objective function

A constant level contour of an objective function $ \mathbb{R^n} \rightarrow \mathbb{R}$, corresponding to a given value c is the set: $$ F_c(c)= \{ x \in \mathbb{R}^n | f(x)=c \} $$ Given points $x_0, x_1 \in \mathbb{R}^n $ suppose that the…
Sanja
  • 15
1
vote
0 answers

Minimizing a linear function over the probability simplex

I am trying to derive the solution of the problem below but am having trouble This is my solution $L = c^Tx + v(1^Tx - 1) - \lambda^Tx \\ \ \ \ = (c + v1 - \lambda)^Tx - v $ The dual is thus $\min v \\ st. v1 = \lambda - c \\ \lambda \ge 0$ I dont…
Kong
  • 884
1
vote
1 answer

Solve a Convex optimization Problem which Involves Non Linear Constraints (Using $ \log \left( \cdot \right) $ Function)

I want to solve the following optimization problem $\text{min.}_{x,y}\ \sum_{i=1}^{N} x_i+\sum_{i=1}^{N} y_i$ subject to $\sum_{i=1}^{N}\log_2(1+a_{i}x_{i}) \geq A$ $\sum_{i=1}^{N} a_{i}y_{i}\geq B$ $x_{i}+y_{i}\leq c_{i}$ $x_{i} \geq0$…
user841315
  • 55
1 2 3
…
24 25