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

1
vote
1answer
96 views

Nested convex optimization

Suppose I have a convex optimization problem of the form $$\min_x f(x) ~~s.t.\\x\in X$$. Say that $f(x)$ and its (sub)gradient are not given in a closed form, but are determined by solving a convex ...
1
vote
0answers
74 views

A version of isotone projection cones

We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
5
votes
0answers
68 views

Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
4
votes
1answer
101 views

Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...
4
votes
1answer
191 views

Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

I was wondering if anybody has any suggestions on the following problem: Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which ...
5
votes
0answers
178 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
1
vote
0answers
116 views

Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form: $$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log \...
2
votes
0answers
94 views

How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
8
votes
3answers
320 views

Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D =\...
6
votes
0answers
118 views

A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
1
vote
1answer
101 views

What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in \mathbb{R}^{...
0
votes
1answer
92 views

accelerate convex optimization by proximal projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ): http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf ...
1
vote
0answers
123 views

Proximal mapping of composition with linear operator

Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by $$ (I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x), $$ as ...
4
votes
0answers
136 views

Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$ Subject to $ A \...
0
votes
2answers
158 views

Does removing some constraints in convex program change the optimal solution? [closed]

Suppose I have a convex program which has only two variables, the objective function is strictly convex, and the constraints are linear functions. I think removing all non-tight constraints doesn't ...
1
vote
1answer
144 views

An optimization problem in complex space

Consider the following optimization problem $$ \min \| \textbf{Ax-B}\| $$ $$ s.t.|x_i|=1,i=1,...,n $$ where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
5
votes
1answer
435 views

Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?" More formally and generally, what I'm looking for ...
1
vote
0answers
171 views

Restricted strong convexity for biconvex functions

Recently, it has been shown (arxiv paper) that non-convex functions with the restricted strong convexity (RSC) property has the interesting property that their local minima lie within a small ball of ...
0
votes
1answer
70 views

Finding maximum of a function with unfixed number of variables

Can anybody solve this: For a constant positive integer $n\geq6$ find $k$ and positive integers $a_{1},a_{2},...,a_{k}$ that maximize the expression $$\sum_{i=1}^{k}\left[-4a_{i}^{3}+\left(3n-...
17
votes
8answers
2k views

When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...
0
votes
1answer
185 views

Matrix equation

Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that $0<q_{j}...
2
votes
1answer
179 views

Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...
8
votes
2answers
273 views

Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...
1
vote
0answers
139 views

What is the purpose of the definition of “metric regularity”/“regularity modulus”?

A set mapping $F:X \rightrightarrows Y$ is said to be metrically regular for $\overline{x}\in X$ and $\overline{y} \in Y$ if there exists a $\kappa\in(0,\infty)$ for which $$ d(x,F^{-1}(y))\leq \...
3
votes
0answers
117 views

This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
1
vote
0answers
50 views

Is there a unique tilted measure with specified marginals?

Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in \mathcal{...
-3
votes
1answer
90 views

Convert constraint to do convex optimization or use Lagrange multiplier method [closed]

$w_1, w_2, w_3 ... w_n$ are the weights I need to find I have the following constraint: $|w_1| + |w_2| + .. |w_n| <= 5$ That is the sum of the absolute values of the weights has to be less than ...
2
votes
0answers
212 views

Reference request: functional analysis results used in Taubes paper (1980)

I am studying Taubes paper 'Arbitrary N-vortex solutions to the first order Ginzburg-Landau equations'. I am looking for a reference of three following theorems: Let $f(x)$ be a convex funtional ...
5
votes
2answers
797 views

Linearly constrained eigenvalue problem

Suppose I'd like to: \begin{align} \mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\ \text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\ && \...
4
votes
2answers
346 views

Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that $...
3
votes
1answer
116 views

Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem $$\min \|x\|_1 \quad s.t. \;\; A x = b,$$ admits an $m$-sparse solution in ...
9
votes
4answers
541 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
1
vote
2answers
128 views

investigating positivity/negativity of a function [closed]

I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function $$f\left(y_{1},y_{2},y_{3}\...
3
votes
1answer
134 views

A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. $\mid\...
1
vote
2answers
149 views

The set of matrices with same spectral radius

I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...
5
votes
2answers
411 views

Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$? I know ...
3
votes
1answer
194 views

Linear dependency of real numbers with integer coefficients adding up to zero [closed]

Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both ...
1
vote
0answers
96 views

Convex Optimization related problem

Suppose two non-negative convex functions $f$ and $g$ be given. We want to solve the following optimization $$\max_{g\leq\epsilon}f.$$ Now suppose that both $f$ and $g$ can be upper-bounded by a ...
2
votes
0answers
339 views

On increasing the penalty term in convex optimization with regularization

Given the two strictly convex (unique solution) optimization problems as: $$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$ where $X\in\mathbf{S}_{++}^{n}$ (...
2
votes
0answers
58 views

Reference request: Edmond's Algorithm for integer hull

I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...
1
vote
0answers
48 views

Changing a nonlinear equality constraint into some conic inequality plus rank constraint

If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
2
votes
1answer
100 views

Is first term of my cost function convex?

I have an optimization problem in the form of [\begin{array}{l} \mathop {{\rm{Minimize}}}\limits_{\bf{X}} \,\,\,2\left| \delta \right|\sqrt {{\rm{Tr}}\left( {{\bf{A}}{{\bf{X}}^2}} \right)} {\rm{ - ...
0
votes
0answers
66 views

Finding gradient of an optimization

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me? Assume that we have an optimization ...
1
vote
0answers
57 views

Characterization of the optimal solution in relative entropy minimization

The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure. For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, ...
5
votes
1answer
201 views

optimization problem, any solution?

The objective is as follows: $\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$ $s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$ ...
5
votes
1answer
157 views

Reference request: Continuity of unique maximizer of linear functional on convex set

Does anyone know reference for a theorem of the following sort: Proposition: Let $K \subset\mathbb {R}^n$ be a compact convex set, and assume that $$f(w):=\operatorname{argmax}_{x\in K}w(x) $$ is ...
2
votes
1answer
248 views

Projection onto $\ell^{2,1}$ ball

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve $$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 \right)^{...
1
vote
1answer
80 views

mixed semi definite and second order programming complexity order

Consider the following mixed semi definite and second order programming: $\begin{array}{l} \mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\ {\rm{s}}{\rm{.t:}}\, & {\rm{...
1
vote
1answer
487 views

Convergence rate of stochastic gradient decent with projections

Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...
3
votes
2answers
92 views

Is the prox-residual monotone?

$\newcommand{\scp}[2]{\langle #1,#2\rangle}\newcommand{\id}{\mathrm{Id}}$ Let $f$ and $g$ be two proper, convex and lower semi-continuous functions (on a Hilbert space $X$ or $X=\mathbb{R}^n$) and let ...