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

Polyhedron question

Below is a property of polyhedron, which refers to when shrinking the dimension of a polyhedron down, it is still a polyhedron: \begin{equation} \label{eq:poly_proj} P \subseteq \mathbb{R}^{m+n} \text{ is a polyhedron} \; \Rightarrow \; \{x\in…
good2know
  • 665
0
votes
1 answer

Solution set of a linear matrix inequality is the inverse image of the positive semidefinite cone under an affine transformation

Consider the following matrix inequality: $A(x) = x_1A_1 + x_2A_2 + \dots + x_nA_n \preceq B$. In Stephen Boyd's book on convex optimization, it is mentioned that the solution set of the above matrix inequality, $\{x \mid A(x) \preceq B \}$, is the…
niranjantdesai
  • 57
0
votes
1 answer

Reducing LASSO problem size on the fly with TFOCS

Suppose I'm using the TFOCS software package to solve the LASSO problem \begin{equation*} \text{minimize} \quad \frac12 \| Ax - b \|_2^2 + \gamma \| x \|_1. \end{equation*} The optimization variable is $x \in \mathbb R^n$, and the optimal value…
littleO
  • 51,938
0
votes
1 answer

To what extent can the column generation method for solving linear programs be extended to solving more general convex optimization problems?

Are there column generation approaches to solving classes of convex optimization problems other than LPs, and are they guaranteed to find a global minimizer?
littleO
  • 51,938
0
votes
0 answers

Transform a nonconvex problem into a convex problem using perspective function

Suppose I have the problem $$ \text{minimize } f_0(x)\\ \text{subject to } tf_1(x) \leq r $$ with variables $t,x \in \mathbb{R}$ and $f_0, f_1$ are convex. The constraint is not convex, so I was thinking using a variable $y = t*x$ then I can write…
user90593
  • 861
0
votes
1 answer

Convex function and convex optimization

I would like to ask something about convex function and convex model. For example, the function $f(x,y)=\frac{x^2}{y}$ is convex when $x\geqslant0$ and $y>0$. For a convex model (minimization), the constraints must satisfy $$g(x)\leqslant0$$ where…
Dylan Lan
  • 327
  • 1
  • 2
  • 9
0
votes
2 answers

Is the constraint $xy\leqslant 0.001$ convex?

I would like to ask whether the constraint $xy\leqslant 0.001$ ($x,y\geqslant0$) is convex. Since its Hessian matrix is positive semi-definite for $x,y\geqslant0$, the constraint $xy\leqslant 0.001$ ($x,y\geqslant0$) is convex. Is it correct?
Dylan Lan
  • 327
  • 1
  • 2
  • 9
0
votes
1 answer

Brief explaination on convex optimization problem

I have following type optimization problem (I transformed original max-min problem into this kind), and I can show that all $g_1(l_1),\cdots,g_M(l_1,\cdots,l_M)$ functions are concave. $$\max_{\substack{l_1 \in [0, 1],\cdots,l_{M} \in [0,1]}}…
Frey
  • 1,103
0
votes
2 answers

Finding the optimal value in an optimization problem

Given the optimization problem $$\text{minimize}\ f_0(x_1,x_2)$$ $$\text{subject to}\ 2x_1+x_2 \ge 1$$ $$x_1+3x_2 \ge 1$$ $$x_1 \ge 0, x_2 \ge 0$$ Let the objective function be $f_0(x_1,x_2) = x_1^2 + 9x_2^2$. What is the optimal value? I sketched…
Rayne
  • 331
0
votes
1 answer

Weighted sum does not necessarily conserve convexity

Does anyone know a counterexample to show that a weighted sum of convex sets is not necessarily convex, unless our coefficients are positive? A weighted sum for me is defined as: $$\alpha C_1 + \beta C_2 = \{ y : y = \alpha x_1 + \beta x_2, x_1 \in…
Rellek
  • 103
0
votes
1 answer

Tracking a vehicle moving with uniform velocity?

Suppose there are three cell towers at three positions $P_1$, $P_2$ and $P_3$. A vehicle is moving at uniform speed along a straight line. Three towers are pinging the vehicle at certain time and obtaining its distance (e.g., at time…
Sudipta Roy
  • 779
0
votes
1 answer

Is $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ concave?

I want to maximize the capacity function $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ with respect to $F$, subject to the constraints: (1) $\operatorname{trace} F \le Pt$ (2) $\operatorname{trace} G F \bar G \le Ith$ such that: $F$,…
omaralomari
  • 13
0
votes
1 answer

Affine hull smallest affine space

I would like to prove the following statement: "The affine hull is the smallest affine space containing $S$, where $S$ is an arbitrary set". I think the proof is rather trivial, but I cannot find it.
Mavlast
  • 15
0
votes
1 answer

Convex set - in $\mathbb{R}^3$

I need to prove $2$ sets, i hope you could help me: $x^2+y^2\leq z^2$ Is that a convex set? $S: 0\leq x_1\leq x_2\leq \cdots\leq x_n.$ I think about sum of convex sets - but not sure. So i woild say it is convex. Could anyone help?
Math_reald
  • 1,317
0
votes
2 answers

How can I know this simple quadratic function is a convex function?

Sorry.I don't know enough about convex optimization. How can I know this function for the $\theta$ vector $(\theta_0+\theta_1x_1+\theta_2x_2-y_0)^2$ is a convex function? The other variables are arbitrary constants. Thanks in advance.
cloudygoose
  • 183
1 2 3
…
24 25