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

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in D} \{y^Tx - f(x)\}$$ is $y \succeq 0$ since the…
Michael Nguyen
  • 63
5
votes
1 answer

minimization of sum of linear fractional functions

I have the following sum of fractional functions optimization problem $$ \begin{array}{l} \mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1} { {b_i}-{{\bf{a}}_i^T{\bf{x}} }}} \\ subject\,\,to:\,\,\,{\bf{x}} \in…
user51780
  • 361
5
votes
2 answers

Is f(x)=-log(x) a closed function?

I am reading Convex optimization written by Stephen Boyd. In page 640, there is an example said \begin{equation} f(x)=-log(x) \end{equation} is a closed function. But this function seems does not satisfy the definition of closed function in this…
BioCoder
  • 875
4
votes
1 answer

Convex optimization: interpretation of the dual variable

Let us consider the convex optimization problem $$ \tag{P} \underset{x\in\mathbb R^n}{\sf minimize} ~~ f(x) ~+~ g({\bf L}x) $$ where ${\bf L}\in\mathbb R^{m\times n}$. Using the convex conjugate, the corresponding dual problem can be written…
AndreasT
  • 3,772
4
votes
1 answer

What is a first and second order cone?

I am aware of the definition of a cone set $C$. $x_1, x_2 \in C$ and $\theta_1, \theta_2 \ge 0$ $$\theta_1x_1+\theta_2x_2 \in C$$ However, what is a first-order and second-order cone? Specifically, relating to second order cone programming, why do…
Rufus
  • 215
4
votes
2 answers

How to find projection to polyhedron

I have a problem: find $min||\overrightarrow{x}||$ where $A\overrightarrow{x} \leqslant \overrightarrow{b}$ Is it possible to get analytic solution? Or which iteration method should I use?
user1761982
  • 317
4
votes
0 answers

Primal-Dual pair in SDP

Let's we have a primal model like $\max~~ x + \langle I, Z \rangle$ $s.t. ~~~Ax + y I - Z \preceq B$ $~~~~~~~~~Z \succeq 0, ~X \geq 0, ~~y ~free$ where $A, B \in {\mathbb R^{n \times n}}$. The capital letters means they are in the matrix form and…
Royeh
  • 213
4
votes
1 answer

Proving ellipsoid A is a subset of ellipsoid B iff (B-A) is positive semi-definite

I am reading Boyd's Convex Optimization book and I am stuck on the reasoning behind one of the statements. Specifically, I am looking at page 45, line 3 from the bottom. The statement is: $A \preceq B \iff \mathcal{E}_A \subseteq…
jrand
  • 1,959
4
votes
1 answer

Convex optimization with non-convex objective function

Consider the following optimization problem: $$ \min_x \quad x^3 \quad \text{s.t.} \quad x\geq0 $$ We know that the objective function $x^3$ is not a convex function for $x\in\Re$. But we know that it is convex for $x\in\Re^+$ So my question is: Can…
Mohammadreza Barazesh
  • 41
4
votes
1 answer

Is a global optimal solution of a convex problem always unique?

I do not have a specific problem. Could a convex optimization problem (not strictly convex) have alternate solutions?
Larusso
  • 125
4
votes
1 answer

Logistic Regression is convex proof

I am trying to make sense of this paper qwone.com/~jason/writing/convexLR.pdf "Regularized Logistic Regression is Strictly Convex" by Jason D. M. Rennie. I am following the proof and formula (1) is a given: $$ -\ln(P(\vec{y}\mid X,\vec{w})) =…
user1064285
  • 83
3
votes
2 answers

Why is any subspace affine?

I am studying 'Convex Optimization' written by Stephen Boyd. I am confused by an assertion in the book(page 27). Any one can tell me why and give an explanation ? Any subspace is affine, and a convex cone (hence convex). --Convex Optimization
BioCoder
  • 875
3
votes
2 answers

Nonempty interior feature of a proper cone

One of the features of a proper cone is solid which means a proper cone has nonempty interior. What dose nonempty interior mean? I was reading Boyd convex optimization, and I saw this term "Nonempty interior" I don't know what it means.
eHH
  • 463
  • 1
  • 4
  • 14
3
votes
0 answers

Reference required for convergence analysis of an optimization problem

My objective function is quadratic in $\mathbf{a}$, which is vector version of matrix $\mathbf{A}$. But a rank-1 constrain i-e $\mathbf{A}=\mathbf{p}\mathbf{q}^{T}$ makes the problem nonconvex. However if I fix $\mathbf{p}$, the remaining problem…
NAASI
  • 997
3
votes
0 answers

How to minimize the supremum of two convex functions?

Given $f_1(x)$, $f_2(x)$, $x\in \mathbb{R}^d$, two convex functions, we define the following problem: $\underset{x\in C}{{\rm minimize}}\,{\rm max}\left(f_{1}\left(x\right),f_{2}\left(x\right)\right)$, where $C$ is a convex set. This problem should…
bernard
  • 31
1
2
3
…
24 25