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 [optimization]

Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

1
vote
1answer
28 views

Alternate definition of convexity

For any real valued function, $f$, if for all, $x, y, z \in \mathbb{R}$ and $x \leq z$ $$ f(x+y) - f(x) \leq f(z+y) - f(z)$$ Then $f$ is convex. Is this argument generic? Edit: Sorry for the ...
0
votes
0answers
12 views

glossary explanation of optimal method. Penalty method & Augmented Lagrangian method

In the optimization,i believe lots of people heard about Penalty method & Augmented Lagrangian method,but i wonder why are the creators use "penalty" and "Augmented" to name these method . ...
0
votes
0answers
8 views

A question of primal-dual formulation

Suppose we have the primal problem: $\mathop{\min}\limits_{x\in X} F(Kx)+G(x)$, where $F,K,G$ are linear operators. And I want to ask how is the primal-dual formulation work to get the saddle-point ...
0
votes
2answers
34 views

Infimum of $\alpha\cos2\theta+\beta\sin2\theta+t_1\cos\theta+t_2\sin\theta$, if $\beta >0$ and $t_1^2+t_2^2=4$

For given $\alpha\in \mathbb{R}, \beta\in \mathbb{R^+}$, and $t_1^2+t_2^2=4$, we define the following function on $[0,2\pi]$: $$\varphi(\theta)=\alpha\cos2\theta+\beta\sin2\theta+t_1\cos\theta+t_2\...
0
votes
1answer
17 views

KKT condition for the proximal algorithm

This slide shows that the KKT condition for the proximal gradient descent is this inequality. I don't know where this comes from. Using KKT , we can only get equality for the stationary condition, ...
1
vote
0answers
27 views

Dual of linear function with convex and non-convex constraints

I would like to compute the dual of the following problem by using the KKT conditions. However, due to form of the first constraint I am not able to obtain the dual. The problem is the following \...
1
vote
1answer
21 views

help with Lagrange multiplier exercises [on hold]

Considering the following problems: Find the absolute extrema of $ f (x, y, z) = x + y + z \ $ in the set $$A = \{(x, y, z) \in R^3: x^2 + y^2 \leq z \leq 1 \}$$ Find the maximum and minimum ...
0
votes
0answers
17 views

Regression formula derivative

surely, this is an easy problem for a mathematician. Since I am just a student, I have some problems... I am trying to solve the following optimization problem: $$ \min_{w, \gamma} \frac{1}{2}\cdot(Aw+...
1
vote
0answers
47 views

How to form a perfect square?

You are given a square matrix $A \in \mathbb{ N}^{n,n}$, this number contains integers from $1$ to $n^2$. The task is to compute the minimal cost, to change this square into a perfect square. A ...
-1
votes
0answers
18 views

controllable with airplane. [on hold]

Write the linear airplane equations as a four-dimensional linear system using the variables $x_l = a, x_2 = \phi, x_3 = \dot{\phi}$, and $x_4 = h$, and show that the system is controllable.
1
vote
2answers
25 views

Formulation of a constrained optimization problem with probabilities

we are given four probabilities for an event. We shall adapt these probabilities in order to maximize the entropy given a constraint $4 = \sum_{i = 1}^4 2p_ii \Leftrightarrow 2 = \sum_{i = 1}^4 p_ii$. ...
0
votes
0answers
23 views

Optimization and Monte Carlo and a process with no stochastical dynamic

Assume we are in a Brownian filtration where I denote $W$ the Brownian motion. My problem is to numerically compute $$ \min_X E (\int^1_0 X^2_tdt),\ \ \ \ (*) $$ where $X$ is adapted to the filtration ...
0
votes
0answers
32 views

A “divide-and-conquer” iterative procedure for minimizing a sum of convex functions

For simplicity, let's assume $f_i: \mathbb{R} \rightarrow \mathbb{R}$ is convex and define $g(x) = \sum_{i=1}^{n}f_i(x)$. Suppose we want to compute \begin{align*} x^* = \underset{x \in \mathbb{R}}{\...
1
vote
1answer
31 views

Conic formulation with binary variables in Gurobi

I have a constraint of the following form $$x^2 \leq yz$$ where $z$ is binary, $y \geq 0$, and $x$ is free. Can Gurobi handle this constraint?
0
votes
0answers
45 views

Maximising linear function over a specific convex set of density matrices

All matrices being discussed in this question are density matrices, so they have the following properties: Hermitian Positive Semidifinite Trace = 1 We are currently in the space of all 4*4 density ...
0
votes
0answers
16 views

Optimization problem with variables in a sine function

I am trying to solve an optimization problem similar to this:- $$s: \min (\|H(s)g-g\|_2), $$ where $H(i,j)=\sin(k \pi (s_i - s_j))/\sin(\pi (s_i - s_j))$ and $g$ is my observation vector. Are there ...
0
votes
1answer
62 views

Minimum of expression $\frac{16}{a} + \frac{1}{b}$

Let $a$ and $b$ positive real numbers such that $3(a^2 + b^2-1) =4(a+b)$. Find the minimum of expression $\frac{16}{a} + \frac{1}{b}$. I tried a geometric method but it doesn't work.
0
votes
0answers
27 views

how to constrain 2 matrix such that they don't cancel out in optimization

Given a simple generic optimization problem argmin y = (A+B)x + g(x) + epsilon Let's say we want to fix the matrix A, and allow for free-form optimization on B. What kind of regularization or ...
1
vote
0answers
18 views

Minimum of a nested error propagation function

I'm a biology masters student working on a simple practical problem about some of the genetic tools we use. I'm very much a math novice, so please feel free to correct my notation/etc! I'm working ...
0
votes
1answer
29 views

Local Maximum Point; Global Maximum Point

Given is the function: $f(x,y)=cos(x)+cos(y)$ Which of the following statements is correct? 1. The function has a local maximum point in $P (0, 0)$ This is correct, because the first order ...
0
votes
1answer
38 views

Projected gradient descent

$\newcommand{\R}{\mathbb{R}}$There's the following problem that I found in a book: Let function $f:\R^2\to\R$ be defined as $$ f(x) = x_1 + x_1x_2 + (1 + x_2)^2 $$ Considering the feasible set $$ X ...
0
votes
0answers
30 views

How to check whether f is a convex and find all stationary points

Here is the problem What I attempted was calculating the Hessian and trying to prove that it's positive definite/semi-definite or negative definite/semi-definite. It doesn't seam to work as I am ...
0
votes
0answers
15 views

How many swaps in a set of size n will ensure that the set is shuffled reasonably well?

I'm implementing my own version of a shuffle method for shuffling a set of objects in a list. My implementation generates two (pseudo)random numbers and swaps the elements at these two indexes. ...
2
votes
2answers
69 views

Lagrange multipliers example with sympy - all minima but one maxima.

Consider the following optimization problem: Minimize $x^3+y^3$ Subject to: $x^2+y^2 \leq 1$ On the boundary of the constraint, we can consider $x=\cos\theta$ and $y=\sin\theta$. Then, the ...
1
vote
0answers
23 views

A question about the solutions of min-max problems

The minimax theorem states that for compact sets $X$, $Y$, if $f(x,y):X\times Y \rightarrow \mathbb{R}$ is convex for fixed $y$ and concave for fixed $x$, we have $$ \min_{x\in X}\max_{y\in Y} f(x,y) =...
0
votes
1answer
26 views

Is Maxima/Minima of Lagrange function same as Maxima/Minima of function under consideration?

Given: To find critical points of function f(x) subject to constraints: g(x) = 0 We create a Lagrange function: L(x, λ) = f(x) - λg(x) Now, are the critical points and max/min of Lagrange function ...
2
votes
1answer
31 views

Projection of functions in $L^1(\Omega)$ onto a $1$-dimensional subspace.

Suppose $f\in L^1(\Omega)$, where $\Omega\subset \Bbb R^n$ with $|\Omega|<\infty$. Let's consider a (probably not unique) constant function $c$ such that $$ \int_\Omega |f-c|\,d \mu = \inf_{t\in\...
0
votes
1answer
35 views

Optimization: Absolut value function [on hold]

I want to find the minimum of the following function, using a linear solver in Matlab: f = sum(((P * x - d)+|P * x - d|))*0.5*p) x (dimension [ix1]) is binary, P (dimension [nxi]),d and p are always ...
0
votes
1answer
31 views

After reading the quadratic penalty method.i still don't understand what does it actually do,and the time of using it

After reading the quadratic penalty method.i still don't know what is this,take an simple question for example,this example is from page 491~492 of "Numerical Optimization" this book. http://www....
5
votes
1answer
82 views

Find a permutation of the rows of a matrix that minimizes the sum of squared errors

I'm struggling with the following problem: Let $A, B \in \mathbb R^{n \times d}$. Denote by $\mathcal{P}$ the set of all possible permutations of the rows of $A$. Find a permutation $\pi \in \...
1
vote
1answer
32 views

Change of variables in QCLP

Is there any change of variables that makes the following optimization problem easier to solve? \begin{align} \max_{x\in\mathbb{R}^n,t\in\mathbb{R}}\quad & c^\top x,\\ \mbox{s.t.}\quad\quad & ...
-4
votes
0answers
29 views

Solve the optimization problem? [closed]

Minimize: $$F=x^2 + 2y^2$$ Subject to constraint: $x+3y=5$
1
vote
1answer
47 views

Convert the following Riccati equation into an LMI

I need help to convert the following discrete-time Riccati eqn. into an LMI with two decision variables $(K, P)$: $$ (A+BK)^T P (A+BK) - P +Q + K^T R K \prec 0$$ The trick, at least for the ...
4
votes
0answers
42 views

In an irregular grid comprised of squares, how might we find the most efficient way to remove squares such that there is no 2x2 square possible?

Normally in a square grid such as a 5x5 grid the way to accomplish this would to be to remove only 4 squares such that no two touch the wall of the grid, nor do they touch one another This has a ...
0
votes
0answers
44 views

Linear Program is Surprisngly Infeasible - Trying to Write the Dual

I need to solve the following linear program: $$\displaystyle{\min_{\bar{X},t}} \hspace{0.1in}t$$ such that: $$A\bar{X}=\tilde{x} + td$$ where $A$ is $N\times N$ and known, $t$ is scalar, $\tilde{...
1
vote
1answer
34 views

Why the dimension of the objective space of Multi-objective optimization problems is usually lower than the design space?

I was reading a book on non-linear multiobjective optimization by Kaisa M. Miettinen and in a paragraph the author says: "In single objective optimization problems, the main focus is on the decision ...
2
votes
2answers
24 views

Lagrangian multipliers for sensitivity analysis in integer linear programming?

I am a knuckle draggging engineer by training, but find myself possibly contending with how best to conduct sensitivity analysis (SA) for an integer-linear programming (ILP) problem. Being new to ...
0
votes
0answers
12 views

Example: Optimal basic solution to a linear program in standard form for which reduced cost vector has negative entries

I'm looking for an example where we have a basic optimal solution to a linear program in standard form for which the vector of reduced costs has at least one negative value. From thereon we should ...
0
votes
0answers
15 views

Maximizing harvest with random growth time

It's a practical problem I'm facing - in the game of Minecraft, I have a sugar cane farm, and I'd like to maximize its output. First, about random ticks: 20 times per second three random block out of ...
2
votes
2answers
81 views

Find maximize of the function $\frac{a}{1+a^2}+\frac{b}{1+b^2}-\frac{1}{c^2+1}$

Let $a,b\in R^+$ such that $ab+bc+ca=1$. Find the maximize of $$P=\frac{a}{1+a^2}+\frac{b}{1+b^2}-\frac{1}{c^2+1}$$ By Wolframalpha i can see that if $a=b=2-\sqrt 3;c=\sqrt 3$ we will have $P=\dfrac ...
4
votes
0answers
48 views

What are some of the best textbooks on multi-objective optimization?

I am looking for textbooks on non-linear multi-objective optimization that are rigorous. For instance, I am most comfortable with Arkadi Nemirovski style. I am looking for a book on nonlinear multi-...
1
vote
1answer
33 views

Convex function, Epigraph, Sublevel set

The following graph represents the sublevel set $ S_{-1} = \{(x,y):f(x,y)\le-1\} $ (this is not an epigraph!). Is the function $ f(x,y)=-2e^{x} +y$ convex? Is it quasiconvex? Explain based on the ...
1
vote
0answers
26 views

Convex Conjugate of sum-of-max terms

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a sum-of-max linear terms function: $$f(x) = \sum_{k=1}^K \max_i\{a_{k,i}^\top x\}$$ where $a$ are the linear coefficients. I am interested in the convex ...
1
vote
1answer
119 views

Solve $\frac{1}{x} = S x$, an equation that includes an element-wise inverse

Solve the following equation for $x \in \mathbb{R}_+^n$ $$\frac{1}{x} = S x$$ where the inverse on $x$ is taken element-wise, and $S \in \mathbb{R}_+^{n\times n}$ is PSD (or PD, if needed). ...
2
votes
0answers
18 views

How to show $(\text{prox}_{\lambda g }(v))_i=S_{\lambda}(v_i)$ where $S_{\lambda}(v_i)$ is the threshold operator.

How to show $(\text{prox}_{\lambda g }(v))_i=S_{\lambda}(v_i)$ where $S_{\lambda}(v_i)$ is the threshold operator. The threshold operator is the minimizer of of $f(t)=|t|+\frac{1}{2\lambda}(t-a)^2$ ...
0
votes
0answers
40 views

Optimizing a function under strictly positive constraint

Find x and y that optimise \begin{align} f(x,y) &= (-a-y)(\Psi(y)-\Psi(x+y)) + (b-x)(\Psi(x)-\Psi(x+y)) \\ &-\log \Gamma(x+y) + \log\Gamma(x) + \log\Gamma(y) \end{align} where a, b are ...
10
votes
3answers
650 views

How to minimise the cost of guessing a number in a high/low guess game?

In a high/low guess game, the "true" number is one of $\{1,\cdots,1000\}$. You'll be told if your guess is $<,>$ or $=$ the true number for each guess you make, and the game terminates when you ...
-3
votes
1answer
49 views

Inequalities in mathematics [on hold]

Let $a,b,c,d,e,f,g,h$ be 8 non negative real numbers such that $a+b+c+d+e+f+g+h =16$. If $P= ab+bc+cd+de+ef+fg+gh$ then find the maximum value of $P$. I tried using rearrangement inequality but ...
0
votes
0answers
16 views

a lower bound for the optimal solution of $VaR$ problem?

I need to find a lower bound for $VaR_\alpha$ in the problem $CVaR_\alpha(X)$. I think the optimal solution of the Exerted value problem it's work. but I'm not sure. Is the optimal solution of the ...
0
votes
0answers
19 views

The singular values of the best rank-$k$ approximation to a matrix

Let $A\in\mathbb{C}^{m\times n}$ be a complex matrix. Let $B_k$ be a best rank-$k$ approximation to $A$ such that \begin{equation*} B_k\in\arg\min\limits_{{\rm rank}(B)=k}||A-B||_F, \end{equation*} ...