Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

1
vote
1answer
19 views

What does it mean to minimize a convex function with “less than or equal to” inequality constraints? Why?

What does mean to minimize objective function with "less than" inequality constraints? Aren't you suppose to minimize with "greater than" constraints, like in example 1? Example 1 (understand this) $...
0
votes
1answer
23 views

Strict convexity of a function in a given domain

If function $f(\mathbf x)$ is strictly convex at all stationary points in a given domain, $\mathbf x\in[\underline{\mathbf x},\overline{\mathbf x}]$, does it mean that the function may only have local ...
1
vote
0answers
11 views

Weak Convex Optimization Constraints

Fix $\epsilon >0$, and fix a finite measure $\mu$ on $\mathbb{R}$. Let $g:L^2_{\mu}(\Sigma;\mathbb{R})\rightarrow \mathbb{R}$ be continuous and convex (but not affine), and define the ...
0
votes
0answers
23 views

Optimizing the ratio of two convex functions, with some special properties

I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g$ and $h$. It is known that $f(x)$ has a global minimum, achieved at a unique point $x_0$. Also ...
1
vote
0answers
29 views

Linear quadratic regulator via least squares

In this set of slides, the finite horizon LQR problem is stated as a least-squares problem (slide 11), and using a naive method (e.g., QR factorization), the cost to solve this problem is $O(N^3nm^2)$ ...
1
vote
2answers
50 views

Prove convexity of set

I've had a hard time proving this statement. The objective is to prove that the set $M$ is convex where $f(y)$ can be any function. The task is to prove it using triangle inequality. I've looked at ...
-2
votes
0answers
15 views

power distribution network

I work on the power distribution network. To test the convex optimization algorithm, I need to simulate the software on a IEE-123 standard bus. Which software is suitable for this job? Is MATLAB ...
0
votes
2answers
53 views

Subdifferential

I compute the subdifferential of the convex function $f(x)= \displaystyle\max_{1\le i \le N} \{f_{i} + <v_{i},x-z_{i}> \} $. The result is: $conv(\{v_{i}, i \in I(x)\})$ where $I(x) = \{i \in \{...
-1
votes
0answers
18 views

Optimization code error in MATLAB [on hold]

I am trying to run several files of code for an assignment. I am trying to solve an optimization problem using the "quadprog" function from the "optim" package. quadprog is supposed to solve the ...
0
votes
1answer
29 views

How does this list of optimal values prove Farkas' lemma?

From Convex Optimization: Can someone explain how the proof below shows that $5.87$ and $5.88$ are strong alternatives? It seems to just list the optimal values of $5.89$ and $5.90$ depending on the ...
2
votes
1answer
70 views

What does “with probability $1 - \delta$” mean in optimization theorems for algorithms?

I´m reading a paper about second order stochastic optimization. In many of their theories it states that the convergence rate or other inequalities hold "with probability $1 - \delta$" or "with ...
0
votes
1answer
21 views

Why Lagrange dual solution gives a different solution

The original problem is min x s.t. $x^2 \leq 1$ I modified it to min x s.t. $x\leq 1$, $x \geq -1$ And sove its dual problem as: $max_(\lambda, v)(inf_x(x + \lambda (x-1) + v(-x - 1))) ...
0
votes
1answer
31 views

Inequality constraints and the max function

Let $g_i(x):\mathbb{R}^{n} \to \mathbb{R}$, for $i=1,\ldots,n$, be continuous convex functions. Define $g_{\rm max}$ as $g_{\rm max}(x) \triangleq \mbox{max}_{i=1,\ldots,n}\{g_i(x)\}$. Define also the ...
0
votes
0answers
34 views

Why does the solution to one system imply the other system has a negative solution?

Consider two systems A and B: A$: f_i(x) \lt 0, i=1, \dots, m, Ax = b$ B$: \min_{\{x,s\}} s$ subject to $f_i(x) - s \le 0, i = 1, \dots, m; Ax = b$ Then B has optimal value $p^* \lt 0$ ...
0
votes
1answer
30 views
+50

How are these two systems strong alternatives?

Consider the system of linear inequalities: $Ax \preceq b$. The alternative system of inequalities is: $\lambda \succeq 0, A^T\lambda = 0, b^T \lambda \le 0$ These are strong alternatives ...
0
votes
1answer
33 views

Proof $C$= {$(x, y) \in \mathbb{R}^2 | x+y=b $} is convex

In an optimization problem, I have constraints of the form $x+y=b$. In order to prove that the solution is unique, I proved that the criterion is strictly convex and now I need to show that the set of ...
2
votes
1answer
26 views

How can the sum of one and infinity norm minimization problem subject to constraints be rewritten as a linear program?

I have been trying to convert the following problem into a standard LP problem $$\begin{array}{ll} \text{minimize} & \|x\|_1 + \|x\|_\infty\\ \text{subject to} & A x = b\end{array}$$ I know ...
0
votes
1answer
54 views

How to prove huber loss as a convex function?

Huber loss is defined by $$\mathcal{H}(u) = \begin{cases} \frac{1}{2}\|u\|_2^2 & \|u\|_2 \leq 1 \\ \|u\|_2- \frac{1}{2} & \|u\|_2 > 1 \end{cases} . $$ From the graph it's evident, but ...
-1
votes
2answers
35 views

Importance of equivalence of norms

I am doing a course in Convex Optimization where I learned about the equivalence of norms, but there was no mention of its importance or about the scenarios where it can come in handy. The definition ...
1
vote
1answer
37 views

Why is this the optimal value of the dual problem?

Let the primal problem be to determine the feasibility of the system $f_0 =0, f_i(x) \le 0$ for $i=1, 2, \dots, m$ and $h_i(x)=0$ for $i = 1, 2, \dots, m$. The dual problem associated with ...
2
votes
0answers
49 views

Discrete-time linear control with linear state/input constraints

Given a controllable discrete-time linear system $x(k+1) = A x(k) + B u(k)$ the input sequence leading from state $x_0$ to $x_f$ is given by $C^{-1} (x_f - A^n x_0)$ where $C$ is the controllability ...
-1
votes
0answers
63 views

How to find subdifferential of $sin(x)$ [closed]

I want to compute the subdifferential of $f(x) = sin(x)$, where $domf = (0, \frac{3}{4}\pi)$. How do I do this?
0
votes
0answers
24 views

I am trying to prove the minimax convex optimization [closed]

I am trying to prove that this following function is convex, min(max(a)+b). Are there any useful resources that I can use or Do you know how to start with it?
1
vote
0answers
43 views

How to prove that the subgradient of a dual function contains the equality constraint for closed and convex function?

Apologies for the fundamental question. But I am am just trying to understand the pieces. Let us consider a minimization problem \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & f(x) \\ ...
2
votes
1answer
62 views

Isotonic regression with a linear constraint

I'm trying to find a direct approach to solving (for some fixed vector $y$): $$ \begin{aligned} \min & \; \|x - y \|^2 \\ \mbox{s.t. } & \alpha^\top x \leq 0 \\ & x_i \...
0
votes
1answer
36 views

Why is the epigraph of Moreau-Yosida Regularization a projection of a convex set?

The Moreau-Yosida Regularization is given by \begin{equation} f_\mu(x) = \inf_y \left( f(y) + \frac{1}{2\mu} \| x - y \|^2 \right). \end{equation} We know that $L(x, y) = f(y) + \frac{1}{2\mu} \| x -...
1
vote
0answers
25 views

Does subdifferential function with non-convex dom exist?

In this question it was proved that, if $f:X \to \mathbb{R}$ and $\partial f(x)\neq \emptyset$ for all $x \in X$, then $f$ is convex. But in the proof we used the fact, that $x = \lambda x_1 + (1 - \...
0
votes
1answer
9 views

Does Lipschitz continuity of a convex imply boundedness of the domain of its Fenchel conjugate

Let $g:\mathcal{H} \to \mathbb{R}$ be a convex and $L_{g}$-Lipschitz continuous function on a Hilbert space $\mathcal{H}$. Is the domain of its Fenchel conjugate $g^*$, where $$ g^*(y) := \sup_{x \in \...
2
votes
1answer
41 views

Algorithms for projecting a point onto the convex hull spanned by a set of vectors

Given a set of vectors $V = \{ \mathbf{v}_1, \ldots, \mathbf{v}_n \} \subset \mathbb{R}^d$, I want to project a point $\mathbf{x}_0 \in \mathbb{R}^d$ onto the convex hull $\text{conv}(V)$ of the ...
1
vote
0answers
31 views

Are there any known methods for transforming a system of linear inequalities into a system of linear Equalities?

Begin Question Are there any known algorithms for transforming a system of linear inequalities into a system of linear equalities? The resulting system is only allowed to use equality statements ($=$)...
2
votes
0answers
41 views

Minimizing the lower bound of a convex function

Suppose $\bf{A}$ is an $m \times n$ matrix of rank $n$ having entries 0s and 1s. I found that the minimizer of \begin{align*} {\bf Q}^* = \text{min}_{\bf Q} \ \text{tr}({\bf AQQ}^{T}{\bf A}^{T}) \ \ ...
1
vote
0answers
17 views

Maximum volume inscribed ellipsoid of given aspect ratio

It is well know (see Boyd & Vandenberghe's Convex Optimization, Sec. 8.4.2) that the maximum volume ellipsoid inscribed in a given convex polytope in $\cal{H}$-form can be computed by solving the ...
0
votes
0answers
44 views

Optimization Methods in Banach Spaces

does anyone know if there's a theory for the following problem: Optimize the task $\begin{align*} T_\phi(\tilde{u})&=\inf\limits_u T_\phi(u)\\ Au&=b\\ u&\in L^p(\Omega),\,\Omega\subset \...
5
votes
1answer
459 views

Can a polyhedron be an empty set?

A polyhedron is defined as the intersection of finitely many generalized halfspaces. That is, a polyhedron is any set of the form $ \{x \in R : Ax \leq\ b \} $ I would like to understand this ...
0
votes
2answers
41 views

Why is this set not a polyhedron?

(Question from Stephen Boyd and Lieven Vandenberghe - Convex Optimization) $S = \{x \in \mathbb{R}^n |x \ge 0, x^{T}y \le 1$ for all $y \in \mathbb{R}^n$ such that $\lVert y \rVert_2 = 1$}. Is the set ...
0
votes
0answers
18 views

Closed form lasso solution with side constraints

Consider the follwing optimization model known as the lasso problem for which a closed-form solution exists, see Derivation of closed-form lasso solution. Lasso: $$\min_\beta \quad (Y-X\beta)^T(Y-X\...
2
votes
0answers
48 views

How to solve a large scale convex optimization problem?

Consider the following convex optimization problem in vectors $x$ and $y$ $$\begin{array}{ll} \text{minimize} & f(x,y)\\ \text{subject to} & g_1 (x)\le 0\\ & g_2 (y)\le 0\end{array}$$ ...
0
votes
1answer
12 views

Sublinearity and concavity of a function

Problem A function $f$ is said to be sublinear in $n$ when $$\lim_{n\rightarrow \infty} \frac{f(n)}{c^n} =0\ (c > 0)$$ Some classical examples of sublinar function include $f(n)=\sqrt{n}$ and $f(...
0
votes
0answers
21 views

Help with solving a support vector regression problem with Lagrange multipliers

Decided to take an example with only 3 data points as to see the steps of the algorithm. The points (x,y) are (10,26) , (11,35) , (12, 40). When I write out the Lagrangian of the dual problem, I end ...
0
votes
0answers
15 views

What if provide a good initial point for penalty convex-concave procedure?

Recently, I am working on penalty convex-concave procedure (PCCP) to solve some optimization problems. I learned from S. Boyd's great book "Variations and extension of the convex–concave procedure" ...
0
votes
0answers
9 views

First order optimality condition for convex and differentiable $f$ over a set $C$

Consider $\underset{x}{\min}f(x)$ subject to $x \in C$ where $f$ is convex and differentiable. I know there is the first order optimality condition that $x^* \in \underset{x \in C}{argmin}f(x)$ if and ...
0
votes
1answer
23 views

Convexity of 0-1 loss

Problem The 0-1 loss is defined as $\ell(h(\mathbf{x}), y) = 1(h(\mathbf{x} \neq y)$. How could I show the convexity of this loss function? What I Have Done I tried to verify the Jensen's ...
0
votes
0answers
35 views

optimization problem with square root and quadratic

Consider the optimization problem \begin{align} \max_{\mathbf{y\in\mathbb{R}^N}}~~\mathbf{y}^T\mathbf{b}+\beta\sqrt{c-\mathbf{y}^T\mathbf{Ay}} \\s.t.~~\mathbf{0}\leq\mathbf{y}\leq \mathbf{1} \end{...
0
votes
0answers
37 views

Is this objective on a optimization problem convex?

Is this objective convex? If not is there a way to make it convex? I am trying to optimize the values of the matrix A for some defined values of the vectors x,y,w $ min_A: \sum_{m} \Bigg({\dfrac{x_m ...
1
vote
2answers
36 views

Silly question on lower semi-continuity

Suppose that $X_n\rightarrow X$ in a complete separable metric space $(\mathcal{X},d)$. Let $f:\mathcal{X}\rightarrow (-\infty,\infty]$ be a proper, convex, lower semi-continuous function, such that $...
0
votes
0answers
30 views

Linear inequality constraint - in KKT optimisation

I have a query regarding whether KKT is optimal with some linear inequality constraint and non-linear inequality constraint. For KKT to be optimal the inequality constraints must be convex. We know ...
2
votes
0answers
70 views

Is $f(x,y)=\left(\frac{x^a(1-y)}{(1-x)}-\frac{y^{a}(1-x)}{(1-y)}\right)\frac{1}{x-y}$ convex?

Is it possible to prove that, $$f(x,y)=\left(\frac{x^a(1-y)}{(1-x)}-\frac{y^{a}(1-x)}{(1-y)}\right)\frac{1}{x-y}$$ is convex in the following range: $0<y<x<1$, where $a\ge2$ is an integer ...
1
vote
0answers
32 views

How does minimax equality fail for non-convex sets of distribution?

Minimax theorem states that $$ \sup_{P_X \in P}\inf_{\eta} mse(P_X,\eta) = \inf_{\eta} \sup_{P_X \in P} mse(P_X,\eta) $$ where $\eta$ is an estimator of X and $P$ is a convex set of distributions ...
-1
votes
1answer
43 views

Does anyone knows how can I find this gradient?

enter image description here Does anyone know how can I start to find the gradient of this function? Any help or hint would be appreciated.
2
votes
0answers
37 views

Find optimal weight vector $\sum_i \log \left(1 + \exp\left\{ -t_i \left(w^T x_i\right)\right\} \right) + \mu \|w \|_2^2$?

Let the function is, \begin{align} f(w) &= \sum_i \log \left(1 + \exp\left\{ -t_i \left(w^T x_i\right)\right\} \right) + \mu \|w \|_2^2 \ , \end{align} where $t_i \in \mathbb{R}$, $w, x_i \in \...