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.

learn more… | top users | synonyms (5)

0
votes
0answers
12 views

Maximization the difference of a monotone submodular function and a linear function with a cardinality constraint

I know maximizing a monotone submodular function with a cardinality constraint can be solved by a simple greedy heuristic with an approximation factor $1-1/e$. However, if the submodular function is ...
2
votes
1answer
61 views

How to find a sequence that maximizes a ratio

Given positive parameters $n$, $P$ and $Q$, what is a sequence $a_1,\dots,a_n$ such that for every $k$: $$ \frac{1}{k}\leq a_k \leq 1 $$ which maximizes the ratio: $$ R = \frac{P + \sum_{k=1}^n ...
4
votes
1answer
44 views

Common meeting point for 3 points to reach 4th point [closed]

Problem statement: We are 3 friends at 3 different locations $A, B, C$ and want to reach a location $D$. Each person will take a separate cab to a common meeting point $E$, and then take a single cab ...
0
votes
0answers
18 views

Neural network for regression

The way I understand regression for neural networks is weights being added to each x-input from the dataset. I want something slightly different. I want weights ...
1
vote
1answer
41 views

Find local maximum or minimum in 2 variable function

So, I encountered a question (don't worry it's not H.W.) where I have a function with two variables, and I need to find local maximum / minimum points if exists. (More precisely, it is a utility ...
1
vote
1answer
23 views

Penalty and minimization of a social cost

It is part of broader question in economics however it is about minimizing the expression (which depicts social cost of a crime): the expression is $$\min ...
1
vote
2answers
54 views

Tangent line Exercise. $f (x) = 5e^{−(x−2)^2}$ . Find the coordinates of points where the hill is the most steep.

I have this exercise, look easy but I don't know where to start, I think that I need a extra function or value to continue with the calculus. Imagine that you are riding over a hill having its ...
0
votes
2answers
23 views

Kuhn-Tucker's Conditions for optimization problem with non linear inequalities constraints

My problem is to minimize the function \begin{align*} f(x,y,z,t)=& 3 t \left(2 x^2+4 x z\right) \left(2 t x y+t x z-2 t y^2-2 x z+4 y z\right) \\ &+\left(-t x^2+4 t x y+4 t y z+4 x z-8 y ...
0
votes
0answers
10 views

Neural network to optimize function weights

I have a problem that I believe a neural network could accomplish. I have a plot of data. The y values are straight forward values, but the x-values are computed. The function to compute the ...
0
votes
1answer
17 views

Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
0
votes
1answer
113 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 ...
0
votes
0answers
15 views

HMM optimization: Lagrange multiplier problem

In David Barber's textbook "Bayesian Reasoning and Machine Learning" he hints at the derivation of the Baum-Welch algorithm for HMM parameter learning: Textbook excerpt, (cannot include images yet, ...
0
votes
0answers
22 views

How to solve the following convex constrained optimization problem?

\begin{equation}\label{constrained optimization} \begin{aligned} \min\limits_{\mathbf{X}}&\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2 &\ \ s.t. X_{ijk}=M_{ijk}\ \ ...
0
votes
1answer
84 views

Explanation of formula

Suppose that we have $M$ production stations $A_1, \dots, A_M$ of a product and $N$ destination stations $B_1, \dots, B_N$ of the product. We suppose that $x_{ij}$ units of the product are ...
0
votes
2answers
69 views

How can I solve the following linear program?

I want to find the answer for the following linear program. Max $v$ subject to $$v-5x_1-x_2 \le 0 $$ $$ v-x_1-4x_2 \le 0 $$ $$ v-2x_1-3x_2 \le 0 $$ $$ x_1+x_2 = 1 $$ $$ x_1, x_2 \ge 0 $$ $$ v \in R ...
0
votes
0answers
37 views

Did I fully explain this optimization and quadratics problem?

I'm not really sure how to explain the last part; how does solving for $x$ by replacing $y$ show that $x^2+y^2$ is greater than or equal to $9?$ Like, I get why, but I don't know how to express it. ...
1
vote
2answers
31 views

Show that $\underset{x\in X}{\sup}\left(\underset{y\in Y}{\sup}f(x,y)\right) = \underset{(x,y)\in X\times Y}{\sup} f(x,y)$

I have the following problem I don't know how to start. Prove that: $$\underset{x\in X}{\sup}\left(\underset{y\in Y}{\sup}f(x,y)\right) = \underset{(x,y)\in X\times Y}{\sup} f(x,y),$$ ...
2
votes
1answer
35 views

What does the Lagrange multiplier of an equality constraint mean, intuitively?

Consider a nonlinear optimization problem of the form \begin{align} \min_{x}&\quad f(x)\\ \nonumber \text{subject to } \quad&h_i(x) = 0,\,i=1,\ldots,I\\ \nonumber \quad&g_j(x) \le ...
0
votes
3answers
80 views

What is the maximum value of $\sqrt6 xy + 4yz$ given $x^2 + y^2 + z^2 = 1?$

Problem: Let $x$,$y$ and $z$ be real numbers such that $x^2 + y^2 + z^2 = 1.$ Find the maximum possible value of $\sqrt6 xy + 4yz$ I don't know how to proceed with the question. Applying AM-GM ...
2
votes
1answer
32 views

Add weights to inputs of x-value function to optimize regression [closed]

Say I have $n$ functions (not the regression function) each with $n$ inputs. These functions compute the x-values. The function is a simple summation function where the input is multiplied by a ...
0
votes
1answer
36 views

Find two integers that satisfy a property

The finite sequence of integers $Y_1, \dots, Y_M$ takes both positive and negative values, where $M$ is a fixed positive integer. Could you help me to find a formulation using dynamic programming that ...
0
votes
1answer
33 views

Constrained optimization with alternates in special conditions

I have the following optimization problem. $$\max_{a b} acx+bdy+z \ \ \ \ \ \ $$ subjected to $$ c = \begin{cases} 1, & \text{if } 2xa-yb-z\geq 4\\ 0, & \text{if} \ 2ax<yb+z\\ ...
1
vote
1answer
39 views

Apply Simplex method using M-method

I want to solve the following linear programming problem: $$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$ In this ...
0
votes
1answer
50 views

Maximum and minimum of the function $xy+z^2$

Find the maximum and minimum values of the function $f(x,y,z)=xy+z^2$ in the circumference obtained by intersections between the sphere $x^2+y^2+z^2=4$ and the plane $y-x=0$. I did Lagrange and found ...
0
votes
0answers
28 views

Minimization/maximization of system of nonlinear equations

Consider a system of nonlinear equations of the following form: $$F_1(x_2, x_3, x_4...x_n)$$ $$F_2(x_1, x_3, x_4...x_n)$$ $$...$$ $$F_n(x_1, x_2, x_3...x_{n-1})$$ And we wish to simultaneously ...
1
vote
0answers
13 views

Right enunciation/notation in utility maximisation model

I am working on a model that can be defined as a utility optimisation problem but I'm struggling with the enunciation and notation. The model should describe how the utilities of a set of agents ...
0
votes
1answer
19 views

Minimal sum of non-consecutive elements

I have $N$ numbers $a_i$. I want to find the smallest sum of EXACTLY $K$ non-consecutive elements. I know how to solve this in $O(N*K)$ (straightforward dynamic programing) but it is too slow. Anyone ...
0
votes
0answers
17 views

Knapsack problem when the weights are equals to 1.

Knapsack problem: Given a set of $N$ items, each with a weight $w_i$ and a value $v_i$, determine the number of each item to include in a collection so that the total weight is less than or equal to ...
1
vote
0answers
18 views

Find max min with linear programming

I need to solve $$ \max_x \min_y x^T M y $$ subject to $$ \sum_{i=1}^n y_i = 1, \sum_{j=1}^m x_j = 1,\\ x \geq 0, y \geq 0 $$ where $ M \in \mathbb{R}^{m\times n} $, $ x \in ...
4
votes
1answer
45 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
0
votes
1answer
18 views

Limit the objective function in optimization

Is it correct to limit the objective function of an optimization problem sometimes? I heard we shouldn't limit the objective function at all. In other words, a namely problem like this, is possible? ...
0
votes
0answers
28 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
11
votes
2answers
266 views

Largest-area shape with diameter 1?

Define the diameter of a shape as the greatest distance between any two of its points. What diameter 1 shape has the greatest area? Is it the circle? I've been looking for the biggest little ...
0
votes
1answer
35 views

How to derive the dual problem of Knapsack problem

Knapsack problem is $$ \text{max} \, v^Tx$$ $$ \text{s.t.} \, w^Tx \le W, \, \, 0\le x_i \le 1 \, \, (i=1,...,n)$$ This is equivalent to $$ \text{min} \, -v^Tx$$ $$ \text{s.t.} \, ...
0
votes
1answer
24 views

How can I derive the following dual problem?

Standard form of the linear program is $$\text{Min} \, C^{T} x$$ $$ s.t. Ax=b $$ $$x\ge 0$$ Dual is $$\text{Max}\, b^Ty$$ $$s.t. C-A^{T}y \ge 0$$ By using the above definition, I want to find ...
0
votes
0answers
25 views

minmizing frobenius norm($\min_{K \in \mathbb C^{n \times m}} \|KQK^*\|_F$) subject to an equality

In which known approach or algorithm a fat matrix $K\in \mathbb C^{n \times m} ,m>n,$ can be found: $\min_{K \in \mathbb C^{n \times m}} \|KQK^*\|_F$ subject to: $KK^*=I$ $Q\in \mathbb C^{m ...
0
votes
0answers
26 views

Minimizing summation using Karush–Kuhn–Tucker

Let $a_j, c_j , j=1,...n$ and b be positive constants. $$-$$ Minimize : $\sum_{j=1}^n \frac{c_j}{x_j}$ $$-$$ subject to:$\sum_{j=1}^n a_j x_j =b$ $$-$$ Write down the kkt conditions and solve the ...
0
votes
1answer
27 views

What is the best way to connect some street corners with electricity cables using graph theory?

A company wants to place vending machines at some (not all) corners of a street network. They need to find the best way to connect them all to electricity, knowing that electricity cables can only be ...
1
vote
1answer
44 views

Optimization problem. Objective function not differentiable

I am looking at an optimization problem and I am stuck at this point: minimize: $\pi \max{[(x_1-a_i)^2 + (x_2-b_i)^2]} - \pi \min{[(x_1-a_i)^2 + (x_2-b_i)^2]}$ which is a problem in two variables ...
0
votes
0answers
32 views

Are maximize/minimize operators in optimization problem?

Note: I'm not sure if Math.SX is the best community to ask (TeX.SX might be also good), but I decided to post here because my question is about mathematical rule rather than about (La)TeX technique. ...
0
votes
2answers
31 views

Find the number of local extrema of that function without calculus.

I need to find the number of local extrema of that function without derivate or using calculus. I know that in $x = 1$ and $x = 3$ $f(x) = 0$ ... in which way I can affirm that this function has at ...
0
votes
0answers
12 views

Statistical metric for assessing optimality

In a stochastic computational model, I'm given a limited number of parameter sets and hope to identify the one set of input that is optimal, defined by the values of its numerical outputs, i.e., ...
3
votes
0answers
46 views

Minimal number of steps to construct $\cos(2 \pi /n)$

My question is related to this previous one. I was wondering what is the minimal number of steps $S(a)$ to construct a number $a \in \mathbb R$ that is constructible (as defined here). For instance, ...
0
votes
1answer
17 views

Quadratic Equality Constrained Quadratic Program and Convexity

There are a few questions on this topic already. However, none of them really answer my question. The most relevant are these: Quadratic optimisation with quadratic equality constraints Quadratic ...
0
votes
2answers
35 views

Is the logarithm of sum of multiple variables with the constraint on sum of them Concave?

I know that without any constraint $log \sum_{i=1:1:m} \alpha_i C_i $ is not Concave but I am wondering is this function Concave when we have the constraint that $ \sum_{i=1:1:m} \alpha_i =1 $ and ...
0
votes
0answers
21 views

Optimization by KKT-method

I need to solve the following problem by KKT method. $$ \text{min} \ \ 2xy + 2yz + 2zx \\ \text{subject to} \ x^2 + y^2 ≤ 2, \ 2x + 2y + z = 0 $$ I have gotten as far as setting up the system of ...
0
votes
0answers
50 views

Integer programming model not working

I have to formulate an Integer programming model for the following using XPRESS; There are 10 items that need to assigned to 2 categories, A and B. Each item has a weight and 30 % of the weight is ...
2
votes
1answer
105 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 ...
0
votes
0answers
21 views

Conic formulation. Finding a point minimizing the maximum distance to a set of points.

I have to formulate (and I don't know) as a conic problem the next: Problem: Given a set of points $D=\{a_1,a_2, \dots, a_n\} \subset R^2$. Write like a conic problem the problem to find a point ...
0
votes
1answer
34 views

Refinery - Mathematical formulation of problem

In a refinery, two types of crude oil $T_1, T_2$ get mixed with two different procedures $R$ and $W$ and produce two types of petrol $P_1, P_2$ as shown at the following matrix: $\begin{matrix} ...