Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

learn more… | top users | synonyms

0
votes
0answers
18 views

Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...
1
vote
0answers
23 views

Which algorithm is most efficient for a specific QP problem

I have a QP problem of the following kind: $\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$ s.t. $l\leq \alpha \leq u$ The matrix $M$ is symmetric and positive definite and of ...
1
vote
0answers
17 views

Concavity of maxima [closed]

Suppose we have the following optimization problem : $\min\limits_x kf(x) + g(x)$ where $f$ is a decreasing convex function in $x$ and $g$ is an increasing convex function. Can we say that $x^*$ is ...
4
votes
0answers
62 views

Designing Better “Temperature” for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing. For ...
4
votes
1answer
63 views

About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form ...
4
votes
0answers
129 views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & ...
1
vote
0answers
30 views

Minimum of sum of modulus [closed]

How can I evaluate the minimum of $$ \left|7x-1\right|+\left|7y-5\right|+\left|7z-1\right| $$ if $x,y,z$ are non negative reals such that $ x+y+z=1$ and $y^2 \le xz$? Is there a standard way to ...
2
votes
1answer
104 views

Global minimum of nonlinear least square

We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem: Minimize $J(x)=\Vert f(x)-z\Vert^2$ subject to box ...
1
vote
1answer
43 views

On optimizing a function whose projection and projected vector go through a linear transformation

Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...
0
votes
0answers
35 views

Bounds on the curvature of a sequence of convex functions

Let $\{f_n\}$ be a sequence of (real-valued) smooth convex functions on $[0,1]$, with $f_n(0) = f_n(1) = 0$ for all $n$. Let $t_n \in [0,1]$ be the minimizer of $f_n$ and assume that $M_n:= f_n(t_n) ...
-1
votes
1answer
48 views

Does element-wise concavity guarantee joint concavity?

I have a function of two variables, and I have checked that along one direction (fixing another variable), it is a monotonically increasing and concave function. Whereas in another direction (fixing ...
10
votes
2answers
280 views

More general than semidefinite program?

I was TAing my convex optimization class and explaining that Linear Programs are a special case of Second Order Cone Programs, which are themselves special cases of Semidefinite Programs. My question ...
0
votes
1answer
100 views

Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem. Does anyone know if the LPG is a convex ...
0
votes
0answers
43 views

Find optimal value for a regularization parameter in generalized eigenvalue problem

Consider the generalized eigenvalue problem : $ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $ where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices ...
0
votes
0answers
36 views

Nuclear norm maximization

I am trying to solve a nuclear norm maximization problem: $$\arg \max_{Q \in O(n)} \|WQV^T\|_*$$ where $Q$ is an $n \times n$ orthogonal matrix and $W$ and $V$ are real $d \times n$ matrices. I've ...
2
votes
1answer
246 views

Is this a log-concave function?

Let $(a_k)$ be a log-concave positive decreasing sequence. Is $\sum\limits_{k=1}^n a_k(1-e^x)^{k-1}$ log-concave in $x<0$, for each natural $n$?
1
vote
1answer
85 views

A bound on the number of bilinear functions needed in order to obtain the minmax

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$. Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...
0
votes
0answers
20 views

Bounding the error of the optimal solution from an approximated objective

Let $f$ be a smooth convex function defined in a bounded region $X$ and its Hessian is bounded $m I \le |\frac{\partial^2 f(x)}{\partial x^2}| \le M I$ for some $M>m>0$. Let $x^*=argmin_{x\in X} ...
0
votes
0answers
45 views

Question on solving an optimization problem using Variable splitting and ADMM

Tell me if I have found the right approach to the following optimization problem: $$ min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2 \\ s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0 $$ $A$ and $\Phi$ ...
1
vote
1answer
61 views

Envelope theorem for second derivative

I am maximizing a function $f(x,z)$ on $x$ ($z$ is treated a parameter in the maximization). The function $f$ is strictly concave on both variables. I know how to use the envelope theorem for the ...
1
vote
0answers
33 views

Is this QCQP convex or nonconvex

\begin{equation} \begin{split} \min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x \end{split} \end{equation} s.t. $$ g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\} $$ $$ ...
1
vote
0answers
72 views

Projecting on a a special polyhedron

Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron $$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$ Notice that $\mathcal P_X$ is symmetric about the origin. ...
1
vote
0answers
39 views

Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
5
votes
1answer
221 views

Minimize Frobenius norm

My question is the following: Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...
1
vote
0answers
35 views

convergence of unconstrained convex optimization

I encounter an optimization problem. The simplified version is like following: Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. ...
1
vote
2answers
63 views

Sensitivity analysis in minimum norm problems under a linear constraint

Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff. Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...
1
vote
0answers
45 views

Derivatives of Minkowski function?

Let $A\subset \mathbb R^n$ and $M$ be the convex hull of the set $A$, e.g., $M:=Conv(A)$. The Minkowski function on $M$ is defined as follows \begin{align*} &f: \mathbb R^n \to \mathbb R\\ ...
0
votes
0answers
59 views

Well-posedness of gradient flows

For a convex lower-semicontinuous functional on a Hilbert space $I\colon H\rightarrow\mathbb{R}$, it is shown in Evans' PDE that the Hilbert-space-valued ODE $$\begin{cases}\mathbf{u}'(t)\in-\partial ...
11
votes
1answer
304 views

Minimize sum of $\ell_2$ norm and linear combination, on simplex

Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
-1
votes
1answer
57 views

Convex Optimization in an Ellipsoid

Suppose we want to minimize a linear objective inside an ellipsoid that is, $\min _x l^Tx$ such that $(x - \mu)^TA(x - \mu) \leq \beta ^2$. Here, A is PSD and $\mu$ is a fixed vector. Can this be ...
0
votes
0answers
22 views

Maximizing modular function subject to supermodular constaint

I'm trying to solve a constrained optimization problem with submodular functions and get some nice properties of the solution. Unfortunately, I think I am in a setting where Topkis' theorem does not ...
3
votes
1answer
104 views

Finding a semigroup that maximizes the trace of a sum of matrices

Let $H$ be a finite semigroup containing $n$ elements from a compact group $G$. I am trying to solve $$\max_{h_i,\ h_j\ \in\ H} \operatorname{tr} \sum_{i,\ j\ \leq\ n} \rho(h_i^{-1} h_j)(A_j ...
0
votes
0answers
46 views

How to use the property of Frobenius norm in this proof?

Let $A \in \mathcal{S}^{n}$($\mathcal{S}^{n}$ is the $n \times n$ symmetric matrix space), $P,Q \in\mathbb R^{n \times n}$, and $\rho \geq 0$ be given. Show that: $$A \succeq P^{T}ZQ+Q^{T}Z^{T}P$$ for ...
3
votes
1answer
128 views

Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...
0
votes
1answer
199 views

L-infinity-norm regularized proximity problem

I have a question: $$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$ where $t, \lambda$ are given constant. I think this may be a classic problem? However, I didn't find closed form of its ...
1
vote
0answers
54 views

Log convexity for the norm of a vector-valued function

Log convexity of various functions defined on the space of Hermitian matrices plays an important role in matrix analysis and probability theory. Given $v \in \mathbb{C}^n$, $D$ a diagonal matrix with ...
4
votes
2answers
93 views

Questions concerning convergence rate of Iterated Projections

Assume for simplicity $C_1,C_2,...,C_n\subset \mathbb{R}^m$ to be closed and convex subsets with $\underset{i=1}{\overset{n}{\bigcap{}}}C_i\neq\emptyset$. Let $x^0\in\mathbb{R}^n$ and define the ...
2
votes
0answers
34 views

Constrained absolute orientation of 3D point sets

Let us assume we have two 3D point sets, $P=\{p_i\}$ and $Q=\{q_i\}$, and that we need to recover the transformation that takes $P$ as close to $Q$ as possible. In particular, I am interested in ...
0
votes
1answer
56 views

How to compute the direction of slowest ascent from the minimum of a strongly convex function?

Consider a twice differentiable strongly convex function $f:\mathbb{R}^n \rightarrow \mathbb{R^+}$ that attains its minimum value at the point $x^*$. I am wondering if one can compute a direction of ...
2
votes
0answers
79 views

About optimizing a convex function on a hypercube

Given a real valued convex function $g$ on $[-1,1]^n$, let $f$ be the restriction of it on the hypercube $\{-1,1\}^n$. I want to find a vertex on the hypercube $\{-1,1\}^n$ on which either (1) $f$ ...
5
votes
0answers
71 views

Basin of Attraction

I have a function $F$ which is defined as follows: $$ F(x) = \sum_{i=1}^N f(z_i^T x) $$ where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = ...
2
votes
1answer
120 views

Minimizing a convex integral function

Consider the following constrained optimization with the integral objective function $$ \min_{x_i\in D} \int_{t_1}^{t_2} \frac 1 {t - \sum\limits_{i = 1}^N x_i f_i (t)} \, dt $$ where $t - ...
4
votes
0answers
45 views

How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular? It would be helpful is someone can share some specific ...
2
votes
1answer
56 views

Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points

I am currently working on a problem where I have to minimize a $m$-strongly convex function $$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$ over a bounded integer lattice, $$L = \mathbb{Z}^n \cap ...
5
votes
2answers
111 views

convert a special case of nonlinear fractional programming into a convex problem

Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this ...
0
votes
2answers
131 views

Estimating the shift in the $\lambda_{max}$ of a matrix under a diagonal perturbation

Given a matrix $A$ and a diagonal matrix $D$, what ways do we have to estimate, $\lambda_{max}(A+D) - \lambda_{max}(A)$? (Feel free to make other assumptions about the matrices that they are all ...
4
votes
0answers
104 views

An inequality from the “Interlacing-1” paper

This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132) For the argument to ...
2
votes
0answers
34 views

About the partial expectation polynomials in the Interlacing-I paper and perfect matchings

I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf In the use of these ...
0
votes
1answer
119 views

sum of fractional functions optimization problem

Consider the following sum of fractional functions optimization problem $$ \begin{array}{l} \mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1}{{{\bf{a}}_i^T{\bf{x}} + {b_i}}}} \\ ...
3
votes
2answers
119 views

Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...