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

Confusion related to proximal mapping

I was reading this paper http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf and I came across this part I didn't get how the third line came from the second line. Any suggestions?
user12331
  • 299
0
votes
1 answer

Convex min proof.

Suppose $f$ is convex and $x^*$ is a minimizer, and $x^* \in [a,b]$, and let $c,d$ be values such that $a < c < d < b$. Then i) $f(c) \leq f(d) \implies x^* \in [a,d]$ ii) $f(c) = f(d) \implies x^* \in [c,d]$ I am having trouble proving (i), here…
Lemon
  • 12,664
0
votes
1 answer

How to realize $\lambda_{max}(X)$ is convex?

How to realize is convex (f is convex) X is symmetric. (S.Boyd's book p.82, Example 3.10) It is easy to undertand like f = x^2 is convex; however, it is a bit hard for me to understand this function. Thanks
sleeve chen
  • 8,281
0
votes
1 answer

Normal vector of a Hyperplane

I'm reading convex optimization by Boyd and I have a problem with normal of a hyperplane how many normal can we assume for a hyperplane at just one point? is it true that we can assume many vectors with different length (and all of them can be…
eHH
  • 463
  • 1
  • 4
  • 14
0
votes
1 answer

A question on convex

I am thinking about this without solutions. I would like you to give hints. Let $Q$ be a polyhedron with $Q=convex.hull (X)$ for some $X \subset R^n$. Let $E$ be a face of $Q$. Prove that $E \cap X \ne \empty$ and that $E=convex.hull (E \cap…
user130121
  • 1
0
votes
1 answer

Is this a valid transformation?

I have the following objective: \begin{equation} \max_{\mathcal{I}} \sum_{m=1}^{M}w_m\sum_{n \in N_m}^{ }I_{m}^{n} \end{equation} subject to some constraints, beside tha fact that the variables $I_{m}^{n} \in \mathcal{I}$ and $I_{m}^{n} \geq 0$ and…
Amr
  • 73
0
votes
2 answers

Concave function applied to equally distant points

Is the next statement true? Let $f$ be concave and $a \leq b \in dom(f)$. For any $c \geq 0$ such that $a+c, b+c \in dom(f)$ then $$ f(b+c) - f(b) \leq f(a+c) - f(a) $$ If it is, how would you prove it?
htellez
  • 103
0
votes
1 answer

Show that diagonal of a square is not a face

Let C be a convex set in $R^n$. We say that F is a face of C if the following condition holds: if $x_1, x_2 \in C$ and $(1-\lambda)x_1+\lambda x_2 \in F$ for some $0\lt \lambda \lt 1$ then $x_1, x_2 \in F$ Based on this definition, how can we show…
dresden
  • 1,073
  • 2
  • 11
  • 19
0
votes
1 answer

Concavity of a function that is obtained from another concave function

Let $f(x):[0,1]\rightarrow \mathbb{R}$ be a strictly concave function such that $f(0)=f(1)=0$. Let $x^*$ denote the maximizer of $f(x)$. For any value $x\in[0,x^*)$, there exists exactly one other point $y\in[x^*,1]$ such that $f(x)=f(y)$. Let $y$…
Morgan Imbertson
0
votes
2 answers

Optimization issues with positive definite constraints

I have an optimization problem where I have to optimize a function f(A) where A is a matrix(sparse). Like A = \begin{array}{cccc} A_1 & A_0 & A_0 & 0 \\ A_0 & A_2 & 0 & A_0 \\ A_0 & 0 & A_3 & A_0 \\ 0 & A_0 & A_0 & A_4 \\ \end{array} A is a…
user34790
  • 4,192
0
votes
0 answers

Confusion related to a function used for optimization

I have a function $f(x)$, such that at point $x'$, it attains its minimum value, but the gradient at this point $x'$ is not equal to $0$. On the other hand the function $f(x)$ has slightly higher value at point $x''$ but the gradient at this point…
user34790
  • 4,192
0
votes
1 answer

Square of 2-norm

This might be silly but how would I solve the following equation for $x$? $$ \left\| Y - \frac{Z_i}{x} \right\|^2_2 = 2t $$
John
  • 333
0
votes
1 answer

Maximize Trace with Lyapunov inequality as constraint

Let $C$ be a given symmetric matrix, $A$ be a given Hurwitz matrix and $X$ be a symmetric positive definite matrix. Is the following problem solvable to give unique, optimal $X$? max $tr (CX)$ subject to $AX + XA^T<0$ and $X>0$
Lyapunov123
  • 71
0
votes
1 answer

Confusion related to Armijo's rule

I am having confusion related to Armijo's rule used for line search. Can you give me some links to good tutorials. I want to get the geometric interpretation behind it. I found this one…
user34790
  • 4,192
0
votes
1 answer

Proofs regarding convex sets

I need assistance with the following proofs. I am not sure how to prove that one set is contained in another set. Here are the things required to be proven: Let $S$, $S_1$ and $S_2$ be non–empty sets in $R_n$. $ S^*$ = {$p|p^Tx \leq 0, \forall x…
Natalie
  • 309
1 2 3
…
24 25