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

learn more… | top users | synonyms

0
votes
1answer
25 views

Does convergence of iterates imply convergence of function values?

The question came to my find when I was reading convergence of gradient descent. However, my question is general and does not necessarily stick to GD. Concretely,my question is: \begin{equation} \|x^k-...
0
votes
1answer
38 views

Minimal Ellipsoid in $R^{2}$; why is it the Ellipsoid 2 in the figure?

It is stated in the book Convex Optimization, Boyd in page 47 that the ellipsoid 2 is the minimal because no other ellipsoid (centered at the origin) contains the point (top point) and is contained in ...
1
vote
1answer
26 views

How to minimize a linear function over a halfspace efficiently and intuitively

Consider the following fundamental problem: Two methods: By duality: ($\lambda, b \in R$) $L(x,\lambda)=c^Tx+\lambda(a^Tx-b)=x^T(c+\lambda a)-\lambda b \ \ $. Therefore, $g(\lambda)=-\...
0
votes
0answers
15 views

Easy linear matrix inequality (LMI) problem

I'm trying to find a matrix $P$ such that: \begin{equation} x^T P x \leq -1\quad \forall x\neq 0. \end{equation} I'm not sure if I can use Shur's complement, which states that: \begin{equation} \left[...
2
votes
2answers
67 views

How do I solve the following equality-constrained quadratic program?

I am trying to minimize: $$(x_1-k_1)^2 + (x_2-k_2)^2 + (x_3-k_3)^2 +\ldots+ (x_n-k_n)^2$$ subject to following equality: $$B = 1 + x_1 + x_2 + x_3 + x_4+\ldots+x_n.$$ Is there a closed form ...
0
votes
2answers
22 views

Reference required for Alternating Direction Method for Multipliers?

In my understanding, Alternating Direction Method for Multipliers (ADMM) is widely viewed as a tool to parallelize large-scale convex-optimization problems arising in statistics and other related ...
1
vote
1answer
17 views

How to Calculate the normal cone of a covex set at a point?

Let $C$ be a convex set of $\mathbb{R}^d$ and $\overline{x}\in C$ we define the normal cone of $C$ at $\overline{x}$ by \begin{equation} N_C(\overline{x}) = \{ y \in \mathbb{R}^d \ <y ,c-\...
0
votes
1answer
26 views

Reducing LASSO problem size on the fly with TFOCS

Suppose I'm using the TFOCS software package to solve the LASSO problem \begin{equation*} \text{minimize} \quad \frac12 \| Ax - b \|_2^2 + \gamma \| x \|_1. \end{equation*} The optimization variable ...
1
vote
0answers
38 views

Help needed to define a constraint in an optimization problem?

Given objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\...
1
vote
0answers
26 views

How to minimize objective function involving convolution?

My objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t \hspace{4mm}\mathbf{p^Te_p}-1=0\\\mathbf{...
1
vote
3answers
43 views

Easier way of finding out whether a given linear programming problem has optimal solution or not

I have the linear program $$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$ I can solve it using Simplex algorithm, but I ...
1
vote
1answer
35 views

Can Extragradient method be expressed with proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method ...
0
votes
0answers
23 views

Global maximum for constrained optimization of concave function

Suppose I maximize function $x_{1}-f(x_{2})$ where $f$ is strictly convex so $\frac{df}{dx}>0, \frac{d^2f}{d^2x}>0$. Also here is a set of linear constraints in a form $g(x_{1},x_{2})\leq0, min(...
0
votes
0answers
33 views

SVM optimality criterion in Bottou, Lin (2006)

My question relates to an alternative optimality criterion for an SVM dual solution derived in Bottou, Lin (2006) in pages 8 and 9. Let: $\alpha^* = (\alpha_1^*,\dots,\alpha_n^*)$ be a dual ...
1
vote
1answer
55 views

Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$

\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array} For this ...
0
votes
1answer
19 views

Closure of intersection of convex sets

Let $C_i$ be a convex set in $R^n$ for $i\in I$, suppose sets $ri \, C_i$ have at least one point in common, then how to prove this: $cl\bigcap\{C_i\mid i\in I\} = \bigcap\{cl \, C_i \mid i\in I\}$
0
votes
0answers
36 views

Conditions for all positive $x$ solved by $\min \bf{x}^T\bf{x}$ $s.t. Ax=b$

I want to find a condition for having all nonnegative $x_i$ in $\min \bf{x}^T\bf{x}$ $s.t. \bf{Ax}=\bf{b}$ where $\bf{x}\in \mathbb{R}^{n\times 1}$, $\bf{A}\in \mathbb{R}^{m\times n}$, $\bf{b}\in \...
0
votes
0answers
25 views

Stability of a semidefinite programming problem

For the minimum trace factor analysis problem, I want to prove that if I change a parameter in the optimization problem, the solution will be stable. Let $\mathbf{D}^p$ denote the set of $p \times ...
2
votes
1answer
28 views

Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
2
votes
1answer
30 views

Solving a quadratic convex optimization problem

There's this convex optimization problem which I got stuck after writing the Lagrange equation. I simply couldn't find a way to eliminate the Lagrange multiplier. $$\begin{array}{ll} \text{minimize} &...
0
votes
0answers
13 views

References to: If $C\subset\mathbb{R}^n$ is convex and $0\notin C$ then there exists $v\in C$ such that $C$ is in the closed halfspace $H_v$.

For each $v\in\mathbb{R}^n$, we define the notation $H_v=\{u\in\mathbb{R}^n:\langle u,v\rangle\geq0\}$, where $\langle\cdot,\cdot\rangle$ denotes the usual inner product in $\mathbb{R}^n$. Recently, ...
1
vote
0answers
39 views

Good text book recomendation

I would like to do some reading about a technique called sequential convex programming. There is a lot of material about sequential quadratic programming out there, including books (Nocedal & ...
1
vote
0answers
24 views

A question on Edgeworth Expansion

I'm working Edgeworth Expansion. I couldn't understand one thing . Can you help me about that please. $$Z= \frac{\sqrt {n} (\bar {x} -\mu)}{\sigma}$$ converges in distribution to N(0,1) I have ...
0
votes
1answer
59 views

Product of the differences of two pd matrices and their respective inverses is pd

Given two $\textbf{positive definite (pd), Hermitian}$ matrices X and Y, I am trying to determine whether $(X-Y)(Y^{-1}-X^{-1})$ will always be pd as well, and how to prove this. This formulation ...
0
votes
1answer
20 views

To what extent can the column generation method for solving linear programs be extended to solving more general convex optimization problems?

Are there column generation approaches to solving classes of convex optimization problems other than LPs, and are they guaranteed to find a global minimizer?
5
votes
3answers
474 views

Shortest distance between two lines in 3-dimensional space [closed]

Can someone explain to me how to solve this question? Find the shortest distance between the lines $L_1 = \left\{t \begin{bmatrix} 1\\ 1\\ 1\end{bmatrix} : t \in \mathbb{R}\right\}$ and $L_2 = \left\...
1
vote
0answers
39 views

maximum of a concave function in a minkowski sum

Let: $f(x,y)$ - a strictly-concave function, monotonically increasing in $x$ and $y$; $A,B$ - two compact and convex sets in the positive quadrant; $C$ - their Minkowski sum, $A+B$; $(x_A,y_A)$ - ...
0
votes
0answers
17 views

Diagonal Newton's method for unconstrained optimisation.

Assume you are minimising a convex function $f$. The function is twice-differentiable. The well-known Newton's method consists in starting form some point $x_0$ and then using the iteration below. $$ ...
1
vote
1answer
23 views

Property of Conical Hull

Let $H$ be a real Hilbert space and $C$ be a nonempty convex subset of $H$. The conical hull of $C$ is defined by $$ \operatorname{cone}{C} := \bigcup_{\lambda >0}{\lambda C}. $$ (it is a cone in ...
0
votes
0answers
20 views

Solving optimization problem where objective function is of type (affine+(affine/affine))

I need to solve a non linear optimization of the form minimize $f(x) +\frac{g(x)}{h(x)}$ subject to $p(x)\leq0$ $q(x)=0$ Here $f,g,h,p,q$ are affine functions of $x$ and they are convex in the ...
0
votes
0answers
8 views

Deriving a minimizer involving proximal operator

The following are from this thesis http://gpu4vision.icg.tugraz.at/papers/2012/werlberger_phd.pdf I have a difficulty understanding the lines: For example, (4.38) seems very weird to me. I think ...
0
votes
0answers
24 views

Converges extremely slowly, using Douglas-Rachford splitting, how to improve?

my problem looks like this: $\min _{ E,A }{ { \lambda }_{ 1 }{ \left\| E \right\| }_{ 1 }+{ { \lambda }_{ 2 }\left\| A \right\| }_{ * }+{ \left\| D-ME-A \right\| }_{ 2 }^{ 2 } } $ the M is a ...
1
vote
0answers
39 views

Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}argmin_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}argmin_{t}\{t+5\mathbf{E}[Z-t]_{+}\}$$ I ...
0
votes
0answers
13 views

Convex solver returns disordered dual variables, how to re-order?

I have the following convex optimization problem: $$ \begin{align*} \min_{x} &f(x) \\ \text{subject to} \\ x_{k+1} &= x_k+\cdots\qquad k=0,1,2,\ldots,N-1 \end{align*} $$ I managed to solve ...
5
votes
2answers
106 views

Equivalent characterizations of the dual norm on finite dimensional vector spaces

In their book on Convex Optimization, Boyd and Vandenberghe state that given a norm, $||\cdot||$, defined on $\mathbb{R}^n$, the dual norm is defined as $$||z||_*= \sup \{ z^Tx : ||x|| \leq 1 \}$$ ...
0
votes
0answers
18 views

How you can model the other players replies in a game theoretic model?

In a game theory field, the payoff function of a player n is basically a function of the other players responses which are considered as constants. I'm trying to solve the maximization of the payoff ...
1
vote
1answer
39 views

How to get explicit solution of the fractional minimization problem?

I need to minimize $f(x) = \frac{x^tQx}{a^tx-b}$, $Q$ is positive definite, $a,b$ are constant vector. But when I take gradient and set it equal to $0$, it's hard to get an explicit expression for $x$....
0
votes
1answer
18 views

Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ &2x_1&+x_2&...
0
votes
1answer
20 views

Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
0
votes
1answer
37 views

A Question On Triple Integration

Can anyone construct a nonzero continuous function $f:[0, 1]\times[0, 1]\times [0, 1]\rightarrow [0, \infty)$ such that \begin{equation*} \int_{t_1=0}^1 \int_{t_2=0}^1 \int_{t_3=0}^1 f(t_1, t_2, t_3)~...
0
votes
0answers
15 views

subdifferential of $\max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$

How to find the subdifferential of $$f(x) = \max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$$ My derivation is: $\nabla \frac{1}{2}\|x\|_2^2=\nabla \frac{1}{2}x^Tx=x$ ...
0
votes
0answers
56 views

Yale College's Housing Draw Problem — Convex optimization techniques on a modified stable marriage problem?

I'd like to run various optimization techniques on this variation of the stable marriage problem I formulated. Ideally, I'd be able to convert the problem I constructed into one that is more "calculus-...
0
votes
0answers
8 views

Why $x_B=\tilde b +\tilde A x_{\bar B};c^Tx=\psi+\tilde c^Tx_{\bar B}$ doesn't describe an optimal solution iif $\tilde c_i\le 0,\forall i$

How to counterprove the assertion that if a feasible dictionnary in the type \begin{cases} x_B=\tilde b +\tilde A x_{\bar B}\\c^Tx=\psi+\tilde c^Tx_{\bar B} \end{cases} describe an optimal ...
1
vote
1answer
21 views

Can geometric programs be solved more efficiently than general convex optimization problems?

I want to solve an optimization problem for which I have already proven that it is feasible and convex. Introducing further variables and considering a special case of the problem, I can formulate it ...
1
vote
1answer
38 views

piecewise linear minimization equivalent to linear programming

Why is \begin{equation} \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} equivalent to an LP \begin{equation} \begin{aligned} & \min & &...
0
votes
2answers
39 views

Optimization of a function over probability distributions

I'm trying to solve certain optimization problems dealing with probability distributions. Consider the space of probability distributions $\{ 1, ..., N\} \to [0, 1]$ I have a function $f : (\{ 1, ...,...
0
votes
0answers
16 views

Finite Subdifferential

Can the set of subgradient vectors (Subdifferential) have finite number of vectors? I know it can be either empty, have one vector, or have infinite number of vectors
0
votes
0answers
31 views

Minima of non-strictly convex function

I wonder if there is anything that can be said about minimizers of convex, but not strictly convex problems, with regards to initial points provided to an optimization algorithm? Not sure if this is ...
4
votes
2answers
48 views

L1 regularized unconstrained optimization problem

I am encountering an unconstrained minimization problem. The problem is of the form $$\min_x \frac{\|x-a\|_2^2}{2}+\lambda\|x\|_1$$ where $x,a \in R^n$ and $x$ is the optimization variable. $\...
2
votes
2answers
56 views

References on probability theory, stochastic processes, Monte Carlo and convex optimisation, with similar writing style to Terence Tao

I learned a lot from prof Tao's notes and books because unlike many authors, he seems to prefer writing more words, explanations and intuitions rather than just mathematical formulae. His approach is ...