Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

6
votes
0answers
275 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)

As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
6
votes
0answers
171 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
5
votes
0answers
148 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
5
votes
0answers
168 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
4
votes
0answers
220 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
4
votes
0answers
92 views

On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has coordinate-wise Lipschitz constant $M$ (meaning that for all ...
4
votes
0answers
84 views

Primal-Dual pair in SDP

Let's we have a primal model like $\max~~ x + Z $ $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 ...
4
votes
0answers
108 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
3
votes
0answers
98 views

Does convexity of a function guarantee tractability of finding its minimum?

Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not. ...
3
votes
0answers
88 views

On the duality gap for quasiconvex optimisation problems

This stack exchange question got me thinking about quasiconvex analysis. Given a compact,convex subset $X\subset \mathbb{R}^n$ and a quasiconvex function $f:X\rightarrow \mathbb{R}$ Define the ...
3
votes
0answers
212 views

Convex analysis books and self study.

I have taken some courses in Convex optimization. Now I would like to know a little bit more about the pure mathematical side. Is there any good books in convex analysis? I have read and worked with ...
3
votes
0answers
187 views

How to show that a function is piecewise linear

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ Show that Z(t) is a concave, piecewise linear function of t. I'm really not sure how to even start proving this, I would really ...
3
votes
0answers
210 views

Global optimum of sum of convex functions

Take two real differentiable convex functions, $f_1$ and $f_2$, defined on the unit interval $[0; 1]$. I want to find the global optimum of: $\min_{x \in [0;1]} af_1(x)+bf_2(x)$, for given $a, b \in ...
2
votes
0answers
19 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
2
votes
0answers
66 views

How to prove the convexity of the logrithmic gamma function?

Here's what I did: $$\Gamma'(z)=\int_0^\infty \log(t)e^{-t}t^{z-1}dt$$ $$\Gamma''(z)=\int_0^\infty ...
2
votes
0answers
31 views

Strictly convex self-concordant function

Some definitions: A function $f:R^n\rightarrow R$ is convex[strictly convex] if for every $\lambda\in[0,1]$ [$\lambda\in(0,1)$] and for every $x,y$ [$x\neq y$] in $R^n$ we have $f(\lambda ...
2
votes
0answers
31 views

Semidefinite Program formulation

I have the following problem and would like to formulate that as an SDP. I am not sure how to approach this : A set $S$ is given such that : $$ S = \{P \in R^{n \times m} : ||p_i - c_i|| \leq d_i ...
2
votes
0answers
69 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
2
votes
0answers
62 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
2
votes
0answers
46 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
2
votes
0answers
65 views

How to get the minimum and maximum of one convex function?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The Lagrangian function of $Q$ is $\mathcal{L} = h^H(\hat{f} + e)(\hat{f} + e)^Hh + ...
2
votes
0answers
94 views

The most efficient algorithm to solve the following problem

Is there an efficient optimization algorithm to solve the following problem? $(\alpha,\beta,\gamma,\cdots) =$ argmax $\sum_{i}\log(\alpha a_i+\beta b_i+\gamma c_i+\cdots)$, s.t. ...
2
votes
0answers
53 views

Proving an optimization problem has a rational optimum.

Consider the function $$ J_\gamma(X) = \det\left( I - \tfrac{1}{\gamma^2} (A+BXC)^\mathsf{T}(A+BXC)\right) $$ where $A$, $B$, $C$, $X$ are matrices of real numbers. Further suppose that ...
2
votes
0answers
21 views

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 ...
2
votes
0answers
74 views

are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on ...
2
votes
0answers
56 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
0answers
20 views

Analogue of Helly’s theorem for non-exact interpolation

Let $\overrightarrow{x}=(x_1,x_2, \ldots ,x_n),\overrightarrow{a}=(a_1,a_2, \ldots ,a_n)$ and $\overrightarrow{b}=(b_1,b_2, \ldots ,b_n)$ be vectors in ${\mathbb R}^n$, with $a_k \leq b_k$ for every ...
2
votes
0answers
182 views

$\{x:Ax\leq 0\}$ contains a subset of type $\{x:A'x=0, ax\leq 0\}$

If $C:=\{x:Ax\leq 0\}\neq\{x:Ax=0\}$, an independent set of rows of $A$ can be chosen, one denoted by $a$ and the others put as rows into a matrix $A'$, such that $\{x:A'x=0,ax\leq 0\}\subseteq C$. ...
2
votes
0answers
64 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
2
votes
0answers
257 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...
2
votes
0answers
155 views

Optimization problem about large matrices

I'd like to solve the following optimization problem: Find non-negative scalar $a$, $b$, $c$ to minimize $\| (D-(aA+bB+cC+D^{-1})^{-1})y\|^2+2\operatorname{trace}((aA+bB+cC+D^{-1})^{-1})$ where ...
2
votes
0answers
31 views

Convex formulation of a nearly convex optimization problem

The following problem has come up in my studies of logarithmic norms. I wish to find $\mu \in \mathbb{R}$ and a positive semidefinite $B$ so as to minimize the convex function $c \mu - \log\det(B)$ ...
2
votes
0answers
64 views

the dual of the dual is the primal?

Consider a convex optimization problem (call it $P$). Consider its dual (call it $D$). Is it true that the dual of $D$ is $P$? For linear programming, it is true. I'd just like to know under which ...
2
votes
0answers
79 views

Examples of functions that are Lipschitz w.r.t. Schatten p-norm?

A convex function $f$ is $R$-Lipschitz w.r.t. to a norm $\|\cdot\|$ if for all points $a, b$ we have $|f(a)-f(b)| \leq R\|a-b\|$. For a real symmetric $n\times n$ matrix $A$ with eigenvalues denoted ...
2
votes
0answers
107 views

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 ...
2
votes
0answers
120 views

Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this. Read ...
2
votes
0answers
31 views

convex optimization with inconsistent constraints

If you have a problem in convex optimization where all $N$ constraints ($N >> 0$) yield no possible solution but you are able to rank, or weight the constraint in terms of their importance are ...
2
votes
0answers
58 views

Convexity of a function

Suppose we have $F: R^n \longrightarrow R$ , $P: R^n \longrightarrow R^n$ and $G: R^n \longrightarrow R$ all nice- let's say given by polynomial and $P$ is invertible - such that $F(x) =G( P(x) )$. ...
2
votes
0answers
58 views

Prove that $\text{int}(\text{dom}(f))$ is a convex set.

Let $f$ be a convex function. I have to prove that $\text{int}(\text{dom}(f))$ is a convex set. (Be careful with $-∞$ )
2
votes
0answers
212 views

sufficient condition for KKT problems

For the Karush-Kuhn Tucker optimsation problem, Wikipedia notes that: "The necessary conditions are sufficient for optimality if the objective function f and the inequality constraints g_j are ...
2
votes
0answers
84 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
2
votes
0answers
70 views

Find a vector such that its matrix product is positive in every element

Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
2
votes
0answers
567 views

Convex minimization over the Unit Simplex

I have a simple (few variables), continuous, twice differentiable convex function that I wish to minimize over the unit simplex. In other words, $\min. f(\mathbf{x})$, $\text{s.t. } \mathbf{0} \preceq ...
1
vote
0answers
21 views

Confusion related to proximal newton method

I was reading this method related to proximal newton methods http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf. I came across this page I didn't get what this part means $ ...
1
vote
0answers
16 views

First order necessary conditions for nondifferentiable nonconvex minimization problem

I am interested in first order necessary conditions for the following minimization problem where the function $f$ is continuous, nondecreasing and concave, with $f(0)=0$, but not necessarily ...
1
vote
0answers
78 views

Maximize the maximum Eigenvalue under a diagonally constrained matrix

Suppose we have $N\times N$ Hermitian matrix $\mathbf{A}$ I want to find the real $N\times N$ diagonal matrix $\mathbf{D}$ that maximizes the sum of the maximum Eigenvalues : $\mathbf{D}=\arg\max ...
1
vote
0answers
27 views

Infinity norm minimization

I am wondering how to minimize an objective function of the following form: $$\min_{\mathbf{x}\in\mathcal{R}^{MN}} \|\mathbf{x}-\mathbf{y}\|_\infty + \lambda\mathrm{TV}(\mathbf{x})$$ Here, ...
1
vote
0answers
21 views

Interpreting constraints in an optimization problem

I am working on an optimization-based image denoising project in which I have three "flavors" of an optimization problem, one constrained and two unconstrained. They are given as follows: ...
1
vote
0answers
30 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
1
vote
0answers
19 views

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, ...