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

learn more… | top users | synonyms

6
votes
0answers
281 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
179 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
153 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
172 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
266 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
95 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
90 views

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 ...
4
votes
0answers
254 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 ...
4
votes
0answers
111 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
39 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
3
votes
0answers
102 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
93 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
189 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
222 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

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
2
votes
0answers
48 views

Complexity analysis of convex optimization problem

I am studying an optimization problem \begin{equation} \mathbf{x}^*=\text{argmax}\quad\sum_{d=1}^{D}\log(\mathbf{a}_d^T\mathbf{x}+b)+\mathbf{c}_d^T\mathbf{x}+f_d\\ \text{subject to}\quad ...
2
votes
0answers
38 views

Solve the linear program

Please help to solve this problem. I am new to this type of problems and any help will be greatly appreciated $$\text{ Minimize } 7x-5y+3z$$ $$\text{ Such that } \ \ \ 0 ≤ x ≤ 6 , -2 ≤ y ≤ 7 , -4 ...
2
votes
0answers
27 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
69 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
32 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
74 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
66 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
48 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
67 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
95 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
54 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
24 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
79 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
57 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
184 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
68 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
288 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
156 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
33 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
65 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
83 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
112 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
125 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
38 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
59 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
60 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
229 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
88 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
71 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
609 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 ...
2
votes
0answers
288 views

real-time linear programming

I'm going to implement in C a light-weight embedded lp-solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programming problems with ~6-60 ...
1
vote
0answers
44 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
0answers
19 views

Lagrange multipliers for minimax optimization

Does the equally constrained minimax optimization can be solved by using Lagrange multiplier method? Thanks in advance.